基于精英策略改進的自適應布谷鳥搜索算法

李 銳，龍文高，原可欣

（1 湖南科技大學 數學與計算科學學院，湖南 湘潭 411201；2 太原理工大學 文法學院，太原 030024）

0 引 言

布谷鳥搜索算法（Cuckoo Search，CS）是Xin－She Yang與Suash Deb 于2009 年提出的一種新型的群體智能算法［1］。該算法主要通過對生物界中布谷鳥寄生雛鳥的仿生行為，解決現實中的優化問題。

在自然界中，大部分鳥類的育雛習性是自筑巢自育雛，而布谷鳥則是寄生巢異育雛。布谷鳥會在其生活區域內尋找合適的巢穴快速產卵，同時布谷幼鳥會本能地模仿宿主幼鳥的叫聲以得到宿主鳥的哺育，這樣就實現了寄生巢。而且根據相關學者的研究表明，布谷鳥尋巢過程滿足于Levy 分布［2］。不妨將布谷鳥找到的每個巢穴都看作一個可行解，由其Levy 飛行過程中產生替補解，按照一定的概率，遵循“新解更替，舊解淘汰”的規則，從而實現全局尋優，這就是傳統的布谷鳥搜索算法和思想［3］。

傳統的CS 具有仿生能力強、參數少、操作簡單的特點，因而被廣泛的應用于組合優化、電力調度以及機械工程等多個工程領域［4－6］。但在傳統的CS 中，由于步長因子與發現概率是固定不變的，這就導致布谷鳥容易出現過早成熟的情況，尋優解的精確度較差，甚至找不到全局最優值以及收斂速度慢的情況。目前，學術界內主要通過調整參數與混合算法兩種途徑來解決這些缺陷。如：文獻［7］中提出的一種參數動態更新的布谷鳥搜索算法，通過以一定概率下保留次優解及雙向隨機搜索策略，避免陷入局部最優；文獻［8］提出的基于免疫進化改進的布谷鳥算法，通過結合兩種算法的優點來作出改進與提高。

綜上所述，改進算法雖然相較于傳統CS 的性能有一定程度的提升，但改進后布谷鳥種群的全局尋優能力并沒有得到明顯的提高，且忽略了仿生性。因此，本文提出了一種基于精英策略改進的布谷鳥搜索算法（ESCS）。本文將布谷鳥群體進行分類，精英布谷鳥與普通布谷鳥執行不同的飛行策略，從而避免整個布谷鳥群體陷入局部最優而無法跳出；同時，布谷鳥群體的發現概率會基于迭代次數自適應變化，加快了算法后期的收斂速度，且保證布谷鳥會在全局最優值附近進一步搜索尋優。實驗結果表明，本文提出的ESCS 相較于ICS 等一些改進算法具有較強的魯棒性與較優的精確性。

1 傳統的布谷鳥搜索算法（CS）

1.1 仿生學原理

在自然界中，大部分的鳥類會選擇自筑巢和自哺育雛鳥，但有30%～40%的布谷鳥會選擇異巢寄生幼鳥，這是一種特殊且少見的繁殖方式。在布谷鳥的繁殖期，布谷鳥會在一定范圍內尋找合適的巢穴（寄主與布谷鳥生活習性相類同）進行產卵寄生，而寄主的哺育能力是有限的，布谷鳥為了增加其幼鳥的存活概率，會隨機把寄主的一枚或多枚蛋推出巢穴。布谷幼鳥在破殼后，會本能的模仿寄主幼鳥的叫聲，從而得到寄主的哺育。此外，布谷幼鳥在發育一段時間后，會把寄主巢穴中的蛋全部推出，從而進一步增大其生存幾率。但隨著進化過程，寄主也逐漸提高了辨認布谷鳥的能力，在識別出布谷鳥后，會進行攻擊，布谷鳥只能放棄此處巢穴，再次搜索附近合適的巢穴。

1.2 參數定義

依據布谷鳥的生育特性進行仿生，在傳統的CS中，以向量x＝［x1，x2，…，xn］ 代表布谷鳥，即為可行解。其中，xi為每個解分量，n為待求問題的維度。其它參數定義見表1。

表1 CS 中的參數定義Tab.1 Parameter definitions in CS

1.3 更新公式

在傳統的CS 中，布谷鳥在寄巢生中有兩種途徑進行解的更新。一種是在尋找巢穴的過程中，基于Levy 飛行產生新的解：

式中，xb為歷史最優解。

而另一種就是寄主發現布谷鳥的過程中產生新一代解：

式中，xi、xj、xk為隨機選擇的互異可行解。

2 基于精英策略改進的自適應布谷鳥搜索算法（ESCS）

2.1 自適應發現概率

