基于混合策略的緞藍園丁鳥優化算法

曹燦，高鷹，李寧，郭曉語

（廣州大學計算機科學與網絡工程學院，廣州510000）

0 引言

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

緞藍園丁鳥算法（satin bowerbird optimization algorithm，SBO）是Moosavi等人［11］在2017年提出的一種啟發式算法。其原理是模仿自然界中雄性緞藍園丁鳥的求偶行為，且成功地應用在柔性交流輸電和提高軟件開發工作評估的準確性上，但目前國內外對其研究的文獻不多。

本文提出了一種基于混合策略的SBO算法。改進了原算法中收斂速度過慢和收斂精度低的問題。采用Logistic混沌映射對種群進行初始化，使生成的初始種群偽隨機性強，增加了種群的多樣性，從而使初始種群分布更均勻；通過加入自適應權重，提升了算法的全局搜索能力，提高了求解的精度；改變原有的高斯變異，引入了Levy飛行變異，提升了種群分布的多樣性，有利于算法跳出局部最優。

1 緞藍園丁鳥優化算法

在自然界中，成年雄性園丁鳥在交配季節開始在自己的區域上建造求偶亭，它們利用各種各樣的材料來吸引雌性園丁鳥；但是，并不是所有的雄鳥都能成功構建求偶亭，有的求偶亭會被破壞［12］。根據以上原理，可以將SBO算法分為以下5個階段：

（1）隨機生成初始種群。隨機生成一個含有NB個個體的初始種群其中，NB為種群大小，D維數，t代表當前進化代數。

（2）計算每個個體的適應度值，然后計算出此適應度值在群體適應度值總和中所占的比例，表示該個體在選擇過程中被選中的概率。每個個體被選中的概率，由等式（1）計算，其中fiti代表第i個求偶亭的適應度值，通過式（2）計算，f(xi)是第i個求偶亭的代價函數，即目標函數，通過公式（2）每次迭代保證代價函數的函數值不斷減小：

（3）位置更新。根據雄性緞藍園丁鳥的生活原理，對求偶亭的位置進行更新，如公式（3）：

其中，α為步長的最大閾值；Pj是目標求偶亭的被選中概率，取值為0～1。當目標位置被選中概率越大時，步長越小；當目標位置被選中概率為0時，步長最大為α；當目標位置的被選中概率為1時，步長最小，為α/2。

（4）變異。根據雄性緞藍園丁鳥的求偶亭會遭到破壞的自然現象，算法采取了一定的概率進行變異，如公式（5）和（6）所示：

其中，xik服從正態分布，δ為標準差，通過公式（7）計算：

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

（5）將舊種群和從變異中獲得的種群進行組合。在每個周期的最后，對舊種群和從變異中獲得的種群進行評價，合并對組合種群中的所有個體的成本函數值進行排序，保留函數值最小的個體，若此時滿足終止條件，則輸出最佳位置及其對應的最優值，否則繼續進行步驟（3）～（6）。

SBO算法的偽代碼設計如下：

2 改進的緞藍園丁鳥優化算法

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

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

混沌是存在于非線性系統中的一種普遍現象［14］。由于混沌運動的遍歷性，規律性和偽隨機性等，它能夠在一定的范圍內不重復的經歷所有狀態，而又不會失去種群初始化的隨機性，正是由于這些特點，采用混沌搜索比其他隨機搜索更具有優越性。基于混沌序列的思想，本文采用一種Logistic混沌映射，這是一種比較常用的混沌序列，其表達式如下：

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

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

Logistic映射在分叉參數3.57

圖1 Logistic映射

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

2.2 指數慣性權重

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

求偶亭位置更新公式：

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

圖2 指數慣性權重曲線

2.3 Levy飛行變異

標準的鍛煉園丁鳥優化算法在種群變異時，使用的是高斯變異來獲得新的種群，但使用此種方式的尋優速度過慢，局部搜索能力太差，容易陷入局部最優，于是引入了一種Levy飛行變異方式。

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

