參數動態調整的自適應布谷鳥算法

宋 鈺，石立寶

電力系統國家重點實驗室深圳研究室（清華大學深圳國際研究生院），廣東 深圳 518055

1 引言

布谷鳥算法（Cuckoo Search algorithm，CS）是由學者Yang X S 和Deb S 于2009 年提出的一種智能優化算法，算法提出的靈感來源于自然界布谷鳥的寄生性育雛行為[1]。相比于其他智能優化算法，CS具有控制參數少、算法易實現、尋優路徑優以及全局搜索能力強的優點[2]，近年來被廣泛應用于優化[3-4]、預測[5-6]以及圖像去噪[7]等領域。學者們針對布谷鳥算法展開了系統而深入的研究。文獻[8]通過馬爾科夫鏈模型證明了布谷鳥算法的收斂性。為克服布谷鳥算法后期收斂速度變慢、搜索能力降低的缺點，一些學者提出將布谷鳥算法與其他智能優化算法相結合，充分利用兩種算法的優點以獲得更佳的求解效果[9-11]。另外一些學者則致力于提升布谷鳥算法本身的性能。2011 年Valian E 等人提出了一種基于自適應機制的布谷鳥算法，通過動態改變布谷鳥算法中的參數提高了算法的局部和全局搜索能力，進而提升了算法的計算精度和收斂速度[12]。此后，國內外學者分別提出了多種動態改變布谷鳥算法參數的自適應機制。其中，部分研究依據當前迭代次數來改變該次迭代中各參數的大小[12-14]，另一些研究則依據每次迭代中各解的好壞來改變本次迭代中各解相應的參數[15-17]。這些研究在一定程度都取得了較好的改進效果。

本文首先簡述了布谷鳥算法的基本原理。為了進一步提高布谷鳥算法的計算精度和收斂速度，本文在已有研究成果基礎上提出了一種新的自適應布谷鳥算法。該算法可依據解的好壞來控制其發現概率的大小，并在運算初期依據迭代次數、解的好壞、種群規模和總迭代次數動態改變步長，在運算后期，不考慮迭代次數、種群規模的影響，僅依據解的好壞動態改變步長。最后，本文利用仿真實驗對比了所提算法與其他算法的求解效果，證明了所提算法的優越性。

2 布谷鳥算法基本原理

布谷鳥算法的靈感源于布谷鳥的育雛行為。一些布谷鳥會將自己的蛋產入云雀、黃鶯等宿主鳥的巢中，讓它們代替自己育雛。由于布谷鳥蛋與宿主鳥蛋外表相似，往往不易被宿主鳥發現。當宿主鳥沒有發現布谷鳥蛋時，它會同時孵化布谷鳥蛋和自己的蛋。由于布谷鳥蛋的孵化時間短于宿主鳥蛋，先孵化的布谷鳥幼雛本能地破壞鳥巢中的其他鳥蛋以獲取更多的資源。當宿主鳥發現布谷鳥蛋時，它會拋出布谷鳥蛋或放棄整個鳥巢并選擇其他地方重新筑巢。為了簡化和模擬布谷鳥的育雛行為，學者Yang X S 和Deb S 提出了以下三條理想規則。

規則1每只布谷鳥每次只產一個蛋，并隨機選擇一個寄生巢來放置。

規則2在隨機選擇的一組寄生巢中，最好的寄生巢會被保留到下一代。

規則3可利用的寄生巢的數量是一定的，布谷鳥蛋被宿主鳥發現的概率為Pa。

此外，研究表明自然界中許多動物的覓食路徑可以用 Lévy 飛行描述。Lévy 飛行是服從 Lévy 分布的隨機搜索路徑，由頻繁出現的短步長和偶爾出現的長步長組成。在布谷鳥算法中，學者Yang X S 和Deb S 利用Lévy 飛行描述布谷鳥的飛行軌跡并更新鳥巢的位置。Lévy 飛行中大量的短步長有利于布谷鳥算法局部尋優，可以提高算法的搜索精度，同時少量的長步長可以擴大算法的搜索范圍，有助于算法跳出局部最優。

將布谷鳥、宿主鳥巢以及布谷鳥蛋均看作解，則從自然界布谷鳥行為中抽象出布谷鳥算法的主要步驟為：

步驟1初始化各參數，隨機生成一組初始解并計算它們的適應度。

步驟2通過Lévy飛行對解進行更新，如式（1）所示：

式中，xi(t)和xi(t+1)分別為第t次和t+1 次迭代時的第i個解，α是步長參數，Levy(β)代表遵循Lévy 飛行的隨機步長。

