基于自適應權重的緞藍園丁鳥優化算法

魯曉藝， 劉 升， 韓斐斐， 于建芳

(上海工程技術大學 管理學院， 上海 201620)

引言

近年來，群智能算法作為一種新興的演化計算技術，其良好的尋優性能已成為越來越多研究者關注的焦點。在管理科學和自然科學等領域中發揮著重要作用，廣泛應用于解決工程調度[1]、組合優化[2]、風險預測[3]等復雜問題。群智能算法受自然規律的啟迪，利用仿生原理進行設計，如人工蜂群(artificial bee colony，ABC)[4]算法模擬蜜蜂群體尋找優質花蜜源的過程，把蜜蜂分為引領蜂、跟隨蜂和偵察蜂3種角色；螢火蟲算法(firefly algorithm，FA)[5]模擬自然界螢火蟲在晚上群聚活動的自然現象而提出的，在螢火蟲的群聚活動中，每只螢火蟲通過散發熒光素與同伴進行尋覓食物以及求偶等信息交流；人工魚群(artificial fishswarm，AF)[6]算法通過模仿魚群的覓食、聚群及追尾行為，從而實現尋優。

緞藍園丁鳥優化算法(satin bower bird optimization algorithm，SBO)[7]是由Seyyed Hamid Samareh Moosavi和Vahid Khatibi Bardsiri于2017年模擬自然界成年雄性緞藍園丁鳥的求偶行為而提出的一種新型群智能算法，并結合了自適應神經模糊推理系統(ANFIS)，發現能夠有效地提高軟件開發工作評估的準確性。該算法融合了動態步長和變異等操作，具有良好的尋優性能。但由于提出時間較短，目前國內外少有文獻對其進行研究。

由于大多數的群智能算法，存在著求解精度粗糙、后期迭代速度緩慢等不足，這些新穎群智能算法在求解精度、尋優效果等方面仍存在較大的提升空間，國內外眾多的專家學者針對這些不足進行了有效的改進。2015 年，孔飛和吳定會提出了一種改進的雞群算法[8]，算法中對小雞的位置更新公式中引入慣性權值和學習因子，解決了求解優化問題時易于跳過最優解及早熟收斂的問題。徐辰華等人于2017年基于Cat混沌與高斯變異改進灰狼優化算法[9]，該算法采用高斯變異擾動和優勝劣汰選擇規則，對當前最優解進行變異操作以避免算法陷入局部最優。

本文鑒于改進的基礎上，首先從原理上對算法的實現步驟進行闡述，并提出了基于自適應權重的緞藍園丁鳥優化算法，通過自適應權重的方法改進SBO算法的局部搜索能力，提高了收斂精度；另外用修改后的高斯變異方法對緞藍園丁鳥求偶亭的位置進行變異，提高了SBO算法的全局搜索能力，避免了陷入局部最優的問題。

1 基本緞藍園丁鳥優化算法

緞藍園丁鳥是一種以水果和昆蟲為食的雀形目鳥，分布在澳大利亞東部的熱帶雨林。成熟的雄鳥在其各自的領地上以特殊的木棍結構建造求偶亭，裝飾以鮮花、羽毛、漿果等，并發出嘹亮的鳴聲來吸引雌鳥。雄性緞藍園丁鳥建筑求偶亭的行為源于其天生的本能和對另類雄鳥的模仿。另外，并不是所有的成年雄鳥都能成功的構建和維護求偶亭，存在求偶亭被破壞的情況[10]。根據緞藍園丁鳥的生活原理，SBO算法由以下幾個步驟組成：

(1)初始化種群。在可行域內隨機生成一個包含NP個求偶亭的初始種群，每個求偶亭的位置定義為D維，當前進化代數為t。

(2)計算每個求偶亭的吸引力。即該個體被選中的概率，由等式(1)計算。fiti代表第i個求偶亭的適應值，可通過等式(2)計算；f(xi)是第i個求偶亭的成本函數(目標函數)，每次迭代需保證成本函數值不斷減小。

(1)

(2)

(3)位置更新。雄鳥會根據自身的歷史經驗和種群交流對求偶亭的位置不斷進行調整，其更新公式如等式(3)所示。

(3)

其中，xikt表示第t次迭代第i個個體的第k維分量；j是通過輪盤賭機制確定的；xelite,k為當前整個種群的最優位置。λk是步長因子，由等式(4)確定。

(4)

其中，α是最大步長，Pj是目標求偶亭被選中的概率，概率值在0到1之間。從等式(4)中明顯看出，步長與目標位置的概率成反比。換句話說，當目標位置的概率為0，步長最大為ɑ；當目標位置概率為1時，步長最小為ɑ/2。

(4)變異。在許多情況下，強壯的雄鳥會從較弱的雄鳥那里偷取材料，甚至破壞其求偶亭。因此，在算法的每個周期結束時，有一定的概率發生隨機變異。在這個過程中，xik服從正態分布，如等式(5)所示。

