《智能系统学报》：布谷鸟搜索算法研究及其应用进展（吴一全、周建伟）

第15卷第3期 智能系统学报 Vol.15 No.3 2020年5月 CAAI Transactions on Intelligent Systems May 2020 D0:10.11992/tis.201811005 布谷鸟搜索算法研究及其应用进展 吴一全2，周建伟 (1,南京航空航天大学电子信息工程学院，江苏南京211106；2.北京市测绘设计研究院城市空间信息工程北 京市重点实验室，北京100038：3.北大方正集团有限公司数字出版技术国家重点实验室，北京100871) 摘要：为进一步加强布谷鸟算法的搜寻能力并提升收敛速度，加快对算法的研究与应用进程，综述了布谷鸟 算法的原理、研究概况和其他同类群体智能优化算法的比较及发展趋势。首先给出了算法的基本模型和实现 步骤：然后重点阐述了基于发现概率和步长控制量、基于自适应步长、基于混沌理论、与其他算法混合、基于种 群特征和种群变异、结合优化策略及基于种群多样性等方面的改进方法，总结了算法的主要应用领域及其进 展：随后将其与遗传算法、蚁群优化算法、粒子群优化算法及人工蜂群优化算法的优点、缺点及适用性诸方面 进行了对比：最后指出了布谷鸟搜索算法尚存在的缺陷并对进一步的研究方向进行了展望。 关键词：群体智能；布谷鸟搜索算法：启发式算法；寄巢产卵：莱维飞行；自适应步长：混沌：种群多样性 中图分类号：TP301.6文献标志码：A文章编号：1673-4785(2020)03-0435-10 中文引用格式：吴一全，周建伟.布谷鸟搜索算法研究及其应用进展机智能系统学报，2020,15(3)：435-444. 英文引用格式：VU Yiquan,ZHOU Jianwei..Overview of the cuckoo search algorithm and its applications J].CAAI transactions on intelligent systems,2020,15(3):435-444. Overview of the cuckoo search algorithm and its applications WU Yiquan'23,ZHOU Jianwei' (1.College of Electronic and Information Engineering,Nanjing University of Aeronautics and Astronautics,Nanjing 211106,China; 2.Beijing Key Laboratory of Urban Spatial Information Engineering,Beijing Institute of Surveying and Mapping,Beijing 100038, China;3.State Key Laboratory of Digital Publishing Technology,Peking University Founder Group Corp,Beijing 100871,China) Abstract:To improve the searching ability and convergence rate and further accelerate the research and application pro- cess of the algorithm,a review on the basic principles and state of the art and a comparison with other swarm intelligent optimization algorithms are performed,and the development trend is presented here.First,the basic model and steps of the cuckoo search algorithm are elaborated.Then,the improved methods of the cuckoo search algorithms are discussed, such as algorithms based on the discovery probability and step-size control parameter,algorithms based on the adaptive step size,algorithms based on chaos theory,combination algorithms with other algorithms,algorithms based on popula- tion characteristics and variations,combined optimization strategy,and algorithms based on population diversity.Their main application fields and progress are also summarized.Next,the cuckoo search algorithm is compared with a genetic algorithm,ant colony optimization algorithm,particle swarm optimization algorithm,and artificial bee colony algorithm in terms of advantages,disadvantages,and applicable scope.Finally,the existing problems of the algorithm are pointed out,and the research direction is prospected. Keywords:swarm intelligence;cuckoo search algorithm;metaheuristic algorithm;nest spawning;Levy flights;adapt- ive step size;chaotic;population diversity 收稿日期：2018-11-06. 在生物界的许多种群里，个体行为都较为简 基金项目：国家自然科学基金项目(61573183)：城市空间信息 工程北京市重点实验室开放基金项目(2014203)：北 单，例如蚁群、蜂群、鸟群等，然而这些生物个体 大方正集团有限公司数字出版技术国家重点实验室 开放课题项目， 一旦聚集进行沟通合作，行为上可能表现出十分 通信作者：吴一全.E-mail:nuaaimage@163.com 复杂的特征，由此产生了群体智能。群体智能即

