優(yōu)化算法筆記（十）螢火蟲算法

1. 螢火蟲算法簡(jiǎn)介

（以下描述，均不是學(xué)術(shù)用語，僅供大家快樂的閱讀）

螢火蟲算法(Firefly Algorithm,FA)是一種模仿螢火蟲之間信息交流，相互吸引集合，警戒危險(xiǎn)。算法的原理簡(jiǎn)單，但實(shí)現(xiàn)過程較為復(fù)雜，而且算法的提出時(shí)間不長(zhǎng)，算法的改進(jìn)、優(yōu)化處于初級(jí)階段，國內(nèi)外相應(yīng)的應(yīng)用研究已經(jīng)有了一定的成果。

螢火蟲算法中，每個(gè)螢火蟲的位置代表了一個(gè)待求問題的可行解，而螢火蟲的亮度表示該螢火蟲位置的適應(yīng)度，亮度越高的螢火蟲個(gè)體在解空間內(nèi)的位置越好。螢火蟲個(gè)體之間，高亮度的螢火蟲會(huì)吸引低亮度的螢火蟲。在解空間內(nèi)，每個(gè)螢火蟲會(huì)像著亮度比自己高螢火蟲飛行來搜尋更優(yōu)的位置。亮度越大對(duì)其他的螢火蟲的吸引度越大。同時(shí)，螢火蟲之間光的傳播介質(zhì)會(huì)吸收光，降低光的亮度，影響光的傳播，所以螢火蟲之間的吸引度會(huì)隨著空間距離成反比，即兩只螢火蟲之間的吸引度會(huì)隨著這兩只螢火蟲之間距離的增大而減小

2. 算法流程

這次我們的主角就是它了。（順便吐槽一下，螢火蟲發(fā)光原理是熒光素氧化發(fā)光，那為什么螢火蟲的位置會(huì)影響它的亮度呢，難道是不同位置的氧氣濃度不一樣？假裝就是這樣吧）。

一句話簡(jiǎn)述螢火蟲算法流程：每只螢火蟲都向著看上去比自己更亮的螢火蟲飛行。

在D維解空間內(nèi)每個(gè)螢火蟲的位置為X =(x_1,x_2,...,x_D) 。

螢火蟲之間的相對(duì)吸引度由以下公式(1)
\beta(r)=\beta_0e^{-\gamma r^2} 　　　　　　(1)

式(1)中\beta_0為其初始吸引度，即兩只螢火蟲之間距離為0時(shí)的吸引度，r為兩只螢火蟲之間的距離。

算法運(yùn)行過程中，每只螢火蟲將會(huì)朝著所有亮度比自己高的所有螢火蟲移動(dòng)，其移動(dòng)距離由以下公式(2)計(jì)算得出：
X_i^{,}=X_i+\beta_0e^{-\gamma r^2}(X_i-X_j)+ \alpha rand()　　　　　(2)
　　其中X_i表示一個(gè)比第i個(gè)個(gè)體亮度更高的螢火蟲的位置，r表示第i個(gè)螢火蟲與第j個(gè)螢火蟲之間的距離。rand()為一個(gè)隨機(jī)擾動(dòng)，\alpha為擾動(dòng)的步長(zhǎng)因子。一般rand()取值為[-0.5,0.5]范圍內(nèi)的均勻分布或者U(0,1)的標(biāo)準(zhǔn)正態(tài)分布a取值為[0,1]之間。

基本流程如下：

（1）初始化，設(shè)定螢火蟲的種群為N，介質(zhì)對(duì)光的吸收系數(shù)為 \gamma = 1 ，初始步長(zhǎng) a=0.97 ，初始吸引度 \beta_0 = 1.0，其中 \beta_{max} = 1.0,\beta_{min}=0.2 ，其吸引度公式如(3):
\beta(r)=(\beta_{max}-\beta_{min})e^{-\gamma r^2}+　\beta_{min}　　　　　　(3)
　　式（3）以保證任何兩個(gè)螢火蟲之間的最小吸引度為0.2，最大的吸引度為1.0。

（2）根據(jù)螢火蟲的位置計(jì)算出每個(gè)螢火蟲的適應(yīng)度值，適應(yīng)度值越優(yōu)的螢火蟲亮度越高。

（3）每個(gè)螢火蟲將根據(jù)式（2）向所有比自己亮度高的螢火蟲飛行其中第t代時(shí)螢火蟲飛行的步長(zhǎng)公式如 (4)：
\alpha (t)=\alpha^t 　　　　(4)
　　式（4）計(jì)算出的螢火蟲飛行步長(zhǎng)將隨時(shí)間遞減。

由于所有個(gè)體只會(huì)向比自己亮度高的個(gè)體飛行，那么群體中亮度最高的個(gè)體將不會(huì)更新其位置。本文中群體中亮度最大的個(gè)體將按照以下公式(5)來更新自己的位置。
X_i^{,}=X_i+ \alpha randGuass()　　　　　(5)

