何慶 黃閩茗 周曉南

摘要：布谷鳥搜索算法（CS）是一種簡單有效的仿生學(xué)優(yōu)化算法，但在處理高維復(fù)雜問題時不能快速收斂得到最優(yōu)解，針對此問題，本文引入反向?qū)W習(xí)策略和逐維深度搜索策略改進(jìn)基本的CS。在布谷鳥算法的搜索階段，通過對Levy飛行后的解進(jìn)行反向?qū)W習(xí)，從而有效提升最優(yōu)解的搜索效率;另外，在每一代結(jié)束后，對當(dāng)前的全局最優(yōu)解進(jìn)行逐維深度搜索，捕捉潛在最優(yōu)解，彌補(bǔ)搜索步驟可能出現(xiàn)的問題。實(shí)驗(yàn)結(jié)果表明，本文對算法提出的改進(jìn)，提高了算法的全局搜索能力，收斂速度以及收斂精度。

關(guān)鍵詞：布谷鳥搜索算法;仿生群優(yōu)化算法;并行算法;反向?qū)W習(xí);深度搜索

中圖分類號：TP301

文獻(xiàn)標(biāo)識碼： A

布谷鳥搜索（Cuckoo Search，CS）算法是在2009年開發(fā)的自然啟發(fā)式算法。該算法基于布谷鳥育雛行為的寄生性，并包含鳥類和果蠅的levy飛行行為[1]為雛形設(shè)計算法原理。由于其簡單性和有效性，從誕生之日起，吸引了很多學(xué)者的關(guān)注，并成功應(yīng)用于工程優(yōu)化和函數(shù)優(yōu)化問題[2-3]以及機(jī)器學(xué)習(xí)[4]等方面。但是，對于一些復(fù)雜的問題，CS算法也存在著局部搜索能力較差、后期收斂速度慢[5]等缺點(diǎn)，暫時無法滿足最優(yōu)解的精度要求，因此其性能需要進(jìn)一步改進(jìn)。

王凡等[6]通過分析CS算法的Markov鏈模型，證明了CS算法的收斂性。張燕[7]提出了一種基于Cubic混沌模型的自適應(yīng)布谷鳥優(yōu)化算法，自適應(yīng)的調(diào)整levy flights的隨機(jī)搜索補(bǔ)償因子，并Cubic混沌映射嵌入算法，通過實(shí)驗(yàn)證明了有效性;汪峰坤等[8]提出的一種改進(jìn)的布谷鳥算法，通過交叉操作和變異操作，增強(qiáng)了布谷鳥算法的種群多樣性和搜索性能。

基于以上算法的啟發(fā)，本文設(shè)計了一種改進(jìn)的深度搜索布谷鳥（Deep Search Cuckoo Search，DSCS）算法。改進(jìn)算法引入反向?qū)W習(xí)策略和逐維深度搜索策略來改進(jìn)基本的CS。首先，對Levy飛行后的解進(jìn)行反向?qū)W習(xí)，提升最優(yōu)解的搜索效率;然后，對迭代結(jié)束后的全局最優(yōu)解進(jìn)行逐維深度搜索，捕捉潛在的最優(yōu)解，彌補(bǔ)搜索步驟可能出現(xiàn)的問題，提高了算法的全局搜索能力。通過5個測試函數(shù)的實(shí)驗(yàn)結(jié)果證明，本改進(jìn)的DSCS算法具有更好的全局搜索能力，搜索精度和收斂速度。

1相關(guān)工作

1.1布谷鳥算法

CS算法通過模擬布谷鳥的寄生繁衍策略來尋找最優(yōu)解。尋找最適合產(chǎn)蛋的鳥巢是一種隨機(jī)的或類似隨機(jī)的方式。其基本原理就是把布谷鳥所寄生的鳥巢位置映射為算法種群空間中的解，以寄生巢位置的優(yōu)劣作為算法的適應(yīng)度值，為了模擬布谷鳥的繁衍機(jī)制，CS算法設(shè)定了三個理想規(guī)則[1]：

規(guī)則1每只布谷鳥只產(chǎn)一個蛋，并隨機(jī)放入所選擇的寄主鳥類的巢穴中。

