原文
仿照布谷鳥(也叫大杜鵑)“寄生”和"levy的飛行方式"。
寄生:借别人的巢來養自己的鳥蛋; levy飛行:萊維飛行,大多數鳥類的飛行軌迹都是是長、短不一的各種飛行距離相間的一種組合,每段飛行距離都和前一段距離相差一個很小的角度。圖形如下:
整個過程原理如下:布谷鳥在一堆鳥窩 n 中做選擇,選出最好的鳥巢,把自己的蛋放在裡面;宿主(被寄生的鳥)以一定機率pa發現有自己的鳥巢,則把布谷鳥的鳥蛋扔出去/建造新的鳥巢。
————————
下面詳細介紹算法内容:
布谷鳥算法(Cuckoo search, CS)是由英國學者 Xin-She Yang 和 Suash Deb 于2009年在群體智能技術的基礎上提出的一種新型基于自然元啟發式算法。模拟某些種屬布谷鳥(Cuckoo Species)的寄生育雛(Brood Parasitism)有效求解最優化問題的算法。
該算法的思想是基于布谷鳥的巢寄生行為以及鳥類的 Lévy 飛行行為。
為了簡單的描述布谷鳥算法,利用以下3條理想化規則對其闡述。
1)每隻布谷鳥每次随機選擇一個巢,并産生一個卵;
2)具有最高品質卵的巢保留至下一代;
3)可寄主巢的數量n是固定的,且寄主以機率為pa屬于(0,1)發現布谷鳥放的卵,在這種情況下,寄主鳥将布谷鳥的卵扔掉或者丢棄現有的巢。
為了簡單起見,假定n個巢(寄主鳥的數量)中pa部分被新的巢(新解)替代。
在布谷鳥算法中,每個巢中的卵代表一個解,布谷鳥的卵代表新解,目标是利用新解或者潛在的優解替代巢中的劣解。
————————————算法步驟——————————————
————————整體搜尋原理————————————————
如何執行 Levy 飛行【全局搜尋】
式(2)本質上是一種随機行走的随機(stochastic)公式。事實上,随機行走是一個馬爾科夫鍊,其下一個狀态/位置僅取決于目前狀态(上式的第一項)和轉移機率(上式的第二項)。然而,新解的很大一部分應該由遠場随機化産生,它們的位置應該離目前最佳解足夠遠,這将確定系統不會陷入局部最優。
從實作的角度來看,用 Lévy 飛行生成随機數應包括兩個步驟:随機方向的選擇和服從 Lévy 分布的步長的生成。方向的生成應該服從均勻分布,而生成步長是相當棘手的。有幾種方法可以實作,但是最有效且直接的方法就是使用所謂的 Mantegna 算法來實作對稱的 Lévy 穩定分布。
然而,生成正确服從 Lévy 分布的僞随機步長并不簡單。 在 Mantegna 算法中,步長 s 可以通過以下變換使用兩個服從高斯分布的變量 U 和 V 來計算:
——————————參數取值——————
——————————結論——————
布谷鳥算法參數少,速度快,是以被廣泛應用。
除此以外,它還能與其他算法無縫對接,也就是說它的通用性好。