（4）計(jì)算在螢火蟲向所有比自己亮度高的其它個(gè)體飛行后所到的新位置的適應(yīng)度值，若該位置優(yōu)于飛行之前的位置，則該螢火蟲將飛行到新的位置，否則螢火蟲將停留在原處。

（5）若算法到達(dá)最大迭代次數(shù)則將搜索到的最優(yōu)的螢火蟲的位置作為解輸出，否則將跳到步驟（2）。

（又想吐槽了，該算法的論文中的描述與實(shí)際算法實(shí)現(xiàn)相差較大，我的實(shí)現(xiàn)是根據(jù)作者提供的代碼反推得出，若按照原文實(shí)現(xiàn)，得到的算法性能極差。該算法作者提出的其他算法亦如此）

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

實(shí)驗(yàn)一：標(biāo)準(zhǔn)螢火蟲算法

    適應(yīng)度函數(shù)還是

f(x_1,x_2)=(x_1-a)^2+(x_2-b)^2

參數(shù) 值
問題維度(維度) 2
螢火蟲數(shù)量(種群數(shù)) 20
飛行次數(shù)(最大迭代次數(shù)) 50
初始吸引度 1
吸引度范圍 (0.2,1.0)
介質(zhì)吸收系數(shù) 1
擾動(dòng)步長(zhǎng)因子 0.97
擾動(dòng)方式 正態(tài)分布
取值范圍 （-100，100）
實(shí)驗(yàn)次數(shù) 10

從搜索圖像上看，標(biāo)準(zhǔn)螢火蟲算法的搜索行為挺不錯(cuò)的，可以看出最亮的個(gè)體在自身周圍小幅度的搜索，而其他個(gè)體則幾乎是圍繞著最優(yōu)個(gè)體搜索的同時(shí)也在慢慢向其靠近。我們先看看實(shí)驗(yàn)的結(jié)果。

值
最優(yōu)值 0.008157162631779914
最差值 3.1035842131176095
平均值 0.35455247525429945

從結(jié)果中我們可以看出，上面看似良好的搜索行為得出的結(jié)果卻不是很穩(wěn)定，一個(gè)最差值拉低了整個(gè)實(shí)驗(yàn)的平均值。

為什么會(huì)這樣呢？

前面我們說過，螢火蟲算法的核心行為就是每只螢火蟲都向著看上去比自己更亮的螢火蟲飛行，這必然會(huì)導(dǎo)致群體迅速收斂。群體全都集中于一個(gè)位置時(shí)，算法的搜索能力會(huì)迅速下降且無法跳出局部最優(yōu)。

如何改變現(xiàn)狀呢？

方案1.隨機(jī)挑選數(shù)個(gè)個(gè)體，選擇這些個(gè)體中比自己亮的螢火蟲作為目標(biāo)飛行。

方案2.將螢火蟲群體分為數(shù)個(gè)組，每個(gè)個(gè)體向組內(nèi)比自己更亮的螢火蟲飛行。（當(dāng)年師兄的創(chuàng)新點(diǎn)）

    **實(shí)驗(yàn)二**.方案1，隨機(jī)挑選10個(gè)個(gè)體
參數(shù) 值
問題維度(維度) 2
螢火蟲數(shù)量(種群數(shù)) 20
飛行次數(shù)(最大迭代次數(shù)) 50
初始吸引度 1
吸引度范圍 （0.2,1.0）
（介質(zhì)吸收系數(shù)） 1
擾動(dòng)步長(zhǎng)因子 0.97
擾動(dòng)方式 正態(tài)分布
目標(biāo)個(gè)體 10
取值范圍 （-100，100）
實(shí)驗(yàn)次數(shù) 10

看圖像好像與標(biāo)準(zhǔn)螢火蟲算法的結(jié)果沒有什么別，看看實(shí)驗(yàn)結(jié)果。

值
最優(yōu)值 2.4611221154186236E-4
最差值 0.6282110775105908
平均值 0.13701600336856032

可以看出方案1的結(jié)果比標(biāo)準(zhǔn)螢火蟲算法更好，不過仍在誤差范圍內(nèi)（有可能是這幾次運(yùn)氣好使結(jié)果較好），但是算法的穩(wěn)定性提升了不少。

實(shí)驗(yàn)三.方案2，將螢火蟲隨機(jī)分組，組數(shù)為\sqrt{N}，其中N為螢火蟲總數(shù)

參數(shù) 值
問題維度(維度) 2
螢火蟲數(shù)量(種群數(shù)) 20
飛行次數(shù)(最大迭代次數(shù)) 50
初始吸引度 1
吸引度范圍 (0.2,1.0)
（介質(zhì)吸收系數(shù)） 1
擾動(dòng)步長(zhǎng)因子 0.97
擾動(dòng)方式 正態(tài)分布
分組數(shù) 4
取值范圍 （-100，100）
實(shí)驗(yàn)次數(shù) 10

圖像依然沒有太大的變化。

