基于混合策略的緞藍(lán)園丁鳥(niǎo)優(yōu)化算法

曹燦，高鷹，李寧，郭曉語(yǔ)

（廣州大學(xué)計(jì)算機(jī)科學(xué)與網(wǎng)絡(luò)工程學(xué)院，廣州510000）

0 引言

啟發(fā)式算法是一種基于直觀或經(jīng)驗(yàn)，利用類似仿生學(xué)的原理，根據(jù)自然、動(dòng)物中的一些現(xiàn)象而抽象成的算法［1］。對(duì)于非確定性多項(xiàng)式難度問(wèn)題，是無(wú)法求解到最優(yōu)解的，因此，使用啟發(fā)式算法是一種較好的選擇，去盡可能逼近最優(yōu)解，得到一個(gè)相對(duì)優(yōu)解。因?yàn)閱l(fā)式算法具有簡(jiǎn)單直觀、易于修改、處理問(wèn)題較快，且能夠在可接受的時(shí)間內(nèi)給出一個(gè)較優(yōu)解等特點(diǎn)，被廣泛運(yùn)用于生產(chǎn)生活中的各種優(yōu)化問(wèn)題中。常見(jiàn)的啟發(fā)式算法有蟻群算法（ant clony optimization,ACO）、模擬退火法（simulated annealing，SA）、神經(jīng)網(wǎng)絡(luò)算法（neural network algorithm，NNA）、粒子群算法（particle swarm optimization，PSO）、遺傳算法（ge?netic algorithm，GA）、螢火蟲(chóng)算法（firefly algo?rithm，F(xiàn)A）等［2-7］，雖然這些啟發(fā)式算法的編碼各種各樣,但是它們的本質(zhì)都是一樣的，就是要求解出全局的最優(yōu)解。如在PSO算法［8］中，把鳥(niǎo)看做粒子，模仿鳥(niǎo)類的捕食行為來(lái)尋找目標(biāo)函數(shù)的最優(yōu)值；在GA［9］中，通過(guò)模擬自然進(jìn)化過(guò)程來(lái)搜索目標(biāo)函數(shù)最優(yōu)解；FA［10］模仿螢火蟲(chóng)之間的信息交流，螢火蟲(chóng)的位置代表了一個(gè)待求問(wèn)題的可行解，螢火蟲(chóng)的亮度表示該螢火蟲(chóng)位置的適應(yīng)度，通過(guò)尋找位置最亮的螢火蟲(chóng)來(lái)搜索目標(biāo)函數(shù)最優(yōu)解。

緞藍(lán)園丁鳥(niǎo)算法（satin bowerbird optimization algorithm，SBO）是Moosavi等人［11］在2017年提出的一種啟發(fā)式算法。其原理是模仿自然界中雄性緞藍(lán)園丁鳥(niǎo)的求偶行為，且成功地應(yīng)用在柔性交流輸電和提高軟件開(kāi)發(fā)工作評(píng)估的準(zhǔn)確性上，但目前國(guó)內(nèi)外對(duì)其研究的文獻(xiàn)不多。

本文提出了一種基于混合策略的SBO算法。改進(jìn)了原算法中收斂速度過(guò)慢和收斂精度低的問(wèn)題。采用Logistic混沌映射對(duì)種群進(jìn)行初始化，使生成的初始種群偽隨機(jī)性強(qiáng)，增加了種群的多樣性，從而使初始種群分布更均勻；通過(guò)加入自適應(yīng)權(quán)重，提升了算法的全局搜索能力，提高了求解的精度；改變?cè)械母咚棺儺?，引入了Levy飛行變異，提升了種群分布的多樣性，有利于算法跳出局部最優(yōu)。

1 緞藍(lán)園丁鳥(niǎo)優(yōu)化算法

在自然界中，成年雄性園丁鳥(niǎo)在交配季節(jié)開(kāi)始在自己的區(qū)域上建造求偶亭，它們利用各種各樣的材料來(lái)吸引雌性園丁鳥(niǎo)；但是，并不是所有的雄鳥(niǎo)都能成功構(gòu)建求偶亭，有的求偶亭會(huì)被破壞［12］。根據(jù)以上原理，可以將SBO算法分為以下5個(gè)階段：

