李 銳，龍文高，原可欣

（1 湖南科技大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，湖南 湘潭 411201；2 太原理工大學(xué) 文法學(xué)院，太原 030024）

0 引 言

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

在自然界中，大部分鳥類的育雛習(xí)性是自筑巢自育雛，而布谷鳥則是寄生巢異育雛。布谷鳥會(huì)在其生活區(qū)域內(nèi)尋找合適的巢穴快速產(chǎn)卵，同時(shí)布谷幼鳥會(huì)本能地模仿宿主幼鳥的叫聲以得到宿主鳥的哺育，這樣就實(shí)現(xiàn)了寄生巢。而且根據(jù)相關(guān)學(xué)者的研究表明，布谷鳥尋巢過(guò)程滿足于Levy 分布［2］。不妨將布谷鳥找到的每個(gè)巢穴都看作一個(gè)可行解，由其Levy 飛行過(guò)程中產(chǎn)生替補(bǔ)解，按照一定的概率，遵循“新解更替，舊解淘汰”的規(guī)則，從而實(shí)現(xiàn)全局尋優(yōu)，這就是傳統(tǒng)的布谷鳥搜索算法和思想［3］。

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

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

1 傳統(tǒng)的布谷鳥搜索算法（CS）

1.1 仿生學(xué)原理

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

1.2 參數(shù)定義

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

表1 CS 中的參數(shù)定義Tab.1 Parameter definitions in CS

1.3 更新公式

在傳統(tǒng)的CS 中，布谷鳥在寄巢生中有兩種途徑進(jìn)行解的更新。一種是在尋找巢穴的過(guò)程中，基于Levy 飛行產(chǎn)生新的解：

式中，xb為歷史最優(yōu)解。

而另一種就是寄主發(fā)現(xiàn)布谷鳥的過(guò)程中產(chǎn)生新一代解：

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

2 基于精英策略改進(jìn)的自適應(yīng)布谷鳥搜索算法（ESCS）

2.1 自適應(yīng)發(fā)現(xiàn)概率

在傳統(tǒng)的CS 中，布谷鳥被寄主鳥發(fā)現(xiàn)的概率是固定不變的，通常設(shè)定Pa＝0.35。但這往往會(huì)導(dǎo)致在搜索尋優(yōu)后期，布谷鳥群會(huì)跳過(guò)全局最優(yōu)值而無(wú)法收斂于其鄰域。

本文將布谷鳥被發(fā)現(xiàn)概率基于迭代次數(shù)進(jìn)行自適應(yīng)降低，遵循公式（3）：

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

2.2 精英策略

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

無(wú)論是像狼群與獅群，存在等級(jí)制度的生物種群；還是像蟻群與蜂群，存在不同分工任務(wù)的生物種群；以及像魚群一樣只是簡(jiǎn)單的聚群生物，這些群體中總會(huì)有精英個(gè)體。精英個(gè)體無(wú)論是搜尋食物能力，還是御敵能力，都極大程度地優(yōu)于種群中普通的個(gè)體，而且精英個(gè)體往往具有領(lǐng)導(dǎo)能力，即帶領(lǐng)種群得到更好的食物、空間等資源，使得種群得以更好的生存。

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

式中，μ為黃金分割比。

對(duì)于普通布谷鳥來(lái)說(shuō)，按照公式（1）與公式（2）進(jìn)行解的更新；而對(duì)于任意一精英布谷鳥xnow，其需要考慮到整個(gè)種群的狀態(tài)而進(jìn)行相適應(yīng)解的更新：

而對(duì)于其他精英布谷鳥xelse，其也會(huì)進(jìn)行更新：

基于精英策略對(duì)布谷鳥群體進(jìn)行劃分，確保布谷鳥群始終保持著高強(qiáng)度的搜索能力與活躍度，提高了算法的準(zhǔn)確度與尋優(yōu)效率。

2.3 算法流程