DOI: 10.11992/tis.201811005 布谷鸟搜索算法研究及其应用进展 吴一全1,2,3，周建伟1 （1. 南京航空航天大学 电子信息工程学院，江苏 南京 211106; 2. 北京市测绘设计研究院 城市空间信息工程北 京市重点实验室，北京 100038; 3. 北大方正集团有限公司 数字出版技术国家重点实验室，北京 100871） 摘 要：为进一步加强布谷鸟算法的搜寻能力并提升收敛速度，加快对算法的研究与应用进程，综述了布谷鸟 算法的原理、研究概况和其他同类群体智能优化算法的比较及发展趋势。首先给出了算法的基本模型和实现 步骤；然后重点阐述了基于发现概率和步长控制量、基于自适应步长、基于混沌理论、与其他算法混合、基于种 群特征和种群变异、结合优化策略及基于种群多样性等方面的改进方法，总结了算法的主要应用领域及其进 展；随后将其与遗传算法、蚁群优化算法、粒子群优化算法及人工蜂群优化算法的优点、缺点及适用性诸方面 进行了对比；最后指出了布谷鸟搜索算法尚存在的缺陷并对进一步的研究方向进行了展望。 关键词：群体智能；布谷鸟搜索算法；启发式算法；寄巢产卵；莱维飞行；自适应步长；混沌；种群多样性 中图分类号：TP301.6 文献标志码：A 文章编号：1673−4785(2020)03−0435−10 中文引用格式：吴一全, 周建伟. 布谷鸟搜索算法研究及其应用进展 [J]. 智能系统学报, 2020, 15(3): 435–444. 英文引用格式：WU Yiquan, ZHOU Jianwei. Overview of the cuckoo search algorithm and its applications[J]. CAAI transactions on intelligent systems, 2020, 15(3): 435–444. Overview of the cuckoo search algorithm and its applications WU Yiquan1,2,3 ，ZHOU Jianwei1 (1. College of Electronic and Information Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China; 2. Beijing Key Laboratory of Urban Spatial Information Engineering, Beijing Institute of Surveying and Mapping, Beijing 100038, China; 3. State Key Laboratory of Digital Publishing Technology, Peking University Founder Group Corp, Beijing 100871, China) Abstract: To improve the searching ability and convergence rate and further accelerate the research and application pro￾cess of the algorithm, a review on the basic principles and state of the art and a comparison with other swarm intelligent optimization algorithms are performed, and the development trend is presented here. First, the basic model and steps of the cuckoo search algorithm are elaborated. Then, the improved methods of the cuckoo search algorithms are discussed, such as algorithms based on the discovery probability and step-size control parameter, algorithms based on the adaptive step size, algorithms based on chaos theory, combination algorithms with other algorithms, algorithms based on popula￾tion characteristics and variations, combined optimization strategy, and algorithms based on population diversity. Their main application fields and progress are also summarized. Next, the cuckoo search algorithm is compared with a genetic algorithm, ant colony optimization algorithm, particle swarm optimization algorithm, and artificial bee colony algorithm in terms of advantages, disadvantages, and applicable scope. Finally, the existing problems of the algorithm are pointed out, and the research direction is prospected. Keywords: swarm intelligence; cuckoo search algorithm; metaheuristic algorithm; nest spawning; Levy flights; adapt￾ive step size; chaotic; population diversity 在生物界的许多种群里，个体行为都较为简 单，例如蚁群、蜂群、鸟群等，然而这些生物个体 一旦聚集进行沟通合作，行为上可能表现出十分 复杂的特征，由此产生了群体智能。群体智能即 收稿日期：2018−11−06. 基金项目：国家自然科学基金项目 (61573183)；城市空间信息 工程北京市重点实验室开放基金项目 (2014203)；北 大方正集团有限公司数字出版技术国家重点实验室 开放课题项目. 通信作者：吴一全. E-mail：nuaaimage@163.com. 第 15 卷第 3 期 智 能 系 统 学 报 Vol.15 No.3 2020 年 5 月 CAAI Transactions on Intelligent Systems May 2020

·436· 智能系统学报 第15卷 个体借助相互合作由简单的智能行为产生复杂的 用现状；随后就优缺点及适用范围两方面对CS 智能行为，其控制方式不是集中式，而采用分布 算法与其他群体智能算法进行了比较；最后指出 式。群体智能具有自组织性、简单性和可扩充性 了目前CS算法中尚存在的问题及有待研究的方 等特性，突出了在适当的进化机制引导下个体通 向，以期为CS算法的研究提供指导和启迪。 过协同合作而表现出复杂行为的能力。针对这些 行为现象，人们对个体简单的智能行为及协同合 1布谷鸟搜索算法原理 作智能行为等建立数学模型并深入分析，研究种 1.1生物背景 群的协同合作智能行为和强大的处理问题能力的 布谷鸟最特殊的习性是寄巢产卵。大自然 背后机理，目前已提出了许多群体智能算法，攻 中有一些布谷鸟会将自己的卵产在寄主鸟巢中， 破了一些较为困难的优化课题。群智能优化算法 同时布谷鸟也会移除鸟巢中其他卵使得鸟巢中的 将生物界的各种种群中的个体表示为搜寻空间内 卵数量保持相近。因为布谷鸟的卵与寄主的卵相 的点，个体的进化和觅食行为类似优化和搜索阶 比孵化周期更短，孵出的布谷鸟幼雏势必本能地 段；将个体对环境的适应性通过定义目标函数并 把寄主的卵推出卵巢，以此增加自己的存活率， 进行优化求解得以实现：优化与搜寻阶段中用可 提高竞争性。在某些情况下，当布谷鸟寄生其卵 行的较优解代替可行的较劣解的更新过程被类比 时，寄主鸟类会攻击布谷鸟，也有可能发现鸟巢 为个体的优胜劣汰过程或觅食过程，整个群体将 中陌生的卵。这时，寄主鸟类会丢弃布谷鸟所产 会逐步收敛，直至最优解。因此，构成一类以“生 的卵或直接重新筑巢。与寄主鸟类不停地争斗 成+核查”为特点的迭代优化算法。 中，布谷鸟的卵及孵化的幼雏皆沿着仿照寄主鸟 布谷鸟搜索(cuckoo search,CS)算法属于典型 类的方式生长。 的具有迭代搜寻特征的群智能优化算法。作为新 在自然界中，动物会以随机或准随机的方式 型的启发式搜索算法，是以布谷鸟的寄巢产卵特 寻找食物。一般来说，是根据当前的位置或状态 点及少部分生物的莱维飞行(Levy flights)模式为 和到下一位置的转移概率而作出下一次移动，因 参照，由Yang等)于2009年提出。其主要思想 此动物的觅食过程实际上是随机行走，其所选取 是通过随机行走方式产生候选鸟巢以及采用贪婪 的方向可以用数学建模方法来表示。例如，大量 策略更新鸟巢位置，最终使鸟巢位置达到或者接 实验表明，动物界中许多如信天翁、蜜蜂等动物的 近全局最优解1。文献[4]针对CS算法构造了 寻觅食物轨迹符合Levy飞行的典型特性"。Levy Markov链数学模型，验证了CS算法具有全局收 飞行一词出自法国数学家Paul Pierre Levy,.是一 敛特性。 种Markov过程，其步长满足Levy分布，是一种在 布谷鸟搜索算法的优点包括简单、参数少、 短程搜索中穿插长行程的游走方式，如图1所示。 易实现、搜索路径优、易收敛到全局最优且收敛 速度快等，自从提出后就得到人们的关注，目前 已经成为一种活跃的群智能算法$刀。近几年来 国内外众多学者对CS算法及其应用做了较为深 入的研究，但是迄今有关CS算法的综述比较 少。文献[8]简单地介绍了CS算法的发展概况 并比较了几种改进算法，文献[9]详述了CS算法 原理，并将其与遗传算法(genetic algorithm, GA)和粒子群优化(particle swarm optimization, PSO)算法作了比较，但它们都对CS算法的发展 概况论述得不够系统和全面。因此，为了进一步 加快CS算法的研究与应用进程，能够更有效地 图1Levy飞行轨迹 Fig.1 Levy flight track 解决实际问题，需要对CS算法作较全面、系统的 从图1中可以看出，一部分解可以在当前最 总结和评述。本文首先阐述了CS算法的生物背 优值附近进行局部搜索，另一部分解则可以跳出 景、基本模型及实现步骤：然后对当前CS算法的 当前最优值附近搜索，因此Levy飞行可以加大搜 改进研究进行了归纳：其次总结了C$算法的应 寻的区间，使用Ley飞行的优化算法更容易摆脱

