多策略調(diào)和的布谷鳥搜索算法

彭 虎，李源漢，鄧長(zhǎng)壽，吳志健

（1.九江學(xué)院 計(jì)算機(jī)與大數(shù)據(jù)科學(xué)學(xué)院，江西 九江 332005；2.武漢大學(xué) 計(jì)算機(jī)學(xué)院，武漢 430072）

0 概述

群智能算法是模擬自然界生物群體行為而設(shè)計(jì)的算法，能有效解決現(xiàn)實(shí)世界中的復(fù)雜問題。隨著學(xué)者們對(duì)群智能算法研究的深入，在其基礎(chǔ)上提出了蟻群優(yōu)化（Ant Colony Optimization，ACO）［1］、粒子群優(yōu)化（Particle Swarm Optimization，PSO）［2］、人工蜂群（Artificial Bee Colony，ABC）［3］、螢火蟲算法（Firefly Algorithm，F(xiàn)A）［4］、布谷鳥搜索（Cuckoo Search，CS）［5］等多種優(yōu)化算法。這些算法不僅能夠解決復(fù)雜函數(shù)優(yōu)化問題，而且適用于控制工程［6］、生產(chǎn)調(diào)度［7］、圖像處理［8］等領(lǐng)域。

CS 算法是受布谷鳥的寄生育雛行為啟發(fā)而提出的，與其他群智能算法相比，一方面具有參數(shù)少、運(yùn)算簡(jiǎn)單、尋優(yōu)能力強(qiáng)等優(yōu)點(diǎn)，另一方面存在勘探能力與開采能力不平衡以及容易陷入局部最優(yōu)解的缺陷。近年來，國(guó)內(nèi)外學(xué)者們提出了很多新的CS 改進(jìn)算法。RAKHSHANI 等［9］提出捕捉和漂移布谷鳥搜索算法（SDCS），利用2 種學(xué)習(xí)模式，一種傾向于增強(qiáng)全局搜索，另一種傾向于增強(qiáng)局部搜索，同時(shí)引入新的交叉和變異搜索算子，提高SDCS 的搜索能力。PENG 等［10］提出一種新的高斯布谷鳥搜索算法（GBCS），以隨機(jī)的方式選擇Lévy 分布和高斯分布，防止算法的過早收斂以及增強(qiáng)算法的搜索能力。PENG 等［11］還提出一種多策略串行布谷鳥搜索算法（MSSCS），通過對(duì)布谷鳥尋巢行為、驅(qū)逐行為和乞求行為的觀察，設(shè)計(jì)3 種新的學(xué)習(xí)策略以及一種多策略串行框架來提高算法的性能。LI等［12］提出一種自適應(yīng)參數(shù)方法的改進(jìn)布谷鳥算法（SACS），將2 種新的變異規(guī)則通過線性遞減概率規(guī)則進(jìn)行組合以平衡算法的勘探與開發(fā)，再根據(jù)兩個(gè)新參數(shù)的相對(duì)成功率，引入自適應(yīng)參數(shù)作為均勻隨機(jī)值，以增強(qiáng)種群的多樣性。劉景森等［13］提出一種具有動(dòng)態(tài)步長(zhǎng)和發(fā)現(xiàn)概率的布谷鳥搜索算法（DCS），通過引入步長(zhǎng)調(diào)整因子動(dòng)態(tài)約束Lévy 飛行移動(dòng)步長(zhǎng)，還使用具有均勻分布和F 分布特性的隨機(jī)慣性權(quán)重增強(qiáng)算法的多樣性。周詩(shī)源等［14］提出一種基于布谷鳥搜索優(yōu)化算法的多文檔摘要方法，將經(jīng)過數(shù)據(jù)預(yù)處理后的多文檔句子信息作為CS 算法的輸入，再基于多目標(biāo)函數(shù)生成包含原始文檔重要信息的句子以組成最終的摘要。向庭立等［15］提出一種基于布谷鳥搜索的覆蓋優(yōu)化策略，將混合傳感器節(jié)點(diǎn)隨機(jī)部署在目標(biāo)區(qū)域，利用CS 算法初步確定移動(dòng)傳感器節(jié)點(diǎn)的候選目標(biāo)位置，通過位置優(yōu)化方案得到移動(dòng)傳感器節(jié)點(diǎn)的最佳目標(biāo)位置以完成覆蓋優(yōu)化。AGARWAL 等［16］提出一種基于布谷鳥搜索算法的任務(wù)調(diào)度方法，有助于在可用的虛擬機(jī)之間有效地分配任務(wù)，并保持總體響應(yīng)時(shí)間最小。

通過分析CS 算法Lévy 飛行和隨機(jī)游走的特性，發(fā)現(xiàn)在迭代過程中CS 算法存在勘探能力與開采能力不平衡以及易陷入局部最優(yōu)的缺陷。為解決此問題，本文提出一種多策略調(diào)和的布谷鳥搜索（Multi-Strategy Reconciled Cuckoo Search，MSRCS）算法。該算法設(shè)計(jì)基于自適應(yīng)步長(zhǎng)和改進(jìn)解更新方法的調(diào)和策略，并利用線性遞減概率規(guī)則對(duì)調(diào)和策略進(jìn)行選擇，實(shí)現(xiàn)多策略調(diào)和以平衡算法的勘探能力與開采能力，并在不同迭代過程中調(diào)節(jié)全局搜索和局部搜索。