（1）隨機(jī)生成初始種群。隨機(jī)生成一個(gè)含有NB個(gè)個(gè)體的初始種群其中，NB為種群大小，D維數(shù)，t代表當(dāng)前進(jìn)化代數(shù)。

（2）計(jì)算每個(gè)個(gè)體的適應(yīng)度值，然后計(jì)算出此適應(yīng)度值在群體適應(yīng)度值總和中所占的比例，表示該個(gè)體在選擇過(guò)程中被選中的概率。每個(gè)個(gè)體被選中的概率，由等式（1）計(jì)算，其中fiti代表第i個(gè)求偶亭的適應(yīng)度值，通過(guò)式（2）計(jì)算，f(xi)是第i個(gè)求偶亭的代價(jià)函數(shù)，即目標(biāo)函數(shù)，通過(guò)公式（2）每次迭代保證代價(jià)函數(shù)的函數(shù)值不斷減?。?/p>

（3）位置更新。根據(jù)雄性緞藍(lán)園丁鳥(niǎo)的生活原理，對(duì)求偶亭的位置進(jìn)行更新，如公式（3）：

其中，α為步長(zhǎng)的最大閾值；Pj是目標(biāo)求偶亭的被選中概率，取值為0～1。當(dāng)目標(biāo)位置被選中概率越大時(shí)，步長(zhǎng)越小；當(dāng)目標(biāo)位置被選中概率為0時(shí)，步長(zhǎng)最大為α；當(dāng)目標(biāo)位置的被選中概率為1時(shí)，步長(zhǎng)最小，為α/2。

（4）變異。根據(jù)雄性緞藍(lán)園丁鳥(niǎo)的求偶亭會(huì)遭到破壞的自然現(xiàn)象，算法采取了一定的概率進(jìn)行變異，如公式（5）和（6）所示：

其中，xik服從正態(tài)分布，δ為標(biāo)準(zhǔn)差，通過(guò)公式（7）計(jì)算：

其中，z是縮放比例因子，varmax和varmin分別是變量xi的上限和下限。

（5）將舊種群和從變異中獲得的種群進(jìn)行組合。在每個(gè)周期的最后，對(duì)舊種群和從變異中獲得的種群進(jìn)行評(píng)價(jià)，合并對(duì)組合種群中的所有個(gè)體的成本函數(shù)值進(jìn)行排序，保留函數(shù)值最小的個(gè)體，若此時(shí)滿足終止條件，則輸出最佳位置及其對(duì)應(yīng)的最優(yōu)值，否則繼續(xù)進(jìn)行步驟（3）～（6）。

SBO算法的偽代碼設(shè)計(jì)如下：

2 改進(jìn)的緞藍(lán)園丁鳥(niǎo)優(yōu)化算法

2.1 基于Logistic混沌映射的種群初始化

對(duì)于元啟發(fā)算法而言，種群的初始化對(duì)算法的收斂速度和收斂精度有一定的影響［13］。在進(jìn)行迭代尋優(yōu)時(shí)，要盡可能使種群初始值在搜索空間分布均勻，來(lái)獲得更高的全局搜索能力和種群多樣性。在原算法中種群初始化是隨機(jī)的，隨機(jī)過(guò)程并不能保證初始種群能夠分布均勻，種群位置隨機(jī)分布，使得部分個(gè)體遠(yuǎn)離最優(yōu)解，從而會(huì)影響算法的收斂速度。為了解決原算法中存在的這些問(wèn)題，引入了logistic混沌映射。

混沌是存在于非線性系統(tǒng)中的一種普遍現(xiàn)象［14］。由于混沌運(yùn)動(dòng)的遍歷性，規(guī)律性和偽隨機(jī)性等，它能夠在一定的范圍內(nèi)不重復(fù)的經(jīng)歷所有狀態(tài)，而又不會(huì)失去種群初始化的隨機(jī)性，正是由于這些特點(diǎn)，采用混沌搜索比其他隨機(jī)搜索更具有優(yōu)越性?；诨煦缧蛄械乃枷耄疚牟捎靡环NLogistic混沌映射，這是一種比較常用的混沌序列，其表達(dá)式如下：

