程春英

(內(nèi)蒙古民族大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,內(nèi)蒙古通遼,028043)

0 引言

螢火蟲(chóng)算法(Glowworm Swarn Optimization, GSO)是2005年由印度學(xué)者Krishnanand和Ghose提出的一種基于生物群體智能的隨機(jī)優(yōu)化算法，它是繼粒子群優(yōu)化算法、蟻群優(yōu)化算法、人工魚(yú)群優(yōu)化算法之后的又一種新型的群體智能優(yōu)化算法。螢火蟲(chóng)算法是通過(guò)模擬螢火蟲(chóng)在覓食、求偶和警戒等生活習(xí)性中產(chǎn)生的因光而吸引并移動(dòng)的行為來(lái)進(jìn)行尋優(yōu)的。該算法具有實(shí)現(xiàn)簡(jiǎn)單、計(jì)算效率高、適用能力強(qiáng)等特點(diǎn)，引起了諸多學(xué)者的關(guān)注和研究，已經(jīng)成為了計(jì)算智能領(lǐng)域的研究熱點(diǎn)。

螢火蟲(chóng)算法因?qū)崿F(xiàn)簡(jiǎn)單，不受搜索空間連續(xù)的限制、魯棒性好等特點(diǎn)，被廣泛應(yīng)用于機(jī)器人群體協(xié)作、有害氣體泄漏定位、聚類問(wèn)題、無(wú)線感測(cè)網(wǎng)絡(luò)布置等多個(gè)領(lǐng)域。

1 螢火蟲(chóng)算法

自然界中的螢火蟲(chóng)都會(huì)發(fā)出特有的閃光信號(hào)來(lái)確定位置并吸引異性，這種閃光信號(hào)就是短促并有節(jié)奏的熒光，螢火蟲(chóng)借助熒光來(lái)完成覓食、警戒和求偶等行為。螢火蟲(chóng)算法是模擬自然界中螢火蟲(chóng)發(fā)光行為來(lái)構(gòu)造出的一種隨機(jī)優(yōu)化算法。在螢火蟲(chóng)算法中利用的是螢火蟲(chóng)的發(fā)光特性在其感知范圍內(nèi)尋找同伴，并向感知范圍內(nèi)位置較好的螢火蟲(chóng)方向移動(dòng)，從而實(shí)現(xiàn)位置更新過(guò)程。

螢火蟲(chóng)算法的基本原理是：用搜索空間中的點(diǎn)模擬自然界中的螢火蟲(chóng)個(gè)體，將搜索和優(yōu)化過(guò)程模擬成螢火蟲(chóng)個(gè)體的吸引和移動(dòng)過(guò)程，將求解問(wèn)題的目標(biāo)函數(shù)度量成螢火蟲(chóng)個(gè)體所處位置的優(yōu)劣，將螢火蟲(chóng)個(gè)體的優(yōu)勝略汰過(guò)程類比為求解問(wèn)題目標(biāo)函數(shù)的搜索和優(yōu)化過(guò)程中用好的解取代較差的解的迭代過(guò)程。

螢火蟲(chóng)算法在問(wèn)題空間隨機(jī)分布 只螢火蟲(chóng)，這些螢火蟲(chóng)都帶有一定的熒光，每個(gè)螢火蟲(chóng)都具有自己的感知范圍而 是最大感知半徑。螢火蟲(chóng)實(shí)現(xiàn)尋優(yōu)時(shí)，在其感知范圍內(nèi)尋找熒光素值較高的螢火蟲(chóng)，并且會(huì)朝著這個(gè)方向移動(dòng)。螢火蟲(chóng)移動(dòng)之后，其感知半徑要進(jìn)行更新，最后大部分的螢火蟲(chóng)都會(huì)聚集在一個(gè)或多個(gè)極值上。

1.1 螢火蟲(chóng)的熒光素

螢火蟲(chóng)算法中，螢火蟲(chóng)的熒光素體現(xiàn)了螢火蟲(chóng)所處位置的優(yōu)劣并決定螢火蟲(chóng)的移動(dòng)方向。螢熒光素值越高對(duì)其感知范圍內(nèi)的螢火蟲(chóng)的吸引力就越強(qiáng)。螢火蟲(chóng)熒光素的更新方法如公式（2-1）所示：

1.2 鄰居的集合

每一個(gè)螢火蟲(chóng)個(gè)體都可以被熒光素值較高的其它螢火蟲(chóng)個(gè)體所吸引，但吸引動(dòng)作受到感知范圍的影響。螢火蟲(chóng)只能在其感知范圍內(nèi)尋找熒光素值較高的其它螢火蟲(chóng)。螢火蟲(chóng)的感知范圍內(nèi)的鄰居集合如公式（2-2）所示：