在傳統的CS 中，布谷鳥被寄主鳥發現的概率是固定不變的，通常設定Pa＝0.35。但這往往會導致在搜索尋優后期，布谷鳥群會跳過全局最優值而無法收斂于其鄰域。

本文將布谷鳥被發現概率基于迭代次數進行自適應降低，遵循公式（3）：

在實際的優化問題中，如果減小布谷鳥被發現的概率，那么布谷鳥群就會趨向“當前最優值”不斷靠近并繼續搜索尋優，這就保證了算法的收斂速度與尋優解的精度；但如果發現概率過小，則很容易導致算法陷入局部最優解而無法跳出。因此，設置發現概率的下限為Pa／100，即便在后期，布谷鳥也有一定的概率跳出局部最優情況，間接確保布谷鳥在后期的搜索尋優能力不會退化。

2.2 精英策略

在傳統的CS 中，布谷鳥群中離散程度較大，布谷鳥個體之間均視為同一等級。在進行搜索巢穴與寄生時，可以視為獨立分工完成，這與實際的生物群體特性是不相符的。在對CS 進行初始化時，nestnum往往是大于50 的，這就要考慮群體效應。

無論是像狼群與獅群，存在等級制度的生物種群；還是像蟻群與蜂群，存在不同分工任務的生物種群；以及像魚群一樣只是簡單的聚群生物，這些群體中總會有精英個體。精英個體無論是搜尋食物能力，還是御敵能力，都極大程度地優于種群中普通的個體，而且精英個體往往具有領導能力，即帶領種群得到更好的食物、空間等資源，使得種群得以更好的生存。

本文參考生物種群的這一特性，將布谷鳥群進行分類：

式中，μ為黃金分割比。

對于普通布谷鳥來說，按照公式（1）與公式（2）進行解的更新；而對于任意一精英布谷鳥xnow，其需要考慮到整個種群的狀態而進行相適應解的更新：

而對于其他精英布谷鳥xelse，其也會進行更新：

基于精英策略對布谷鳥群體進行劃分，確保布谷鳥群始終保持著高強度的搜索能力與活躍度，提高了算法的準確度與尋優效率。

2.3 算法流程

（1）初始化參數；

（2）布谷鳥群基于Lvey 飛行進行搜索巢穴，可行解進行更新；

（3）判斷是否被寄主發現：若是，則精英布谷鳥按照式（7）、式（8）更新解，普通布谷鳥按照式（2）更新解；否則均按照式（1）更新解；

（4）更新記錄牌；

（5）判斷是否達到最大迭代次數；若是則結束迭代；否則返回步驟（2）；

（6）輸出歷史最優值。

流程如圖1 所示。

圖1 ESCS 算法流程Fig.1 ESCS algorithm flow

3 仿真實驗

3.1 仿真實驗環境

本次仿真實驗環境設置：操作系統Windows 10、CPU 為Intel（R）Core（TM）i7－7500U CPU、主頻2.70Ghz、內存為4GB、仿真軟件Matlab2020a。

3.2 實驗參數初始化設定

該文參考了文獻［9］、文獻［10］以及文獻［13］中參數的初始設定，并選取nestnum、Pa以及maxgen作為通用參數；對3 組通用參數進行等權平均化：

得到參數組合PM*，再借助專家意見，最終確定了針對于ESCS 的一組較優的參數組合，見表2。

表2 ESCS 參數設定Tab.2 ESCS parameter settings

3.3 測試函數

為了驗證ESCS 的高效性與準確性，探究其實際的性能表現，該文選用ICS［8］與MCCS［12］進行橫向對比，并選用表3 所列的6 個標準測試函數［11］進行仿真對比實驗。

表3 標準測試函數Tab.3 Standard test functions

需要特別說明的是，為了更好檢驗ESCS 的全局搜索能力，該文將自變量的范圍設定為［－5，5］。

3.4 實驗結果分析

為了避免單次實驗的偶然性而導致的實驗誤差，所有算法依次對6 個測試函數進行了20 次的重復實驗。

該文選取最優測試值（Optimun results，OR）、方差（Variance，Var）以及正確率（Accuracy，AC）作為算法性能表現的評定指標，實驗結果見表4。

表4 基于標準測試函數的對比結果Tab.4 Comparison results based on standard test functions

OR與AC反映了算法求解的準確性，而VAR與AC反映了算法求解的魯棒性與效率。

對表4 的實驗結果進行對比分析可知，在6 個標準測試函數的20 次重復試驗中，MCCS 僅在f3中AC為100%，ICS在f3與f4中AC為100%，而對于ESCS，除了f5外，在其它5 個標準測試函數中的AC均為100%。