x(t+1)=ux(t)(1-x(t))t=0,1,2,…,n（8）其中，u是混沌參數(shù)，t是迭代次數(shù)。

u∈(2.6,4]，且u越大，混沌性越高，0

Logistic映射在分叉參數(shù)3.57

圖1 Logistic映射

引入Logistic混沌映射后，提升了種群的多樣性和均勻性，從而使算法能夠快速收斂并接近最優(yōu)解。

2.2 指數(shù)慣性權(quán)重

在原算法中，前期存在收斂速度快，容易陷入局部最優(yōu)；后期收斂速度慢，搜索范圍變小。因此，引入了指數(shù)慣性權(quán)重因子w，公式如下所示：

求偶亭位置更新公式：

式中，c為變化因子，it為當(dāng)前迭代次數(shù)，maxIt為最大迭代次數(shù)。圖2為慣性權(quán)重迭代500次的曲線圖。從圖中可以看出，慣性權(quán)重w總體呈遞增趨勢(shì)，不管是迭代初期還是迭代后期，都保持較穩(wěn)定的非線性變化速度，平衡了算法的全局和局部搜索能力。這樣，既繼續(xù)保持了算法早期全局搜索的能力，避免陷入局部最優(yōu)，又提高了算法后期的收斂速度和收斂精度。

圖2 指數(shù)慣性權(quán)重曲線

2.3 Levy飛行變異

標(biāo)準(zhǔn)的鍛煉園丁鳥(niǎo)優(yōu)化算法在種群變異時(shí)，使用的是高斯變異來(lái)獲得新的種群，但使用此種方式的尋優(yōu)速度過(guò)慢，局部搜索能力太差，容易陷入局部最優(yōu)，于是引入了一種Levy飛行變異方式。

Levy飛行，是由P.Levy于1937年提出的［15］，最初是用來(lái)描述生物群體的活動(dòng)方式，通過(guò)對(duì)生物群體游走覓食行為的研究，逐漸形成了一種以長(zhǎng)短距離跳躍相結(jié)合的Levy飛行。正是根據(jù)Levy飛行長(zhǎng)短距離跳躍的多變性特點(diǎn)，可以使種群在迭代過(guò)程保持較高的多樣性，從而在長(zhǎng)距離搜索時(shí)能夠擴(kuò)大搜索范圍，提高全局搜索能力，并使跳出局部最優(yōu)，而更為頻繁的短距離搜索，能夠在更小的搜索范圍內(nèi)快速找到最優(yōu)解。

近年來(lái)，Levy飛行已經(jīng)應(yīng)用于各種仿生優(yōu)化算法中，并且很好地提高了算法的性能，例如基于Levy飛行策略的自適應(yīng)改進(jìn)鳥(niǎo)群算法［16］，基于Levy飛行策略的改進(jìn)樽海鞘群算法［17］，一種基于Levy飛行的改進(jìn)蝗蟲(chóng)優(yōu)化算法［18］，基于Levy飛行的螢火蟲(chóng)模糊聚類算法［19］，等。

它的概率密度函數(shù)積分形式為:

該積分用來(lái)計(jì)算隨機(jī)數(shù)分布是一個(gè)難題，后來(lái)，Xin-She Yang與Suash Deb在提出的布谷鳥(niǎo)算法中將Levy分布的密度函數(shù)進(jìn)行了簡(jiǎn)化，得到了它的冪次形式［20］：

其中，t為步長(zhǎng)，β為指數(shù)參數(shù)，將Levy飛行作為變異算子引入到SBO算法中:

經(jīng)過(guò)實(shí)驗(yàn)，發(fā)現(xiàn)Levy飛行分布有較好的擾動(dòng)性能，增加了變異的范圍，提高了算法的局部搜索能力，避免了陷入局部最優(yōu)。

2.4 基于混合策略的緞藍(lán)園丁鳥(niǎo)優(yōu)化算法