1 布谷鳥搜索算法

2009 年，YANG 等［5］受布谷鳥的孵化寄生行為啟發(fā)，提出布谷鳥搜索算法。在自然界中，布谷鳥尋找適合產(chǎn)卵的巢穴的行為是隨機(jī)的。因此，為了模擬布谷鳥找到巢穴的方式，設(shè)置以下簡(jiǎn)化規(guī)則：

1）每只布谷鳥一次只下一顆蛋，并隨機(jī)選擇一個(gè)鳥巢下蛋。

2）在隨機(jī)選擇的鳥巢中，最好的鳥巢將被保存到下一代。

3）鳥巢的數(shù)量是恒定的。鳥巢的主人拋棄外來蛋的概率為pa∈（0，1）。

CS 算法中每一個(gè)鳥巢代表問題的一個(gè)解，攜帶著鳥蛋的布谷鳥會(huì)通過Lévy 飛行隨機(jī)地移動(dòng)到一個(gè)寄主鳥的巢中產(chǎn)卵。通過評(píng)價(jià)函數(shù)，對(duì)替換后的巢進(jìn)行評(píng)價(jià)。因此，許多更好的解將被發(fā)現(xiàn)和更新。同時(shí)布谷鳥的蛋如果被寄主鳥發(fā)現(xiàn)，則寄主鳥拋棄布谷鳥的蛋以及放棄自己的蛋和巢，并再建新巢。

原始的CS算法主要包括Lévy飛行和隨機(jī)游走2種重要策略。每一代布谷鳥都通過Lévy 飛行尋找更好的巢來產(chǎn)卵。因此，布谷鳥的移動(dòng)由Lévy飛行主導(dǎo)，即：

其中：μ和ν是服從均勻分布的隨機(jī)數(shù)；β為1.5。φ的表示方法如下：

布谷鳥通過式（1）的Lévy 飛行尋找到新的寄主鳥巢并將蛋放置于巢后，若寄主鳥發(fā)現(xiàn)布谷鳥的蛋，則會(huì)按概率pa拋棄部分巢，并使用隨機(jī)游走策略新建與被拋棄巢數(shù)量相等的新巢，公式如下：

CS 算法流程如下：

2 多策略調(diào)和的CS 算法

2.1 自適應(yīng)步長(zhǎng)

自適應(yīng)步長(zhǎng)是提高CS 搜索效率的有效方法。張永韡等［17］根據(jù)布谷鳥每次迭代成功更新解的改善率調(diào)整步長(zhǎng)大小，提出動(dòng)態(tài)適應(yīng)布谷鳥搜索算法（DACS）。若改善率較大，說明搜索空間相對(duì)單調(diào)，算法找到更優(yōu)解的概率較高，故適當(dāng)增大步長(zhǎng)增加種群的探索性和搜索范圍；若改善率較小，說明搜索空間相對(duì)復(fù)雜，找到更優(yōu)解的概率較低，以適當(dāng)減小步長(zhǎng)來提高算法局部開發(fā)性。

Lévy 飛行是原始CS 算法中一種重要的隨機(jī)搜索策略，以隨機(jī)的小步長(zhǎng)或偶然的大步長(zhǎng)控制布谷鳥移動(dòng)。在原始CS 算法迭代過程的前期，Lévy 飛行搜索范圍較小，效益較低，迭代次數(shù)增加從而導(dǎo)致算法收斂性較差。在迭代過程的中后期，算法逐漸靠近最優(yōu)解，全局搜索減弱并逐漸轉(zhuǎn)至局部搜索，易使算法陷入局部極值。

基于以上分析，本文提出一種新的自適應(yīng)步長(zhǎng)策略以提高CS 算法的搜索效率，即自適應(yīng)步長(zhǎng)隨迭代次數(shù)的增加而減小。在迭代前期，MSRCS 的大步長(zhǎng)擴(kuò)大了其搜索范圍，提高算法的全局搜索能力，有利于算法更快找到更優(yōu)解，加快收斂速度；在迭代后期，小步長(zhǎng)有利于算法的局部搜索。步長(zhǎng)的規(guī)律變化對(duì)布谷鳥的搜索起引導(dǎo)作用，即在整體上從全局搜索逐漸過渡到局部搜索。該策略主要是由線性遞減的自適應(yīng)步長(zhǎng)控制因子α0決定，公式如下：

其中：η是控制步長(zhǎng)變化范圍的調(diào)和因子，并決定步長(zhǎng)的初值。根據(jù)余弦函數(shù)在范圍內(nèi)呈遞減變化的特性，將步長(zhǎng)與迭代次數(shù)進(jìn)行關(guān)聯(lián)，使步長(zhǎng)也隨著迭代次數(shù)的增加而減小。自適應(yīng)α0為近似一條直線的曲線，為整個(gè)搜索過程提供了輕微的緩沖作用，α0的取值范圍為［0.00，0.25］。

