布谷鸟搜索算法研究综述

兰少峰，刘 升

（上海工程技术大学 管理学院，上海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.