自適應調整布谷鳥搜索算法研究

張毅 雷玉霞

摘 要：布谷鳥算法是基于啟發式搜索的智能仿生算法。傳統的布谷鳥算法收斂速度較慢，容易陷入局部最優解。針對該算法特點，對算法原理進行了分析，并就算法中步長和發現概率兩個控制因素進行改進，使其根據迭代次數動態變化，提出了具有自適應調整特點的搜索算法，改變了步長和發現概率相應的更新方式，避免了傳統布谷鳥算法容易陷入局部最優的缺陷，以增強算法搜索性能。實驗對比表明，自適應調整的布谷鳥算法具有更好的尋優性能。

關鍵詞：布谷鳥算法;自適應;搜索算法

DOI：10. 11907/rjdk. 182613 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP312 文獻標識碼：A 文章編號：1672-7800（2019）008-0056-03

Research on Adaptive Adjustment of Cuckoo Search Algorithm

ZHANG Yi， LEI Yu-xia

（Department of Information Science & Engineering， Qufu Normal University， Rizhao 276800， China）

Abstract： The cuckoo algorithm is an intelligent bionic algorithm based on heuristic search. The traditional cuckoo algorithm has a slow convergence speed and is easy to fall into the local optimal solution. According to the characteristics of the algorithm， the algorithm principle is analyzed. The two control factors of the step size and discovery probability are improved， so that they change dynamically according to the number of iterations. A search algorithm with adaptive adjustment characteristics is proposed， which changes the step size and the update probability corresponding to the discovery probability， and make the traditional cuckoo algorithm avoid to fall into local optimum so as to enhance the search performance of the algorithm. After experimental comparison， the adaptively adjusted cuckoo algorithm has better performance.

Key Words： cuckoo algorithm; adaptive; search algorithm; algorithm optimization

作者簡介：張毅（1992-），男，曲阜師范大學信息科學與工程學院碩士研究生，研究方向為智能信息處理;雷玉霞（1976-），男，博士，曲阜師范大學信息科學與工程學院副教授、碩士生導師，研究方向為智能信息處理、概念格。

0 引言

布谷鳥搜索算法（Cuckoo Search Algorithm，CS）是根據自然界中布谷鳥尋找合適的鳥窩產蛋繁殖的仿生算法，該算法參數較少，簡單高效，容易實現，具有全局收斂性[1-3]。但是該算法容易陷入局部最優， 因此不少學者從基于步長和發現概率等方面提出改進方法。例如，Walton[4]對萊維飛行的隨機步長進行了改進，Wang[5]提出用混沌序列作為步長改進，李榮雨等[6-7]提出對步長進行自適應改進，還有學者通過改變發現概率使其具有動態性來加快收斂速度[8-9]。固定的步長會使算法在求解過程中容易越過最優解，固定的發現概率會在搜索最優解過程中增加迭代成本，單獨對步長或發現概率的控制有一定局限性。因此，Valian[10]提出動態調整發現概率和步長思路。受此啟發，本文針對后期算法收斂速度慢、尋優精度低的問題，分析布谷鳥的搜索策略和特點，提出從步長和發現概率兩個因素綜合進行改進，隨迭代次數的增加進行自適應參數調整，提高算法性能。經過標準函數和問題實例測試，將改進后算法與原算法進行比較研究。

1 布谷鳥搜索算法

布谷鳥繁殖后代方式是通過將鳥蛋產在其它鳥類的鳥巢中，由宿主孵化鳥蛋。有些情況下宿主會發現布谷鳥的鳥蛋，發現后將其拋棄，這樣會使布谷鳥繁殖失敗。

將自然界布谷鳥繁殖演變為算法后，約定如下3個假設規則[1]：

假設1：布谷鳥自由選擇鳥巢產蛋，一個鳥巢只產一只蛋;

假設2：存在有最合適的布谷鳥蛋會傳遞保留到下一代;

假設3：鳥巢的數量固定，寄主發現鳥蛋的概率是[Pa]，如果被寄主發現，鳥蛋將會被破壞，隨之被放棄。

所以，布谷鳥鳥蛋所在的鳥巢就是一個解，尋優的過程就是不斷用新解代替上一次的較差解，在算法中主要依靠隨機游動和萊維飛行這兩個環節產生新解搜索。