規(guī)則2每次進(jìn)化都保留最優(yōu)蛋的巢穴到下一代。

規(guī)則3可用的寄主巢穴數(shù)量固定，且寄主鳥類以概率R∈（0，1）發(fā)現(xiàn)布谷鳥放的蛋。寄主發(fā)現(xiàn)布谷鳥的蛋，可以消滅該蛋或放棄舊巢另建新巢。

根據(jù)這三條規(guī)則，CS包括四個步驟，初始化，搜索，選擇和判斷。該步驟如下：

（1）初始化

定義目標(biāo)函數(shù)F（x），并隨機(jī)生成N個鳥窩的初始位置Xi=1，2，…，N，設(shè)置問題維數(shù)、發(fā)現(xiàn)概率Pa和最大迭代次數(shù)等參數(shù)。

（2）搜索

選擇目標(biāo)函數(shù)并計算每個鳥窩位置的目標(biāo)函數(shù)值，得到當(dāng)前的最優(yōu)函數(shù)值，根據(jù)levy飛行生成新的鳥巢位置，計算每個蛋的適應(yīng)度函數(shù)Ft，比較存優(yōu)。levy飛行的隨機(jī)步長公式為[1]

xt+1，i=xt，i+α0Levy（β）。（1）

式中：xt+1，i為巢穴位置更新后的位置;xt，i為當(dāng)前巢穴位置;α0為步長縮放因子，通常為001[2]。

萊維飛行隨機(jī)搜索路徑公式為

Levy（β）～Φ×uv1β。（2）

式中：u和v為標(biāo)準(zhǔn)正態(tài)隨機(jī)變量，β為萊維飛行的控制因子，通常為1.5[1]。Φ的計算公式為

Φ=Γ1+β×sinπ×β2Γ1+β2×β×2（β-1）21β。（3）

（3）選擇

依據(jù)布谷鳥的蛋發(fā)現(xiàn)概率Pa丟棄不好的巢穴位置，用式（3）更新巢穴中蛋的位置，并計算目標(biāo)函數(shù)Ft，選擇存優(yōu)。位置更新式（3）為

xt+1，i=xt，i+r（xt，j-xt，k）。（4）

式中：r為比例因子，是（0，1）區(qū)間的均勻分布隨機(jī)數(shù);xt，j和xt，k為t代中的兩個隨機(jī)解。

（4）結(jié)束判決

若滿足預(yù)設(shè)的求解精度或最大迭代次數(shù)，則結(jié)束，否則返回步驟（2）。算法的實(shí)現(xiàn)過程如圖1描述。

1.2反向?qū)W習(xí)

反向?qū)W習(xí)（Opposition￣based Learning， OBL）被TIZHOOSH[9]2005年提出，是智能計算領(lǐng)域中的一種新技術(shù)。直到2008年，它才被RAHNAMAYAN等[10]用于差分進(jìn)化算法。OBL是計算可行解決方案的基于反向的解決方案，同時評估原始解決方案和基于反向的解決方案，并選擇更好的解決方案[11]。

2.1反向?qū)W習(xí)策略

反向?qū)W習(xí)被RAHNAMAYAN等[10]證明了當(dāng)前可行解的基于反向的解有50%的概率更接近全局最優(yōu)解。雖然可行解決方案和基于反向的解決方案在相同條件下具有相同的概率保留給下一代，評估兩者的解決方案，并選擇更好的解決方案，它的生成算法能夠提高獲得最優(yōu)解的概率。

本文在CS的搜索階段，本文將levy飛行之后的目標(biāo)函數(shù)值，與其在作用域范圍內(nèi)的反向解的目標(biāo)函數(shù)和當(dāng)前最優(yōu)解的目標(biāo)函數(shù)值進(jìn)行比較，對最優(yōu)解和當(dāng)前最優(yōu)解進(jìn)行更新。通過反向?qū)W習(xí)減少搜索范圍，從而提升解的搜索效率。具體步驟如下：

