天天看點

布谷鳥搜尋算法

原文

仿照布谷鳥(也叫大杜鵑)“寄生”和"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 來計算:

布谷鳥搜尋算法

——————————參數取值——————

布谷鳥搜尋算法

——————————結論——————

布谷鳥算法參數少,速度快,是以被廣泛應用。

除此以外,它還能與其他算法無縫對接,也就是說它的通用性好。

布谷鳥搜尋算法

繼續閱讀