2.2 解更新方法

由于原始CS 算法具有參數(shù)少、操作簡(jiǎn)單的特點(diǎn)，因此單策略CS 算法的可操作性有限，布谷鳥的行動(dòng)相似，且對(duì)于求解復(fù)雜的高維優(yōu)化問題，若一只布谷鳥陷入局部極值，則無法靠鄰域內(nèi)相同情況的其他布谷鳥跳出局部極值。GAO 等［18］為了解決這些問題，提出一種多策略自適應(yīng)布谷鳥算法（MSACS），采用自適應(yīng)參數(shù)控制5 種新的搜索策略進(jìn)行相互協(xié)作，以提高算法的搜索效率。由此證明多策略CS 算法能夠針對(duì)迭代過程的不同階段采用不同策略，相比靈活性較差的單策略，不僅能增加算法的多樣性，還能增強(qiáng)算法應(yīng)對(duì)不同場(chǎng)景的搜索能力。LIU 等［19］對(duì)BSO 算法的多策略改進(jìn)也取得了顯著成效。因此，本文提出CS-current、CS-best和CS-rand 3 種不同的解更新方法。

CS-current 解更新方法以布谷鳥自身當(dāng)前位置為中心，在其鄰域內(nèi)搜索潛在更優(yōu)解，并加入Xtbest控制尋優(yōu)方向，防止布谷鳥在其他方向上進(jìn)行無效的搜索和評(píng)價(jià)次數(shù)的浪費(fèi)。如圖1 所示，黑點(diǎn)表示布谷鳥個(gè)體，虛線表示布谷鳥的鄰域范圍，此時(shí)布谷鳥個(gè)體分布較分散，每個(gè)個(gè)體鄰域內(nèi)都可能存在更優(yōu)解，布谷鳥以自身為學(xué)習(xí)目標(biāo)，嘗試在自身鄰域內(nèi)搜索更優(yōu)解，增強(qiáng)局部搜索能力有助于尋找解周圍的潛在更優(yōu)解。CS-current 解更新方法的表達(dá)式如下：

圖1 CS-current 解更新方法示意圖Fig.1 Schematic diagram of the solution-update method of CS-current

CS-best 解更新方法以當(dāng)前最優(yōu)解為引導(dǎo)，使當(dāng)前布谷鳥向著當(dāng)前最優(yōu)解的方向移動(dòng)。彭虎等［20］在ELDDE 算法中設(shè)計(jì)的精英區(qū)域?qū)W習(xí)策略，通過對(duì)精英個(gè)體的學(xué)習(xí)顯著提高了算法性能。如圖2 所示，灰點(diǎn)表示當(dāng)代最優(yōu)解虛線箭頭表示布谷鳥的移動(dòng)方向，此時(shí)布谷鳥種群密度較大，且大部分布谷鳥個(gè)體集中在周圍，但仍有少部分分散在密集種群外，在密集種群外的布谷鳥以為學(xué)習(xí)目標(biāo)，向其所在種群密度大的方向移動(dòng)，有利于加快算法的收斂速度。CS-best 解更新方法的表達(dá)式如下：

圖2 CS-best 解更新方法示意圖Fig.2 Schematic diagram of the solution-update method of CS-best

CS-rand 解更新方法通過學(xué)習(xí)兩個(gè)隨機(jī)個(gè)體各維度的不同信息，生成一個(gè)新的隨機(jī)個(gè)體。如圖3所示，白點(diǎn)表示隨機(jī)選取的兩個(gè)布谷鳥個(gè)體，灰點(diǎn)表示以兩個(gè)隨機(jī)個(gè)體為學(xué)習(xí)目標(biāo)產(chǎn)生的新個(gè)體，新個(gè)體在密集種群范圍之外，且有可能優(yōu)于當(dāng)代最優(yōu)解，有助于算法跳出局部極值以尋找到更優(yōu)解。CS-rand 解更新方法的表達(dá)式如下：

圖3 CS-rand 解更新方法示意圖Fig.3 Schematic diagram of the solution-update method of CS-rand

基于以上分析發(fā)現(xiàn)，3 種新的解更新方法能夠從多方面尋找算法更優(yōu)解，根據(jù)算法在迭代過程中的缺陷使用不同的解更新方法在搜索空間中進(jìn)行尋優(yōu)，不僅能在迭代過程中加快收斂速度，而且有效克服算法收斂停滯，提高了算法跳出局部極值的能力。

2.3 多策略調(diào)和

為適應(yīng)算法在不同階段的需求，使策略的選擇更加有效，對(duì)自適應(yīng)步長(zhǎng)和3 種改進(jìn)的解更新方法組成的調(diào)和策略進(jìn)行選擇，以調(diào)和算法的勘探與開采。