近年來，Levy飛行已經應用于各種仿生優化算法中，并且很好地提高了算法的性能，例如基于Levy飛行策略的自適應改進鳥群算法［16］，基于Levy飛行策略的改進樽海鞘群算法［17］，一種基于Levy飛行的改進蝗蟲優化算法［18］，基于Levy飛行的螢火蟲模糊聚類算法［19］，等。

它的概率密度函數積分形式為:

該積分用來計算隨機數分布是一個難題，后來，Xin-She Yang與Suash Deb在提出的布谷鳥算法中將Levy分布的密度函數進行了簡化，得到了它的冪次形式［20］：

其中，t為步長，β為指數參數，將Levy飛行作為變異算子引入到SBO算法中:

經過實驗，發現Levy飛行分布有較好的擾動性能，增加了變異的范圍，提高了算法的局部搜索能力，避免了陷入局部最優。

2.4 基于混合策略的緞藍園丁鳥優化算法

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

（1）初始化種群的大小nPop，最大迭代次數maxIt等參數，根據公式（8）來初始化種群。

（2）計算種群個體的目標函數值，確定種群中的最優位置xelite和最優值。

（3）用公式（2）計算每個求偶亭的適應度值，并通過公式（1）來算出每個求偶亭被選中的概率。

（4）用公式（4）計算步長，公式（9）計算權重因子，再用公式（10）來更新求偶亭的位置。

（5）當rand

（6）將舊種群和變異種群進行組合，更新全局最優解和最優值。

（7）判斷是否達到最大迭代次數，如果是，則輸出最優解和最優值；否則，跳轉到（3）繼續迭代。

3 HSBO性能測試

3.1 測試函數及參數設置

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

表1 測試函數

續表1

3.2 仿真實驗結果分析

為了提升實驗結果的可靠性，分別對每個測試函數進行30次獨立實驗，并算出其最優值、最差值、平均值和標準差，12個測試函數的實驗結果如表2所示，通過均值可以看出算法的尋優精度，而標準差反映出算法的穩定性和魯棒性。

表2 實驗結果對比

續表2

續表2

在表2中，對于12個測試函數，本文提出的HSBO算法的實驗結果在最優值、最差值和標準差上要明顯優于其他算法，說明了HSBO算法具有更高的尋優精度、魯棒性和穩定性。其中，函數f1、f2、f7、f9、f10和f12的標準方差均為0，說明改進后的算法的穩定性得到了大幅提升。在單峰測 試 函 數f1、f3、f4、f5、f6、f7、f11和f12結 果 中，HSBO算法的綜合性能要高于WSBO、tSBO、SBO、FA和PSO。除了在單峰函數上有良好的表現，HSBO算法在多峰函數上也達到了較好性能。在Griewank函數f2的測試結果中，HSBO算法達到了最優的尋優精度，且標準差為0，對于Alpine函數f8，HSBO算法都獲得了最好的最優值、最差值和標準差，而對于Rastigin函數f9和Griewank函數f10，最優值、最差值和標準差都為0，說明在多峰函數的測試上，HSBO算法的尋優精度和穩定性也同樣明顯高于其他算法。

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

圖3 測試函數收斂曲線

4 結語

針對標準緞藍園丁鳥優化算法存在的收斂速度慢、尋優精度低和易陷入局部最優等問題，本文在種群初始化時，引入了Logistic混沌映射，在位置更新時，加入了指數慣性權重，又在個體變異時，引入了Levy飛行變異，最終提出了一種基于混合策略改進的緞藍園丁鳥優化算法HSBO。該算法改善了標準SBO算法的不足，提升了種群的全局和局部搜索能力，加快了算法的收斂速度，提高了收斂精度。本文還對算法進行了12個測試函數的仿真實驗。實驗結果表明，HSBO算法的收斂精度、收斂速度和尋優性能要明顯優于基于自適應權重的緞藍園丁鳥優化算法、基于自適應t分布變異的緞藍園丁鳥優化算法、標準緞藍園丁鳥優化算法、螢火蟲算法和粒子群算法。下一步研究的工作是將改進后的算法應用到更多的領域。