圖1 萊維飛行軌跡

布谷鳥算法用隨機游動產生新解：

[Xi+1=Xi+α⊕Levy（β）] （1）

其中：[i=1，2，3，？，n]，[α]為步長控制量，[⊕]為點對點乘法，[Levy]為萊維飛行搜索，服從[Levy]分布式。

[L（s，λ）～s-λ，λ∈（1，3]] （2）

S屬于萊維飛行的隨機步長，通過萊維飛行進行位置更新后，隨機產生0到1的數r，與鳥窩的發現概率[Pa]進行比較，如[r>Pa]則繼續進行位置更新，[r

布谷鳥算法流程如下：①初始化設置相應參數，隨機生成初始解并計算初始解的適應度;②通過萊維飛行產生新解;③計算新解的適應度;④通過發現概率[Pa]對解進行淘汰;⑤通過隨機游動產生新解，替代被丟棄的解;⑥保留最好的解，回到第②步循環。

2 自適應調整布谷鳥搜索算法

在布谷鳥算法中，有4個參數控制算法，分別是鳥巢數量n、發現概率[Pa]、步長[α]、萊維飛行公式中的[λ]。通常情況下，[λ]=1.5，n=30（原標準CS算法設定[2]），這兩個參數對算法的影響可以忽略不計。步長[α]和發現概率[Pa]影響算法的搜索性能，因此本文從這兩個方面進行改進。

2.1 步長[α]的改進

在布谷鳥算法中步長[α]是固定的，在步長保持不變的情況下無法達到更加精確的搜索，只能增加迭代次數。本文將步長的改進與迭代次數相關，使步長伴隨著迭代次數的增加逐漸呈動態指數遞減變化，采用這種指數遞減的動態步長可提高搜索精度，公式如下：

[α（t）=α（t）？tmax？exp（-titmax）] （3）

其中，[ti]是當前迭代的次數，[tmax]是總迭代次數。

2.2 發現概率[Pa]的改進

布谷鳥算法中發現概率[Pa]決定是否保留當前解，它的取值會影響最優解搜索效果，若要把發現概率的取值調整為最佳就要使其動態變化。改進后的發現概率通過適應值可更好地區分解的優劣。方法是發現適應值更好的解的概率小于發現適應值差的解的概率，從而保留適應值更好的解，公式如下：

[Pa，i=nPa（t）fij=1nfj]? ? ? ? ?（4）

其中，[Pa，i]表示第i個鳥巢中蛋被發現的概率，n表示鳥巢的數目，[Pa（t）]表示當前的迭代次數下布谷鳥蛋的平均發現概率，[fi]表示當前第i代適應值，[fj]表示第j代適應值（最大迭代次數）。

3 實驗與分析

算法測試環境為：Window 7，CPU為酷睿i5，內存8G，Matlab 7.0，測試函數包含：Rastrigin、Griewank、Rosebrock、Sphere、Schaffer、Schwefel。算法中鳥群規模參數n=30，發現概率[Pa=0.25]，最大迭代次數[tmax=1 000]，平均獨立運行30次。

表1 標準測試函數

仿真圖像橫坐標為算法迭代次數，縱坐標為適應度，實驗結果見圖2-圖7及表2所示。

圖2 Rastrigin收斂曲線? ? ? ? ? ? ? ? 圖3 Griewank 收斂曲線

圖4 Rosebrock收斂曲線? ? ? ? ? ? ? ?圖5 Sphere收斂曲線

圖6 Schaffer 收斂曲線? ? ? ? ? ? ? 圖7 Schwefel收斂曲線

表2 相同迭代次數下算法比較

函數測試顯示，對于單峰Schaffer、Schwefel函數效果比較明顯，凸顯收斂優勢。對于多峰Rastrigin、Griewank函數，搜索性能改進有限，但算法性能整體上有所提升。為進一步檢驗改進后算法的尋優性能和效率，采用經典的0-1背包問題作為應用測試實例：設物品個數N=50，背包容量C=1 000，重量W={80，82，85，70，72，70，66，50，55，25，50，55，40，48，50，32，22，60，30，32，40，38，35，32，25，28，30，22，50，30，45，30，60，50，20，65，20，25，30，10，20，25，15，10，10，10，4，4，2，1}，價值V={220，208，198，192，180，180，165，162，160，158，155，130，125，122，120，118，115，110，105，101，100，100，98，96，95，90，88，82，80，77，75，73，72，70，69，66，65，63，60，58，56，50，30，20，15，10，8，5，3，1}，見表3。

表3 算法最優值計算結果對比

圖8 4種算法的收斂性對比

實驗對比表明，自適應CS算法與解決0-1背包問題的經典智能蟻群算法、蜂群算法和原始CS算法相比，具有更好的收斂性能和搜索能力，見圖8。

4 結語

布谷鳥算法與其它智能算法相比，具有通用性好、魯棒性強的優點。針對其后期收斂速度慢、精度不高等不足，本文提出根據迭代次數調整的自適應布谷鳥算法，改寫算法的步長和發現概率公式，提高算法搜索效率。采用測試函數和實際問題用例進行測試，實驗表明該改進算法在收斂速度和尋優性能上均有提高。后續工作將進一步探討更優的尋優策略應用于更多優化問題。

參考文獻：

[1] YANG X S， DEB S. Cuckoo search via levy flights[J]. Mathematics， 2010（1）：210 - 214.

[2] YANG X S， DEB S. Cuckoo search via lévy flights[C]. Nature & Biologically Inspired Computing， 2009. NaBIC 2009. World Congress on. IEEE， 2010：210-214.

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

[4] WALTON S，HASSAN O，MORGAN K，et al. Modified cuckoo search： a new gradient free optimisation algorithm[J]. Chaos Solitons & Fractals， 2011， 44（9）：710-718.

[5] WANG L，ZHONG Y. Cuckoosearch algorithm with chaotic maps[J].Mathematical Problems in Engi-neering，2015，9（4）：623-635.

[6] 李榮雨，戴睿聞. 自適應步長布谷鳥搜索算法[J]. 計算機科學， 2017，44（5）：235-240.

[7] 鄭洪清，周永權. 一種自適應步長布谷鳥搜索算法[J]. 計算機工程與應用，2013， 49（10）：68-71.

[8] WANG L，YANG S，ZHAO W. Structural damage identification of bridge erecting machine based on improved cuckoo search algorithm[J]. Journal of Beijing Jiaotong University， 2013， 37（4）：168-173.

[9] 胡欣欣. 求解函數優化問題的改進布谷鳥搜索算法[J]. 計算機工程與設計，2013，34（10）：3639-3642.

[10] VALIAN E，MOHANNA S，TAVAKOLI S. Improved cuckoo search algorithm for global optimization[J]. Computers & Industrial Engineering， 2011（1）：152-160.

[11] 王李進，尹義龍，鐘一文. 逐維改進的布谷鳥搜索算法[J]. 軟件學報，2013，24（11）：2687-2698.

[12] PAVLYUKEVICH I. Levy flights， non-local search and simulated annealing[J]. Mathematics， 2007， 226（2）：1830-1844.

[13] 蘭少峰，劉升. 布谷鳥搜索算法研究綜述[J]. 計算機工程與設計，2015（4）：1063-1067.

[14] 秦嶺，戴睿聞. 具有記憶性的自適應布谷鳥搜索算法[J].微電子學與計算機，2017，34（3）：15-19，24

[15] 林要華，梁忠，胡華平. 貝塔分布的布谷鳥搜索算法[J]. 南京大學學報：自然科學版，2016， 52（4）：638-646.

[16] SHLESINGER M F. Mathematical physics：search research[J]. Nature，2006，443（7109）：281-282.

[17] 張曉鳳，王秀英. 布谷鳥搜索算法綜述[J]. 計算機工程與應用，2018，54（18）：8-16.

[18] 孫敏，房明磊，韋慧. 基于自適應步長的改進布谷鳥算法[J]. 赤峰學院學報：自然科學版，2018，34（7）：45-49.

[19] 林詩潔，董晨，陳明志，等. 新型群智能優化算法綜述[J]. 計算機工程與應用，2018，54（12）：1-9.

[20] 錢偉懿，候慧超，姜守勇. 一種新的自適應布谷鳥搜索算法[J]. 計算機科學，2014，41（7）：279-282.

[21] 余建平，周新民，陳明. 群體智能典型算法研究綜述[J]. 計算機工程與應用，2010，46（25）：1-4，74.

（責任編輯：杜能鋼）