基于反向?qū)W習策略的深度搜索布谷鳥算法

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

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

中圖分類號：TP301

文獻標識碼： A

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

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

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

1相關(guān)工作

1.1布谷鳥算法

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

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

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

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

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

（1）初始化

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

（2）搜索

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

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

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

萊維飛行隨機搜索路徑公式為

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

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

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

（3）選擇

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

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

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

（4）結(jié)束判決

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

1.2反向?qū)W習

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

2.1反向?qū)W習策略

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

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

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

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

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

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

2.2逐維深度搜索

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

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

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

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

3實驗與結(jié)果分析

本節(jié)將DSCS與CS進行比較，以驗證其有效性。實驗平臺是Windows7 MATLAB R2014b，5個測試函數(shù)如表1所示，F(xiàn)1—F3是單峰函數(shù)，F(xiàn)4—F5是多峰函數(shù)[14]。在實驗過程中，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。

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

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

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

4結(jié)語

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

參考文獻：

[1]

YANG X S， DEB S. Cuckoo search via levy flights [C]//Proc of world congress on Nature amp; 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].計算機工程與設(shè)計， 2015， 36（4）： 1063-1067.

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

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

[8]汪峰坤，張婷婷.一種改進的布谷鳥算法[J].新鄉(xiāng)學院學報， 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習的動態(tài)適應布谷鳥算法[J].計算機應用研究， 2019，37（4）：1-7.

[14]范帥軍.布谷鳥搜索算法的應用研究與改進[D].成都：西南交通大學，2016.

（責任編輯：曾晶）