快捷導(dǎo)航

蝴蝶優(yōu)化算法及實(shí)現(xiàn)源碼

更新時(shí)間：2022年02月07日 14:41:48 作者：十@八九

這篇文章主要為大家介紹了蝴蝶優(yōu)化算法的講解及實(shí)現(xiàn)源碼，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步

算法簡(jiǎn)介

蝴蝶優(yōu)化算法(butterfly optimization algorithm, BOA)是Arora 等人于2019年提出的一種元啟發(fā)式智能算法。該算法受到了蝴蝶覓食和交配行為的啟發(fā)，蝴蝶接收/感知并分析空氣中的氣味，以確定食物來源/交配伙伴的潛在方向。

蝴蝶利用它們的嗅覺、視覺、味覺、觸覺和聽覺來尋找食物和伴侶，這些感覺也有助于它們從一個(gè)地方遷徙到另一個(gè)地方，逃離捕食者并在合適的地方產(chǎn)卵。在所有感覺中，嗅覺是最重要的，它幫助蝴蝶尋找食物（通常是花蜜）。蝴蝶的嗅覺感受器分散在蝴蝶的身體部位，如觸角、腿、觸須等。這些感受器實(shí)際上是蝴蝶體表的神經(jīng)細(xì)胞，被稱為化學(xué)感受器。它引導(dǎo)蝴蝶尋找最佳的交配對(duì)象，以延續(xù)強(qiáng)大的遺傳基因。雄性蝴蝶能夠通過信息素識(shí)別雌性蝴蝶，信息素是雌性蝴蝶發(fā)出的氣味分泌物，會(huì)引起特定的反應(yīng)。

通過觀察，發(fā)現(xiàn)蝴蝶對(duì)這些來源的位置有非常準(zhǔn)確的判斷。此外，它們可以辨識(shí)出不同的香味，并感知它們的強(qiáng)度。蝴蝶會(huì)產(chǎn)生與其適應(yīng)度相關(guān)的某種強(qiáng)度的香味，即當(dāng)蝴蝶從一個(gè)位置移動(dòng)到另一個(gè)位置時(shí)，它的適應(yīng)度會(huì)相應(yīng)地變化。當(dāng)蝴蝶感覺到另一只蝴蝶在這個(gè)區(qū)域散發(fā)出更多的香味時(shí)，就會(huì)去靠近，這個(gè)階段被稱為全局搜索。另外一種情況，當(dāng)蝴蝶不能感知大于它自己的香味時(shí)，它會(huì)隨機(jī)移動(dòng)，這個(gè)階段稱為局部搜索。

香味

為了理解BOA中的香味是如何計(jì)算的，首先需要理解，像氣味、聲音、光、溫度等這樣的模態(tài)是如何計(jì)算的。感知、處理這些模態(tài)需要知道三個(gè)重要的術(shù)語(yǔ)：感覺模態(tài)C、刺激強(qiáng)度I和冪指數(shù)a。在感覺模態(tài)中，感覺意味著測(cè)量能量的形式并以類似方式對(duì)其進(jìn)行處理，而模態(tài)是指?jìng)鞲衅魇褂玫脑驾斎?。不同的形態(tài)可以是氣味，聲音，光線，溫度，在BOA中，模態(tài)是香味。I是物理刺激的大小。在BOA中，I與蝴蝶/解決方案的適應(yīng)度相關(guān)。這意味著，當(dāng)一只蝴蝶散發(fā)出更多的香味時(shí)，周圍的其他蝴蝶可以感知到并被吸引。冪是強(qiáng)度增加的指數(shù)。參數(shù)a允許正則表達(dá)式、線性響應(yīng)和響應(yīng)壓縮。響應(yīng)擴(kuò)展是當(dāng)I增加時(shí)，香味（f）比I增長(zhǎng)更快。響應(yīng)壓縮是當(dāng)I增加時(shí)，f比I增長(zhǎng)慢。線性響應(yīng)是當(dāng)I增加時(shí)，f成比例地增加。經(jīng)實(shí)驗(yàn)證明，有時(shí)隨著刺激的增強(qiáng)，昆蟲對(duì)刺激變化的敏感性變得越來越低。因此在BOA中，為了估計(jì)I的大小，使用了響應(yīng)壓縮。
蝴蝶的自然現(xiàn)象基于兩個(gè)重要問題：I的變化和f的表示。簡(jiǎn)單地說，蝴蝶的I與編碼后的目標(biāo)函數(shù)相關(guān)聯(lián)。但是，f是相對(duì)的，即應(yīng)該由其他蝴蝶來感知。史蒂文斯冪定律中，為了將氣味與其他形式區(qū)別開來，使用了C?，F(xiàn)在，當(dāng)I較少的蝴蝶向I較多的蝴蝶移動(dòng)時(shí)，f比I增加得更快。因此，我們應(yīng)該允許f隨冪指數(shù)參數(shù)a實(shí)現(xiàn)的吸收程度而變化。在BOA中，香味被表示為刺激物的物理強(qiáng)度的函數(shù)，如下所示：

