01 算法背景

布谷鳥算法（Cuckoo search algorithm，CS），顧名思義，肯定是和布谷鳥有關(guān)。沒錯，這個算法就是英國學(xué)者 Xin-She Yang 和 Suash Deb 于2009年模仿布谷鳥育雛行為而提出的一種新興基于自然元啟發(fā)式算法。

布谷鳥這種鳥很懶，不會筑巢，自己生娃自己不會孵，直接扔到其他種類鳥的鳥巢中，但是有時候會被宿主鳥媽媽發(fā)現(xiàn)不是自己的蛋，然后就會被拋棄，甚至放棄這個巢。但是布谷鳥一般會比其他的鳥更早破殼，他們還有另外一種隱藏技能，幼鳥會模仿宿主鳥孩子的叫聲來騙取鳥媽媽的信任，同時他們還會本能地把其他的蛋推下巢，從而獲得更多的食物。

因此，我們可以這樣理解：鳥巢=蛋=問題解，蛋能否成功被宿主鳥孵化并茁長成長是衡量問題解好壞的唯一標(biāo)準(zhǔn) 。布谷鳥在尋找鳥巢下蛋的過程就是在D維空間中尋找解的過程，而鳥巢的好壞象征著解的好壞。

02 算法原理

在自然界中，布谷鳥尋找適合自己產(chǎn)卵的鳥窩位置是隨機(jī)的或是類似隨機(jī)的方式，為了模擬布谷鳥尋窩的方式，首先，需要設(shè)定以下3個理想的狀態(tài)

(1)布谷鳥一次只產(chǎn)一個卵，并隨機(jī)選擇鳥窩來孵化它;

(2)在隨機(jī)選擇的一組鳥窩中，最好的鳥窩將會被保留到下一代;

(3)可利用的鳥窩數(shù)量n是固定的，一個鳥窩的主人能發(fā)現(xiàn)一個外來鳥蛋的概率Pa∈[0，1]

可能會有人會問，怎么隨機(jī)去尋找鳥窩的位置。因為更新位置的方法十分重要，關(guān)系到后面算法收斂的速度。那這個時候，我們就不得不提到另外一個概念——“萊維飛行”。一些研究證明，使用萊維飛行（Levy Flight）的方式可以讓布谷鳥更有效地去尋找全局最優(yōu)解而不至于陷入局部最優(yōu)解中。

03 萊維飛行

我們可以先來看一下萊維飛行的演示圖。

通過相關(guān)概念我們知道：萊維飛行是由較長時間的短步長和較短時間的長步長組成。

通俗點(diǎn)說就是，點(diǎn)大多數(shù)時間只有小距離移動，偶爾會有大距離移動的情況。這和自然界中大多數(shù)動物覓食方式類似。找到一塊區(qū)域后細(xì)致的查找獵物，如果沒找到，就換一片區(qū)域。

假設(shè)布谷鳥尋找鳥窩首先隨機(jī)選擇一個方向，然后確定要走多遠(yuǎn)。Levy分布要求大概率落在值比較小的位置，小概率落在值比較大的位置，剛好滿足這種均勻分布。

04 搜索機(jī)制

對于這個算法來說，執(zhí)行兩種類型的搜索方式：局部搜索和全局搜索。

局部搜索可以通過局部隨機(jī)行走實現(xiàn)：

其中xj和xk為隨機(jī)選擇的解，H(μ)為赫維賽德函數(shù)，pα是用于平衡局部和全局隨機(jī)游走的切換參數(shù)，s為步長，ε為均勻分布的隨機(jī)數(shù)。

全局搜索通過萊維飛行實現(xiàn)：

其中α>0為步長縮放因子，且：

其中：

萊維飛行是步長服從Lévy分布的隨機(jī)游走：

通過萊維飛行生成的隨機(jī)數(shù)由通過正態(tài)分布創(chuàng)建的隨機(jī)方向選擇組成，步長使用Mantegna算法生成：

其中μ和ν服從正太分布：

05 算法流程

1. 初始化：目標(biāo)函數(shù)f(x)、鳥巢個數(shù)n、最大迭代次數(shù)MaxGeneration、最大發(fā)現(xiàn)概率Pa，解空間上下界Lb與Ub等；

2. 隨機(jī)產(chǎn)生初始解x(i)（鳥巢位置），計算相應(yīng)的初始適應(yīng)度值F(i)，并記錄當(dāng)前的最優(yōu)函數(shù)值；

3. 利用Levy飛行更新解（產(chǎn)生新的鳥蛋），計算相應(yīng)的適應(yīng)度值F(j)；

4. 比較Fi與Fj適應(yīng)度值，如果Fj（新解）更小，將該適應(yīng)度值及鳥蛋所代表的解賦給原來的鳥巢x(i)；

5. 判斷鳥蛋是否會被發(fā)現(xiàn)：用隨機(jī)數(shù)r與最大發(fā)現(xiàn)概率Pa比較，若r＞Pa，被發(fā)現(xiàn)，宿主找新家，鳥巢位置x(i)隨機(jī)改變，反之，則不變；

6. 對各解（鳥巢位置或者鳥巢中的鳥蛋）進(jìn)行適應(yīng)度值排序，保留最優(yōu)適應(yīng)度值的解（鳥巢位置或鳥巢中的鳥蛋）；

7. 循環(huán)步驟3-6，直至達(dá)到最大迭代次數(shù)或者滿足終止條件，則算法終止。

偽代碼

06 Python實現(xiàn)

布谷鳥算法提出者之一的Xin-She Yang教授試了多組參數(shù)，發(fā)現(xiàn)種群規(guī)模在15到40，布谷鳥蛋被發(fā)現(xiàn)的概率?pa 取0.25時，對于大多數(shù)優(yōu)化問題已足夠，并且結(jié)果和分析也表明收斂速度在一定程度上對所使用的參數(shù)不敏感。