个体借助相互合作由简单的智能行为产生复杂的 智能行为，其控制方式不是集中式，而采用分布 式。群体智能具有自组织性、简单性和可扩充性 等特性，突出了在适当的进化机制引导下个体通 过协同合作而表现出复杂行为的能力。针对这些 行为现象，人们对个体简单的智能行为及协同合 作智能行为等建立数学模型并深入分析，研究种 群的协同合作智能行为和强大的处理问题能力的 背后机理，目前已提出了许多群体智能算法，攻 破了一些较为困难的优化课题。群智能优化算法 将生物界的各种种群中的个体表示为搜寻空间内 的点，个体的进化和觅食行为类似优化和搜索阶 段；将个体对环境的适应性通过定义目标函数并 进行优化求解得以实现；优化与搜寻阶段中用可 行的较优解代替可行的较劣解的更新过程被类比 为个体的优胜劣汰过程或觅食过程，整个群体将 会逐步收敛，直至最优解。因此，构成一类以“生 成+核查”为特点的迭代优化算法[1]。 布谷鸟搜索 (cuckoo search, CS) 算法属于典型 的具有迭代搜寻特征的群智能优化算法。作为新 型的启发式搜索算法，是以布谷鸟的寄巢产卵特 点及少部分生物的莱维飞行 (Levy flights) 模式为 参照，由 Yang 等 [2] 于 2009 年提出。其主要思想 是通过随机行走方式产生候选鸟巢以及采用贪婪 策略更新鸟巢位置，最终使鸟巢位置达到或者接 近全局最优解[3]。文献 [4] 针对 CS 算法构造了 Markov 链数学模型，验证了 CS 算法具有全局收 敛特性。 布谷鸟搜索算法的优点包括简单、参数少、 易实现、搜索路径优、易收敛到全局最优且收敛 速度快等，自从提出后就得到人们的关注，目前 已经成为一种活跃的群智能算法[5-7]。近几年来 国内外众多学者对 CS 算法及其应用做了较为深 入的研究，但是迄今有关 CS 算法的综述比较 少。文献 [8] 简单地介绍了 CS 算法的发展概况 并比较了几种改进算法，文献 [9] 详述了 CS 算法 原理，并将其与遗传算法 (genetic algorithm, GA) 和粒子群优化 (particle swarm optimization, PSO) 算法作了比较，但它们都对 CS 算法的发展 概况论述得不够系统和全面。因此，为了进一步 加快 CS 算法的研究与应用进程，能够更有效地 解决实际问题，需要对 CS 算法作较全面、系统的 总结和评述。本文首先阐述了 CS 算法的生物背 景、基本模型及实现步骤；然后对当前 CS 算法的 改进研究进行了归纳；其次总结了 CS 算法的应 用现状；随后就优缺点及适用范围两方面对 CS 算法与其他群体智能算法进行了比较；最后指出 了目前 CS 算法中尚存在的问题及有待研究的方 向，以期为 CS 算法的研究提供指导和启迪。 1 布谷鸟搜索算法原理 1.1 生物背景 布谷鸟最特殊的习性是寄巢产卵[10]。大自然 中有一些布谷鸟会将自己的卵产在寄主鸟巢中， 同时布谷鸟也会移除鸟巢中其他卵使得鸟巢中的 卵数量保持相近。因为布谷鸟的卵与寄主的卵相 比孵化周期更短，孵出的布谷鸟幼雏势必本能地 把寄主的卵推出卵巢，以此增加自己的存活率， 提高竞争性。在某些情况下，当布谷鸟寄生其卵 时，寄主鸟类会攻击布谷鸟，也有可能发现鸟巢 中陌生的卵。这时，寄主鸟类会丢弃布谷鸟所产 的卵或直接重新筑巢。与寄主鸟类不停地争斗 中，布谷鸟的卵及孵化的幼雏皆沿着仿照寄主鸟 类的方式生长。 在自然界中，动物会以随机或准随机的方式 寻找食物。一般来说，是根据当前的位置或状态 和到下一位置的转移概率而作出下一次移动，因 此动物的觅食过程实际上是随机行走，其所选取 的方向可以用数学建模方法来表示。例如，大量 实验表明，动物界中许多如信天翁、蜜蜂等动物的 寻觅食物轨迹符合 Levy 飞行的典型特性[11]。Levy 飞行一词出自法国数学家 Paul Pierre Levy，是一 种 Markov 过程，其步长满足 Levy 分布，是一种在 短程搜索中穿插长行程的游走方式[12] ，如图 1 所示。 图 1 Levy 飞行轨迹 Fig. 1 Levy flight track 从图 1 中可以看出，一部分解可以在当前最 优值附近进行局部搜索，另一部分解则可以跳出 当前最优值附近搜索，因此 Levy 飞行可以加大搜 寻的区间，使用 Levy 飞行的优化算法更容易摆脱 ·436· 智 能 系 统 学 报 第 15 卷