步驟3比較新解的適應度值和舊解的適應度值，若新解的適應度值優于舊解的適應度值，則用新解替換舊解。

步驟4根據發現概率丟棄部分解，然后隨機偏好游走生成同樣多的解來代替被丟棄的解，如式（2）所示：xi(t+1)=xi(t)+r?Heaviside(Pa-ε)?(xk(t)-xj(t))（2）式中，r和ε為[0,1]區間內正態分布的隨機數，Heaviside(u) 表示階躍函數，Pa為發現概率，xk(t) 和xj(t)為第t次迭代時的兩個隨機解。

步驟5計算通過步驟2至步驟4產生的新一代的解的適應度值并挑選出最優解。

步驟6重復步驟2至步驟5，直到達到最大迭代次數。

3 改進的布谷鳥算法

在布谷鳥算法中，參數α控制每次迭代的步長δ（即變異量），并且α越大，步長δ越大。發現概率Pa控制產生新解的概率，并且Pa越大，產生新解的概率越大。而步長和產生新解的概率越大，每次迭代的搜索范圍就越大，算法的全局尋優能力就越強，收斂速度也就越快。但隨著搜索規模的擴大，算法的局部尋優能力會下降，算法的搜索精度也會下降。與之相反地，α和Pa越小，每次迭代的搜索范圍就越小，全局尋優能力就越差，收斂速度也就越慢，但算法的局部尋優能力會增強，搜索精度也會提高。針對不同的優化問題，應選取適當的α和Pa以同時獲取較快的收斂速度與較高的搜索精度。然而目前并沒有一種系統的方法來確定α和Pa。此外，還應在較差解附近用較大的α和Pa全局尋優以提高收斂速度，用較小的α和Pa在較好解的附近局部尋優以提高搜索精度。而在傳統的布谷鳥算法中，α和Pa為定值，不能根據解的好壞進行動態調整。針對以上問題，本文在文獻[14-16]的基礎上提出了步長δ和發現概率Pa的動態調整機制，令δ和Pa隨著解的好壞、迭代次數的大小而自發地朝著合適的方向變化。

3.1 步長δ 的動態調整機制

假設優化問題的目標為求解函數最小值，xmin(t)和xmax(t)分別表示第t次迭代時的最優解和最差解，它們對應的適應度值分別為fmin(t)和fmax(t)，即第t次迭代時求解出的最小和最大適應度。則對于最差解xmax(t)，其步長δmax(t)應為一個很大的值。受到文獻[18]思想的啟發，δmax(t)可采用如下方式確定：

上述解的更新過程如圖1 所示，其中a和b點分別代表。

圖1 解的更新過程

而對于最優解xmin(t)，其步長δmin(t)應為一個很小的值。此外，隨著迭代次數的增加，xmin(t)應逐漸趨于最全局優解，相應地，其步長δmin(t)也應逐漸趨于一個很小的值。同時，當迭代次數很大時，種群規模對于求解結果的影響較小。綜合考慮這些因素，提出采用如下表達式來確定δmin(t)的第k個分量δmin,k(t)：

式中，p為種群規模。經過大量實驗發現，當其指數取2.5時效果最好。

由于種群規模最小為1，因此在任何一次迭代時，δmin,k(t)都小于，不存在變異后解超出約束范圍的情況。此外，智能優化算法的求解精度和穩定程度會隨著種群規模和迭代次數的增加而提高，但種群規模和迭代次數的增加會導致運算時間和規模的擴大，同時種群規模和迭代次數的不同取值也可能對優化結果造成較大影響。而在式（4）的機制下，δmin,k(t)會隨著種群規模和迭代次數的增加而減小，這將制約種群規模和迭代次數增加對優化結果的正面影響，進而減小種群規模和迭代次數的不同取值對優化結果造成的影響。

而對于第t次迭代時的第i個解xi(t)，它的步長δi(t)應位于區間[δmax(t),δmin(t)]內，并且它對應的適應度fi(t)越大，δi(t)就應該越大。鑒于此，本文采用指數形式來描述δi,k(t)和fi(t)的關系，即有：

式中，δi,k(t)為步長δi(t)的第k個分量，ai,k(t)和bi,k(t)分別為相應的系數。當xi,k(t)在區間內時取-，反之取+。結合式（3）與（4），可得到：

解得ai,k(t)和bi,k(t)分別為：