對(duì)于SBO算法中存在的求解精度低，收斂速度慢，易陷入局部最優(yōu)等問(wèn)題，本文提出了一種基于混合策略改進(jìn)的鍛煉園丁鳥(niǎo)算法，在種群初始化時(shí)，加入了Logistic混沌映射，使初始種群分布更均勻；在位置更新時(shí)，引入了指數(shù)慣性權(quán)重；又在種群變異時(shí)，改變了原有的正態(tài)分布變異方式，引入了Levy飛行變異。HSBO的算法步驟如下：

（1）初始化種群的大小nPop，最大迭代次數(shù)maxIt等參數(shù)，根據(jù)公式（8）來(lái)初始化種群。

（2）計(jì)算種群個(gè)體的目標(biāo)函數(shù)值，確定種群中的最優(yōu)位置xelite和最優(yōu)值。

（3）用公式（2）計(jì)算每個(gè)求偶亭的適應(yīng)度值，并通過(guò)公式（1）來(lái)算出每個(gè)求偶亭被選中的概率。

（4）用公式（4）計(jì)算步長(zhǎng)，公式（9）計(jì)算權(quán)重因子，再用公式（10）來(lái)更新求偶亭的位置。

（5）當(dāng)rand

（6）將舊種群和變異種群進(jìn)行組合，更新全局最優(yōu)解和最優(yōu)值。

（7）判斷是否達(dá)到最大迭代次數(shù)，如果是，則輸出最優(yōu)解和最優(yōu)值；否則，跳轉(zhuǎn)到（3）繼續(xù)迭代。

3 HSBO性能測(cè)試

3.1 測(cè)試函數(shù)及參數(shù)設(shè)置

為了驗(yàn)證HSBO算法的性能，本文將采用12個(gè)測(cè)試函數(shù)對(duì)HSBO算法進(jìn)行仿真實(shí)驗(yàn)，詳細(xì)信息如表1所示。所要測(cè)試的算法的種群規(guī)模統(tǒng)一設(shè)為20，最大迭代次數(shù)為500次，維度為30，并與基于自適應(yīng)權(quán)重的緞藍(lán)園丁鳥(niǎo)優(yōu)化算法［21］（WSBO）、基于自適應(yīng)t分布變異的緞藍(lán)園丁鳥(niǎo)優(yōu)化算法［22］（tSBO）、緞藍(lán)園丁鳥(niǎo)優(yōu)化算法（SBO）、螢火蟲(chóng)算法（firefly algorithm，F(xiàn)A）和粒子群算法（PSO）進(jìn)行實(shí)驗(yàn)對(duì)比。各種算法的參數(shù)設(shè)置：SBO算法、tSBO算法和WSBO算法參數(shù)：最大步長(zhǎng)α=0.94，縮放比例因子z=0.02，變異概率p=0.05；HSBO算法參數(shù)：最大步長(zhǎng)α=0.94，縮放比例因子z=0.02，變異概率p=0.05，混沌參數(shù)u=3.98，變化因子c=0.8；FA算 法 參 數(shù):β0=2，α=0.2，γ=1。PSO算法參數(shù)：權(quán)重因子w=1，遞減因子wdamp=0.99，學(xué)習(xí)因子c1=1.5、c2=1.5。

表1 測(cè)試函數(shù)

續(xù)表1

3.2 仿真實(shí)驗(yàn)結(jié)果分析

為了提升實(shí)驗(yàn)結(jié)果的可靠性，分別對(duì)每個(gè)測(cè)試函數(shù)進(jìn)行30次獨(dú)立實(shí)驗(yàn)，并算出其最優(yōu)值、最差值、平均值和標(biāo)準(zhǔn)差，12個(gè)測(cè)試函數(shù)的實(shí)驗(yàn)結(jié)果如表2所示，通過(guò)均值可以看出算法的尋優(yōu)精度，而標(biāo)準(zhǔn)差反映出算法的穩(wěn)定性和魯棒性。

表2 實(shí)驗(yàn)結(jié)果對(duì)比

續(xù)表2

續(xù)表2

