1.概述
杜鹃是一种迷人的鸟类，不仅因为它会唱歌，还因为它激进的繁殖策略，其中包括将蛋产入其它鸟类的巢穴之中。因此，这种鸟完全将其应承担的父母责任转移到其它物种身上。每种杜鹃都会产下某种颜色和大小的蛋，以便更好地匹配各种养父母的蛋。扔进其它鸟巢的杜鹃雏鸟通常比鸟巢主人自己的雏鸟更大、更强壮，所以杜鹃需要更多的食物。在发育过程中，霍奇森（Hodgson）的杜鹃雏鸟在翅膀上以开放喙的形式发展出一种特殊的图案，这令它们能够从养父母那里获得更多的食物。杜鹃并不是唯一表现出这种特征的鸟类。在至少80种鸟类中都发现了筑巢寄生。此外，这种现象在某些种群的社会性昆虫中很普遍—大黄蜂、蜜蜂、和蚂蚁，它们的雌性渗透到另一个繁殖地，杀死原本的女王并产卵。一些鱼类也存在巢穴寄生，例如来自非洲坦噶尼喀湖（LakeTanganyika）的鲶鱼，它们将卵扔给其它在嘴里孵化鱼卵的鱼类。
杜鹃搜索是杨（Yang）和Deb于年开发的最新型自然启发式算法之一。它基于一些杜鹃物种的寄生。该算法已由所谓的Levy飞行进一步改进，远超简单的各向同性随机游走方法。
2.算法说明
杜鹃优化算法（COA）用于连续非线性优化。COA的灵感来自这种鸟的生活方式。优化算法基于物种产蛋繁殖的特点。像其它进化方法一样，COA从初始种群开始。该算法的基础是争夺生存权。在竞争生存的同时，一些鸟类会死亡。幸存的杜鹃会搬到更好的地方，开始繁殖和产蛋。最后，幸存的杜鹃会收敛这样的方式，如此杜鹃社会获得了相似的适应度。这种方法的主要优点是它的简单性：杜鹃搜索只需要四个可理解的参数，因此调优变得不费吹灰之力。在杜鹃搜索算法中，鸟巢中原来的蛋被解释为优化问题的可能解，杜鹃蛋代表新的解。该方法的终极目标是使用这些新的（并且可能更好）寄生杜鹃蛋解决方案来取代当前的鸟巢蛋解。这种替换，迭代进行，最终导出最佳解。杨教授和Deb教授为该算法提出了以下三组理想状态：1.每只杜鹃产一枚蛋，并将其放入随机选择的鸟巢当中。2.拥有优质鸟蛋的最佳巢穴将传给下一代。3.可用的鸟巢数量是固定的，且鸟巢具有检测出外来鸟蛋的“pa”概率。在这种情况下，宿主鸟可以扔掉鸟蛋，或离开巢穴，鸟蛋就会死亡。出于简单起见，第三个假设可以用n个鸟巢的pa分数来近似。对于最大化问题，解的品质或适当性也许只是与目标函数成正比。然而，也可以定义适应度函数的其它（更复杂的）表达式。对于每次迭代g，随机选择一枚杜鹃鸟蛋i，并采用Levy飞行生成新的解xi(g+1)，这是一种随机游走，其中步数由具有一定概率分布的步长范围内判定，且步长的方向是各向同性和随机的。根据该方法的原建者的说法，采用Levy飞行策略比其它简单的随机游走更可取，因为它会产生更好的整体性能。一般的Levy飞行方程如下所示：xi(g+1)=xi(g)+α⊕levy(λ),其中g表示当前生成的数量，而α0表示步长，这应该与正在研究的特定问题的规模有关。⊕符号则表示逐元素乘法。请注意，这本质上是一个马尔可夫（Markov）链，因为第g+1代的下一个位置仅取决于g代的当前位置，以及分别由第一项和第二项给出的转移概率。该转移概率由Levy分布调制为：levy(λ)～g?λ,(1λ≤3),其具有无限均值的无限方差。实践表明，在固定的2.0度下，可以达到最好的结果。此处，这些步骤基本上形成了一个随机游走过程，具有幂律重尾步长分布。从计算的角度来看，利用Levy飞行生成随机数包括两个阶段：首先，根据均匀分布选择随机方向，然后根据所选的Levy分布生成步骤。然后，该算法评估新解的适用度，并将其与当前解进行比较。如果新解提供了更好的适用度，则它将取代当前解。另一方面，一些鸟巢被遗弃（鸟巢的宿主扔掉杜鹃蛋，或离开巢穴，故鸟蛋坏死了），以便提升针对搜索空间的探索，从而寻找更有希望的解。替换率由pa概率判定，模型参数需要调整以便提高性能。该算法应用迭代方式，直到满足停止条件。常见的终止准则是，已找到满足较低阈值的解、已达到固定的更新换代数量、或者连续迭代不再产生更好的结果。
我们来更详细地讨论杜鹃产蛋的过程。从所有鸟巢中，随机选择一个预备产蛋的鸟巢。由于鸟蛋是一个解，因此可以用鸟蛋的质量来表示。如果杜鹃蛋的质量高于宿主蛋，那么它将被替换。否则，宿主蛋将留在鸟巢中。事实上，随后的进化将自幸存的雏鸟继续。这意味着，如果宿主蛋的雏鸟幸存下来，那么进化将从同一个地方继续。进而只有当杜鹃蛋变得更强势，并且从新的地方继续寻找解时，才有可能进一步发展。示意性决策树如图例1所示。
编辑
切换为居中
添加图片注释，不超过字（可选）
图例1.决策树。红点是开始，绿点是最终决策
决策树之后算法基础的第二个组成部分是Levy飞行。Levy飞行是一种随机游走（马尔可夫统计过程），其中跳跃的长度以步为单位变化，跳跃的方向随机变化，概率分布是帕累托（Pareto）分布的特例，其特征是重尾。它被定义为空间中的跳跃，并且跳跃在随机方向上是各向同性的。Levy飞行是描述异常随机过程的工具。分散是无限的（长距跳跃也有可能），跳跃的长度在所有级别上都是自相似的（短跳穿插着长途飞行）。术语Levy飞行有时会扩展为包括发生在离散网格，而不仅是连续空间中的随机游走。
如果我们考虑一个参数的优化问题，可以想象Levy飞行在布谷鸟算法中的明确应用。我们以一个假设的函数（图例2中的黑线）为例，它在其大部分定义域，即水平线（y=x）上不会改变。仅在很小的区域内，该函数会发生变化，并且有一个最大值。如果我们从图例2中的橙点开始搜索最大值，然后得到一个带有Levy分布的随机值x，我们将远离起点，同时在函数里不再得到变化。然而，随着在分布尾部的强烈跳跃，我们得到一个绿点，这是一个比原始橙色更好的解，然后只从绿点我们能改善结果，同时接近函数的最大值。在此示例中，Levy飞行极大地提高了算法的搜索能力。
编辑
切换为居中
添加图片注释，不超过字（可选）
图例2.利用Levy飞行查找假设一维函数解的示例
Levy飞行的概念用于混沌理论，用于模拟随机或伪随机自然现象（例如，信天翁的飞行，结合长短轨迹）。示例包括地震数据分析、金融数学、密码学、信号分析、湍流运动，以及天文学、生物学和物理学中的许多应用。
COA算法伪代码（图例3）:
1.初始杜鹃是随机值。2.定义适应度。3.在随机鸟巢中产蛋。4.以给定的概率清空鸟巢。5.从当前位置将杜鹃发送到Levi飞行距离内的随机方向。6.定义适应度。7.在随机鸟巢中产蛋。8.以给定的概率清空鸟巢。9.重复第5步，直到满足停止准则。