1.3 轉(zhuǎn)移概率

每一個(gè)螢火蟲(chóng)個(gè)體都可以被熒光素值高的螢火蟲(chóng)個(gè)體吸引，但螢火蟲(chóng)只能在其感知范圍內(nèi)尋找熒光素值較高的其它螢火蟲(chóng)，并朝著這個(gè)方向移動(dòng)。螢火蟲(chóng)個(gè)體的鄰居的集合中所有個(gè)體被選擇作為目標(biāo)個(gè)體的概率如公式（2-3）所示，尋優(yōu)時(shí)，根據(jù)計(jì)算概率值大的作為目標(biāo)移動(dòng)方向。

1.4 位置的更新

1.5 感知半徑的更新

螢火蟲(chóng)移動(dòng)之后要對(duì)其感知半徑進(jìn)行更新。感知半徑的更新與當(dāng)前螢火蟲(chóng)個(gè)體的鄰居的集合有關(guān)，如果感知范圍內(nèi)有很多熒光素值高的螢火蟲(chóng)個(gè)體，那么感知半徑應(yīng)適當(dāng)縮小。如果感知范圍內(nèi)只有少數(shù)的熒光素值高的螢火蟲(chóng)個(gè)體，那么感知半徑就應(yīng)適當(dāng)放大。螢火蟲(chóng)個(gè)體的感知半徑如公式（2-5）所示。

2 螢火蟲(chóng)算法現(xiàn)有的各種改進(jìn)算法

近年來(lái)，關(guān)于螢火蟲(chóng)算法的研究目標(biāo)主要集中在如何改善喜螢火蟲(chóng)算法的性能方面。具體改進(jìn)的方法集中在以下幾方面：

（1）K.N.Krishnanand 和D.Ghose最早在IEEE群智能會(huì)議上提出了螢火蟲(chóng)優(yōu)化算法，并且利用螢火蟲(chóng)算法進(jìn)行了信號(hào)源定位，取得了較好的效果。

（2）K.N.Krishnanand 等人提出了利用螢火蟲(chóng)算法求解多模函數(shù)優(yōu)化問(wèn)題，并取得了較好的效果。

（3）K.N.Krishnanand等人提出了利用螢火蟲(chóng)算法進(jìn)行群體機(jī)器人的多聲源定位操作。

（4）劉長(zhǎng)平等人將螢火蟲(chóng)算法應(yīng)用于函數(shù)優(yōu)化問(wèn)題和組合優(yōu)化問(wèn)題，并通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了該算法在連續(xù)空間和離散空間應(yīng)用的可行性。

（5）黃正新提出來(lái)一種用于解決TSP問(wèn)題的離散型螢火蟲(chóng)優(yōu)化算法，該算法中加入了2-Opt局部?jī)?yōu)化算子，提高了算法的局部搜索能力，并通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了該算法的有效性。

（6）黃正新將人工螢火蟲(chóng)算法應(yīng)用于聚類問(wèn)題，提出了基于螢火蟲(chóng)算法的聚類算法，將該算法的應(yīng)用推廣到解決聚類問(wèn)題領(lǐng)域。

（7）周永權(quán)等人在基本人螢火蟲(chóng)算法中結(jié)合C2Opt算子，將該改進(jìn)的算法應(yīng)用于求解TSP問(wèn)題，并通過(guò)仿真驗(yàn)證了該算法在小規(guī)模問(wèn)題上的可行性。

（8）李詠梅等人在基本人工螢火蟲(chóng)算法的基礎(chǔ)上加入了人工魚(yú)群算法的追尾行為，提出了一種基于追尾行為的改進(jìn)型人工螢火蟲(chóng)算法，并將該算法用于解決多峰函數(shù)的優(yōu)化問(wèn)題，獲得了較滿意的結(jié)果。

（9）祝華正提出了一種基于螢火蟲(chóng)和粒子群優(yōu)化的混合算法，在算法中使用串聯(lián)的方法將螢火蟲(chóng)群算法與粒子群優(yōu)化算法相互結(jié)合，再通過(guò)改變種群布局方式對(duì)算法進(jìn)行改進(jìn)，并通過(guò)函數(shù)優(yōu)化問(wèn)題的應(yīng)用驗(yàn)證了該算法的有效性。

（10）付強(qiáng)等人提出了一種基于多種群學(xué)習(xí)機(jī)制的新型螢火蟲(chóng)優(yōu)化算法。該算法中將螢火蟲(chóng)群分為不同參數(shù)下的多個(gè)子群，各子群內(nèi)的螢火蟲(chóng)跟隨所屬子群的最優(yōu)螢火蟲(chóng)分別進(jìn)行尋優(yōu)，再將該改進(jìn)的算法應(yīng)用于函數(shù)優(yōu)化問(wèn)題。