在以上提出的步長動態調整機制下，在算法運行的初期，迭代次數較小時，由于各解對應的適應度差值較大，根據式（5）和式（7）可知，此時算法的步長較大，算法的全局搜索能力較強，收斂速度較快。而到了算法運行的后期，大多數解對應的適應度會趨近最小適應度，根據式（5）和式（7）可知，此時步長δi,k(t)會趨近式（4）。由于該式的分母中存在t+p2.5，在算法運行后期迭代次數t很大時，搜索步長δi,k(t)會急劇減小，導致算法的全局搜索能力和收斂速度下降，甚至還可能使算法陷入局部最優。為解決這個問題，本文在算法運行前期使用式（5）來控制步長，在算法運行后期引入一種不考慮種群規模和迭代次數的自適應機制來控制步長，其基本原理如式（8）和式（9）所示：

式中，為第二種自適應機制下第t次迭代時第i個解的步長參數分別為第二種自適應機制下步長參數的最大值和最小值，為第二種自適應機制下的步長，xi,k(t)是第t次迭代時第i個解的第k個分量，‖xi(t)-xmin(t)‖為xi(t)與xmin(t)之間的距離，dmax(t)為最優解和其他解距離的最大值。

當解越接近最優解時，其‖xi(t)-xmin(t)‖和(xi,k(t)-xmin,k(t))的值越小，由式（8）和式（9）可知，其搜索步長也越小，有利于在最優解附近局部尋優；反之，當個體距離最優位置越遠時，其‖xi(t)-xmin(t)‖和(xi,k(t)-xmin,k(t))的值越大，相應搜索步長也越大，有利于差的解跳出當前的不利位置。因此該自適應機制可以提高算法的全局尋優和局部尋優能力。此外，式（9）還通過引入Lévy飛行避免使算法陷入局部最優。

將上述兩種步長動態調整策略相結合，可使算法在避免陷入局部最優的同時獲得較快的收斂速度和較高的搜索精度。結合后的步長動態調整機制為：

式中，T為轉折代數，大量實驗的結果表明，T取50～150之間的值時優化效果最佳。

3.2 發現概率的動態調整機制

本文采用文獻[16]所提出的自適應機制來描述發現概率，如式（11）所示：

式中，pa,i(t)為第t次迭代時第i個解的發現概率，pa,max和pa,min分別為發現概率的最大值和最小值。當某個解對應的適應度接近最小適應度時，其發現概率接近最小值，說明它不容易被拋棄；反之，當個體的適應度與最小適應度相差很大時，其發現概率接近最大值，說明它容易被拋棄。這有利于好的解被留下而壞的解被替換，從而可以加速算法的收斂速度。

3.3 參數動態調整的自適應布谷鳥算法

參數動態調整的自適應布谷鳥算法流程圖如圖2所示。

圖2 參數動態調整的自適應布谷鳥算法流程圖

相應的偽代碼為：

1.Initialize a population withnsolutionsxi( 1),i=1,2,…,n

2.For all solutions do

3.Calculate fitness value byFi(1)=f(xi(1))

4.End for

5.While iteration numbert＜max iteration number

6.Calculate mutation step size by formula（10）

7.Generate new solutions according to mutation step size

8.Calculate fitness values of new solutions by

11.End if

12.Calculate discovery rate by formula（11）

13.Abandon some solutions according to discovery rate and generate new solutions to replace them by formula（2）

14.Calculate the fitness values of all solutions and pick out the best solution

15.Iteration numbert=t+1

16.End while

4 數值仿真與分析

4.1 仿真實驗設計

為驗證所提出的自適應布谷鳥算法的有效性，本文選取表1所示的10個標準測試函數進行仿真分析，并對比常規布谷鳥算法（以下記為CS）、文獻[12]、[13]、[15]、[16]提出的改進的布谷鳥算法（以下分別記為ICS1、ICS2、ICS3 和ICS4）、粒子群算法（以下記為PSO）以及本文提出的參數動態調整的自適應布谷鳥算法（以下記為ACS）的測試結果。各算法的參數設置分別如表2和表3所示。其中，ACS的最優參數設置通過大量實驗獲得，其余各算法分別依照文獻[12]、[13]、[15]、[16]設置參數。實驗的測試平臺為Matlab?環境，所用計算機硬件配置為（Intel?Core?i5-5200U）2.2 GHz，內存為4 GB。

表1 測試函數

表2 各種布谷鳥算法參數設置

表3 粒子群算法參數設置

4.2 實驗結果及分析