綜合對比OR與VAR，ESCE 的性能表現最佳，ICS 次之，MCCS最差。在實際的工程項目中，對算法的準確性與魯棒性有很高要求。假定算法準確性與魯棒性同樣重要，結合3 個指標，可以得出以下結論：ESCS 相較于ICS 和MCCS，在魯棒性與準確性方面均有較大的提升。

3.5 補充對比實驗

3.5.1 測試函數

為了進一步驗證ESCS 的全局尋優能力與尋優解的精確度，本文選用了文獻［8］、文獻［15］以及MCCS 算法與ESCS 進行對比實驗，并選取3 類高精度的測試函數：

其中，自變量的取值范圍均為［－1，1］，全局最大值為2.118 8。

其中，自變量的取值范圍均為［－10，10］，全局最大值為210.482 3。

其中，自變量的取值范圍均為［－5，5］，全局最優值為1.031 628 453 489 88。

3.5.2 參數設定

為保證各算法的性能，在測試函數F1～F3中，分別對算法的一些基本公共參數［14］進行初始設定，見表5～表7。

表5 F1中的基本參數設定Tab.5 Basic parameter settings in F1

表6 F2中的基本參數設定Tab.6 Basic parameter settings in F2

表7 F3中的基本參數設定Tab.7 Basic parameter settings in F3

3.5.3 實驗結果

第一輪性能對比實驗，選取了“最佳適應度值變化趨勢”作為對比指標，該指標可以很好的體現出算法之間收斂速度與準確度的差異，實驗結果如圖2～圖4 所示。

圖2 F1—最佳適應度值對比Fig.2 F1－comparison of optimal fitness values

圖3 F2—最佳適應度值對比Fig.3 F2－comparison of optimal fitness values

圖4 F3—最佳適應度值對比Fig.4 F3－comparison of optimal fitness values

其次，為了對比不同算法下種群之間搜索能力與全局尋優能力的差異，選取了“平均適應度值變化趨勢”作為第二個對比指標，實驗結果如圖5～圖7 所示。

圖5 F1—平均適應度值對比Fig.5 F1－comparison of average fitness values

圖6 F2—平均適應度值對比Fig.6 F2－comparison of average fitness values

圖7 F3—平均適應度值對比Fig.7 F3－comparison of average fitness values

為避免單次實驗因偶然性導致的實驗誤差，設置30 次的重復實驗進一步驗證ESCS 算法的性能。

本次實驗選取最優測試值（optimum results）和最差測試值（worst results）為對比指標，實驗結果見表8。

表8 仿真對比實驗結果Tab.8 Experimental results of simulation

3.5.4 實驗結果分析

由圖2～圖4 可知，ESCS 算法在迭代10 次后，收斂于全局最優值，收斂速度僅次于MCCS，且尋優解的準確度高于其它對比算法；MCCS 算法總體算法收斂速度最快，但在F1與F3中所得尋優解的準確度為最低；文獻［8］的算法收斂速度在F1中呈現明顯的斷層狀，在F2與F3中以近似對數遞增趨勢，因而其總體收斂速度是較為優異的，同時尋優解的準確度也是較高的；文獻［15］算法的收斂速度與尋優解的準確度的綜合表現僅次于MCCS。另外，由圖5～圖7 可知，在種群尋優搜索能力方面，ESCS與MCCS 不相上下，文獻［8］次之，文獻［15］最差。

由表8 對平均實驗結果進行分析可得，針對于最優測試值（OR），ESCS 的精確度最高，文獻［8］與文獻［15］的精確度次之，MCCS 的精確度最差（尤其是在F2中）；而針對于最差測試值（WR），ESCS在F3中表現一般，但在F1與F2中表現最為優異，文獻［15］在F3中表現最佳，在F1與F2中表現也較為滿意，MCCS 的綜合表現次之，文獻［8］的綜合表現最差。

結合以上分析，表明ESCS在收斂速度、尋優解的精度以及全局搜索能力等方面的綜合表現優于其它參與實驗的改進算法，驗證了ESCS 的高效性與可行性。

4 結束語

針對傳統的布谷鳥搜索算法存在過早成熟、尋優解的精確度與準確度差，以及收斂速度慢等問題，本文提出了一種基于精英策略改進的自適應布谷鳥搜索算法。ESCS在參數初始化階段，將布谷鳥分為精英布谷鳥與普通布谷鳥，兩種布谷鳥在被寄主鳥發現時會執行不同的飛行策略。精英策略可以避免算法陷入局部最優導致過早成熟。此外，再對布谷鳥被發現概率進行自適應改進，加快了算法后期的收斂速度。最后設置6 種標準測試函數與縱向對比實驗，進一步驗證ESCS 的綜合性能表現，仿真結果表明ESCS 具有較好的魯棒性與尋優性能。