在反向?qū)W習(xí)策略中，設(shè)種群規(guī)模為N，維度為D，迭代過程選擇更新位置時的位置矩陣為nestN×Di。每個維度的上下限分別為upN×Di，lowN×Di，則解的每維的基于反向?qū)W習(xí)的位置矩陣如下：

nestN×Di′=upN×Di+lowN×Di-nestN×Di（7）

在DSCS中，產(chǎn)生的三個隨機(jī)位置將會被反向群體nestN×Di選擇，這種變化有效地擴(kuò)大了搜索范圍，并加快了全局最優(yōu)解的搜索速度。

比較Levy飛行獲得的解、Levy飛行獲得的解的反向解以及當(dāng)前最優(yōu)解的目標(biāo)函數(shù)值，本文將三個解中最小的目標(biāo)函數(shù)值的解作為下一次迭代的最優(yōu)解;蛋的位置更新，選擇Levy飛行獲得的解與Levy飛行獲得的解的反向解中獲得的位置更新。

2.2逐維深度搜索

若群體個體的維數(shù)為2，達(dá)到全局最優(yōu)之前A的坐標(biāo)為XA=xt1，xt2，當(dāng)前全局最優(yōu)B的坐標(biāo)為XB=xt+11，xt+22，顯然，B優(yōu)于A，進(jìn)化方向?yàn)锳B，則A和B之間的位置關(guān)系如圖3所示。

由于在搜索步驟中搜索到的解不一定是最好的解。如果搜索步長太小，則更好的解將存在于BC方向上，相反，如果搜索步長太大，則更好的解將存在于BA方向上[13]。

在DSCS中，為了彌補(bǔ)獲得最優(yōu)步長的難度，提出了一種逐維深度搜索方法。它是為了在各維

方向上BC和BA上尋找合適的步長Δ以尋找更好的解。兩個步驟如下：

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

本節(jié)將DSCS與CS進(jìn)行比較，以驗(yàn)證其有效性。實(shí)驗(yàn)平臺是Windows7 MATLAB R2014b，5個測試函數(shù)如表1所示，F(xiàn)1—F3是單峰函數(shù)，F(xiàn)4—F5是多峰函數(shù)[14]。在實(shí)驗(yàn)過程中，DSCS和CS的參數(shù)如下：

固定參數(shù)：種群數(shù)量為N=30，個體維度D=20，每個維度的范圍為[-20，20]，收斂精度δ=10-5，最大迭代次數(shù)tmax=5 000。

可變參數(shù)：被發(fā)現(xiàn)概率Pa=0.05，levy飛行的步長縮放因子α0=0.1;控制因素β=1.3。

DSCS參數(shù)：比例因子η=150，單向位置搜索最大數(shù)量Pmax=15。

每個實(shí)驗(yàn)分別運(yùn)行30次，實(shí)驗(yàn)結(jié)果如表2所示。從表中可以看出，DSCS的性能相比CS算法，總體改善了解的質(zhì)量，特別地，在F4函數(shù)上取得全局最優(yōu)解。

為了更好地觀察改進(jìn)算法的性能，實(shí)驗(yàn)設(shè)置算法結(jié)束條件為最大迭代次數(shù)，設(shè)置為5 000次，即tmax=5 000，其他參數(shù)保持不變。圖4（a）～（e）以算法的迭代次數(shù)為橫軸，適應(yīng)度函數(shù)的對數(shù)值為豎軸，圖形化的展示了改進(jìn)算法和CS算法在5個測試函數(shù)中的尋優(yōu)搜索收斂過程，其中，測試函數(shù)的維度為20?？梢钥闯觯瑹o論測試函數(shù)是簡單的單模函數(shù)還是復(fù)雜的多模函數(shù)，DSCS的收斂速度和收斂精度都高于CS的收斂速度和收斂精度。特別的，在函數(shù)F4和F5中，函數(shù)能夠收斂到理論最優(yōu)值，并且在函數(shù)的收斂過程中，相比較于CS算法，尋優(yōu)收斂曲線斜率更小;因此，改進(jìn)算法具有更好的后期搜索能力和更強(qiáng)的搜索活力。由此可得，本文改進(jìn)的算法有效提高了CS算法的收斂精度和收斂速度。

