布谷鳥搜索算法研究綜述

蘭少峰，劉 升

（上海工程技術大學 管理學院，上海201620）

0 引 言

布谷鳥搜索算法 （cuckoo search，CS），是由劍橋大學YANG等在文獻 ［1］中提出的一種群智能優化算法，它也是一種新型元啟發式搜索算法。其思想主要基于兩個策略：布谷鳥的巢寄生性和萊維飛行 （Lévy flights）機制。通過隨機游走的方式搜索得到一個最優的鳥窩來孵化自己的鳥蛋，這種方式可以達到一種高效的尋優模式［2］。

CS算法主要優點是參數少、操作簡單、易實現、隨機搜索路徑優和尋優能力強等，備受學者關注，相關的科研成果也日益倍增［3］。目前，王凡、賀興時等已在文獻 ［4］中通過建立CS算法的Markov鏈模型，理論證明了該算法可收斂于全局最優。CS算法的衍生算法以及應用研究也已得到了快速的發展，但目前國內外對CS算法的綜述性研究比較少，YANG等在文獻 ［5］中對CS算法最初的發展和它的多種改進算法之間進行了比較，沒有詳細概述CS算法的發展現狀。因此，有必要對CS算法的原理、算法改進、其各領域的應用、算法優缺點、使用范圍、目前存在的問題以及下一階段的研究方向等進行系統、全面的總結和評述，進而呈現CS算法的發展現狀，期望該算法能夠解決更多更有效的實際問題。

1 CS算法原理

1.1 布谷鳥的巢寄生殖行為

布谷鳥具有孵卵寄生性，本身沒有孵化行為，這就促使它通過尋找質優的巢窩，依靠養父母孵化和育雛［6］。巢寄生殖行為主要表現在宿主的選擇，繁殖期間，大布谷鳥尋找在孵化和育雛時間上基本相似、雛鳥飲食習性基本相同的、卵形狀和顏色相當的宿主，通常表現為雀形目鳥類。確定寄生的宿主后，大布谷鳥要選擇適當的時機，一般要在宿主即將孵化之前，趁宿主外出覓食時迅速寄生產卵。春末夏初，便向北飛，它自己不會做窩，不會育雛，也不會孵化，它每次飛到一個巢窩里只產一個鳥蛋。通常情況下，大布谷鳥在產卵前，為了不被宿主察覺，會把宿主一枚或數枚卵移走，使得巢穴中的卵數量相等或相近。而一旦靠養母孵化的雛鳥孵出，它有將養母本身的雛鳥推出巢外的本性，從而獨享養母撫養，這樣自己成活的概率大大增加。

1.2 萊維飛行

自然界中，動物以隨機或擬隨機的方式來覓食。從文獻 ［7］可以看出，許多飛行動物像信天翁、蜘蛛猴等，其飛行間隔服從冪率分布，比較其飛行軌跡 （如圖1所示）發現，較長線段出現的頻率與無標度的負二次方Lévy分布相像，都具有萊維飛行的特征。最新研究也顯示［8］，人的行為中也存在類似萊維飛行行為。

圖1 萊維飛行軌跡與信天翁飛行軌跡對比

萊維飛行是一類非高斯隨機過程，其平穩增量服從Lévy穩定分布，其飛行步長滿足一個重尾的萊維穩定分布。在飛行過程中，步長較小的短距離行走與偶爾較大步長的長距離行走相互交替，從萊維飛行軌跡圖 （如圖1（a）所示）中可以看出，較小的跳躍組成的聚集被較大的跳躍分隔開的現象。M.F在文獻 ［9］中將該飛行方式植入到群智能搜索算法中，搜索前期大步長用于探索發現，有利于增加種群多樣性、并擴大搜索范圍，不至于陷入局部最優；搜索后期，小步長使得群體在小范圍內收斂于全局最優解。Pavly［10］將該飛行模式應用于優化算法和最優搜索中，顯示了令人滿意的結果。AM等在文獻 ［11］中證明了當目標位置呈現隨機特征，并且無規律地稀疏排布時，對于M個相互獨立的尋優者來說，萊維飛行是最有效、最理想的搜索策略。

1.3 CS算法的實現過程