（11）郁書(shū)好等人提出了一種基于切比雪夫映射的混沌螢火蟲(chóng)優(yōu)化算法，該算法中利用混沌系統(tǒng)的隨機(jī)性和遍歷性初始化螢火蟲(chóng)的同時(shí)，對(duì)部分適應(yīng)度值低的個(gè)體進(jìn)行了混沌優(yōu)化，提高了種群的多樣性，并將該算法用于解決函數(shù)優(yōu)化問(wèn)題，結(jié)果表明該算法求解精度、全局搜索能力優(yōu)于基本螢火蟲(chóng)群算法。

（12）李瑞強(qiáng)將螢火蟲(chóng)優(yōu)化算法應(yīng)用到煤炭發(fā)熱預(yù)測(cè)模型中，并通過(guò)實(shí)驗(yàn)驗(yàn)證了該算法具有一定的實(shí)用價(jià)值。

（13）郭麗萍等人提出了一種改進(jìn)的螢火蟲(chóng)算法來(lái)求解阻塞流水線調(diào)度問(wèn)題。算法中提出了一種離散機(jī)制的個(gè)體編碼方式的作業(yè)序列，再將NEH啟發(fā)式方式應(yīng)用的螢火蟲(chóng)的初始化中，并將該算法應(yīng)用的Taillard數(shù)據(jù)集中部分實(shí)例的求解，實(shí)驗(yàn)結(jié)果驗(yàn)證了該改進(jìn)算法的有效性。

（15）韓凱等人將自適應(yīng)機(jī)制引入到時(shí)間同步協(xié)議中，提出了一種自適應(yīng)的螢火蟲(chóng)時(shí)間同步算法。并將該算法用于求解無(wú)線傳感器網(wǎng)絡(luò)，實(shí)驗(yàn)結(jié)果表明該算法適合于大規(guī)模的無(wú)線傳感器網(wǎng)絡(luò)。

（16）程奎等人提出了一種用于求解平面選址問(wèn)題的螢火蟲(chóng)優(yōu)化算法，該算法中引入了一種鄰域搜索的局部搜索方法，較好的避免了螢火蟲(chóng)算法易陷入局部極值的問(wèn)題。

（17）吳斌等人借鑒蜂群和鳥(niǎo)群的群體智能行為，提出了改進(jìn)螢火蟲(chóng)優(yōu)化算法的移動(dòng)策略并通過(guò)實(shí)驗(yàn)驗(yàn)證了該算法的有效性。

（18）劉佳昆等人針對(duì)螢火蟲(chóng)算法易陷入局部極值和收斂速度慢等缺點(diǎn)，提出了一種最大最小熒光素值人工螢火蟲(chóng)算法，該算法中對(duì)螢火蟲(chóng)的熒光素的變化范圍加以限定，給出了最大值最小值熒光素范圍，從而避免了陷入局部最優(yōu)的問(wèn)題。

3 結(jié)束語(yǔ)

螢火蟲(chóng)算法在應(yīng)用上取得了一定的成績(jī)，但算法本身沒(méi)有一個(gè)較好的數(shù)學(xué)模型支撐，還處于實(shí)驗(yàn)論證階段，因此，對(duì)螢火蟲(chóng)算法的改進(jìn)還有很大的空間。

（1）螢火蟲(chóng)算法理論研究

對(duì)于螢火蟲(chóng)的研究，現(xiàn)階段還只是停留在仿真階段，還沒(méi)有提出一個(gè)完善準(zhǔn)確的理論分析，對(duì)它的有效性也沒(méi)有給出嚴(yán)格的數(shù)學(xué)解釋。因此對(duì)螢火蟲(chóng)算法的理論研究對(duì)未來(lái)螢火蟲(chóng)算法的應(yīng)用研究是非常重要。

（2）將螢火蟲(chóng)算法和其它智能算法的結(jié)合

目前，已經(jīng)出現(xiàn)了螢火蟲(chóng)算法與粒子群算法和人工魚(yú)群算法混合算法，并得到很好的應(yīng)用。但是關(guān)于螢火蟲(chóng)算法與蛙群群算法、蜂群算法、蟻群算法等這些群體智能優(yōu)化算法之間的融合還是很少，因此，將螢火蟲(chóng)算法和這些智能算法的結(jié)合有待于進(jìn)一步的研究。

（3）擴(kuò)充螢火蟲(chóng)算法應(yīng)用的范圍

螢火蟲(chóng)算法的應(yīng)用還主要集中在函數(shù)優(yōu)化問(wèn)題上，組合優(yōu)化問(wèn)題的研究相對(duì)較少，應(yīng)用領(lǐng)域有待于進(jìn)一步的研究和擴(kuò)展。

