孫威威，張 崢

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

0 引言

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

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

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

1 模擬竹林生長(zhǎng)算法

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

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

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

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

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

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

2 實(shí)驗(yàn)

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

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

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

Table 1 Comparison of the performance of PGSA and BGSA表1 PGSA 和BGSA 性能對(duì)比

3 分析

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

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

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

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

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

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

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

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

4 結(jié)論

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

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

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

5 結(jié)語(yǔ)

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