實(shí)驗(yàn)結(jié)果表明，針對本文選取的5個測試函數(shù)，本文提出的算法在引入基于反向?qū)W習(xí)策略和局部增強(qiáng)搜索操作后，算法的收斂速度，收斂精度和全局搜索能力都得到了不同程度的提高。

4結(jié)語

在算法DSCS的選擇階段，基于初始化群體生成基于反向群體，然后隨機(jī)選擇三個新的個體替換初始化群體中丟棄的個體。在每一代的演化中，它類似于同時搜索兩個對稱區(qū)域，這加速了收斂速度并提高了全局搜索能力。對5種標(biāo)準(zhǔn)測試函數(shù)的實(shí)驗(yàn)表明，DSCS的性能明顯優(yōu)于CS。DSCS的全局搜索能力，收斂速度和收斂精度要好得多。對于簡單的單模函數(shù)和復(fù)雜的多模態(tài)函數(shù)，DSCS在優(yōu)化實(shí)驗(yàn)上表現(xiàn)出良好的魯棒性。此外，本文的算法還需要在實(shí)際優(yōu)化問題中進(jìn)行分析驗(yàn)證，例如，應(yīng)用于機(jī)器學(xué)習(xí)中的參數(shù)優(yōu)化等。

參考文獻(xiàn)：

[1]

YANG X S， DEB S. Cuckoo search via levy flights [C]//Proc of world congress on Nature & Biologically inspired computing. Piscataway： IEEE Publications， 2009： 210-214.

[2]JIANG M L， LUO J Y， JIANG D D， et al. A Cuckoo search￣support vector machine model for predicting dynamic measurement errors of sensors[J]. IEEE Access， 2017， 4（99）： 5030-5037.

[3]WANG L J， ZHONG Y W， YIN Y L. Nearest neighbor cuckoo search algorithm with probabilistic mutation[J]. Elsevier Science Publishers B. V. Amsterdam， 2016， 49：498-509.

[4]HE S L， HAN J H. Parameter selection of support vector regression based on cuckoo search algorithm[J]. Journal of South China Normal University （Natural Science Edition）， 2014， 46（6）： 33-39.

[5]蘭少峰， 劉升.布谷鳥搜索算法研究綜述[J].計算機(jī)工程與設(shè)計， 2015， 36（4）： 1063-1067.

[6]王凡，賀興化，王燕，等.基于CS算法的Markov模型及收斂性分析[J].計算機(jī)工程， 2012， 38（11）：180-185.

[7]張燕. 基于Cubic混沌模型的自適應(yīng)布谷鳥優(yōu)化算法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識， 2018， 48（17）：246-254.

[8]汪峰坤，張婷婷.一種改進(jìn)的布谷鳥算法[J].新鄉(xiāng)學(xué)院學(xué)報， 2017， 34（6）： 28-31.

[9]TIZHOOSH H R. Opposition￣based learning： A new scheme for machine Intelligence[C]//Computational Intelligence for Modelling. Vienna， Austria： Computer Society， 2005：695-701.

[10]RAHNAMAYAN S， TIZHOOSH H R， SAalama M A. Opposition￣based differential evolution[J]. Evolutionary Computation， 2008，12（1）： 64-79.

[11]WEI W H， ZUOU J L， FANG C， et al. Constrained differential evolution using generalized opposition￣based learning[J]. Acta Electronica Sinica， 2016， 20（11）：4413-4437.

[12]ZHANG S， LUO Q F， ZHOU Y Q. Hybrid grey wolf optimizer using elite opposition￣based learning strategy and simplex method [J]. International Journal of Computational Intelligence and Applications， 2017，16（2）：1-12.

[13]黃閩茗，何慶，文熙.基于逐維反向?qū)W習(xí)的動態(tài)適應(yīng)布谷鳥算法[J].計算機(jī)應(yīng)用研究， 2019，37（4）：1-7.

[14]范帥軍.布谷鳥搜索算法的應(yīng)用研究與改進(jìn)[D].成都：西南交通大學(xué)，2016.

（責(zé)任編輯：曾晶）