在SACS［8］算法中的線性遞減概率規(guī)則(1-t/G)利用一個(gè)隨機(jī)值與該規(guī)則產(chǎn)生的調(diào)和值進(jìn)行比較，使算法能夠在不同階段對(duì)策略進(jìn)行自適應(yīng)選擇。相比于原始CS 算法，該規(guī)則使用動(dòng)態(tài)變化的值有效地從前期向后期自適應(yīng)過渡。在MSRCS 算法中，使用了線性遞減規(guī)則作為多策略調(diào)和的框架，對(duì)調(diào)和策略進(jìn)行概率選擇。在迭代前期，調(diào)和值較大，選擇調(diào)和策略1 的概率也更大，但隨著迭代次數(shù)的增加，調(diào)和值逐漸減小，則概率逐漸向調(diào)和策略2 偏移。當(dāng)t=G/2 時(shí)，選擇兩個(gè)調(diào)和策略的概率相等。之后選擇調(diào)和策略2 的概率逐漸增加。

調(diào)和策略1 將自適應(yīng)步長(zhǎng)和CS-current 結(jié)合，并設(shè)置調(diào)和因子p1=0.8 來調(diào)節(jié)選擇概率。

調(diào)和策略1 的流程如下：

1.If r

2.使用自適應(yīng)Lévy 飛行更新個(gè)體；

3.Else

4.使用CS-current 方法更新個(gè)體；

在迭代前期，算法的最優(yōu)解不明顯，且解較為分散，適度使用CS-current 有利于算法更快地找到自身鄰域內(nèi)的潛在最優(yōu)解，在迭代前期對(duì)算法的勘探與開采起調(diào)和作用。

調(diào)和策略2 將自適應(yīng)步長(zhǎng)和CS-best、CS-rand 結(jié)合。自適應(yīng)步長(zhǎng)和解更新方法的概率調(diào)和因子p2=0.5，對(duì)2 種解更新方法的概率調(diào)和因子為p1。

調(diào)和策略2 的流程如下：

1.If r

2.使用自適應(yīng)Lévy 飛行更新個(gè)體；

3.Else

4.If r

5.使用CS-best 方法更新個(gè)體；

6.Else

7.使用CS-rand 方法更新個(gè)體；

8.End

9.End

在迭代中后期，自適應(yīng)步長(zhǎng)逐漸減小，全局搜索逐漸過渡至局部搜索，解向當(dāng)前最優(yōu)解逐步收斂。若目標(biāo)函數(shù)值與全局最優(yōu)解近似，自適應(yīng)的小步長(zhǎng)或者CS-best 則有利于向最優(yōu)解收斂。若目標(biāo)函數(shù)值與全局最優(yōu)解相差較大，或陷入局部極值，則基于隨機(jī)思想，算法有小概率使用CS-rand 嘗試尋找更優(yōu)解或嘗試跳出局部極值，且適當(dāng)增大選擇CS-best 和CS-rand 的概率，在迭代后期使算法的收斂性、多樣性和解的精度得以提升。

調(diào)和策略的選擇建立在線性遞減概率規(guī)則的框架下，根據(jù)迭代次數(shù)動(dòng)態(tài)更新選擇概率，達(dá)到調(diào)和策略之間從前期向后期的自適應(yīng)過渡，以及調(diào)和算法的勘探和開采能力。

MSRCS 算法的流程如下：

1.初始化個(gè)體Xi(i=1，2，…，n)，計(jì)算其適應(yīng)度值；

2.While t

3.If r<(1 ?t/G)

4.使用調(diào)和策略1 更新個(gè)體Xi；

5.Else

6.使用調(diào)和策略2 更新個(gè)體Xi；

7.End if

9.根據(jù)拋棄概率pa和隨機(jī)游走式（5）更新個(gè)體；

11.End While

2.4 算法復(fù)雜度

為證明MSRCS 不會(huì)增加CS 的時(shí)間復(fù)雜度，對(duì)CS 和MSRCS 進(jìn)行復(fù)雜度分析。假設(shè)在CS 流程中，初始化階段生成解的時(shí)間為t1，計(jì)算d維問題的目標(biāo)函數(shù)時(shí)間為f(d)，種群規(guī)模為n，則整個(gè)初始化階段的時(shí)間復(fù)雜度為O(n(t1d+f(d)))≈O(d+f(d))。迭代階段采用式（1）計(jì)算Lévy 飛行生成新解的時(shí)間為t2，比較產(chǎn)生的新解與舊解的時(shí)間為t3，新解替換舊解的時(shí)間為t4，且記錄該過程最優(yōu)解的時(shí)間為t5，則Lévy飛行階段的時(shí)間復(fù)雜度為O(n(t2d+f(d)+t3+t4d+t5d))≈O(d+f(d))。采用式（5）計(jì)算隨機(jī)游走生成新解的時(shí)間為t6，比較新解與舊解，替換舊解及記錄最優(yōu)解的時(shí)間與Lévy 飛行階段相同，隨機(jī)游走階段的時(shí)間復(fù)雜度為O(n(t2d+f(d)+t3+t4d+t5d))≈O(d+f(d))。最后比較當(dāng)代最優(yōu)解與當(dāng)前最優(yōu)解的時(shí)間為t7，替換當(dāng)前最優(yōu)解的時(shí)間為t8，更新當(dāng)前最優(yōu)解的時(shí)間復(fù)雜度為O(n(t7+t8d))≈O(d)。假設(shè)最大迭代次數(shù)為G，CS 算法總時(shí)間復(fù)雜度為T(n)=G?(3O(n(d+f(d)))+O(d))≈O(G?n(d+f(d)))。