(5)

(6)

在等式(6)中，標準差σ的計算公式如(7)所示。

σ=z*(varmax-varmin)

(7)

其中，varmax和varmin分別是變量xi的上界和下界，z是上下限之間差值的百分比，是可變的。

(5)將舊種群和從變異中獲得的種群進行組合。在每個周期的最后，對舊種群和從變異中獲得的種群進行評價。評估后，這兩個種群被組合并對組合種群中的所有個體的成本函數值進行排序，保留函數值最小的個體，其余個體被刪除。若此時滿足終止條件，則輸出最佳位置及其對應的最優值，否則繼續進行步驟(2)到(4)。SBO算法的偽代碼設計如下：

Initialize the first population of bowers randomly

Calculate the cost of bowers

Find the best bower and assume it as elite

While the end criterion is not satisfied

Calculate the probability of bowers using Eqs. (1) and (2)

For every bower

For every element of bower

Select a bower using roulette wheel

Calculate λkusing Eq. (4)

Update the position of bower using Eqs. (3) and (6)

End for

End for

Calculate the cost of all bowers

Update elite if a bower becomes fitter than the elite

End while

Return best bower

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

2.1 自適應權重

慣性權重是粒子群中很重要的一個參數，如果慣性權重較大，算法搜索能力較強，便于進行全局搜索；如果慣性權重較小，則有利于算法在最優解周圍精確搜索。本文受文獻[11]的啟發，運用自適應權重策略。當所有個體的適應值差異較大時，將慣性權重減小，當所有個體的適應值趨于一致或趨于局部最優時，將慣性權重增大。慣性權重W求解如式(8)所示。

W=Wmax-(Wmax-Wmin)*(t/itmax)＾2

(8)

式中，Wmax、Wmin分別表示W設置的最大值和最小值，t為當前迭代次數，itmax是最大迭代次數。運用上述方法設置權重，在迭代初期，W較大，有利于在全局范圍進行搜索；在迭代后期，W較小，便于向最優解靠近。

2.2 改進原高斯變異形式

高斯分布又叫正態分布，是數理統計中非常重要的概率分布。高斯變異就是在原有的個體上加一個服從高斯分布的隨機擾動項來取代原先的個體[12]。高斯變異能以較大的概率產生較小的變異值，在小范圍內具有良好的搜索能力，不易像柯西變異因其過大的步長而跳離最優值。在智能優化算法中引入變異算子，既可以增強種群的多樣性，又可以避免使算法陷入局部極小。基本的緞藍園丁鳥優化算法采用了公式(6)的高斯變異策略對個體進行變異，但效果不太理想。經過多次實驗，本文對原本的高斯變異方法進行了修改如公式(9)，不僅能使個體跳出局部極值點的束縛收斂于全局極值點，同時也提高了SBO算法的收斂速度和精度。

(9)

其中，N(0,1)為服從均值為0、方差為1的高斯分布。

2.3 混合優化的SBO算法

為了能夠較好地避免基本緞藍園丁鳥算法存在的收斂速度慢，尋優精度低等問題，本文通過上述方法將原SBO算法進行了改進，稱為基于自適應權重的緞藍園丁鳥優化算法(WSBO)。WSBO的基本步驟如下：

(1)初始化最大步長α、變異概率P、最大迭代次數Maxit等參數，隨機初始化種群；

(2)計算每個求偶亭的成本函數值，確定最佳求偶亭的位置xelite及最優值；

(3)采用公式(2)計算每個求偶亭的適應值，并根據公式(1)計算每個求偶亭被選中的概率；

(4)采用公式(4)計算步長；

(5)采用公式(8)更新慣性權重W；

(6)采用公式(3)更新求偶亭的位置；

(7)如果rand

(8)將舊種群和從變異中獲得的種群進行組合，并計算組合種群中的最優解和最優值。判斷此時是否滿足終止條件，若達到最大迭代次數，則終止算法，輸出最佳位置及其對應的最優值；反之，繼續迭代轉向(3)。

2.4 算法流程圖

改進的緞藍園丁鳥算法從兩個方面優化了雄鳥的求偶行為，一方面通過自適應權重，使算法有更好的局部勘探能力，另一方面通過改進的高斯變異形式使算法獲得了更好的全局尋優能力，使求偶亭獲得更好的全局最優解，改進后的緞藍園丁鳥優化算法流程如圖1所示。

圖1 改進的SBO算法流程圖

3 WSBO性能分析

3.1 函數測試及參數設置

為了進一步驗證混合優化SBO算法的性能和收斂情況，本文對8個基準測試函數進行仿真實驗來檢驗算法的改進效果，表1中詳細地列出了各個測試函數的信息。

