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

孫威威，張 崢

（上海理工大學管理學院，上海 200093）

0 引言

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

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

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

1 模擬竹林生長算法

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

Fig.1 Bamboo nodes圖1 竹子節點

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

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

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

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

2 實驗

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

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

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

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

3 分析

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

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

Fig.3 PGSA Ackley test function圖3 PGSA Ackley 測試函數

Fig.4 Bgsa Ackley test function圖4 BGSA Ackley 測試函數

Fig.5 PGSA Rastrigin test function圖5 PGSA Rastrigin 測試函數

Fig.6 Bgsa Rastrigin test function圖6 BGSA Rastrigin 測試函數

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

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

4 結論

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

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

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

5 結語

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