第3期 吴一全，等：布谷鸟搜索算法研究及其应用进展 ·437· 局部极值点。文献[13]在PS0优化算法中引入 1.3CS算法的实现步骤 Levy飞行，克服了易收敛到局部最优的缺陷，取 综合CS算法上述2种更新方式，可得到CS 得了令人满意的效果。Levy飞行能较大地提高 算法的以下实现步骤： 不确定环境下的资源搜索效率。 1)初始化算法的基本参数：鸟巢数目，发现 1.2CS算法的基本模型 概率P。,搜索精度ε或最大迭代次数T,并以随 针对布谷鸟的寄巢产卵习性，CS算法假定如 机方式生成n个鸟巢的初始位置X(i=1,2,…,n), 下3个条件： 这里X=[x2,…x,d为待求解问题的维数，求 1)布谷鸟每次仅仅产一只卵，孵化时鸟巢的 解初始鸟巢位置的适应度函数值，并得到初始最 选取是随机的： 优适应度函数值； 2)在每组鸟巢中，最好的鸟巢可以被保留到 2)根据式(2)(4)更新当前鸟巢位置； 下一代； 3)求出当前全部鸟巢的适应度函数值，若在 3)可以选择的鸟巢数目一定，鸟巢主人察觉 适应度函数值上新鸟巢优于原鸟巢，则替换原鸟 布谷鸟卵的概率为P.。 巢位置； CS算法的鸟巢坐标位置与解空间中的解一 4)根据式（⑤）更新鸟巢的位置，依然采用适应 一对应，在以上3个假定基础上，CS算法利用 度函数值较好的鸟巢位置替换原鸟巢位置： Levy飞行随机行走方式和偏好随机行走方式更 5)得到当代最优的适应度函数值，且和上一 新鸟巢位置。 代最优适应度函数值比较，保留一组最佳适应度 1)Ley飞行随机行走。利用式(I)产生新解。 函数值的鸟巢位置，迭代次数加1： x1=x+a⊕L(),i=1,2,,n (1) 6)如果未满足搜索精度要求或未达到最大迭 式中：x和x分别表示第t代和第t+1代第i个 代次数，那么回到2)，反之继续： 鸟巢的位置；α表示步长控制量；⊕为点对点乘 7)得到全局最优位置。 法；n为鸟巢个数，即可行解个数；L()为Levy随 机搜索路径，且L()~(1<d≤3)，其中u表示 2布谷鸟搜索算法研究现状 由Levy飞行得到的随机步长。 CS算法自从2009年发表后就受到许多重 由于对Levy分布进行积分运算比较困难，文 视，并得到大量的研究。目前关于C$算法的研 献[l4提出了使用Mantegana算法来进行计算，即 究主要分为两个方面：算法的改进和算法的应用。 =+stepsize randn(),i=1,2....n (2) 2.1CS算法的改进 式中：randn(为满足高斯分布的随机函数：stepsize= 1)基于P.和a的改进 aS⊕(x-xe),a通常取0.01，xa为第t代最优 在CS算法中，发现概率P.和步长控制量a 鸟巢位置。S通过式(3)求得： 作为关键的两个参数，在迭代过程中通常保持不 S=·IN0,v~N0,） (3) 变。但在寻优过程中，若P。一直较大，α较小，会 式中：c,=1,B=1.5,m按式(4)计算： 缩短算法收敛时间，但是易收敛到局部最优；而 r1+B)·sin(/2) 若P。较小，α较大，则会使收敛速度变慢。因此 .={T0+/2B-29-r (4) 可对P。和α进行调整以改进CS算法。 2)偏好随机行走。仿照寄主察觉布谷鸟的卵 文献[15]使P.和α随迭代次数变化： 后将其丢弃的想法和原理。具体操作如下：得到 Pa(t)=Pamin+(Pa.max -Pa.min) (N-t)" (6) 一个满足[0,1]均匀分布的随机数r,并与发现概 率P。∈0,1]进行比较，若r>P。,则按式（⑤）得到 a(t)=amin+(amax-amin). N-t)": N (7 新解： 式中：t为当前迭代次数；W表示总迭代次数； x=x+r(x-x),i=1,2,…,n (5) Pamx、Pamin表示P。的最大值与最小值；ams、amn 式中x与表示第t代的随机解。反之，若r≤P, 表示α的最大值与最小值；m,和m2为非线性因 则保持不变，即x1=xo 子，取值大于0，用来控制P。和α的下降速率，m 通过上述2种方式所得新解均采用贪婪选择 应小于1，相反m2应大于1。实验证明了改进的 操作，即得到新解后，将新解和原解的适应度函 CS算法能减少时间并提升精度。 数值进行比较，与原解相比，如果新解较优，那么 文献[I6]按照Rechenberg原则，即将“所有变 将新解取代原解，反之保持原解不变。 异的成功比例应该保持在1/5原则”作为调整策

局部极值点。文献 [13] 在 PSO 优化算法中引入 Levy 飞行，克服了易收敛到局部最优的缺陷，取 得了令人满意的效果。Levy 飞行能较大地提高 不确定环境下的资源搜索效率。 1.2 CS 算法的基本模型 针对布谷鸟的寄巢产卵习性，CS 算法假定如 下 3 个条件： 1) 布谷鸟每次仅仅产一只卵，孵化时鸟巢的 选取是随机的； 2) 在每组鸟巢中，最好的鸟巢可以被保留到 下一代； Pα 3) 可以选择的鸟巢数目一定，鸟巢主人察觉 布谷鸟卵的概率为 。 CS 算法的鸟巢坐标位置与解空间中的解一 一对应，在以上 3 个假定基础上，CS 算法利用 Levy 飞行随机行走方式和偏好随机行走方式更 新鸟巢位置。 1) Levy 飞行随机行走。利用式 (1) 产生新解。 x t+1 i = x t i +α⊕ L(λ), i = 1,2,· · ·,n (1) x t i x t+1 i t t+1 i α ⊕ n L(λ) L(λ) ∼ u −λ (1 < λ ⩽ 3) u 式中： 和 分别表示第 代和第 代第 个 鸟巢的位置； 表示步长控制量； 为点对点乘 法； 为鸟巢个数，即可行解个数； 为 Levy 随 机搜索路径，且 ，其中 表示 由 Levy 飞行得到的随机步长。 由于对 Levy 分布进行积分运算比较困难，文 献 [14] 提出了使用 Mantegana 算法来进行计算，即 x t+1 i = x t i +stepsize⊕randn(), i = 1,2,· · ·,n (2) randn() stepsize = α· S ⊕(x t i − x t best) α x t best t S 式中： 为满足高斯分布的随机函数； ， 通常取 0.01， 为第 代最优 鸟巢位置。 通过式 (3) 求得： S = u |v| 1/β , u ∼ N(0,σ2 u ), v ∼ N(0,σ2 v ) (3) 式中：σv = 1， β = 1.5，σu 按式 (4) 计算： σu = { Γ(1+β)·sin(πβ/2) Γ [ (1+β)/2 ] · β · 2 (β−1)/2 }1/β (4) [0,1] r Pα ∈ [0,1] r > Pa 2) 偏好随机行走。仿照寄主察觉布谷鸟的卵 后将其丢弃的想法和原理。具体操作如下：得到 一个满足 均匀分布的随机数 ，并与发现概 率 进行比较，若 ，则按式 (5) 得到 新解： x t+1 i = x t i +r(x t j − x t k ), i = 1,2,· · ·,n (5) x t j x t k t r ⩽ Pa x t+1 i = x t i 式中 与 表示第 代的随机解。反之，若 ， 则保持不变，即 。 通过上述 2 种方式所得新解均采用贪婪选择 操作，即得到新解后，将新解和原解的适应度函 数值进行比较，与原解相比，如果新解较优，那么 将新解取代原解，反之保持原解不变。 1.3 CS 算法的实现步骤 综合 CS 算法上述 2 种更新方式，可得到 CS 算法的以下实现步骤： n Pa ε T n Xi(i = 1,2,· · ·,n) Xi = [x1 x2,··· xd] T d 1) 初始化算法的基本参数：鸟巢数目 ，发现 概率 ，搜索精度 或最大迭代次数 ，并以随 机方式生成 个鸟巢的初始位置 ， 这里 ， 为待求解问题的维数，求 解初始鸟巢位置的适应度函数值，并得到初始最 优适应度函数值； 2) 根据式 (2)~(4) 更新当前鸟巢位置； 3) 求出当前全部鸟巢的适应度函数值，若在 适应度函数值上新鸟巢优于原鸟巢，则替换原鸟 巢位置； 4) 根据式 (5) 更新鸟巢的位置，依然采用适应 度函数值较好的鸟巢位置替换原鸟巢位置； 5) 得到当代最优的适应度函数值，且和上一 代最优适应度函数值比较，保留一组最佳适应度 函数值的鸟巢位置，迭代次数加 1； 6) 如果未满足搜索精度要求或未达到最大迭 代次数，那么回到 2)，反之继续； 7) 得到全局最优位置。 2 布谷鸟搜索算法研究现状 CS 算法自从 2009 年发表后就受到许多重 视，并得到大量的研究。目前关于 CS 算法的研 究主要分为两个方面：算法的改进和算法的应用。 2.1 CS 算法的改进 1) 基于 Pa 和 α 的改进 Pa α Pa α Pa α Pa α 在 CS 算法中，发现概率 和步长控制量 作为关键的两个参数，在迭代过程中通常保持不 变。但在寻优过程中，若 一直较大， 较小，会 缩短算法收敛时间，但是易收敛到局部最优；而 若 较小， 较大，则会使收敛速度变慢。因此 可对 和 进行调整以改进 CS 算法。 文献 [15] 使 Pa 和 α 随迭代次数变化： Pa(t) = Pa,min +(Pa,max − Pa,min)· (N −t N )m1 (6) α(t) = αmin +(αmax −αmin)· (N −t N )m2 (7) t N Pa,max Pa,min Pa αmax αmin α m1 m2 Pa α m1 m2 式中： 为当前迭代次数； 表示总迭代次数； 、 表示 的最大值与最小值； 、 表示 的最大值与最小值； 和 为非线性因 子，取值大于 0，用来控制 和 的下降速率， 应小于 1，相反 应大于 1。实验证明了改进的 CS 算法能减少时间并提升精度。 1/5 文献 [16] 按照 Rechenberg 原则，即将“所有变 异的成功比例应该保持在 原则”作为调整策 第 3 期 吴一全，等：布谷鸟搜索算法研究及其应用进展 ·437·