為了模擬布谷鳥這種尋窩寄生的習性，YANG等在文獻 ［1］中將CS算法假設以下3種理想狀態：

（1）每只布谷鳥一次只產一枚卵，并且隨機選擇一個鳥巢存放；

（2）在尋窩的過程中，卵最好的鳥巢將會被保留到下一代；

（3）可用鳥巢的數量是固定的，并且設鳥巢中外來卵被發現的概率是Ρ，Ρ∈［0， 1］。如果發現外來鳥蛋，則鳥窩主人重新建立一個鳥窩。

通過以上3種理想狀態的假設，布谷鳥尋優搜索的位置和路徑的更新公式如下

式中：x（t）i——第i個鳥窩在第t代的鳥窩位置，⊕——點對點乘法，α——步長控制量，用于控制步長的搜索范圍，其值服從正態分布。

在式 （1）中，L（λ）為Lévy隨機搜索路徑，隨機步長為Lévy分布

式中：s——由萊維飛行得到的隨機步長。

有式 （1）可以看出，該行走方式是一個隨機漫步的過程。由于萊維飛行的隨機游動特征，局部極值點附近往往會出現新解，因此萊維飛行的短步長搜索更加有利于提高解的質量。另外，距離局部最優值較遠的地方也存在新解，偶爾的大步長探索，使得算法不容易陷入局部極值點［12］。

根據布谷鳥的孵化鳥蛋的過程，CS算法的算法描述如下：

步驟1 定義目標函數f（X），X ＝ （x1，…xd）T，函數初始化，并隨機生成n個鳥窩的初始位置Xi（i＝1，2，…，n），設置種群規模、問題維數、最大發現概率Ρ和最大迭代次數等參數；

步驟2 選擇適應度函數并計算每個鳥窩位置的目標函數值，得到當前的最優函數值；

步驟3 記錄上一代最優函數值，利用式 （1）對其他鳥窩的位置和狀態進行更新；

步驟4 現有位置函數值與上一代最優函數值進行比較，若較好，則改變當前最優值；

步驟5 通過位置更新后，用隨機數r∈［0，1］與P對比，若r＞P，則對x（t＋1）i進行隨機改變，反之則不變。最后保留最好的一組鳥窩位置y（t＋1）i；

步驟6 若未達到最大迭代次數或最小誤差要求，則返回步驟2，否則，繼續下一步；

步驟7 輸出全局最優位置。

2 CS改進算法

2.1 基于發現概率Ρ的改進

文獻 ［13］認為被發現的概率Ρ的選擇會影響最優解的搜索：Ρ選擇過大，較好解很難收斂到最優解；Ρ選擇過小，就會使得當前較壞的解收斂較慢。因此引入了動態發現概率

式中：Ρmax、Ρmin——最大、最小發現概率；ΡInterNum——當前迭代次數；ΡIntermax——最大迭代次數。通過兩個典型的30維的測試函數驗證表明，改進后的CS算法優化性能有較大的提升。

文獻 ［14］通過改變發現概率，采用動態自適應機制控制發現概率Ρ，來提高搜索能力和加快收斂速度

式中：Pt——第t代種群中，第i個個體被發現并重新生成新解的概率；Pmax和Pmin——Pt的上下限；fti和ftbest——第t代種群中，第i個個體和最優個體的適應度。通過多個測試函數的對比實驗結果表明，該改進算法提高了CS算法的收斂速度。

2.2 基于自適應步長的改進

文獻 ［15］認為萊維飛行模式缺乏自適應性，為了能夠自適應動態調整大、小步長的間隔，協調好尋優精度和全局尋優能力之間的關系，引入了

式中：dmax——當前最優位置與其余所有鳥窩位置距離的最大值；ni——第i個鳥窩的位置；nbest——當前最佳的鳥窩位置。由此提出了基于最佳鳥窩位置的自適應動態調整步長策略

式中：stepmax和stepmin——步長的最大值和最小值。通過對比標準的CS算法，結果表明改進后的自適應動態調整步長策略使算法具有較高的尋優精度和較快的收斂速度。

Walton等在文獻 ［16］中針對優勢解交換信息步長進行改進，以加強局部搜索能力，使其優勢互補，實驗結果表明，在高維上能夠快速的收斂于全局最優。Andrew W等在文獻 ［17］中利用一種基于種群排序的改進版本來指導隨機游動時的步長，結果顯示該改進算法優于標準的CS算法。文獻 ［18］引入自適應機制，將自適應發現概率和自適應步長相結合，也提高了算法的最優解。