MSRCS 僅在Lévy 飛行階段進(jìn)行改進(jìn)，其他部分與CS 相同。假設(shè)調(diào)和策略1 產(chǎn)生新解的時(shí)間為t9，調(diào)和策略2 產(chǎn)生新解的時(shí)間為t10，該階段的時(shí)間復(fù)雜度為O(n(t9d+f(d)+t3+t4d+t5d)) 或O(n(t10d+f(d)+t3+t4d+t5d))。MSRCS總的時(shí)間復(fù)雜 度為T(n)=O(G?n(t1d+f(d)))+O(G?pa?n(t9d+f(d)+t3+t4d+t5d))+O(G?(1-pa)?n(t10d+f(d)+t3+t4d+t5d)+t8d))≈O(G?n(d+f(d)))。

由此可見，在各參數(shù)相同的情況下，MSRCS 與CS 的算法時(shí)間復(fù)雜度一致。同時(shí)MSRCS 未使用額外的存儲(chǔ)空間存放數(shù)據(jù)，空間復(fù)雜度也相同。因此，MSRCS 的改進(jìn)并未增加算法的復(fù)雜度。

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

3.1 實(shí)驗(yàn)設(shè)置

為了驗(yàn)證MSRCS 的性能，在廣泛使用的CEC2013［21］測(cè)試集上進(jìn)行實(shí)驗(yàn)。CEC2013 包含28個(gè)測(cè)試函數(shù)，其中f1～f5為單峰函數(shù)，f6～f20為多峰函數(shù)，f21～f28為組合函數(shù)，函數(shù)的求解約束范圍為[-100,100]d。為了探究MSRCS 的準(zhǔn)確性和收斂性，將其與原始CS 及其7 種改進(jìn)算法進(jìn)行對(duì)比分析，這7 種CS 改進(jìn)算法分別為ACS［22］、DACS［17］、SACS［8］、GBCS［10］、GCS［23］、NACS［24］和SDCS［9］，表1 給出了各算法的具體參數(shù)設(shè)置，其中CS、ACS、DACS、SACS、GBCS、GCS、NACS 和SDCS 參數(shù)遵循相應(yīng)文獻(xiàn)中的設(shè)置。通過顯著性水平為0.05 的Wilcoxon 秩和檢驗(yàn)與Friedman 檢驗(yàn)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行統(tǒng)計(jì)分析。Wilcoxon 秩和檢驗(yàn)通過將兩組的值排秩次，比較兩組的秩次總和來判斷是否存在統(tǒng)計(jì)學(xué)差異。Friedman 檢驗(yàn)利用秩分析多組相關(guān)樣本之間是否存在統(tǒng)計(jì)學(xué)差異。MSRCS 及其他比較算法在Matlab R2016a 上編程實(shí)現(xiàn)。MSRCS 的Matlab 代碼可從https：//whuph.github.io/index.html 下載。

表1 算法參數(shù)設(shè)置Table 1 Parameter setting of algorithms

為了保證實(shí)驗(yàn)的公平性，設(shè)置種群數(shù)量n為20、問題維度d為30、發(fā)現(xiàn)概率pa為0.25、總評(píng)價(jià)次數(shù)Fmax為1E6、最大迭代次數(shù)Gmax為25 000。步長(zhǎng)控制因子通過對(duì)比不同η值的實(shí)驗(yàn)結(jié)果，選出其中結(jié)果最好的η值作為最終的η值。每個(gè)測(cè)試函數(shù)在相同環(huán)境下運(yùn)行30次，并記錄下其平均誤差值與標(biāo)準(zhǔn)誤差值。

3.2 與原始CS 及其改進(jìn)算法的比較

將MSRCS 與原始CS 以及7 種CS 改進(jìn)算法進(jìn)行性能對(duì)比。表2 和表3 給出了d=30 時(shí)MSRCS 與其他8 種CS 算法在CEC2013 測(cè)試函數(shù)上的實(shí)驗(yàn)結(jié)果，其中，加粗的字體表示最好結(jié)果，Avg 和Std 分別表示平均誤差值和標(biāo)準(zhǔn)誤差值，rank 表示Friedman檢驗(yàn)的平均排名結(jié)果，Wilcoxon 秩和檢驗(yàn)結(jié)果中的“+”表示對(duì)比算法結(jié)果優(yōu)于MSRCS，“?”表示對(duì)比算法結(jié)果差于MSRCS，“≈”表示對(duì)比算法和MSRCS 結(jié)果相差不大。

表2 d=30 時(shí)CS、ACS、DACS、SACS、MSRCS 算法的CEC2013 測(cè)試函數(shù)實(shí)驗(yàn)結(jié)果Table 2 Experimental results of CEC2013 test functions for CS，ACS，DACS，SACS，MSRCS algorithms when d=30