·438· 智能系统学报 第15卷 略对P。和a修正： 性搜索与全局性搜索之间的均衡。通过实验证明 Pa(t)fe. R>0.3 改进的方法和标准C$算法比较，在迭代后期所 P.(t+1)= P.(), 0.2≤R≤0.3 (8) 得精度和达到的速度均有提升。文献[23]同时利 P.(t)/fp,R<0.2 用自适应调整步长与自适应发现概率来对算法进 a)f,R>0.3 行改进，因此提升了结果的准确性。 (t+1)= a(t),0.2≤R≤0.3 (9) a(t)/f,R<0.2 动态地调整步长，使得C$算法具有更好的 式中：R为新解改善的比例；∫。为发现概率的学习 自适应性，从而算法的求解速度加快，收敛精度 因子；为步长控制量的学习因子。针对6个函 也有相应的提升，但是当遇到复杂多模态问题及 数的测试结果表明该改进算法行之有效。 优化高维空间时受到局限。 文献[17]采用余弦递减策略实现P。的动态 3)基于混沌理论的改进 变化： 在原始C$算法中，由于采用随机行走模式， πt-1 其单一性导致搜索时随机性强，将混沌理论引入 P.()=P.+P (10) CS算法中，可以使算法更容易跳出局部最优点， 式中：t表示当前迭代次数；N表示总迭代次数； 提升算法在迭代更新后期的收敛速度。 Pamax与Pa.min分别为P。的最大值与最小值。 文献[24]应用12个混沌映射来调整原始 文献[18-19]同样将P。和α调整成关于迭代 CS算法中使用的步长，通过测试27个基准函数 次数的自适应方程，以提高算法的准确性和收敛 和一个工程案例，验证了改进的算法，进一步提 速度。通过自适应调整P。和α参数，加快了算法 高了CS算法的评价指标。 迭代后期的收敛速度，但是对于算法前期收敛速 文献[25]借用混沌映射对鸟巢位置进行初始 度的提升有限，有待进一步改进。 化，增加了种群的多样性，并将改进后的混沌布 2)基于自适应步长的改进 谷鸟算法运用于图像增强中，实验从视觉分析和 CS算法利用Levy飞行机制得到步长是盲目 定量分析两方面证明了混沌CS算法优于其他同 的，缺乏自适应性，无法保证快速收敛，为此依据 类算法。 不同搜寻阶段中所得结果，对步长大小进行自适 文献[26]采用Logistic映射生成混沌序列，将 应调整。 其映射到鸟巢位置的更新过程中，其次运用混沌 文献[20]提出的自适应调整步长策略为 CS算法进行高光谱影像波段选择，实验结果证明 Si=Smin+(S max-S min)di (11) 混沌C$算法的搜寻性能更优，最终的分类更为 式中：Smax和Smm分别表示最大步长和最小步 精确。 长。d定义为 4)与其他算法混合的改进 d,=lr rbcall 文献[27]组合PSO和CS两种优化方法，把 (12) dmax PSO的解融入CS方法中鸟巢位置的迭代过程。 式中：m:表示第i个鸟巢位置；e表示此时最佳 其基本思想是：在每次进行更新迭代时，先利用 状态的鸟巢位置；dax表示其他鸟巢与当前的最 P$O算法对初始位置进行更新，得到一组最优的 优位置的最大距离。通过实验证明这一改进方法 粒子位置P:=[pp2…P…PJ「和一个全局最优位 能快速地达到全局最优。 置P6,保留全局最优解P,并将这组粒子位置的 文献[21]结合迭代次数及鸟巢的适应度值给 最优解P:代替CS算法里的相应位置继续更新。 出了自适应选取步长的另一种模型： 该方法既保留了PSO算法的搜索特性，又兼顾了 S+1)= CS算法在搜索全局最优解上的优点，提高了求解 (13) 精度。文献[28]在偏好随机游动的鸟巢更新公式 式中：t代表当前迭代次数；f)是第i个鸟巢位 中引入全局最优导向算法，使被保留的鸟巢也向 置的第t代适应度值；无m(①为第t代最优适应度 最优的方向游动，增加了鸟巢的多样性，提高了 值；天()为第t代最差适应度值。仿真结果验 收敛速度。文献[29]将人工蜂群优化算法和 证了该方法可更高效地搜寻到局部最优解或次优解。 CS算法相融合，达到算法的局部及全局搜索性能 文献[22]利用了当前解与最优解间的距离， 的均衡，使算法的精度得到提升。文献[30]在迭 距离较长则增加步长，距离较短则减小步长，以 代过程中加入正交交叉运算，C$算法的搜寻能力 此实现步长的自适应动态更新，达到算法的局部 有所提高，同时引入外部存档机制以此维持一段

略对 Pa 和 α 修正： Pa(t+1) =    Pa(t)· fp, R > 0.3 Pa(t), 0.2 ⩽ R ⩽ 0.3 Pa(t)/ fp , R < 0.2 (8) α(t+1) =    α(t)· fα, R > 0.3 α(t), 0.2 ⩽ R ⩽ 0.3 α(t)/ fα, R < 0.2 (9) R fp fα 式中： 为新解改善的比例； 为发现概率的学习 因子； 为步长控制量的学习因子。针对 6 个函 数的测试结果表明该改进算法行之有效。 文献 [17] 采用余弦递减策略实现 Pa 的动态 变化： Pa(t) = Pa,max cos( π 2 · t−1 N +1 ) + Pa,min (10) t N Pa,max Pa,min Pa 式中： 表示当前迭代次数； 表示总迭代次数； 与 分别为 的最大值与最小值。 Pa α Pa α 文献 [18-19] 同样将 和 调整成关于迭代 次数的自适应方程，以提高算法的准确性和收敛 速度。通过自适应调整 和 参数，加快了算法 迭代后期的收敛速度，但是对于算法前期收敛速 度的提升有限，有待进一步改进。 2) 基于自适应步长的改进 CS 算法利用 Levy 飞行机制得到步长是盲目 的，缺乏自适应性，无法保证快速收敛，为此依据 不同搜寻阶段中所得结果，对步长大小进行自适 应调整。 文献 [20] 提出的自适应调整步长策略为 S i = S min +(S max −S min)di (11) S max S min di 式中： 和 分别表示最大步长和最小步 长。 定义为 di = ∥ni −nbest∥ dmax (12) ni i nbest dmax 式中： 表示第 个鸟巢位置； 表示此时最佳 状态的鸟巢位置； 表示其他鸟巢与当前的最 优位置的最大距离。通过实验证明这一改进方法 能快速地达到全局最优。 文献 [21] 结合迭代次数及鸟巢的适应度值给 出了自适应选取步长的另一种模型： S i(t+1) = ( 1 t )|(fbest(t)−fi(t))/(fbest(t)−fworst(t))| (13) t fi(t) i t fbest(t) t fworst(t) t 式中： 代表当前迭代次数； 是第 个鸟巢位 置的第 代适应度值； 为第 代最优适应度 值； 为第 代最差适应度值。仿真结果验 证了该方法可更高效地搜寻到局部最优解或次优解。 文献 [22] 利用了当前解与最优解间的距离， 距离较长则增加步长，距离较短则减小步长，以 此实现步长的自适应动态更新，达到算法的局部 性搜索与全局性搜索之间的均衡。通过实验证明 改进的方法和标准 CS 算法比较，在迭代后期所 得精度和达到的速度均有提升。文献 [23] 同时利 用自适应调整步长与自适应发现概率来对算法进 行改进，因此提升了结果的准确性。 动态地调整步长，使得 CS 算法具有更好的 自适应性，从而算法的求解速度加快，收敛精度 也有相应的提升，但是当遇到复杂多模态问题及 优化高维空间时受到局限。 3) 基于混沌理论的改进 在原始 CS 算法中，由于采用随机行走模式， 其单一性导致搜索时随机性强，将混沌理论引入 CS 算法中，可以使算法更容易跳出局部最优点， 提升算法在迭代更新后期的收敛速度。 文献 [24] 应用 12 个混沌映射来调整原始 CS 算法中使用的步长，通过测试 27 个基准函数 和一个工程案例，验证了改进的算法，进一步提 高了 CS 算法的评价指标。 文献 [25] 借用混沌映射对鸟巢位置进行初始 化，增加了种群的多样性，并将改进后的混沌布 谷鸟算法运用于图像增强中，实验从视觉分析和 定量分析两方面证明了混沌 CS 算法优于其他同 类算法。 文献 [26] 采用 Logistic 映射生成混沌序列，将 其映射到鸟巢位置的更新过程中，其次运用混沌 CS 算法进行高光谱影像波段选择，实验结果证明 混沌 CS 算法的搜寻性能更优，最终的分类更为 精确。 4) 与其他算法混合的改进 Pi = [p1 p2 · · · pi · · · pn] T Pb Pb Pi 文献 [27] 组合 PSO 和 CS 两种优化方法，把 PSO 的解融入 CS 方法中鸟巢位置的迭代过程。 其基本思想是：在每次进行更新迭代时，先利用 PSO 算法对初始位置进行更新，得到一组最优的 粒子位置 和一个全局最优位 置 ，保留全局最优解 ，并将这组粒子位置的 最优解 代替 CS 算法里的相应位置继续更新。 该方法既保留了 PSO 算法的搜索特性，又兼顾了 CS 算法在搜索全局最优解上的优点，提高了求解 精度。文献 [28] 在偏好随机游动的鸟巢更新公式 中引入全局最优导向算法，使被保留的鸟巢也向 最优的方向游动，增加了鸟巢的多样性，提高了 收敛速度。文献 [29] 将人工蜂群优化算法和 CS 算法相融合，达到算法的局部及全局搜索性能 的均衡，使算法的精度得到提升。文献 [30] 在迭 代过程中加入正交交叉运算，CS 算法的搜寻能力 有所提高，同时引入外部存档机制以此维持一段 ·438· 智 能 系 统 学 报 第 15 卷