2.3 混合CS算法改進

文獻 ［19］介紹了一種和差分進化算法結合的混合CS算法。差分進化存在易陷入局部最優、過早收斂和停滯的缺陷，利用CS算法尋優能力強的優點，在DE每次完成選擇操作后，不直接進入下一次迭代，而是引入CS算法，繼續進行搜索，這樣就增加了粒子的搜索活力，來提高尋優的精度。

文獻 ［20］提出了二進制布谷鳥搜索算法，將該算法應用到求解旅行商問題和0／1背包問題兩類NP完全問題。試驗結果顯示，BCS算法優于其他混合算法。

此外，文獻 ［21］在算法中偏好隨機游動和萊維隨機游動之間融合PSO組件，提高了算法的性能。文獻 ［22］將CS與PSO算法串行，在迭代開始時，利用PSO算法優化種群，然后利用CS算法在最優個體中繼續尋優。文獻［23］在算法迭代過程中對鳥窩位置加入高斯擾動，即在每一次迭代得到較優的鳥窩位置后，進行高斯擾動，使鳥窩位置得到進一步搜索，增強了鳥窩位置變化的活力，提高了算法的收斂速度。

3 CS算法應用

CS算法具有較強的優越性，一經提出，便得到了迅速的發展。CS算法的應用已經涉及到多目標優化［8］、軟件測試數 據 自 動 生 成［24］、神 經 網 絡 訓 練［25］、工 程 設 計 優化［2，26］、交通流量預測［27］、人臉識別［28］、函數優化［29］、計算機網絡［31］等理論與應用領域。

文獻 ［2］以Otsu法設計適應度函數，利用CS算法的并行尋優性能在多閾值圖像分割問題中成功運用。文獻［24］則將CS算法中引入禁忌搜索思想，將當前搜索得到的最優解保存在禁忌搜索隊列中，達到避免陷入局部最優的目的，該算法在軟件結構測試數據自動生成中得到了較好的效果。文獻 ［25］對CS算法的搜索參數進行適當的策略分析，并用于訓練神經網絡的兩個基準分類問題。文獻［26］提出一種基于隨機局部搜索的改進布谷鳥搜索算法，以加快算法的收斂速度，兩個工程結構優化問題的實驗結果表明該算法具有可行性和有效性。文獻 ［27］采用CS算法找到BP神經網絡最優參數，建立了短時交通的預測模型，仿真結果表明，該方法更好的反應了短時交通的變化趨勢。文獻 ［28］將CS算法運用到人臉識別中，結果顯示該算法優于PSO算法和ACO算法。文獻 ［29］利用基本CS算法求解整數規劃問題，實驗結果表明該算法具有比PSO算法擁有更好的性能和更強的全局尋優能力。文獻［30］提出一種基于正交學習的搜索策略，提高了CS算法的局部搜索能力，并成功運用于連續函數優化問題。文獻［31］采用CS算法優化支持向量機參數，使用這組優化參數建立網絡流量預測模型，仿真結果顯示該方法有效可行。

4 CS算法與相關群智能算法性能對比

CS算法、蟻群算法 （ACO）、粒子群算法 （PSO）、蜂群算法 （ABC）等都是基于仿生群智能而產生的優化算法，在種群進化過程中，通過迭代完成搜索尋優的過程。在應用過程中，不同的算法有著不同的優缺點，本文通過總結歸納文獻 ［1－3，6，7，12－31］，對幾種優化算法進行比較，得出表1的結果。

表1 CS與ACO、PSO、ABC算法的比較

由表1可以看出，相對于其它3種優化算法，CS算法在參數設置、全局搜索能力、通用性和魯棒性方面具有綜合性優勢。文獻 ［1，15，22，26］中經過多種測試函數的測試，比較了CS算法與螢火蟲算法、人工蜂群算法、粒子群算法的參數及性能，其性能均接近或優于其他標準的優化算法，CS算法作為后起之秀，它的優越性使其廣泛應用于各個研究領域。

5 CS算法存在的問題及展望