（1）初始化參數(shù)；

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

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

（4）更新記錄牌；

（5）判斷是否達(dá)到最大迭代次數(shù)；若是則結(jié)束迭代；否則返回步驟（2）；

（6）輸出歷史最優(yōu)值。

流程如圖1 所示。

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

3 仿真實(shí)驗(yàn)

3.1 仿真實(shí)驗(yàn)環(huán)境

本次仿真實(shí)驗(yàn)環(huán)境設(shè)置：操作系統(tǒng)Windows 10、CPU 為Intel（R）Core（TM）i7－7500U CPU、主頻2.70Ghz、內(nèi)存為4GB、仿真軟件Matlab2020a。

3.2 實(shí)驗(yàn)參數(shù)初始化設(shè)定

該文參考了文獻(xiàn)［9］、文獻(xiàn)［10］以及文獻(xiàn)［13］中參數(shù)的初始設(shè)定，并選取nestnum、Pa以及maxgen作為通用參數(shù)；對(duì)3 組通用參數(shù)進(jìn)行等權(quán)平均化：

得到參數(shù)組合PM*，再借助專家意見，最終確定了針對(duì)于ESCS 的一組較優(yōu)的參數(shù)組合，見表2。

表2 ESCS 參數(shù)設(shè)定Tab.2 ESCS parameter settings

3.3 測(cè)試函數(shù)

為了驗(yàn)證ESCS 的高效性與準(zhǔn)確性，探究其實(shí)際的性能表現(xiàn)，該文選用ICS［8］與MCCS［12］進(jìn)行橫向?qū)Ρ?，并選用表3 所列的6 個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)［11］進(jìn)行仿真對(duì)比實(shí)驗(yàn)。

表3 標(biāo)準(zhǔn)測(cè)試函數(shù)Tab.3 Standard test functions

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

3.4 實(shí)驗(yàn)結(jié)果分析

為了避免單次實(shí)驗(yàn)的偶然性而導(dǎo)致的實(shí)驗(yàn)誤差，所有算法依次對(duì)6 個(gè)測(cè)試函數(shù)進(jìn)行了20 次的重復(fù)實(shí)驗(yàn)。

該文選取最優(yōu)測(cè)試值（Optimun results，OR）、方差（Variance，Var）以及正確率（Accuracy，AC）作為算法性能表現(xiàn)的評(píng)定指標(biāo)，實(shí)驗(yàn)結(jié)果見表4。

表4 基于標(biāo)準(zhǔn)測(cè)試函數(shù)的對(duì)比結(jié)果Tab.4 Comparison results based on standard test functions

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

對(duì)表4 的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比分析可知，在6 個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的20 次重復(fù)試驗(yàn)中，MCCS 僅在f3中AC為100%，ICS在f3與f4中AC為100%，而對(duì)于ESCS，除了f5外，在其它5 個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)中的AC均為100%。

綜合對(duì)比OR與VAR，ESCE 的性能表現(xiàn)最佳，ICS 次之，MCCS最差。在實(shí)際的工程項(xiàng)目中，對(duì)算法的準(zhǔn)確性與魯棒性有很高要求。假定算法準(zhǔn)確性與魯棒性同樣重要，結(jié)合3 個(gè)指標(biāo)，可以得出以下結(jié)論：ESCS 相較于ICS 和MCCS，在魯棒性與準(zhǔn)確性方面均有較大的提升。

3.5 補(bǔ)充對(duì)比實(shí)驗(yàn)

3.5.1 測(cè)試函數(shù)

為了進(jìn)一步驗(yàn)證ESCS 的全局尋優(yōu)能力與尋優(yōu)解的精確度，本文選用了文獻(xiàn)［8］、文獻(xiàn)［15］以及MCCS 算法與ESCS 進(jìn)行對(duì)比實(shí)驗(yàn)，并選取3 類高精度的測(cè)試函數(shù)：

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

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

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

3.5.2 參數(shù)設(shè)定

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