在表2中，對(duì)于12個(gè)測(cè)試函數(shù)，本文提出的HSBO算法的實(shí)驗(yàn)結(jié)果在最優(yōu)值、最差值和標(biāo)準(zhǔn)差上要明顯優(yōu)于其他算法，說(shuō)明了HSBO算法具有更高的尋優(yōu)精度、魯棒性和穩(wěn)定性。其中，函數(shù)f1、f2、f7、f9、f10和f12的標(biāo)準(zhǔn)方差均為0，說(shuō)明改進(jìn)后的算法的穩(wěn)定性得到了大幅提升。在單峰測(cè) 試 函 數(shù)f1、f3、f4、f5、f6、f7、f11和f12結(jié) 果 中，HSBO算法的綜合性能要高于WSBO、tSBO、SBO、FA和PSO。除了在單峰函數(shù)上有良好的表現(xiàn)，HSBO算法在多峰函數(shù)上也達(dá)到了較好性能。在Griewank函數(shù)f2的測(cè)試結(jié)果中，HSBO算法達(dá)到了最優(yōu)的尋優(yōu)精度，且標(biāo)準(zhǔn)差為0，對(duì)于Alpine函數(shù)f8，HSBO算法都獲得了最好的最優(yōu)值、最差值和標(biāo)準(zhǔn)差，而對(duì)于Rastigin函數(shù)f9和Griewank函數(shù)f10，最優(yōu)值、最差值和標(biāo)準(zhǔn)差都為0，說(shuō)明在多峰函數(shù)的測(cè)試上，HSBO算法的尋優(yōu)精度和穩(wěn)定性也同樣明顯高于其他算法。

為了進(jìn)一步體現(xiàn)HSBO算法的性能，圖3給出了上面所有算法在12個(gè)測(cè)試函數(shù)上的收斂曲線圖。從圖中可以看出，HSBO的初始最優(yōu)值明顯要優(yōu)于其他5個(gè)算法，充分證明了Logistic初始化能使初始種群分布更均勻，在迭代開(kāi)始時(shí)就有一個(gè)較好的初始尋優(yōu)精度；函數(shù)f1、f3、f4、f5、f7、f8、f9、f10、f11、f12的收斂圖近似于直線，說(shuō)明算法在整個(gè)迭代過(guò)程中，收斂速度均勻，有較好的全局搜索能力，避免了陷入局部最優(yōu)；從f2函數(shù)的收斂曲線可以看出，HSBO算法在未達(dá)到最大迭代次數(shù)500次時(shí)，就已經(jīng)找到了最好的尋優(yōu)精度，說(shuō)明了算法的尋優(yōu)性能高、收斂速度快；而f6函數(shù)的收斂曲線表明，HSBO算法對(duì)比于其他算法，具有更快的收斂速度、更高的尋優(yōu)精度，并且在迭代中期，就已經(jīng)接近或達(dá)到了最優(yōu)值。

圖3 測(cè)試函數(shù)收斂曲線

4 結(jié)語(yǔ)

針對(duì)標(biāo)準(zhǔn)緞藍(lán)園丁鳥(niǎo)優(yōu)化算法存在的收斂速度慢、尋優(yōu)精度低和易陷入局部最優(yōu)等問(wèn)題，本文在種群初始化時(shí)，引入了Logistic混沌映射，在位置更新時(shí)，加入了指數(shù)慣性權(quán)重，又在個(gè)體變異時(shí)，引入了Levy飛行變異，最終提出了一種基于混合策略改進(jìn)的緞藍(lán)園丁鳥(niǎo)優(yōu)化算法HSBO。該算法改善了標(biāo)準(zhǔn)SBO算法的不足，提升了種群的全局和局部搜索能力，加快了算法的收斂速度，提高了收斂精度。本文還對(duì)算法進(jìn)行了12個(gè)測(cè)試函數(shù)的仿真實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，HSBO算法的收斂精度、收斂速度和尋優(yōu)性能要明顯優(yōu)于基于自適應(yīng)權(quán)重的緞藍(lán)園丁鳥(niǎo)優(yōu)化算法、基于自適應(yīng)t分布變異的緞藍(lán)園丁鳥(niǎo)優(yōu)化算法、標(biāo)準(zhǔn)緞藍(lán)園丁鳥(niǎo)優(yōu)化算法、螢火蟲(chóng)算法和粒子群算法。下一步研究的工作是將改進(jìn)后的算法應(yīng)用到更多的領(lǐng)域。