基于PGSA 的模擬竹林生長算法

孫威威，張 崢

（上海理工大學(xué)管理學(xué)院，上海 200093）

0 引言

通過模擬植物生長原理計算植物生長素，基于植物向光性的生長規(guī)律，李彤等［1］提出模擬植物生長算法（Plant Growth Simulation Algorithm，PGSA）。借鑒匈牙利生物學(xué)家Rozenberg［2］的L-系統(tǒng)分支規(guī)則迭代重寫，構(gòu)建模擬植物在搜索空間中找到最優(yōu)解的理論體系。郭改文等［3］提出的森林競爭算法是基于自然樹枝條的生長、凋落矛盾統(tǒng)一原理和森林生態(tài)系統(tǒng)中競爭排斥原理提出的算法，竹林算法則是基于模擬植物生長算法的新算法，主要區(qū)別在于允許多棵樹木生長，不刪除單棵樹木個體，不需要計算營養(yǎng)因子、遮擋因子等，計算步驟較為簡化。與吳俊秋等［4］提出的模擬植物生長算法改進方案不同，模擬竹林生長算法不在單棵樹計算過程中進行初始化及改變步長，而是盡可能快地生長單棵樹，并從多棵樹木中找到全局最優(yōu)解。

PGSA 算法在不同領(lǐng)域如電力系統(tǒng)、企業(yè)管理、生產(chǎn)調(diào)度、物流優(yōu)化等多種場景中得到應(yīng)用，但存在一定的改進空間，如較大的生長空間導(dǎo)致優(yōu)化效率降低，算法缺乏有效的終止判斷設(shè)計，初始值和步長設(shè)置不當(dāng)容易陷入局部最優(yōu)解等。因此很多學(xué)者從不同角度對算法進行改進，但改進基本上都側(cè)重于對于特定問題的數(shù)學(xué)模型進行改造，或者對單棵樹木的生長規(guī)則進行調(diào)整，沒有從多棵樹木角度以及簡化計算步驟角度進行改進［5-23］。

本文受模擬植物生長算法和隨機森林思想啟發(fā)，提出模擬竹林生長算法（Bamboo Grove Simulation Algorithm，BGSA），取消了適應(yīng)度（生長素）計算和生長節(jié)點的隨機選擇，而是基于根節(jié)點與生長步長（每次生長的樹干長度）的隨機化通過快速迭代尋找全局最優(yōu)解。

1 模擬竹林生長算法

竹子生長特征是由一根主干組成，雖然會生長小的莖葉，但是整體向上生長依然是從主干的竹節(jié)上依次生長，具有快速生長、枝干挺拔的特征，見圖1。借鑒竹子生長特征，且考慮到模擬植物生長算法尋找全局最優(yōu)解受到生長步長和初始樹根的影響，參考隨機森林算法［24］，通過選擇不同的生長位置，按照不同的步長快速生長出不同的竹子，進而在竹林中找到最高點作為全局最優(yōu)點。

Fig.1 Bamboo nodes圖1 竹子節(jié)點

首先取消生長素計算，將每次最高節(jié)點作為新的生長基點，減少計算過程和時間消耗；其次減少莖葉生長，集中在主干上快速生長。將竹林多重迭代優(yōu)化并選取最大值，每棵竹子的初始生長點、步長均不同，從而更大程度上避免陷入局部最優(yōu)解，更快尋找到全局最優(yōu)解。

模擬竹林生長算法流程見圖2，步驟如下：①初始化，確定初始解，隨機選擇根節(jié)點和迭代步長；②生長新的節(jié)點，計算并保存局部最優(yōu)解；③選擇局部最優(yōu)解作為新的生長基點；④重新在不同位置生長新的竹子，迭代以上步驟；⑤迭代終止。

根據(jù)問題性質(zhì)和規(guī)模，設(shè)置終止條件如下：在步驟④處，如果滿足單棵竹子的迭代終止條件，如達到單棵竹子生長次數(shù)，或最優(yōu)節(jié)點重復(fù)次數(shù)達到局部最優(yōu)節(jié)點最大允許出現(xiàn)的次數(shù)，則單棵竹子停止生長；在步驟⑤處，如果竹林中的竹子總數(shù)達到設(shè)定上線則整片竹林停止生長，并將竹林中所有竹子的最高點作為全局最優(yōu)解。

Fig.2 Flow of simulating bamboo growth algorithm圖2 模擬竹林生長算法流程

2 實驗

首先，模擬植物生長算法要計算樹干和樹枝上所有節(jié)點的適應(yīng)度（生長素），在生長出新的樹枝后計算公式會變得更加復(fù)雜，增加了計算工作量；其次，基于適應(yīng)度隨機選擇節(jié)點雖然降低了陷入局部最優(yōu)解概率，但也會造成計算工作的重復(fù)。而模擬竹林生長算法首先取消了適應(yīng)度計算，其借鑒竹子每次從最高節(jié)點生長新的節(jié)點，減少了計算步驟。由于隨機化步長和根節(jié)點的選擇，以較小的成本生長單棵竹子，并從多棵竹子的最優(yōu)解集合中找到全局最優(yōu)解，減少了計算步驟。