將本文所提出的基于自適應權重的緞藍園丁鳥優化算法(WSBO)與人工蜂群算法(artificial bee colony algorithm，ABC)和螢火蟲算法(firefly algorithm，FA)以及基本緞藍園丁鳥算法進行對比實驗。為了盡量保證各算法在實驗中的客觀性，所有算法種群規模統一設置為20，迭代次數為500次，各種算法的其它參數設置如下：基本SBO算法和WSBO算法的最大步長α=0.94，縮放比例因 子z=0.02，變異概率p=0.05；ABC算法的放棄閾值limit=60；FA算法參數：β0=2，α=0.2，γ=1。

表1 測試函數

3.2 實驗結果分析

為減少實驗中隨機性的影響，每種算法對每個測試函數均獨立運行30次，分別記錄其最優值、均值和標準差，實驗結果見表2。對于每個測試函數，在固定迭代次數下，均值反映了算法的尋優精度，標準方差反映了算法的魯棒性和穩定性。

表2列出了4種算法在單峰、多峰函數上的測試結果，根據數值結果可以看出：在進行單峰函數測試中，相較于SBO、ABC和FA 3種算法，WSBO算法在最優值、平均值和標準差上都顯著優于這3種算法，說明WSBO算法具有較高的搜索精度和較好的穩定性。

WSBO算法在處理多峰函數優化中同樣也表現出了優越的性能。多峰值函數存在許多局部極小點，很難優化查找到全局最優值，但在Rastrigrin函數f2和Griewank函數f4的測試中，WSBO算法都能夠快速找到理論最優值，且標準方差均為0；對于函數f3和f6，WSBO 算法同樣也獲得了最優的精度值，收斂速度和穩定度都明顯優于其它3種算法。

通過以上分析表明，在大部分函數優化問題中，本文提出的改進算法的尋優精度以及穩定性要優于SBO、ABC以及FA 3種算法，并且在多極值、多峰函數上，WSBO算法仍然尋找到了最優的精度值，說明WSBO算法具有較好的全局和局部搜索性能，并且在函數尋優過程中表現出較好的魯棒性，相較于原SBO算法有了很大程度的提高。

表2 4種算法實驗結果比較

為了能更直觀地顯示WSBO 算法的優化效果，圖2給出了4 種算法在8個標準測試函數f1～f8上搜索函數最優值過程中隨迭代次數增加的收斂曲線。從圖中可以看出，WSBO 算法不管對于多峰函數還是單峰函數，變化近似于直線，說明其速度下降快，能夠在較短的時間內找到或者接近理論最優值，并不斷向最優解靠近，達到很高的精度。這體現了WSBO算法的尋優速度、收斂精度都優于其余3種算法。函數f2和f4的優化圖表明，在迭代次數不到500次時,WSBO 算法已經找到理論最優值；函數f1、f3、f5、f6、f7和f8的優化圖表明，在迭代過程中, WSBO算法能夠快速接近理論最優值。這充分證明了WSBO 算法的可行性及其尋優性能的提升。同時表明，改進的WSBO算法能有效提升全局搜索能力，并在算法后期，有效提升局部開發能力。

(a) f1函數收斂曲線對比

(c) f3函數收斂曲線對比

(e) f5函數收斂曲線對比

(g) f7函數收斂曲線對比

(b) f2函數收斂曲線對比

(d) f4函數收斂曲線對比

(f) f6函數收斂曲線對比

(h) f8函數收斂曲線對比

圖24種算法在函數f1～f8上的收斂曲線

Fig.2Theconvergencecurvesof4algorithmsonfunctionf1～f8

3.3 WSBO時間復雜度分析

對WSBO算法的時間復雜度進行分析，設算法的種群規模為NP；問題維度為numbervar，最大迭代次數為MaxIt,則每個操作的時間復雜度如下：初始化：O(NP*numbervar)；計算求偶亭個體被選擇概率：O(NP*numbervar)；自適應參數：O(NP*numbervar)；位置更新：O(NP*numbervar)；適應度計算：O(NP)；整體復雜度為：O(MaxIt*NP*numbervar)，這與基本SBO的時間復雜度相同，沒有增加計算負擔。

4 結束語

為提高SBO算法的收斂精度，避免算法陷入局部最優，本文提出了基于自適應權重的緞藍園丁鳥優化算法—WSBO 算法。該算法通過使用自適應權重和改變高斯變異形式提升了基本SBO算法的全局搜索能力和局部尋優能力，從而在很大程度上提高了算法的收斂精度。本文還進行了8個函數的仿真測試，實驗結果表明，改進的SBO 算法是可行有效的，在收斂速度和收斂精度方面都要優于原緞藍園丁鳥算法、人工蜂群算法和螢火蟲算法，其尋優性能有了很大的提高。如何將改進算法應用到更多的領域，是今后的研究工作。