·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 卷