1. 杜鵑搜索算法簡(jiǎn)介
（以下描述拙友，均不是學(xué)術(shù)用語吏饿，僅供大家快樂的閱讀）
杜鵑搜索算法（Cuckoo search庇楞，CS）是一種模仿杜鵑鳥尋窩產(chǎn)卵活動(dòng)的群集智能優(yōu)化算法钦无。杜鵑搜索算法的流程簡(jiǎn)單丛忆，有較強(qiáng)的跳出局部最優(yōu)能力祠汇，但由于算法中列維飛行實(shí)現(xiàn)較復(fù)雜且算法提出時(shí)間不長(zhǎng)，還有很多基礎(chǔ)研究正在進(jìn)行熄诡。
杜鵑搜索算法中可很，每個(gè)杜鵑的寄生巢的位置代表待求問題的一個(gè)可行解。每個(gè)杜鵑每次只會(huì)在一個(gè)寄生巢中生產(chǎn)一枚卵凰浮。在所有的寄生巢中我抠，最優(yōu)秀的寄生巢才會(huì)被留到下一代，繼續(xù)在該寄生巢中產(chǎn)卵袜茧。每個(gè)寄生巢的主人都有一定的幾率察覺自己的巢中有外來單從而放棄該鳥巢菜拓。寄生巢被放棄后，杜鵑將會(huì)重新隨機(jī)選擇一個(gè)鳥巢作為新的寄生巢笛厦。
2. 算法流程
杜鵑搜索算法的主角當(dāng)然就是杜鵑了纳鼎。
杜鵑不自己養(yǎng)育后代，而是將自己的卵放置在其他鳥的鳥巢中裳凸，將自己的后代寄養(yǎng)其中贱鄙。每一個(gè)寄生鳥窩是一個(gè)候選解。為了生存繁衍姨谷，杜鵑有兩種產(chǎn)卵的策略：
1. 列維飛行逗宁，杜鵑將在通過列維飛行所找到的與之前的寄生巢對(duì)比，選擇較優(yōu)的寄生巢作為下一代的寄生巢
2. 隨機(jī)選擇梦湘，每個(gè)寄生巢的主人都有一定的幾率發(fā)現(xiàn)自己的巢被寄生瞎颗。發(fā)現(xiàn)后件甥，杜鵑將隨機(jī)選擇一個(gè)新的鳥巢作為自己的寄生巢。
可以說杜鵑搜索的算法流程也是極其的簡(jiǎn)單言缤，但是其實(shí)現(xiàn)起來并沒有看上去的那么容易嚼蚀，困難點(diǎn)在于如何實(shí)現(xiàn)列維飛行禁灼。什么是列維飛行以及其特點(diǎn)將在下一節(jié)介紹管挟。
在D維解空間內(nèi)每個(gè)鳥巢的位置為:
第t+1代時(shí)，杜鵑將根據(jù)第t代的寄生巢的位置弄捕，結(jié)合列維飛行求得新的寄生巢的位置僻孝，飛行公式如下：
其中表示第i個(gè)杜鵑在第t代時(shí)選擇的寄生巢的位置的第d維，
為列維飛行的步長(zhǎng)守谓。 levy表示服從當(dāng)前迭代次數(shù)的t的隨機(jī)分布穿铆，在杜鵑搜索算法中其真正的含義其實(shí)是向當(dāng)前的全局最優(yōu)解以levy飛行的方式靠近（這是作者原代碼中的實(shí)現(xiàn)，與論文不相符(╰_╯)#）斋荞。
實(shí)際的飛行公式如下：
其中ｒ?yàn)閇0,1]內(nèi)的均勻隨機(jī)數(shù)荞雏。
杜鵑搜索算法的流程是不是相當(dāng)?shù)暮?jiǎn)單明了，其中的關(guān)鍵步驟就是列維（levy）飛行了平酿，很許多小伙伴都是在學(xué)習(xí)杜鵑搜索算法時(shí)才知道列維飛行這個(gè)概念凤优，當(dāng)然我自己也是。
下面我們將來詳細(xì)的探究一下什么是列維飛行蜈彼，這對(duì)以后我們改進(jìn)其他優(yōu)化算法提供了一個(gè)思路筑辨。
3.levy飛行
Levy 過程直觀上講,可以看做連續(xù)時(shí)間的隨機(jī)游動(dòng) .它的特征是有平穩(wěn) 獨(dú)立的增量, 重要的 Levy 過程有 Brown 運(yùn)動(dòng), Poisson 過程, Cauchy 過程等。（沒看過隨機(jī)過程的小伙伴應(yīng)該看不懂吧）幸逆。
來個(gè)levy飛行的鏈接棍辕，也是杜鵑搜索算法的：levy飛行。
Levy飛行簡(jiǎn)單來說就是一種隨機(jī)飛行的過程还绘，飛行有很大的概率在當(dāng)前位置周圍運(yùn)動(dòng)楚昭，也會(huì)有極小的概率飛到很遠(yuǎn)的地方去。就好比我們不經(jīng)常打掃房間拍顷，平時(shí)也就清理一下垃圾桶哪替，但是也會(huì)偶爾抽風(fēng)花點(diǎn)時(shí)間將房間從里到外仔細(xì)的打掃一遍，這也是一個(gè)列維過程菇怀，可以稱之為列維打掃房間凭舶。
看一下列維飛行的公式，找了好久爱沟，還是從自己論文抄一個(gè)吧帅霜。
表示服從當(dāng)前迭代次數(shù)的t的隨機(jī)分布，其概率分布為式如下：
本文中采用Mantegna 于1992 年提出的模擬levy 飛行來進(jìn)行搜索呼伸，其計(jì)算公式如式（2） ：
其中s即為所求得的路徑身冀，參數(shù) 與式（1）中 的關(guān)系為 钝尸，通常 取值在[0,2]范圍內(nèi)，杜鵑搜索算法中取 搂根。 為服從正態(tài)分布的隨機(jī)數(shù)珍促，如下式 (3)：
式（3）中 的定義如下式 (4)：
從式（2）中我們可以看出列維飛行的長(zhǎng)度其實(shí)是兩個(gè)正態(tài)分布隨機(jī)數(shù)之商。
我們先看看 函數(shù)的圖像：
由
然后我們?cè)賮砜匆幌聵?biāo)準(zhǔn)正態(tài)分布的分布圖：
可以看出方差越大的正態(tài)分布曲線越平緩。而levy飛行長(zhǎng)度可以看成是兩個(gè)正態(tài)分布相關(guān)隨機(jī)數(shù)的商仁卷，其中分母為標(biāo)準(zhǔn)正態(tài)分布相關(guān)穴翩，而分子為服從標(biāo)準(zhǔn)差為1.85，均值為0的正態(tài)分布的隨機(jī)數(shù)锦积。
我們看一下此時(shí)列維飛行的分布圖芒帕，
總共進(jìn)行飛行了100次，可以看出有近1/2的次數(shù)分布在0左右丰介，而最大值取到了16僅出現(xiàn)了1次背蟆，最小取到了-41，也只出現(xiàn)了一次哮幢。比較符合我們心中的levy飛行的特點(diǎn)带膀，大多數(shù)集中于絕對(duì)值較小的數(shù)，極少量為絕對(duì)值較大的數(shù)家浇。我們?cè)賮砜纯?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Cbeta" alt="\beta" mathimg="1">取其他值時(shí)分布圖：
我們可以看出本砰，不同的
現(xiàn)在問題來了,既然levy飛行在杜鵑搜索算法中只是提供了一個(gè)小概率的大波動(dòng),那么能不能使用其他的概率分布呢?
先看看
怎么樣乍惊，是不是感覺和levy飛行的分布很像杜秸，只不過最大值更大，最小值更小润绎，其實(shí)levy飛行本來就是兩個(gè)符合正態(tài)分布的隨機(jī)數(shù)相除撬碟，所以直接用感覺也不會(huì)有太大的影響。
u均為符合正態(tài)分布的隨機(jī)數(shù)凡橱，v為（-1,1）的均勻分布隨機(jī)數(shù)時(shí)小作，那么S的概率分布如下
其分布與levy也比較相似亭姥，但是分布更為均勻稼钩。
4.實(shí)驗(yàn)
實(shí)驗(yàn)又開始了
實(shí)驗(yàn)1.標(biāo)準(zhǔn)杜鵑搜索算法
| 參數(shù) | 值 |
|---|---|
| 問題維度(維度) | 2 |
| 杜鵑數(shù)量(種群數(shù)) | 20 |
| 搜索次數(shù)(最大迭代次數(shù)) | 50 |
| 最大步長(zhǎng) | 1 |
| 飛行方式 | Levy |
| 宿主發(fā)現(xiàn)概率 | 0.3 |
| 取值范圍 | （-100，100） |
| 實(shí)驗(yàn)次數(shù) | 10 |
| 值 | |
|---|---|
| 最優(yōu)值 | 5.6989487065157614E-8 |
| 最差值 | 2.1765283245215035E-5 |
| 平均值 | 7.18140639739042E-6 |
可以看出杜鵑搜索的位置跳躍性較大达罗，符合我們對(duì)levy飛行的期待坝撑。真的是這樣嗎，我們先看看其他算法的位置移動(dòng)路線圖粮揉。
對(duì)比可以發(fā)現(xiàn)巡李，杜鵑搜索的路線圖會(huì)出現(xiàn)部分較遠(yuǎn)的飛行距離，且路線圖也相對(duì)曲折扶认，但是飛行的長(zhǎng)度明顯少于其他算法侨拦。
粒子群算法的路線圖，由于不會(huì)要求下一個(gè)位置優(yōu)于上一個(gè)位置辐宾，所以飛行的路線圖非常的密集狱从，也說明了其較強(qiáng)的全局搜索能力。
遺傳算法的進(jìn)化曲線在初始階段比較密集叠纹，到了后來基因多樣性降低后只能靠變異取產(chǎn)生新的基因時(shí)才會(huì)出現(xiàn)進(jìn)化曲線季研。
差分進(jìn)化算法的進(jìn)化曲線非常有意思，多數(shù)為橫線或者豎線誉察，這也和其算法描述一致与涡，至少保留一位交叉基因到下一代。
人工蜂群算法的飛行曲線與遺傳算法相似持偏，不過其飛行目標(biāo)更加集中驼卖，遺傳算法的進(jìn)化曲線比較散亂，這也圖像了它們的區(qū)別鸿秆，進(jìn)化-不向最優(yōu)解靠近酌畜，群智能-向最優(yōu)解靠近。
實(shí)驗(yàn)2.使用正態(tài)分布相除為飛行距離的杜鵑搜索算法
| 參數(shù) | 值 |
|---|---|
| 問題維度(維度) | 2 |
| 杜鵑數(shù)量(種群數(shù)) | 20 |
| 搜索次數(shù)(最大迭代次數(shù)) | 50 |
| 最大步長(zhǎng) | 1 |
| 飛行方式 | 正態(tài)分布隨機(jī)數(shù)相除 |
| 宿主發(fā)現(xiàn)概率 | 0.3 |
| 取值范圍 | （-100谬莹，100） |
| 實(shí)驗(yàn)次數(shù) | 10 |
上面的飛行路線圖與使用levy飛行時(shí)的路線圖好像沒什么差別檩奠，都是有較少飛到了較遠(yuǎn)的位置桩了，然后飛行軌跡越來越少。我們?cè)賮砜纯唇Y(jié)果埠戳。
| 值 | |
|---|---|
| 最優(yōu)值 | 1.0910862398043029E-6 |
| 最差值 | 2.1833086940861702E-4 |
| 平均值 | 4.1908193647164885E-5 |
對(duì)比使用levy飛行的杜鵑搜索算法結(jié)果井誉，使用正態(tài)分布相除的杜鵑搜索算法的結(jié)果更差，不過差距不大整胃。對(duì)比它們的飛行公式可知颗圣，當(dāng)作為分母的正態(tài)分布隨機(jī)數(shù)的絕對(duì)值<1時(shí)，使用levy飛行方式會(huì)使得飛行長(zhǎng)度更小屁使，而作為分布的標(biāo)準(zhǔn)正態(tài)分布隨機(jī)數(shù)的絕對(duì)值小于1的概率約為68%在岂，這說明使用levy飛行的杜鵑搜索算法的飛行精度會(huì)更高，但是使用正態(tài)分布相除的杜鵑搜索算法的搜索能力會(huì)更強(qiáng)那么一點(diǎn)蛮寂。
實(shí)驗(yàn)3.去除levy飛行杜鵑搜索算法
前面看了使用不同飛行方式的杜鵑搜索算法蔽午，我們?cè)賮砜纯慈コ齦evy飛行的杜鵑搜索算法，此時(shí)酬蹋，杜鵑們只會(huì)向著最優(yōu)位置飛行及老，是不是像一個(gè)弱化的人工蜂群算法？
| 參數(shù) | 值 |
|---|---|
| 問題維度(維度) | 2 |
| 杜鵑數(shù)量(種群數(shù)) | 20 |
| 搜索次數(shù)(最大迭代次數(shù)) | 50 |
| 最大步長(zhǎng) | 1 |
| 飛行方式 | 飛向最優(yōu)位置 |
| 宿主發(fā)現(xiàn)概率 | 0.3 |
| 取值范圍 | （-100范抓，100） |
| 實(shí)驗(yàn)次數(shù) | 10 |
從圖像可以看出骄恶，沒有了levy飛行的杜鵑們，它們的收斂速度變快了匕垫，同時(shí)僧鲁，它們的飛行路線明顯少于標(biāo)準(zhǔn)杜鵑搜索算法，這表明沒有l(wèi)evy的杜鵑們的搜索能力弱于標(biāo)準(zhǔn)杜鵑搜索算法象泵，我們看一看結(jié)果寞秃。
| 值 | |
|---|---|
| 最優(yōu)值 | 1.2450419211891007E-19 |
| 最差值 | 0.0606152612083874 |
| 平均值 | 0.008891217058396326 |
結(jié)果與我預(yù)料的一致，算法的搜索能力較弱单芜，但是收斂速度和收斂性較好蜕该，當(dāng)有杜鵑“出生在羅馬”時(shí)，其他個(gè)體迅速靠近可能得出進(jìn)度超高的結(jié)果洲鸠，而其他情況則是只能找到大致的結(jié)果堂淡，精確度較低。
5.總結(jié)
杜鵑搜索算法的探究到此也告一段落扒腕，杜鵑搜索算法的流程相對(duì)比較簡(jiǎn)單绢淀，但是杜鵑們的搜索行為則比較復(fù)雜，我們較為詳細(xì)的看了levy飛行的實(shí)現(xiàn)以及其分布的特點(diǎn)瘾腰，可以看出levy飛行實(shí)際上實(shí)現(xiàn)了一個(gè)類似與買彩票的過程皆的，不得獎(jiǎng)或的小獎(jiǎng)的概率較大，但是得大獎(jiǎng)的概率非常低蹋盆，的大獎(jiǎng)一次既可以改變（人生）軌跡费薄。同時(shí)硝全，由于levy飛行的實(shí)現(xiàn)方式過于復(fù)雜，也給出了一個(gè)結(jié)果較為相似但過程更加簡(jiǎn)單的方式-正態(tài)分布隨機(jī)數(shù)相除楞抡，出了精度有點(diǎn)差異外伟众，分布情況大致相同。
杜鵑搜索算法的流程如此簡(jiǎn)單召廷，僅憑levy飛行就能得出如此結(jié)果凳厢，那么我們是不是可以詳細(xì)研究一下《隨機(jī)過程》，說不定下一個(gè)算法就使用了brown過程或是poisson過程竞慢，又發(fā)明了一個(gè)什么燕子算法先紫、大雁算法甚么的。
以下指標(biāo)純屬個(gè)人yy,僅供參考
| 指標(biāo) | 星數(shù) |
|---|---|
| 復(fù)雜度 | ★★★☆☆☆☆☆☆☆ |
| 收斂速度 | ★★★★★☆☆☆☆☆ |
| 全局搜索 | ★★★★★★☆☆☆☆ |
| 局部搜索 | ★★★★★★☆☆☆☆ |
| 優(yōu)化性能 | ★★★★★★☆☆☆☆ |
| 跳出局部最優(yōu) | ★★★★★★★★☆☆ |
| 改進(jìn)點(diǎn) | ★★☆☆☆☆☆☆☆☆ |