以整數(shù)域問題求解為例，選取常見的Ackley、Beale、H?lder Table、Sphere、Rastrigin 和Bukin 測試函數(shù)，分別使用模擬植物生長算法和模擬竹林生長算法計算，使用Python 3.7 編程，在Windows 10 家庭版操作系統(tǒng)、Intel i5-8300H 2.30 GHz、內(nèi)存8GB 環(huán)境下測試。

初始化根節(jié)點設(shè)置為（-10，10）之間的隨機整數(shù)值，步長為（5，12）之間的隨機整數(shù)值，每棵樹最大迭代次數(shù)200次，允許重復(fù)出現(xiàn)局部最優(yōu)解次數(shù)10 次，竹林最多生長5棵竹子。其中PGSA 迭代5 次，全局最優(yōu)解選取5 次迭代中的最小值，計算時間和收斂次數(shù)取平均值進行對比。與模擬植物生長算法相比，平均計算時間減少了79%，平均收斂次數(shù)降低了48%，全局最優(yōu)解準確率提升了50%，如表1 所示。

Table 1 Comparison of the performance of PGSA and BGSA表1 PGSA 和BGSA 性能對比

3 分析

根據(jù)以上數(shù)據(jù)分析可知，BGSA 在平均收斂次數(shù)和計算時間上的性能優(yōu)于PGSA 算法。由于PGSA 每次生長節(jié)點選擇存在隨機性，并不是在局部最優(yōu)點選擇，所以存在一定的計算資源浪費，同時也因為步長選擇和初始節(jié)點選擇原因，并不一定能夠每次找到全部最優(yōu)解，如果不通過多次迭代比較則容易陷入局部最優(yōu)。

選取幾個具有代表性的測試函數(shù)作為對比，可以看出PGSA 與BGSA 算法在收斂迭代速度上存在差異，圖3-圖6（彩圖掃OSID 碼可見）由左邊收斂下降曲線和測試函數(shù)三維曲線組成，其中x 軸為迭代次數(shù)，y 軸為局部最優(yōu)函數(shù)值。由于BGSA 最大迭代次數(shù)設(shè)置較小，BGSA 最大迭代測試的x 軸比PGSA 短。

Fig.3 PGSA Ackley test function圖3 PGSA Ackley 測試函數(shù)

Fig.4 Bgsa Ackley test function圖4 BGSA Ackley 測試函數(shù)

Fig.5 PGSA Rastrigin test function圖5 PGSA Rastrigin 測試函數(shù)

Fig.6 Bgsa Rastrigin test function圖6 BGSA Rastrigin 測試函數(shù)

以圖7 迭代收斂曲線為例，可以看出BGSA 和PGSA在收斂速度上存在差異，BGSA 收斂速度優(yōu)于PGSA 算法。為便于對比展示兩個算法，將BGSA 迭代次數(shù)作延長處理。

Fig.7 Convergence curves of Ackley iteration for BGSA and PGSA圖7 BGSA 與PGSA Ackley 迭代收斂曲線

4 結(jié)論

針對優(yōu)化問題中PGSA 算法可能存在多個局部最優(yōu)解，導(dǎo)致算法無法自動終止、計算時間長等問題，PGSA 通過隨機選擇生長點在更小范圍內(nèi)避免陷入局部最優(yōu)，但存在收斂迭代次數(shù)較多、計算時間較長的缺陷。本文受竹子生長特性啟發(fā)，基于竹子生長特征，提出BGSA 模擬竹林生長算法，通過常見的測試函數(shù)對比驗證得出如下結(jié)論：

（1）去除掉生長素計算和隨機選擇生長點之后，減少了計算時間消耗，加快了搜索能力，減少陷入局部最優(yōu)解的風(fēng)險。

（2）通過隨機化根節(jié)點和多棵竹子計算比較發(fā)現(xiàn)，BGSA 在計算速度、收斂速度和全局最優(yōu)解尋找上存在一定的比較優(yōu)勢，可以更快收斂到全局最優(yōu)解，基于多棵竹子的最優(yōu)解綜合計算避免了固定步長和固定初始根節(jié)點對尋找全局最優(yōu)點的不利影響。

5 結(jié)語

本文通過理論分析和測試驗證，基于不同植物的生長特性比較，發(fā)現(xiàn)竹子的生長尋優(yōu)特征更加明顯。節(jié)點快速生長特性去除了隨機選擇節(jié)點，每次基于最高節(jié)點繼續(xù)生長，提高了優(yōu)化算法效率。通過簡化計算步驟、更改迭代步驟，以及根據(jù)隨機根節(jié)點在不同地點生長出不同竹子，采取每根竹子的步長為隨機長度的優(yōu)化方法，尋找到全局最優(yōu)解。通過測試函數(shù)發(fā)現(xiàn)，BGSA 相對于PGSA 存在一定的改進優(yōu)勢。后續(xù)將在此基礎(chǔ)上，通過研究更多維的空間測試函數(shù)解決計算優(yōu)化問題，以及不同場景下的具體算法應(yīng)用，不斷完善該算法。