續(xù)表

表3 d=30 時(shí)GBCS、GCS、NACS、SDCS、MSRCS 算法的CEC2013 測(cè)試函數(shù)實(shí)驗(yàn)結(jié)果Table 3 Experimental results of CEC2013 test functions of GBCS，GCS，NACS，SDCS，MSRCS algorithms when d=30

從表2可以看出，MSRCS 在f4、f7、f8、f9、f12、f15、f16、f18、f20、f23、f24、f25上有較 好的結(jié)果。在單峰函數(shù)中，MSRCS 在f4上效果明顯優(yōu)于其他算法，在f2上僅劣于DACS，在f1、f3上各算法的性能趨于一致。在多峰函數(shù)f7、f8、f9、f12、f15、f16、f18、f20上的結(jié)果優(yōu)于其他算法，在f19上僅劣于SACS。在組合函數(shù)f23、f24、f25上MSRCS 的結(jié)果較好。通過表2 和表3 底部的Friedman 檢驗(yàn)與Wilcoxon 秩和檢驗(yàn)的結(jié)果可以看出，MSRCS 在28 個(gè)測(cè)試函數(shù)上的平均排名為3.321 4，排名第一，相比于GBCS 有12 個(gè)函數(shù)更優(yōu)，相比于其他算法至少有14 個(gè)函數(shù)更優(yōu)?？梢?，MSRCS 在處理不同類型的問題時(shí)均具有更好的穩(wěn)定性和收斂性。

為了更直觀地顯示表2 和表3 結(jié)果的排名情況，整理總結(jié)每個(gè)函數(shù)的平均誤差值（最小化問題）排名，繪制了基于排名統(tǒng)計(jì)情況的堆疊直方圖。如圖4所示，每個(gè)排名用一個(gè)彩色塊表示，從第一到第五分別為棕色、粉色、橘色、藍(lán)色和綠色，含棕色塊越多的算法性能越強(qiáng)，反之綠色塊越多算法性能越差，彩色效果見《計(jì)算機(jī)工程》官網(wǎng)HTML 版。圖4（a）表示CS、ACS、DACS、SACS 和MSRCS的排名情況，圖4（b）表示GBCS、GCS、NACS、SDCS 和MSRCS 的排名情況。由圖4 可知，排名第一的棕色塊在MSRCS 中的比例最多，說明MSRCS 與其他算法相比表現(xiàn)最佳。

圖4 在CEC2013 測(cè)試函數(shù)上各算法的排名堆疊直方圖Fig.4 Stacked histograms of the ranks of the algorithms on CEC2013 test function

為進(jìn)一步說明MSRCS 的收斂能力和尋優(yōu)精度，選取原始CS 以及4 種具有代表性的CS 改進(jìn)算法，分別從CEC2013 測(cè)試集的單峰函數(shù)、多峰函數(shù)和組合函數(shù)中挑選具有代表性的f5、f9、f13、f20、f24、f25函數(shù)，其中f5為單峰函數(shù)，f9、f13、f20為多峰函數(shù)，f24、f25為組合函數(shù)，并在圖5 中繪制了其收斂曲線。從圖5（a）中可以看出，MSRCS 在單峰函數(shù)f5的整個(gè)迭代過程中收斂速度相比于其他算法是最快的，在18 000 次迭代時(shí)已經(jīng)收斂到了最優(yōu)值。這證明了MSRCS 中的CS-best 解更新方法在單峰函數(shù)問題上有利于算法更快地 收斂于 最優(yōu)解。在f13、f24、f25函數(shù)中，CS、ACS、DACS、SACS、GCS 都存在著陷入局部極值從而停止收斂的情況，在其他算法都陷入局部極值時(shí)，MSRCS 跳出局部最優(yōu)達(dá)到了更高的精度值，說明MSRCS 算法中的CS-rand 解更新方法嘗試跳出局部極值并尋找更優(yōu)解。對(duì)于f9、f20函數(shù)，MSRCS 優(yōu)勢(shì)較為明顯，由于其根據(jù)概率選擇不同調(diào)和策略來平衡勘探與開采，因此收斂曲線并非階段性斷層而是呈逐步尋優(yōu)狀，以靠近全局最優(yōu)解。根據(jù)上述分析，MSRCS 的調(diào)和策略在各種類型的測(cè)試函數(shù)上均具有較好的收斂速度、較強(qiáng)的尋優(yōu)能力以及跳出局部極值的能力。

圖5 CS、ACS、DACS、SACS、GCS、MSRCS 算法在部分測(cè)試函數(shù)上的收斂曲線Fig.5 Convergence curves of CS，ACS，DACS，SACS，GCS，MSRCS algorithms on the sectional test functions

3.3 多策略調(diào)和的有效性分析