第3期 吴一全，等：布谷鸟搜索算法研究及其应用进展 ·439· 时间里的种群状况，实验表明提出的策略能提高 管网调压阀优化模型，结果显示，该方法更好地 收敛速度。 降低了漏损。文献「41]针对配电系统中在电容器 上述的改进方法有效地改善了CS算法的性 开关约束条件下的分流电容器放置问题，利用 能，但是对于多维问题，由于可能存在维间的干 CS算法作为优化工具，设计了最佳的电容器分配 扰，统一更新解的每一维会对算法求解的准确性 方案，结果证明该方法可以降低系统中的峰值负 产生影响，使得搜寻效果不够理想。 载损耗和容量成本。文献[42]在设计现代农场的 5)基于种群特征和种群变异的改进 集成电力系统中引入C$算法，对影响电力系统 文献[31]在算法框架中引入如年龄结构、变 性能的特定部件的选择进行优化，结果表明此系 异成功率等种群特征的反馈信息，自适应地调节 统取得了很好的效果。文献[43]在多机电力系统 算法参数，提升了CS优化方法的局部搜索性能， 最优稳定器(PSS)设计中，用CS算法调整PSS的 针对8个函数的测试结果表明了它具有较好的收 参数，通过在不同的工作和干扰条件下的实验证 敛特性。文献[32]利用合作协同进化框架的思 明了CS算法在提供良好阻尼特性方面的有效性。 想，对种群的解向量进行平均分解，得到若干子 2)资源分配 向量，并对每个子向量利用CS算法进行更新，最 文献[44]利用交叉与变异操作改进离散 后重新组合成解向量，有效地改善了CS算法的 C$算法，并将其引入敌我辨认系统的干扰资源分 性能。但是此类改进方法会使目标函数计算的次 配问题，仿真分析表明，该方法能更好地解决干 数增多，使得算法变得复杂，寻优时间加长。 扰资源的一对一，多对少分配问题。文献[45]在 6)结合优化策略的改进 解决可靠性冗余分配问题时，在多个约束条件下 文献33]结合全局随机扰动策略加快算法收 使用CS算法对组件或子系统的可靠性目标进行 敛速度，引入模拟退火机制防止算法陷入局部最 设置，仿真结果表明和现有同类方法比较，CS算 优，实验结果证明了该算法在精度和稳定性方面 法优化求得的解更为精确。文献[46]涉及具有执 的优势。文献[34]引人均衡单进化函数评价策 行器故障的分布式结构变型飞机的控制分配问 略，避免了多维度之间互相干扰。但是此类方法 题，将执行器控制分配转换成整数规划，并使用 在搜索速度上有待提高。 改进的CS算法来获得实际的执行器控制分配指 7)基于种群多样性的改进 令，实验结果表明该方法得到的分配结果更加精确。 文献「35]借助多策略差分操作来提高种群的 3)多目标优化 多样性，并增加排队优选机制，避免陷入局部极 文献「47]针对作业车间多目标调度的问题， 值，加快搜索进程。文献[36]通过移民算子进行 在CS算法中利用帕累托存档保存所有非支配 各种群间的信息交流，利用多个种群同时进行全 解，并利用改进的算法寻找到最优解，测试结果 局探索和局部开发，提高全局寻优性能。 表明CS算法相比其他方法，所求解更加有效。 8)其他方法 文献[48]在CS算法中引入交叉和选择算子，增 文献[37]使用正交学习的搜寻方式以改善 加了种群的多样性，并将其用于板翅式换热器 CS优化方法的搜索能力。文献[38]将逐维改进 (PFHEs)的多目标优化设计，通过仿真实验证明 的思想引入CS算法中，改进了鸟巢飞行步长的 CS算法拥有更精确的优化结果。文献[49]利用 调整方法，使算法收敛速度加快，求解精度有所 自适应CS算法解决多目标函数的优化问题，有 提高。文献[39]利用模式搜索趋化机制的局部寻 效地改善了求解的性能。 优能力加强局部求解，同时采用自适应竞争机制 4)图像处理 来改进CS算法，测试结果验证了其全局搜寻性 最近几年，在图像处理许多领域采用了C$ 能优，所求得的结果精度高。 算法。文献[50]利用CS算法的并行寻优性能加 2.2CS算法的应用 快图像多阈值分割中最优阈值的搜索过程，取得 C$算法因其需要较少的参数、实现简单、高 了更好的分割结果。文献[5l]采用非完全Beta 效等优点，已经成为当下群智能算法活跃的研究 函数灰度变换达到增强图像的目的，并将CS算 分支之一。至今为止，C$算法通常应用于下列领域。 法用于参数的自适应寻优，实验结果表明该方法 1)水电系统 效率更高，鲁棒性更强。文献[52]将Tent映射生 文献[40]采用CS算法确定压力调节阀的数 成的混沌序列用于优化布谷鸟算法，用改进的布 量、最佳安装位置和最佳操作模式，建立了给水 谷鸟算法来搜索二维Renyi灰度熵最优阈值，提

