優(yōu)化算法筆記（九）杜鵑搜索算法

1. 杜鵑搜索算法簡(jiǎn)介

（以下描述，均不是學(xué)術(shù)用語(yǔ)，僅供大家快樂(lè)的閱讀）
　　杜鵑搜索算法（Cuckoo search，CS）是一種模仿杜鵑鳥(niǎo)尋窩產(chǎn)卵活動(dòng)的群集智能優(yōu)化算法。杜鵑搜索算法的流程簡(jiǎn)單，有較強(qiáng)的跳出局部最優(yōu)能力，但由于算法中列維飛行實(shí)現(xiàn)較復(fù)雜且算法提出時(shí)間不長(zhǎng)，還有很多基礎(chǔ)研究正在進(jìn)行。
　　杜鵑搜索算法中，每個(gè)杜鵑的寄生巢的位置代表待求問(wèn)題的一個(gè)可行解。每個(gè)杜鵑每次只會(huì)在一個(gè)寄生巢中生產(chǎn)一枚卵。在所有的寄生巢中，最優(yōu)秀的寄生巢才會(huì)被留到下一代，繼續(xù)在該寄生巢中產(chǎn)卵。每個(gè)寄生巢的主人都有一定的幾率察覺(jué)自己的巢中有外來(lái)單從而放棄該鳥(niǎo)巢。寄生巢被放棄后，杜鵑將會(huì)重新隨機(jī)選擇一個(gè)鳥(niǎo)巢作為新的寄生巢。

2. 算法流程

杜鵑搜索算法的主角當(dāng)然就是杜鵑了。



　　杜鵑不自己養(yǎng)育后代，而是將自己的卵放置在其他鳥(niǎo)的鳥(niǎo)巢中，將自己的后代寄養(yǎng)其中。每一個(gè)寄生鳥(niǎo)窩是一個(gè)候選解。為了生存繁衍，杜鵑有兩種產(chǎn)卵的策略：
　　1. 列維飛行，杜鵑將在通過(guò)列維飛行所找到的與之前的寄生巢對(duì)比，選擇較優(yōu)的寄生巢作為下一代的寄生巢
　　2. 隨機(jī)選擇，每個(gè)寄生巢的主人都有一定的幾率發(fā)現(xiàn)自己的巢被寄生。發(fā)現(xiàn)后，杜鵑將隨機(jī)選擇一個(gè)新的鳥(niǎo)巢作為自己的寄生巢。
　　可以說(shuō)杜鵑搜索的算法流程也是極其的簡(jiǎn)單，但是其實(shí)現(xiàn)起來(lái)并沒(méi)有看上去的那么容易，困難點(diǎn)在于如何實(shí)現(xiàn)列維飛行。什么是列維飛行以及其特點(diǎn)將在下一節(jié)介紹。
　　在D維解空間內(nèi)每個(gè)鳥(niǎo)巢的位置為:

X=(x_1,x_2,...,x_d)

第t+1代時(shí)，杜鵑將根據(jù)第t代的寄生巢的位置，結(jié)合列維飛行求得新的寄生巢的位置，飛行公式如下：
x_{i,d}^{t+1}=x_{i,d}^{t}+\alpha\times Levy(\lambda)
其中x_{i,d}^{t}表示第i個(gè)杜鵑在第t代時(shí)選擇的寄生巢的位置的第d維，\alpha為列維飛行的步長(zhǎng)。 levy表示服從當(dāng)前迭代次數(shù)的t的隨機(jī)分布，在杜鵑搜索算法中其真正的含義其實(shí)是向當(dāng)前的全局最優(yōu)解以levy飛行的方式靠近（這是作者原代碼中的實(shí)現(xiàn)，與論文不相符(╰_╯)#）。
　　實(shí)際的飛行公式如下：
x_{i,d}^{t+1}=x_{i,d}^{t}+r\times\alpha\times Levy(\lambda)\times (x_{best,d}^{t}-x_{i,d}^{t})
　　其中ｒ?yàn)閇0,1]內(nèi)的均勻隨機(jī)數(shù)。


