自適應(yīng)調(diào)整布谷鳥搜索算法研究

張毅 雷玉霞

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

關(guān)鍵詞：布谷鳥算法;自適應(yīng);搜索算法

DOI：10. 11907/rjdk. 182613 開放科學(xué)（資源服務(wù)）標識碼（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-），男，曲阜師范大學(xué)信息科學(xué)與工程學(xué)院碩士研究生，研究方向為智能信息處理;雷玉霞（1976-），男，博士，曲阜師范大學(xué)信息科學(xué)與工程學(xué)院副教授、碩士生導(dǎo)師，研究方向為智能信息處理、概念格。

0 引言

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

1 布谷鳥搜索算法

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

將自然界布谷鳥繁殖演變?yōu)樗惴ê?，約定如下3個假設(shè)規(guī)則[1]：

假設(shè)1：布谷鳥自由選擇鳥巢產(chǎn)蛋，一個鳥巢只產(chǎn)一只蛋;

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

假設(shè)3：鳥巢的數(shù)量固定，寄主發(fā)現(xiàn)鳥蛋的概率是[Pa]，如果被寄主發(fā)現(xiàn)，鳥蛋將會被破壞，隨之被放棄。

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

圖1 萊維飛行軌跡

布谷鳥算法用隨機游動產(chǎn)生新解：

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

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

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

S屬于萊維飛行的隨機步長，通過萊維飛行進行位置更新后，隨機產(chǎn)生0到1的數(shù)r，與鳥窩的發(fā)現(xiàn)概率[Pa]進行比較，如[r>Pa]則繼續(xù)進行位置更新，[r

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

2 自適應(yīng)調(diào)整布谷鳥搜索算法

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

2.1 步長[α]的改進

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

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

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

2.2 發(fā)現(xiàn)概率[Pa]的改進

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

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

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

3 實驗與分析

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

表1 標準測試函數(shù)

仿真圖像橫坐標為算法迭代次數(shù)，縱坐標為適應(yīng)度，實驗結(jié)果見圖2-圖7及表2所示。

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

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

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

表2 相同迭代次數(shù)下算法比較

函數(shù)測試顯示，對于單峰Schaffer、Schwefel函數(shù)效果比較明顯，凸顯收斂優(yōu)勢。對于多峰Rastrigin、Griewank函數(shù)，搜索性能改進有限，但算法性能整體上有所提升。為進一步檢驗改進后算法的尋優(yōu)性能和效率，采用經(jīng)典的0-1背包問題作為應(yīng)用測試實例：設(shè)物品個數(shù)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 算法最優(yōu)值計算結(jié)果對比

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

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

4 結(jié)語

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

參考文獻：

[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] 李榮雨，戴睿聞. 自適應(yīng)步長布谷鳥搜索算法[J]. 計算機科學(xué)， 2017，44（5）：235-240.

[7] 鄭洪清，周永權(quán). 一種自適應(yīng)步長布谷鳥搜索算法[J]. 計算機工程與應(yīng)用，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] 胡欣欣. 求解函數(shù)優(yōu)化問題的改進布谷鳥搜索算法[J]. 計算機工程與設(shè)計，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]. 軟件學(xué)報，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]. 計算機工程與設(shè)計，2015（4）：1063-1067.

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

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

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

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

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

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

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

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

（責任編輯：杜能鋼）