CS算法之所以能夠廣泛應用，主要表現在兩個方面：①萊維飛行模式能夠正確協調局部搜索和全局搜索之間的關系，這使得算法在搜索解的精度上更加有效。②控制參數少，較少的參數使它通用性和魯棒性更好。但是，CS算法是一個新型的群智能優化技術，尚處于快速發展階段，還有一些問題尚需要學者們關注，未來的研究方向可歸納如下：

5.1 算法的收斂性

CS算法在實際應用中已被證明是一種有效的優化工具，在收斂性方面，只有文獻 ［6］通過建立Markov鏈模型，分析該Markov鏈的有限齊次性，證明了CS算法滿足隨機搜索算法全局收斂的兩個條件。但是對于CS算法的內部機理的認識還不夠，它的理論研究需要完善，其收斂速度和解的質量需要進一步提高，深入研究CS算法的內部機理，對于它的應用領域的擴展，具有深遠的意義。

5.2 算法的改進

原始的CS算法只能用于求解連續型的優化問題，對于離散型的、組合的、有約束的、多目標的優化問題，CS算法還需進一步研究。對于已有的連續型的優化問題，有步長改進、參數自適應、與其他算法相互耦合等，也存在適應能力不強、搜索效果不夠理想、對復雜問題求解能力有限等缺點，如何探索新的改進方法和策略，提高變量間高度關聯函數的性能，例如如何利用合作協同進化框架來處理復雜函數優化問題，值得我們進一步研究。

5.3 算法的應用

科學與工程實踐中的許多問題都可以歸結為優化問題。相對于ACO、PSO等發展較為完善的仿生智能算法來說，CS算法的應用研究在涉及電力系統、生物醫藥、模糊控制、金融、電子與電磁場等領域還較少，如何找到CS算法及其衍生算法與實際問題的切入點，將CS算法與實際問題相結合，將會有力地推動CS算法的快速發展。相信本文能夠為從事CS算法研究的學者提供有意義的參考和建議。

6 結束語

布谷鳥搜索算法是一種新型元啟發式搜索算法，具有十分廣闊的研究前景。與其他群智能算法相比，其優越性已被眾多學者認可，不僅表現出魯棒性強、通用性好等優點，還具有可移植性、平臺無關性等強大的活力。系統地梳理CS算法的研究現狀以及目前所存在的不足，若能夠對上述問題進行深入研究，將會極大地促進該算法的發展，也將拓展相關技術的研究和應用領域。下一步，將緊跟該領域世界發展趨勢進行研究，以期該算法能夠有效解決更多更復雜的實際問題。

［1］Yang XS.Cuckoo search via Lévy flights ［C］／／Nature ＆Biologically Inspired Computing.World Congress on IEEE，2009：210－214.

［2］LIU Xinni.Application of cuckoo search algorithm in multithreshold image segmentation ［J］.Computer Engineering，2013，39 （7）：274－278.

［4］WANG Fan.Markov model and convergence analysis based on cuckoo search algorithm ［J］.Computer Engineering，2012，38 （11）：180－182 （in Chinese）. ［王凡.基于 CS算法的Markov模型及收斂性分析 ［J］.計算機工程，2012，38（11）：180－182.］

［5］Yang XS.Swarm intelligence and bio－inspired computation：Theory and applications ［M］.Elsevier，2013.

［6］Yang XS.Nature－inspired meta heuristic algorithms ［M］.2nd ed.Luniver Press，2010.

［7］Schreier AL.Ranging patterns of hamadryas baboons：Random walk analyses ［J］.Animal Behaviour，2010，80 （1）：75－87.

［8］Yang XS.Multiobjective cuckoo search for design optimization［J］.Computers ＆ Operations Research，2013，40 （6）：1616－1624.

［9］Michael F Shlesinger.Mathematical physics：Search research［J］.Nature，2006，443 （7109）：281－282.

［10］Pavly.Lévy flights，non－local search and simulated annealing［J］.Journal of Computational Physics，2007，226 （2）：1830－1844.

［11］Reynolds AM，Smith AD，Menzel R，et al.Displaced honeybees perform optimal scal－free search flights ［J］.Ecology，2007，88 （8）：1955－1961.