　　杜鵑搜索算法的流程是不是相當(dāng)?shù)暮?jiǎn)單明了，其中的關(guān)鍵步驟就是列維（levy）飛行了，很許多小伙伴都是在學(xué)習(xí)杜鵑搜索算法時(shí)才知道列維飛行這個(gè)概念，當(dāng)然我自己也是。
　　下面我們將來(lái)詳細(xì)的探究一下什么是列維飛行，這對(duì)以后我們改進(jìn)其他優(yōu)化算法提供了一個(gè)思路。

3.levy飛行

Levy 過(guò)程直觀上講,可以看做連續(xù)時(shí)間的隨機(jī)游動(dòng) .它的特征是有平穩(wěn) 獨(dú)立的增量, 重要的 Levy 過(guò)程有 Brown 運(yùn)動(dòng), Poisson 過(guò)程, Cauchy 過(guò)程等。（沒(méi)看過(guò)隨機(jī)過(guò)程的小伙伴應(yīng)該看不懂吧）。
　　來(lái)個(gè)levy飛行的鏈接，也是杜鵑搜索算法的：levy飛行。
　　Levy飛行簡(jiǎn)單來(lái)說(shuō)就是一種隨機(jī)飛行的過(guò)程，飛行有很大的概率在當(dāng)前位置周?chē)\(yùn)動(dòng)，也會(huì)有極小的概率飛到很遠(yuǎn)的地方去。就好比我們不經(jīng)常打掃房間，平時(shí)也就清理一下垃圾桶，但是也會(huì)偶爾抽風(fēng)花點(diǎn)時(shí)間將房間從里到外仔細(xì)的打掃一遍，這也是一個(gè)列維過(guò)程，可以稱之為列維打掃房間。
　　看一下列維飛行的公式，找了好久，還是從自己論文抄一個(gè)吧。
Levy(\lambda)表示服從當(dāng)前迭代次數(shù)的t的隨機(jī)分布，其概率分布為式如下：
Levy(\lambda)\sim u=t^{-\lambda},1<\lambda<3　　(1)

本文中采用Mantegna 于1992 年提出的模擬levy 飛行來(lái)進(jìn)行搜索，其計(jì)算公式如式（2） ：
s=\frac{u}{|v|^{\frac{1}{\beta}}}　　(2)
　　其中s即為Levy(\lambda)所求得的路徑，參數(shù) 與式（1）中 的關(guān)系為 ，通常 取值在[0,2]范圍內(nèi)，杜鵑搜索算法中取 。 為服從正態(tài)分布的隨機(jī)數(shù)，如下式 (3)：
u\sim N(0,\sigma_u^2),\sigma_u^2=\{\frac{\Gamma(1+\beta)sin(\beta\pi/2)}{\Gamma((1+\beta)/2)2^{(\beta-1)/2}\beta}\}^\frac{1}{\beta}　　(3)
v\sim N(0,\sigma_v^2),\sigma_v^2=1
　　式（3）中 \Gamma(x)的定義如下式 (4)：
\Gamma(x)=\int_{0}^{+\infty} t^{x-1}e^{-t}\,dt
　　從式（2）中我們可以看出列維飛行的長(zhǎng)度其實(shí)是兩個(gè)正態(tài)分布隨機(jī)數(shù)之商。
\beta=1.5
\Gamma(1+1.5)=1.329340388179137
\sigma_u=1.849902656990532
我們先看看\Gamma 函數(shù)的圖像：


由 1<\lambda<3可知，列維飛行中g(shù)amma函數(shù)的取值范圍為[1,2]。
然后我們?cè)賮?lái)看一下標(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è)賮?lái)看看\beta取其他值時(shí)分布圖：