时间里的种群状况，实验表明提出的策略能提高 收敛速度。 上述的改进方法有效地改善了 CS 算法的性 能，但是对于多维问题，由于可能存在维间的干 扰，统一更新解的每一维会对算法求解的准确性 产生影响，使得搜寻效果不够理想。 5) 基于种群特征和种群变异的改进 文献 [31] 在算法框架中引入如年龄结构、变 异成功率等种群特征的反馈信息，自适应地调节 算法参数，提升了 CS 优化方法的局部搜索性能， 针对 8 个函数的测试结果表明了它具有较好的收 敛特性。文献 [32] 利用合作协同进化框架的思 想，对种群的解向量进行平均分解，得到若干子 向量，并对每个子向量利用 CS 算法进行更新，最 后重新组合成解向量，有效地改善了 CS 算法的 性能。但是此类改进方法会使目标函数计算的次 数增多，使得算法变得复杂，寻优时间加长。 6) 结合优化策略的改进 文献 [33] 结合全局随机扰动策略加快算法收 敛速度，引入模拟退火机制防止算法陷入局部最 优，实验结果证明了该算法在精度和稳定性方面 的优势。文献 [34] 引入均衡单进化函数评价策 略，避免了多维度之间互相干扰。但是此类方法 在搜索速度上有待提高。 7) 基于种群多样性的改进 文献 [35] 借助多策略差分操作来提高种群的 多样性，并增加排队优选机制，避免陷入局部极 值，加快搜索进程。文献 [36] 通过移民算子进行 各种群间的信息交流，利用多个种群同时进行全 局探索和局部开发，提高全局寻优性能。 8) 其他方法 文献 [37] 使用正交学习的搜寻方式以改善 CS 优化方法的搜索能力。文献 [38] 将逐维改进 的思想引入 CS 算法中，改进了鸟巢飞行步长的 调整方法，使算法收敛速度加快，求解精度有所 提高。文献 [39] 利用模式搜索趋化机制的局部寻 优能力加强局部求解，同时采用自适应竞争机制 来改进 CS 算法，测试结果验证了其全局搜寻性 能优，所求得的结果精度高。 2.2 CS 算法的应用 CS 算法因其需要较少的参数、实现简单、高 效等优点，已经成为当下群智能算法活跃的研究 分支之一。至今为止，CS 算法通常应用于下列领域。 1) 水电系统 文献 [40] 采用 CS 算法确定压力调节阀的数 量、最佳安装位置和最佳操作模式，建立了给水 管网调压阀优化模型，结果显示，该方法更好地 降低了漏损。文献 [41] 针对配电系统中在电容器 开关约束条件下的分流电容器放置问题，利用 CS 算法作为优化工具，设计了最佳的电容器分配 方案，结果证明该方法可以降低系统中的峰值负 载损耗和容量成本。文献 [42] 在设计现代农场的 集成电力系统中引入 CS 算法，对影响电力系统 性能的特定部件的选择进行优化，结果表明此系 统取得了很好的效果。文献 [43] 在多机电力系统 最优稳定器 (PSS) 设计中，用 CS 算法调整 PSS 的 参数，通过在不同的工作和干扰条件下的实验证 明了 CS 算法在提供良好阻尼特性方面的有效性。 2) 资源分配 文 献 [44] 利用交叉与变异操作改进离 散 CS 算法，并将其引入敌我辨认系统的干扰资源分 配问题，仿真分析表明，该方法能更好地解决干 扰资源的一对一，多对少分配问题。文献 [45] 在 解决可靠性冗余分配问题时，在多个约束条件下 使用 CS 算法对组件或子系统的可靠性目标进行 设置，仿真结果表明和现有同类方法比较，CS 算 法优化求得的解更为精确。文献 [46] 涉及具有执 行器故障的分布式结构变型飞机的控制分配问 题，将执行器控制分配转换成整数规划，并使用 改进的 CS 算法来获得实际的执行器控制分配指 令，实验结果表明该方法得到的分配结果更加精确。 3) 多目标优化 文献 [47] 针对作业车间多目标调度的问题， 在 CS 算法中利用帕累托存档保存所有非支配 解，并利用改进的算法寻找到最优解，测试结果 表明 CS 算法相比其他方法，所求解更加有效。 文献 [48] 在 CS 算法中引入交叉和选择算子，增 加了种群的多样性，并将其用于板翅式换热器 (PFHEs) 的多目标优化设计，通过仿真实验证明 CS 算法拥有更精确的优化结果。文献 [49] 利用 自适应 CS 算法解决多目标函数的优化问题，有 效地改善了求解的性能。 4) 图像处理 最近几年，在图像处理许多领域采用了 CS 算法。文献 [50] 利用 CS 算法的并行寻优性能加 快图像多阈值分割中最优阈值的搜索过程，取得 了更好的分割结果。文献 [51] 采用非完全 Beta 函数灰度变换达到增强图像的目的，并将 CS 算 法用于参数的自适应寻优，实验结果表明该方法 效率更高，鲁棒性更强。文献 [52] 将 Tent 映射生 成的混沌序列用于优化布谷鸟算法，用改进的布 谷鸟算法来搜索二维 Renyi 灰度熵最优阈值，提 第 3 期 吴一全，等：布谷鸟搜索算法研究及其应用进展 ·439·