針對不同測試函數，各算法獨立運行100 次，得到的實驗結果如表4 所示。其中，f1為單峰函數，但由于它在全局最小值附近函數值變化極為緩慢，因此常被用于評價算法的后期搜索性能。從100 次實驗結果的最大值、最小值、平均值以及達到目標值的次數可以看出，ACS 的求解精度較 CS、ICS 以及 PSO 有大幅提高。同時，ACS 求解結果的方差遠遠小于其余算法，說明ACS的求解結果更加穩定。f2是一個復雜的多峰函數，擁有無數的局部極小值和局部最大值，常導致算法在求解時陷入局部最優。可以看到，雖然ACS 的求解精度和穩定性遠遠高于其他算法，但在求解后期卻陷入了局部最優值4.44E?15。f3是典型的非線性多模態函數，搜索空間大并擁有許多局部極小點，通常被認為是智能優化算法很難求解的復雜問題。雖然從100 次實驗結果的平均值和最大值來看，ACS的求解精度只是略微優于其他算法，但ACS達到目標值1E?05的次數更多，并且能夠在其余算法的最好求解結果達不到1E?05 時搜索到全局最優解0，這說明ACS 的求解能力高于其余算法。與此類似，同樣f4也是一個典型的非線性多模態函數。它的局部極小值的個數與問題的維數成正比，且函數峰谷起伏不定，因此也很難求解出全局最優值。可以看到，雖然ACS的100次實驗結果均值和方差都與其他算法的結果相差不大，但ACS 可以搜索到全局最優解0，并且有更大的概率達到目標值。f5的全局最小值位于一個拋物線形的山谷中，由于山谷內函數值變化很小，很難求解出全局最優值，常被用于評價算法的搜索能力。可以看出，ACS在求解這個問題時的求解精度和穩定性都遠遠高于其余算法，說明ACS 的搜索能力很強。f6是一個復雜的二維函數，擁有無數個局部極小值并具有強烈振蕩的特征，是評價算法收斂性和搜索能力的經典函數。可以從100次實驗結果的最大值看出，ICS1、ICS2、ICS3、ICS4 以及 PSO 均在求解時陷入了局部最優值9.71E?03，而ACS 則避開了該值。同時，ACS可以搜索到全局最優值0，并且求解結果的最大值、平均值、方差以及達到目標值的次數均遠遠超過了其他算法。說明ACS 具有很強的收斂性和搜索能力。f7、f8和f9均為復雜多峰值函數，擁有許多局部極小值點。可以看到，ACS 的求解結果的最值、平均值以及穩定性均優于其他算法，并且ACS 大多數時候總能達到目標值。f10為一單峰函數，常被用于檢測算法的尋優能力。可以看到，ACS的求解精度和穩定性均遠遠優于其他算法，說明ACS的尋優能力很強。

表4 多種算法的計算結果

各算法求解10 個標準函數的收斂曲線分別如圖3至圖12所示。可以看到，在求解初期，多數時候ACS的收斂速度雖然小于PSO 的，但大于其余算法。而PSO到了求解后期會陷入局部最優，ACS 除去在求解f2時陷入了局部最優，其余情況下都能在求解后期依然保持很快的收斂速度。

圖3 f1 的收斂曲線

圖4 f2 的收斂曲線

圖5 f3 的收斂曲線

圖6 f4 的收斂曲線

圖7 f5 的收斂曲線

圖8 f6 的收斂曲線

圖9 f7 的收斂曲線

圖10 f8 的收斂曲線

圖11 f9 的收斂曲線

圖12 f10 的收斂曲線

CS和ACS求解各函數所需的時間如表4中平均運行時間所示。可以看到，CS 與ACS 求解各函數的運行時間都很短，說明兩種算法的運行速度均很快。此外，ACS求解各問題所需的時間略大于CS的求解時間。這是由于ACS 在CS 的基礎上增加了自適應機制，使得ACS 的計算復雜度有一定的提高，導致ACS 求解優化問題所需的時間有所變長。需要說明的是，本文所提出的自適應機制僅需簡單的代數運算即可實現，不會對算法造成很大的運算負擔。

綜上所述，相較于其他各算法，ACS 具有更高的計算精度和穩定性，收斂速度更快，不易陷入局部最優。此外，所提出的自適應機制在一定程度上沒有給ACS增加運算負擔。

5 結束語

本文簡述了布谷鳥算法的基本原理。在前人研究基礎上，本文提出了一種基于參數動態調整機制的自適應布谷鳥算法。所提出算法會依據解的好壞動態改變發現概率的大小，并在運算前期和后期分別利用兩種自適應機制控制步長動態變化。通過對比該算法與其他算法求解10 個標準測試函數的結果，可知本文所提算法計算復雜性較低，并且在計算精度、穩定性以及收斂速度上均具有一定的優勢。