在這里插入圖片描述

其中f為香味的大小，即其他蝴蝶感知到的香味強(qiáng)度，c 為感官模態(tài)，在[0,1]之間取值；I 為刺激強(qiáng)度；a 為冪指數(shù)，在[0,1]之間取值。在一個(gè)極端情況下，a=1，意味著一只特定蝴蝶發(fā)出的香氣量被其他蝴蝶以同樣的能力感知到，這相當(dāng)于說香味是在理想化的環(huán)境中傳播的，在這個(gè)區(qū)域的任何地方都可以感覺到一只散發(fā)著香味的蝴蝶。因此，可以很容易地達(dá)到單個(gè)(通常是全局的)最優(yōu)值。另一方面，如果a=0，這意味著任何一只蝴蝶散發(fā)出的香味都不會(huì)被其他蝴蝶感覺到。所以，參數(shù)a控制算法的行為。另一個(gè)重要參數(shù)是c，它也是決定BOA算法收斂速度和性能的關(guān)鍵參數(shù)。理論上c∈[0，∞]，但實(shí)際上是由待優(yōu)化系統(tǒng)的特性決定的。A和c的取值對(duì)算法的收斂速度有重要影響。在最大化問題中，強(qiáng)度可以與目標(biāo)函數(shù)成正比。

具體算法

為了用搜索算法演示上述討論，將蝴蝶的上述特征理想化如下：

1.所有的蝴蝶都可以發(fā)出氣味，這使蝴蝶間相互吸引。

2.每只蝴蝶都會(huì)隨機(jī)移動(dòng)或朝最好的蝴蝶移動(dòng)，散發(fā)出更多的芳香。

3. 蝴蝶的刺激強(qiáng)度受目標(biāo)函數(shù)的景觀影響或決定。

該算法分為三個(gè)階段：(1)初始化階段、(2)迭代階段和(3)結(jié)束階段。

在BOA的每次運(yùn)行中，首先執(zhí)行初始化階段，然后進(jìn)行迭代搜索，最后在找到最優(yōu)解時(shí)終止算法。BOA中使用的參數(shù)值也會(huì)被分配，設(shè)置這些值后，算法將繼續(xù)創(chuàng)建初始蝴蝶種群以進(jìn)行優(yōu)化。由于在BOA的模擬過程中蝴蝶總數(shù)保持不變，分配了一個(gè)固定大小的內(nèi)存來存儲(chǔ)信息。蝴蝶的位置是在搜索空間中隨機(jī)生成的，并計(jì)算和存儲(chǔ)它們的香味和適應(yīng)值。這樣就完成了初始化階段，算法開始了迭代階段，該階段使用創(chuàng)建的人工蝶形執(zhí)行搜索。算法的第二階段，即迭代階段，由算法執(zhí)行多次迭代。在每次迭代中，解空間中的所有蝶形都移到新位置，然后重新評(píng)估其適應(yīng)性值。算法首先計(jì)算解空間中不同位置的所有蝴蝶的適應(yīng)度值。那么這些蝴蝶就會(huì)利用式1在自己的位置產(chǎn)生香味。該算法有兩個(gè)關(guān)鍵步驟，即全局搜索階段和局部搜索階段。在全局搜索階段，蝴蝶向最合適的蝴蝶/解g∗邁出一步，該蝴蝶/解g可以用公式(2)來表示。

在這里插入圖片描述

這里，g∗表示在當(dāng)前迭代的所有解中找到的當(dāng)前最佳解；fi表示第i只蝴蝶的香味，r是[0，1]中的隨機(jī)數(shù)。局部搜索階段可以表示為

在這里插入圖片描述

其中，xjt和xkt是解空間中的第j個(gè)蝴蝶和第k個(gè)蝴蝶。

蝴蝶尋找食物、交配伙伴可以在局部和全局范圍內(nèi)發(fā)生?？紤]到地理上的接近和各種其他因素，如雨、風(fēng)等，在整個(gè)交配伙伴或蝴蝶的覓食活動(dòng)中，尋找食物可能占很大比例。因此，在BOA中使用切換概率p來在普通全局搜索和密集局部搜索之間切換。

在未達(dá)到停止標(biāo)準(zhǔn)之前，一直進(jìn)行迭代。迭代結(jié)束的標(biāo)準(zhǔn)可以有多個(gè)，如使用的最大CPU時(shí)間、達(dá)到的最大迭代次數(shù)、沒有改進(jìn)的最大迭代次數(shù)、達(dá)到錯(cuò)誤率的特定值或任何其他適當(dāng)?shù)臉?biāo)準(zhǔn)。當(dāng)?shù)A段結(jié)束時(shí)，算法輸出具有最佳適應(yīng)度的最優(yōu)解。