值
最優(yōu)值 0.009197087309433645
最差值 0.6407287765162609
平均值 0.09772547993102201

與方案1相比，雖然最優(yōu)值沒有方案1好，但是平均值更加好，算法的穩(wěn)定性更高。
　　上面的兩種方案給出的都是螢火蟲算法群聚方式的改進(jìn)，但是我們從圖像中可以看出，按照理論，螢火蟲們應(yīng)該會(huì)快速收斂到一起，而實(shí)際圖像卻是在整個(gè)空間內(nèi)飛行。導(dǎo)致這樣的原因是步長(zhǎng)擾動(dòng)因子計(jì)算的方式。
　　我們可以看看y=0.97^x的曲線圖像


　　可以看出到200代左右時(shí)，其值已經(jīng)非常接近0了，故我們可以推測(cè)標(biāo)準(zhǔn)螢火蟲算法會(huì)在200代時(shí)收斂，在200代之后即失去了全局搜索能力。
　　對(duì)于優(yōu)化算法來說，這不是一個(gè)好的設(shè)計(jì)，因?yàn)閱栴}的難易程度不同，但是算法的收斂時(shí)間卻很固。對(duì)于簡(jiǎn)單的問題，其他算法可能用不了200代就得出結(jié)果，而螢火蟲算法卻還未收斂，對(duì)于復(fù)雜的問題，可能200代還未能接近正確結(jié)果卻已經(jīng)收斂，陷入局部最優(yōu)。
　　如何改進(jìn)這個(gè)問題呢？我們需要找一個(gè)與最大迭代次數(shù)相關(guān)的函數(shù)來計(jì)算步長(zhǎng)擾動(dòng)因子，即最大迭代次數(shù)為100時(shí)和最大迭代次數(shù)為1000時(shí)，其曲線不會(huì)有太大的區(qū)別。

方案3.步長(zhǎng)擾動(dòng)計(jì)算公式為y=0.97^{400*i/iter}

可以看出當(dāng)最大迭代次數(shù)為100、1000時(shí)，曲線的圖像沒有太大的區(qū)別，為什么要取400呢，因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=0.97%5E%7B200%7D%20%3D%200.002%EF%BC%8C0.97%5E%7B400%7D%3D5.1132E-6" alt="0.97^{200} = 0.002，0.97^{400}=5.1132E-6" mathimg="1">，即有接近一半的迭代周期內(nèi)可以全局搜索，另一半的迭代周期可以局部搜索。

實(shí)驗(yàn)四.方案3

參數(shù) 值
問題維度(維度) 2
螢火蟲數(shù)量(種群數(shù)) 20
飛行次數(shù)(最大迭代次數(shù)) 50
初始吸引度 1
吸引度范圍 (0.2,1.0)
(介質(zhì)吸收系數(shù)） 1
擾動(dòng)步長(zhǎng)因子 0.97^(400*i/iter)
擾動(dòng)方式 正態(tài)分布
取值范圍 （-100，100）
實(shí)驗(yàn)次數(shù) 10

圖像表現(xiàn)的與理論上一致接近20代時(shí)螢火蟲結(jié)束全局搜索并收斂于一點(diǎn)，開始局部搜索。在看看最終結(jié)果。

值
最優(yōu)值 3.614101894633592E-9
最差值 4.5271253657421557E-7
平均值 6.55382970718115E-8 
   可以看出結(jié)果明顯好于上面的所有實(shí)驗(yàn)結(jié)果，而且也相對(duì)穩(wěn)定，說明上述改進(jìn)方案改進(jìn)了算法的收斂速度并提升了算法的性能。

4. 總結(jié)

螢火蟲算法的探究到此也到了尾聲，螢火蟲算法的思想相對(duì)比較簡(jiǎn)單，但是實(shí)際的實(shí)現(xiàn)仍然有點(diǎn)復(fù)雜，尤其是論文與實(shí)現(xiàn)之間的區(qū)別讓人頭疼。

相對(duì)標(biāo)準(zhǔn)螢火蟲算法，給出了3種改進(jìn)方案，都對(duì)算法的性能有一定的提升。由于改進(jìn)點(diǎn)各不相同，因此這3種方案可以兩兩混合產(chǎn)生新的方案，此處不再贅述

以下指標(biāo)純屬個(gè)人yy,僅供參考

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

參考文獻(xiàn)
Yang X S . Fire?y Algorithms for Multimodal Optimization[C]// Proceedings of the 5th international conference on Stochastic algorithms: foundations and applications. Springer, Berlin, Heidelberg, 2010.提取碼：mzgt

目錄
上一篇 優(yōu)化算法筆記（九）杜鵑搜索算法
下一篇 優(yōu)化算法筆記（十一）群搜索算法

優(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)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。
禁止轉(zhuǎn)載，如需轉(zhuǎn)載請(qǐng)通過簡(jiǎn)信或評(píng)論聯(lián)系作者。

相關(guān)閱讀更多精彩內(nèi)容

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