為了驗(yàn)證多策略調(diào)和的有效性，本文提出了MSRCS-1、MSRCS-2、MSRCS-3 這3 種MSRCS 改進(jìn)算法，分別為只使用自適應(yīng)步長(zhǎng)、不使用線性遞減規(guī)則（將迭代過程分為前期和后期）以及單獨(dú)使用調(diào)和策略公式，測(cè)試結(jié)果如表4 所示，實(shí)驗(yàn)參數(shù)設(shè)置與3.1 節(jié)一致。從表4可以看出：在Wilcoxon檢驗(yàn)結(jié)果中，由于MSRCS分別有12、14、19 個(gè)函數(shù)比MSRCS-1、MSRCS-2 和MSRCS-3 更好，因此MSRCS 中的調(diào)和策略應(yīng)用在測(cè)試函數(shù)上的效果相比于其他單獨(dú)使用策略的改進(jìn)算法更好；在Friedman 檢驗(yàn)的平均排名（rank）中，數(shù)據(jù)顯示MSRCS為1.982 1，MSRCS-1為2.303 6，MSRCS-2 為2.678 6，MSRCS-3 為3.035 7。可見，在多策略調(diào)和的作用下MSRCS 效果最佳。

表4 d=30 時(shí)MSRCS 算法在CEC2013 測(cè)試函數(shù)上單獨(dú)使用不同策略的實(shí)驗(yàn)結(jié)果Table 4 Experimental results of MSRCS algorithm by using different strategy on the CEC2013 test functions when d=30

在此基礎(chǔ)上，進(jìn)一步對(duì)多策略調(diào)和MSRCS 的收斂性及穩(wěn)定性進(jìn)行驗(yàn)證。圖6 給出了MSRCS 和3 種改進(jìn)算法在函數(shù)f11、f12、f13、f14上的收斂曲線圖。由圖6 可知，含多策略調(diào)和的MSRCS 在解的精度方面要優(yōu)于其他改進(jìn)算法，且在其他改進(jìn)算法都陷入局部極值時(shí)能夠達(dá)到更高的精度，由此證明了MSRCS 的多策略調(diào)和跳出局部極值和持續(xù)尋優(yōu)的能力較好。此外，還證明了多策略調(diào)和相比于其他改進(jìn)算法的單策略更加有效。

圖6 MSRCS-1、MSRCS-2、MSRCS-3、MSRCS 算法在f11、f12、f13、f14函數(shù)上的收斂曲線Fig.6 Convergence curves of MSRCS-1，MSRCS-2，MSRCS-3，MSRCS algorithms on f11，f12，f13，f14 functions

3.4 與群智能優(yōu)化算法的比較

差分進(jìn)化（Differential Evolution，DE）算法［25］、人工蜂群（ABC）算法［3］和螢火蟲算法（FA）［4］是被廣泛研究與使用的群智能優(yōu)化算法。為進(jìn)一步驗(yàn)證MSRCS的性能，選取DE、ABC 和FA 的改進(jìn)算法進(jìn)行比較，分別為CUDE［26］、MEABC［27］和NSRaFA［28］。

鑒于實(shí)驗(yàn)的公平性，對(duì)這些算法設(shè)置種群數(shù)量n為20、問題維度d為30 及評(píng)價(jià)次數(shù)Fmax為1E6，且每個(gè)測(cè)試函數(shù)獨(dú)立運(yùn)行30 次，CUDE、MEABC 和NSRaFA 參數(shù)遵循相應(yīng)文獻(xiàn)中的設(shè)置，MSRCS 參數(shù)設(shè)置與表1 一致。CEC2013 測(cè)試集的實(shí)驗(yàn)結(jié)果如表5 所示，其中加粗的字體表示最好結(jié)果。從表5 可以看出：MSRCS 有11 個(gè)函數(shù)優(yōu)于其他算法；對(duì)于單峰函數(shù)f2、f3、f4，CUDE相比于其他3 種算法具有更好的結(jié)果，MSRCS 在f1上找 到了最優(yōu)值；在多峰函數(shù)f7、f8、f10、f12、f13、f16、f18上MSRCS 有相對(duì)優(yōu)勢(shì)，說明其在解決多峰函數(shù)問題時(shí)有著比其他算法更好的效果；MEABC 在組合函數(shù)f21、f22、f26、f28上的結(jié)果較好；在Wilcoxon 值和檢驗(yàn)結(jié)果中，MSRCS 相比于其他3 種改進(jìn)算法，至少有12 個(gè)函數(shù)有更優(yōu)結(jié)果?？梢?，MSRCS 在解決單峰和多峰問題時(shí)相對(duì)于其他算法具有更強(qiáng)的尋優(yōu)能力。

表5 d=30 時(shí)CUDE、MEABC、NSRaFA、MSRCS 算法在CEC2013 測(cè)試函數(shù)上的實(shí)驗(yàn)結(jié)果Table 5 Experimental results of CUDE，MEABC，NSRaFA，MSRCS algorithms on the CEC2013 test functions when d=30

續(xù)表

圖7 給出了CUDE、MEABC、NSRaFA 和MSRCS在f1、f5、f6、f7、f10、f28函數(shù)上的收斂曲線圖，其中包含單峰函數(shù)、多峰函數(shù)以及組合函數(shù)。