　　我們可以看出，不同的\beta值對(duì)應(yīng)的levy飛行長(zhǎng)度分布基本相似，大多數(shù)分布于較小數(shù)，較少出現(xiàn)于極大數(shù)，由于算法可以根據(jù)問(wèn)題各維度的取值范圍來(lái)設(shè)定levy飛行的最大最小值。如取值為（-100,100）的問(wèn)題，若\beta=0.5，那么其最大取到273030，最小取到-711，這些極少出現(xiàn)的較大值在整個(gè)算法過(guò)程中幾乎沒(méi)有意義，它們會(huì)使進(jìn)行l(wèi)evy飛行的杜鵑飛出了搜索空間的邊界，然后被遣返，這浪費(fèi)了杜鵑的一次搜索。而取\beta=1.5是，最大最小值均在搜索范圍內(nèi)，越界的可能較小（當(dāng)飛到邊界附近后再向邊界外飛行仍會(huì)越界）。
　　現(xiàn)在問(wèn)題來(lái)了,既然levy飛行在杜鵑搜索算法中只是提供了一個(gè)小概率的大波動(dòng),那么能不能使用其他的概率分布呢?
　　先看看s=\frac{u}{v} ,其中，u、v均為符合正態(tài)分布的隨機(jī)數(shù)，那么S的概率分布如何呢，

　　怎么樣，是不是感覺(jué)和levy飛行的分布很像，只不過(guò)最大值更大，最小值更小，其實(shí)levy飛行本來(lái)就是兩個(gè)符合正態(tài)分布的隨機(jī)數(shù)相除，所以直接用感覺(jué)也不會(huì)有太大的影響。
　　u均為符合正態(tài)分布的隨機(jī)數(shù)，v為（-1,1）的均勻分布隨機(jī)數(shù)時(shí)，那么S的概率分布如下

　　其分布與levy也比較相似，但是分布更為均勻。

4.實(shí)驗(yàn)

實(shí)驗(yàn)又開(kāi)始了


實(shí)驗(yàn)1.標(biāo)準(zhǔn)杜鵑搜索算法

參數(shù) 值
問(wèn)題維度(維度) 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)路線圖。

粒子群算法

遺傳算法

差分進(jìn)化算法

人工蜂群算法

　　對(duì)比可以發(fā)現(xiàn)，杜鵑搜索的路線圖會(huì)出現(xiàn)部分較遠(yuǎn)的飛行距離，且路線圖也相對(duì)曲折，但是飛行的長(zhǎng)度明顯少于其他算法。
　　粒子群算法的路線圖，由于不會(huì)要求下一個(gè)位置優(yōu)于上一個(gè)位置，所以飛行的路線圖非常的密集，也說(shuō)明了其較強(qiáng)的全局搜索能力。
　　遺傳算法的進(jìn)化曲線在初始階段比較密集，到了后來(lái)基因多樣性降低后只能靠變異取產(chǎn)生新的基因時(shí)才會(huì)出現(xiàn)進(jìn)化曲線。
　　差分進(jìn)化算法的進(jìn)化曲線非常有意思，多數(shù)為橫線或者豎線，這也和其算法描述一致，至少保留一位交叉基因到下一代。
　　人工蜂群算法的飛行曲線與遺傳算法相似，不過(guò)其飛行目標(biāo)更加集中，遺傳算法的進(jìn)化曲線比較散亂，這也圖像了它們的區(qū)別，進(jìn)化-不向最優(yōu)解靠近，群智能-向最優(yōu)解靠近。
實(shí)驗(yàn)2.使用正態(tài)分布相除為飛行距離的杜鵑搜索算法

參數(shù) 值
問(wèn)題維度(維度) 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
正態(tài)分布隨機(jī)數(shù)相除