表5 F1中的基本參數(shù)設(shè)定Tab.5 Basic parameter settings in F1

表6 F2中的基本參數(shù)設(shè)定Tab.6 Basic parameter settings in F2

表7 F3中的基本參數(shù)設(shè)定Tab.7 Basic parameter settings in F3

3.5.3 實(shí)驗(yàn)結(jié)果

第一輪性能對(duì)比實(shí)驗(yàn)，選取了“最佳適應(yīng)度值變化趨勢(shì)”作為對(duì)比指標(biāo)，該指標(biāo)可以很好的體現(xiàn)出算法之間收斂速度與準(zhǔn)確度的差異，實(shí)驗(yàn)結(jié)果如圖2～圖4 所示。

圖2 F1—最佳適應(yīng)度值對(duì)比Fig.2 F1－comparison of optimal fitness values

圖3 F2—最佳適應(yīng)度值對(duì)比Fig.3 F2－comparison of optimal fitness values

圖4 F3—最佳適應(yīng)度值對(duì)比Fig.4 F3－comparison of optimal fitness values

其次，為了對(duì)比不同算法下種群之間搜索能力與全局尋優(yōu)能力的差異，選取了“平均適應(yīng)度值變化趨勢(shì)”作為第二個(gè)對(duì)比指標(biāo)，實(shí)驗(yàn)結(jié)果如圖5～圖7 所示。

圖5 F1—平均適應(yīng)度值對(duì)比Fig.5 F1－comparison of average fitness values

圖6 F2—平均適應(yīng)度值對(duì)比Fig.6 F2－comparison of average fitness values

圖7 F3—平均適應(yīng)度值對(duì)比Fig.7 F3－comparison of average fitness values

為避免單次實(shí)驗(yàn)因偶然性導(dǎo)致的實(shí)驗(yàn)誤差，設(shè)置30 次的重復(fù)實(shí)驗(yàn)進(jìn)一步驗(yàn)證ESCS 算法的性能。

本次實(shí)驗(yàn)選取最優(yōu)測(cè)試值（optimum results）和最差測(cè)試值（worst results）為對(duì)比指標(biāo)，實(shí)驗(yàn)結(jié)果見表8。

表8 仿真對(duì)比實(shí)驗(yàn)結(jié)果Tab.8 Experimental results of simulation

3.5.4 實(shí)驗(yàn)結(jié)果分析

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

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

結(jié)合以上分析，表明ESCS在收斂速度、尋優(yōu)解的精度以及全局搜索能力等方面的綜合表現(xiàn)優(yōu)于其它參與實(shí)驗(yàn)的改進(jìn)算法，驗(yàn)證了ESCS 的高效性與可行性。

4 結(jié)束語(yǔ)

針對(duì)傳統(tǒng)的布谷鳥搜索算法存在過(guò)早成熟、尋優(yōu)解的精確度與準(zhǔn)確度差，以及收斂速度慢等問題，本文提出了一種基于精英策略改進(jìn)的自適應(yīng)布谷鳥搜索算法。ESCS在參數(shù)初始化階段，將布谷鳥分為精英布谷鳥與普通布谷鳥，兩種布谷鳥在被寄主鳥發(fā)現(xiàn)時(shí)會(huì)執(zhí)行不同的飛行策略。精英策略可以避免算法陷入局部最優(yōu)導(dǎo)致過(guò)早成熟。此外，再對(duì)布谷鳥被發(fā)現(xiàn)概率進(jìn)行自適應(yīng)改進(jìn)，加快了算法后期的收斂速度。最后設(shè)置6 種標(biāo)準(zhǔn)測(cè)試函數(shù)與縱向?qū)Ρ葘?shí)驗(yàn)，進(jìn)一步驗(yàn)證ESCS 的綜合性能表現(xiàn)，仿真結(jié)果表明ESCS 具有較好的魯棒性與尋優(yōu)性能。