哈喽，小伙们好~

又到了算法学习的时间，那么今天就给大家介绍一个不是太新的算法——布谷鸟算法。快来一起学习吧~

01 算法背景

布谷鸟算法（Cuckoo search algorithm，CS），顾名思义，肯定是和布谷鸟有关。没错，这个算法就是英国学者 Xin-She Yang 和 Suash Deb 于2009年模仿布谷鸟育雏行为而提出的一种新兴基于自然元启发式算法。

布谷鸟这种鸟很懒，不会筑巢，自己生娃自己不会孵，直接扔到其他种类鸟的鸟巢中，但是有时候会被宿主鸟妈妈发现不是自己的蛋，然后就会被抛弃，甚至放弃这个巢。但是布谷鸟一般会比其他的鸟更早破壳，他们还有另外一种隐藏技能，幼鸟会模仿宿主鸟孩子的叫声来骗取鸟妈妈的信任，同时他们还会本能地把其他的蛋推下巢，从而获得更多的食物。

因此，我们可以这样理解：鸟巢=蛋=问题解，蛋能否成功被宿主鸟孵化并茁长成长是衡量问题解好坏的唯一标准 。布谷鸟在寻找鸟巢下蛋的过程就是在D维空间中寻找解的过程，而鸟巢的好坏象征着解的好坏。

02 算法原理

在自然界中，布谷鸟寻找适合自己产卵的鸟窝位置是随机的或是类似随机的方式，为了模拟布谷鸟寻窝的方式，首先，需要设定以下3个理想的状态

(1)布谷鸟一次只产一个卵，并随机选择鸟窝来孵化它;

(2)在随机选择的一组鸟窝中，最好的鸟窝将会被保留到下一代;

(3)可利用的鸟窝数量n是固定的，一个鸟窝的主人能发现一个外来鸟蛋的概率Pa∈[0，1]

可能会有人会问，怎么随机去寻找鸟窝的位置。因为更新位置的方法十分重要，关系到后面算法收敛的速度。那这个时候，我们就不得不提到另外一个概念——“莱维飞行”。一些研究证明，使用莱维飞行（Levy Flight）的方式可以让布谷鸟更有效地去寻找全局最优解而不至于陷入局部最优解中。

03 莱维飞行

我们可以先来看一下莱维飞行的演示图。

通过相关概念我们知道：莱维飞行是由较长时间的短步长和较短时间的长步长组成。

通俗点说就是，点大多数时间只有小距离移动，偶尔会有大距离移动的情况。这和自然界中大多数动物觅食方式类似。找到一块区域后细致的查找猎物，如果没找到，就换一片区域。

假设布谷鸟寻找鸟窝首先随机选择一个方向，然后确定要走多远。Levy分布要求大概率落在值比较小的位置，小概率落在值比较大的位置，刚好满足这种均匀分布。

04 搜索机制

对于这个算法来说，执行两种类型的搜索方式：局部搜索和全局搜索。

局部搜索可以通过局部随机行走实现：

其中xj和xk为随机选择的解，H(µ)为赫维赛德函数，pα是用于平衡局部和全局随机游走的切换参数，s为步长，ε为均匀分布的随机数。

全局搜索通过莱维飞行实现：

其中α>0为步长缩放因子，且：

其中：

莱维飞行是步长服从Lévy分布的随机游走：

通过莱维飞行生成的随机数由通过正态分布创建的随机方向选择组成，步长使用Mantegna算法生成：

其中µ和ν服从正太分布：

05 算法流程

1. 初始化：目标函数f(x)、鸟巢个数n、最大迭代次数MaxGeneration、最大发现概率Pa，解空间上下界Lb与Ub等；

2. 随机产生初始解x(i)（鸟巢位置），计算相应的初始适应度值F(i)，并记录当前的最优函数值；

3. 利用Levy飞行更新解（产生新的鸟蛋），计算相应的适应度值F(j)；

4. 比较Fi与Fj适应度值，如果Fj（新解）更小，将该适应度值及鸟蛋所代表的解赋给原来的鸟巢x(i)；

5. 判断鸟蛋是否会被发现：用随机数r与最大发现概率Pa比较，若r＞Pa，被发现，宿主找新家，鸟巢位置x(i)随机改变，反之，则不变；

6. 对各解（鸟巢位置或者鸟巢中的鸟蛋）进行适应度值排序，保留最优适应度值的解（鸟巢位置或鸟巢中的鸟蛋）；

7. 循环步骤3-6，直至达到最大迭代次数或者满足终止条件，则算法终止。

伪代码

06 Python实现

布谷鸟算法提出者之一的Xin-She Yang教授试了多组参数，发现种群规模在15到40，布谷鸟蛋被发现的概率 pa 取0.25时，对于大多数优化问题已足够，并且结果和分析也表明收敛速度在一定程度上对所使用的参数不敏感。

以下列目标函数为例，应用布谷鸟算法进行求解：

得到最优解，与迭代图分别为：

07 参考文献

[1] Yang X S . Cuckoo Search and Firefly Algorithm: Overview and Analysis[M]. Springer International Publishing, 2014.

[2] Yang X S ,  Deb S . Cuckoo Search via Lévy flights[C]// World Congress on Nature & Biologically Inspired Computing. IEEE, 2010.

[3] Yang X S ,  Deb S . Cuckoo Search via Levy Flights[J]. mathematics, 2010.

好啦，今天的分享就结束啦。布谷鸟算法的Python源码我已经放到公众号“土博在路上”啦，感兴趣的小伙伴们关注公众号“土博在路上”，后台回复布谷鸟自行获取吧！（ps：需要MATLAB源码的话可以留言告诉我，看到后就会回复！）