　　上面的飛行路線圖與使用levy飛行時(shí)的路線圖好像沒(méi)什么差別，都是有較少飛到了較遠(yuǎn)的位置，然后飛行軌跡越來(lái)越少。我們?cè)賮?lái)看看結(jié)果。

值
最優(yōu)值 1.0910862398043029E-6
最差值 2.1833086940861702E-4
平均值 4.1908193647164885E-5

對(duì)比使用levy飛行的杜鵑搜索算法結(jié)果，使用正態(tài)分布相除的杜鵑搜索算法的結(jié)果更差，不過(guò)差距不大。對(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%，這說(shuō)明使用levy飛行的杜鵑搜索算法的飛行精度會(huì)更高，但是使用正態(tài)分布相除的杜鵑搜索算法的搜索能力會(huì)更強(qiáng)那么一點(diǎn)。
實(shí)驗(yàn)3.去除levy飛行杜鵑搜索算法
　　前面看了使用不同飛行方式的杜鵑搜索算法，我們?cè)賮?lái)看看去除levy飛行的杜鵑搜索算法，此時(shí)，杜鵑們只會(huì)向著最優(yōu)位置飛行，是不是像一個(gè)弱化的人工蜂群算法？

參數(shù) 值
問(wèn)題維度(維度) 2
杜鵑數(shù)量(種群數(shù)) 20
搜索次數(shù)(最大迭代次數(shù)) 50
最大步長(zhǎng) 1
飛行方式 飛向最優(yōu)位置
宿主發(fā)現(xiàn)概率 0.3
取值范圍 （-100，100）
實(shí)驗(yàn)次數(shù) 10
無(wú)·levy飛行

　　從圖像可以看出，沒(méi)有了levy飛行的杜鵑們，它們的收斂速度變快了，同時(shí)，它們的飛行路線明顯少于標(biāo)準(zhǔn)杜鵑搜索算法，這表明沒(méi)有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è)類似與買(mǎi)彩票的過(guò)程，不得獎(jiǎng)或的小獎(jiǎng)的概率較大，但是得大獎(jiǎng)的概率非常低，的大獎(jiǎng)一次既可以改變（人生）軌跡。同時(shí)，由于levy飛行的實(shí)現(xiàn)方式過(guò)于復(fù)雜，也給出了一個(gè)結(jié)果較為相似但過(guò)程更加簡(jiǎn)單的方式-正態(tài)分布隨機(jī)數(shù)相除，出了精度有點(diǎn)差異外，分布情況大致相同。
　　杜鵑搜索算法的流程如此簡(jiǎn)單，僅憑levy飛行就能得出如此結(jié)果，那么我們是不是可以詳細(xì)研究一下《隨機(jī)過(guò)程》，說(shuō)不定下一個(gè)算法就使用了brown過(guò)程或是poisson過(guò)程，又發(fā)明了一個(gè)什么燕子算法、大雁算法甚么的。
以下指標(biāo)純屬個(gè)人yy,僅供參考

指標(biāo) 星數(shù)
復(fù)雜度 ★★★☆☆☆☆☆☆☆
收斂速度 ★★★★★☆☆☆☆☆
全局搜索 ★★★★★★☆☆☆☆
局部搜索 ★★★★★★☆☆☆☆
優(yōu)化性能 ★★★★★★☆☆☆☆
跳出局部最優(yōu) ★★★★★★★★☆☆
改進(jìn)點(diǎn) ★★☆☆☆☆☆☆☆☆

目錄
上一篇 優(yōu)化算法筆記（八）人工蜂群算法
下一篇 優(yōu)化算法筆記（十）螢火蟲(chóng)算法

優(yōu)化算法matlab實(shí)現(xiàn)（九）杜鵑搜索算法matlab實(shí)現(xiàn)

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。
禁止轉(zhuǎn)載，如需轉(zhuǎn)載請(qǐng)通過(guò)簡(jiǎn)信或評(píng)論聯(lián)系作者。

友情鏈接更多精彩內(nèi)容