圖7 CUDE、MEABC、NSRaFA、MSRCS 算法在f1、f5、f6、f7、f10、f28函數(shù)上的收斂曲線Fig.7 Convergence curves of CUDE，MEABC，NSRaFA，MSRCS algorithms on f1，f5，f6，f7，f10，f28 functions

從圖7 可以看出，在f1收斂圖中，MSRCS 前期尋找到的最優(yōu)解與CUDE 相差不大，但是在后期MSRCS 尋找到了比CUDE 更優(yōu)的最優(yōu)解，由此可見MSRCS 中的CS-rand 解更新方法跳出局部極值到達(dá)了更高的精度。MSRCS 除了在解的精度方面較其他改進(jìn)算法更優(yōu)外，在整個(gè)迭代過程中的收斂速度也相比于其他算法更快。綜上所述，MSRCS 相比于其他算法有著相對(duì)更好的收斂能力、尋優(yōu)能力以及跳出局部極值的能力。

3.5 自適應(yīng)參數(shù)分析

布谷鳥步長(zhǎng)控制因子的大小決定其搜索范圍。步長(zhǎng)控制因子越大，搜索范圍越廣，算法的全局搜索能力和種群多樣性增強(qiáng)；反之，步長(zhǎng)越小，算法的局部搜索能力和收斂性增強(qiáng)。在改進(jìn)的自適應(yīng)步長(zhǎng)式（6）中，調(diào)和因子η控制布谷鳥的搜索范圍大小，因此η的大小決定步長(zhǎng)的變化范圍。

為了測(cè)試自適應(yīng)步長(zhǎng)對(duì)MSRCS 性能的提升效果，本文對(duì)參數(shù)η進(jìn)行基于CEC2013 測(cè)試集的Friedman 檢驗(yàn)并篩選出效果最好的η值。實(shí)驗(yàn)選擇無自適應(yīng)、η=0.3、η=0.5 和η=0.7 這4 種情況，得 到MSRCS 在CEC2013 測(cè)試集的28 個(gè)函數(shù)中的平均排名結(jié)果如表6 所示。從表6 可以看出，無自適應(yīng)的排名為3.160 7、η=0.3 時(shí)的排名為2.625 0、η=0.5 時(shí)的排名為1.964 3、η=0.7 時(shí)的排名為2.250 0。由于當(dāng)η=0.5 時(shí)對(duì)MSRCS 的性能提升最明顯，因此選取η=0.5，自適應(yīng)步長(zhǎng)的變化范圍為［0.00，0.25］。

表6 不同η 值的MSRCS 平均排名Table 6 Average rank of MSRCS with the different η value

3.6 MSRCS 計(jì)算時(shí)間分析

根據(jù)MSRCS 算法流程可以看出，MSRCS 僅改變了算法對(duì)策略的選擇機(jī)制，有概率選擇新的解更新方法代替Lévy 飛行，減少了對(duì)Lévy 飛行隨機(jī)步長(zhǎng)的計(jì)算。使用單一的Lévy 飛行成效有限，對(duì)于平衡算法的勘探與開采，多策略調(diào)和對(duì)每個(gè)時(shí)期的策略選擇相對(duì)更加有效。

MSRCS 和CS 在不同維度下計(jì)算CEC2013 測(cè)試集上28 個(gè)測(cè)試函數(shù)的運(yùn)行時(shí)間，如表7 所示。從表7可以看出，無論是在問題維度d為30、50 或100 時(shí)，CS 和MSRCS 的運(yùn)行時(shí)間并無顯著差異。由此再次驗(yàn)證了CS 和MSRCS 的復(fù)雜度分析，MSRCS 和CS在計(jì)算復(fù)雜度上并無顯著差異。

表7 CS和MSRCS算法在CEC2013測(cè)試集上的運(yùn)行時(shí)間Table 7 Runtime of CS and MSRCS algorithms on CEC2013 test set 103 s

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

本文提出一種多策略調(diào)和的布谷鳥搜索（MSRCS）算法，在多策略框架下根據(jù)迭代階段的不同需求進(jìn)行策略選擇，有效加快算法的收斂速度以及豐富種群學(xué)習(xí)的多樣性。但由于調(diào)和策略基于隨機(jī)思想，無法準(zhǔn)確感知布谷鳥的狀態(tài)并做出決策，因此MSRCS 算法對(duì)CEC2013 測(cè)試集的28 個(gè)函數(shù)進(jìn)行實(shí)驗(yàn)和統(tǒng)計(jì)分析，并與原始CS 和其7 種改進(jìn)算法以及3 種經(jīng)典群智能優(yōu)化算法進(jìn)行比較，還對(duì)自適應(yīng)步長(zhǎng)參數(shù)以及策略有效性進(jìn)行研究，結(jié)果表明MSRCS 算法性能優(yōu)于對(duì)比算法，同時(shí)證明了調(diào)和策略的可操作性。后續(xù)可將MSRCS 算法應(yīng)用于車間調(diào)度、旅行商等復(fù)雜組合優(yōu)化問題，進(jìn)一步擴(kuò)大其適用范圍。