［12］Layeb A.A novel quantum inspired cuckoo search ［J］.International Journal of B－I Computation，2011，3 （5）：297－305.

［13］ WANG Liying.Bridge erecting machine based on improved cuckoo search algorithm ［J］.Journal of Beijing Jiaotong University，2013，37 （4）：168－173.

［14］HU Xinxin.Improvement cuckoo search algorithm for function optimization problems ［J］.Computer Engineering ＆ Design，2013，34 （10）：3639－3642 （in Chinese）. ［胡欣欣.求解函數優化問題的改進布谷鳥搜索算法 ［J］.計算機工程與設計，2013，34 （10）：3639－3642.］

［15］ZHENG Hongqing.Self－adaptive step cuckoo search algorithm［J］.Computer Engineering and Applications，2013，49 （10）：68－71 （in Chinese）.［鄭洪清.一種自適應步長布谷鳥搜索算法 ［J］.計算機工程與應用，2013，49 （10）：68－71.］

［16］Walton S.Modified cuckoo search ［J］.Chaos，Solitons ＆Fractals，2011，44 （9）：710－718.

［17］Andrew W.A non－random walk down wall street ［M］.Princeton University Press，2011：263－268.

［18］Valian E.Improved cuckoo search algorithm for global optimization ［J］.Int Journal Communications and Information Technology，2011，1 （1）：31－44.

［19］LI Ming.Hybrid optimization algorithm of cuckoo search and DE ［J］.Computer Engineering and Applications，2013，49（9）：57－60 （in Chinese）. ［李明.混合 CS算法的 DE算法［J］.計算機工程與應用，2013，49 （9）：57－60.］

［20］FENG Dengke.Binary cuckoo search algorithm ［J］.Journal of Computer Application，2013，33 （6）：1566－1570 （in Chinese）.［馮登科.二進制布谷鳥搜索算法 ［J］.計算機應用，2013，33 （6）：1566－1570.］

［21］Ghodrati.A hybrid CS／PSO algorithm for global optimization［M］.Intelligent Information and Database Systems，2012：89－98.

［22］Raveendra.DE based job scheduling in grid environments［J］.Journal of Computer Networks，2013，1 （2）：28－31.

［23］WANG Fan.The cuckoo search algorithm based on Gaussian disturbance ［J］.Journal of Xi’an Polytechnic University，2011，25 （4）：566－569 （in Chinese）.［王凡.基于高斯擾動的布谷鳥搜索算法 ［J］.西安工程大學學報，2011，25（4）：566－569.］

［24］Srivastava PR.Automated test data generation using cuckoo search and tabu search （CSTS）algorithm ［J］.Journal of Intelligent Systems，2012，21 （2）：195－224.

［25］Valian E.Improved cuckoo search algorithm for feed forward neural network training ［J］.International Journal of Artificial I＆A，2011，2 （3）：36－43.

［26］CHEN Le.Modified cuckoo search algorithm for solving engineering structural optimization problem ［J］.Application Research of Computers，2014，31 （3）：679－683 （in Chinese）.［陳樂.求解工程結構優化問題的改進布谷鳥搜索算法 ［J］.計算機應用研究，2014，31 （3）：679－683.］

［27］GAO Shutao.Short time traffic flow prediction model based on neural network and cuckoo search algorithm ［J］.Computer Engineering and Applications，2013，49 （9）：106－109（in Chinese）.［高述濤.CS算法優化BP神經網絡的短時交通流 量 預 測 ［J］.計 算 機 工 程 與 應 用，2013，49 （9）：106－109.］

［28］Tiwari V.Face recognition based on cuckoo search algorithm［J］.Indian Journal of Computer Science and Engineering，2012，7 （8）：401－405.

［29］ WU Jiong.Cuckoo search algorithm for solving integer programming ［J］. Mathematical Theory and Applications，2013，33 （3）：99－106 （in Chinese）. ［吳炅.整數規劃的布谷鳥算法 ［J］.數學理論與應用，2013，33 （3）：99－106.］

［30］Li X.Enhancing the performance of cuckoo search algorithm［J］.Neural Computing and Applications，2013，24 （6）：1233－1247.

［31］LAI Jinhui.Application of GCS－SVM model in network traffic prediction ［J］.Computer Engineering and Applications，2013，49 （21）：75－78.