[1]Krishnanand K N,Ghose D.Detection of multiple source locations using a glowworm metaphor with applications to collective robotics[C]//Swarm Intelligence symposium,2005.SIS 2005.Proceedings 2005 IEEE.IEEE,2005∶84-91.

[2]Krishnanand K N,Ghose D.Glowworm swarm based optimization algorithm for multimodal functions with collective robotics applications[J].Multivalent and Grid Systems,2006∶209-222.

[3]Krishnanand K N,Ghose D.Glowworm swarm optimization for simulataneous capture of multiple local optima of multimodal functions[J].Swarm Intelligence,2009,3(2)∶87-124.

[4]曾國(guó)泰.螢火蟲(chóng)最佳化分群演算法[D].臺(tái)灣：大同大學(xué)，2008.

[5]李穎珊.在無(wú)線感測(cè)網(wǎng)絡(luò)中基于螢火蟲(chóng)最佳化演算法的布置方法[D].臺(tái)灣：大同大學(xué)，2009.

[6]Krishnanand K N,Ghose D.Theoretical foundations for rendezvous of glowworm-inspired agent swarms at multiple locations[J].Robotics and Autonomous Systems,2008,56(7)∶549-569.

[7]Krishnanand K N,Ghose D.Glowworm swarm optimization∶A New method for optimizing Multi-modal functions[J].International Journal of Computational Intelligence Studies,20091(1)∶93-119.

[8]Krishnanand K N,Ghose D.Glowworm swarm optimization forsimultaneous captrue of multiple local optima of multimodal functions[J].Swarm Intelligence,20091,3(2)∶87-124.

[9]Krishnanand K N,Ghose D.Chasing Multiple Mobile signal sources∶A Glowworm Swarm Optimization Approach[C]//Proc.of the 3rd Indian International Conference on Artificial Intelligence.[S.I.]∶IEEE Press,2007.

[10]劉長(zhǎng)平，葉春明.一種新穎的仿生群智能優(yōu)化算法：螢火蟲(chóng)算法[J].計(jì)算機(jī)應(yīng)用研究.2011,28(9)∶3295-3297.

[11]黃正新.人工螢火蟲(chóng)群優(yōu)化算法分析改進(jìn)及應(yīng)用研究[D].廣西民族大學(xué)，2011：20-28.

[12]周永權(quán)，黃正新.求解TSP的人工螢火蟲(chóng)優(yōu)化算法[J].控制與決策.2012,27(12)∶1816-1821.

[13]李詠梅，周永權(quán)，姚祥光.基于追尾行為的改進(jìn)型人工螢火蟲(chóng)群算法[J].計(jì)算機(jī)科學(xué)，2011,38（3）：248-251.

[14]祝華正.螢火蟲(chóng)群算法的改進(jìn)及其應(yīng)用[D].廣西民族大學(xué) ,2011∶12-18.

[15]付強(qiáng)，童楠，趙一鳴.一種基于多種群學(xué)習(xí)機(jī)制的螢火蟲(chóng)優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究.2013,30(12)∶3600-3602.

[16]郁書(shū)好，蘇守寶.混沌螢火蟲(chóng)優(yōu)化算法的研究及應(yīng)用[J].計(jì)算機(jī)科學(xué)與探索.2014,2(3)∶352-358.

[17]李瑞強(qiáng).求解煤炭發(fā)熱量預(yù)測(cè)問(wèn)題的螢火蟲(chóng)優(yōu)化算法研究[J].邢臺(tái)學(xué)院學(xué)報(bào).2013,28(4)∶180-182.

[18]郭麗萍，李向濤，谷文祥，殷明浩.改進(jìn)的螢火蟲(chóng)算法求解阻塞流水線調(diào)度問(wèn)題[J].智能系統(tǒng)學(xué)報(bào).3013,8(1)∶33-38.

[19]韓凱，朱永利.自適應(yīng)螢火蟲(chóng)時(shí)間同步算法的研究[J].河北省科學(xué)學(xué)院學(xué)報(bào).2009,26∶11-15.

[20]程奎，馬良.平面選址問(wèn)題的螢火蟲(chóng)算法[J].上海理工大學(xué)學(xué)報(bào).2013,35(3)∶205-208.

[21]吳斌，崔志勇，倪衛(wèi)紅.具有混合群智能行為的螢火蟲(chóng)優(yōu)化算法研究[J].計(jì)算機(jī)科學(xué).2012,39(5)∶198-200.

[22]劉佳昆，周永權(quán).一種最大最小熒光素值人工螢火蟲(chóng)算法[J].計(jì)算機(jī)應(yīng)用研究.2011,28(10)∶3662-3664.