崔家瑞　李擎　楊柳祎　王恒　張博鈺

摘要：螢火蟲算法（FA）是一種群體智能優(yōu)化算法，它基于螢火蟲的閃爍和吸引特征模擬螢火蟲的社會(huì)行為。為解決螢火蟲算法后期收斂速度慢，易陷入局部最優(yōu)的不足，對算法進(jìn)行了改進(jìn)。提出了兩種啟發(fā)信息引導(dǎo)算法收斂：第一種借鑒粒子群算法中“全局最優(yōu)”的思想，將當(dāng)前最優(yōu)點(diǎn)的位置作為啟發(fā)信息，形成了基于當(dāng)前全局最優(yōu)的螢火蟲算法（FAGO）;第二種將貝葉斯估計(jì)計(jì)算出的最優(yōu)移動(dòng)方向作為啟發(fā)信息，形成了基于貝葉斯估計(jì)的螢火蟲算法（FABE）。最后，將本文算法在多個(gè)常見函數(shù)上進(jìn)行了測試，并與經(jīng)典螢火蟲算法、近年其他文獻(xiàn)改進(jìn)螢火蟲算法進(jìn)行了對比研究，結(jié)果表明本文所提算法能夠加快收斂速度，提高收斂精度。

關(guān)鍵詞：螢火蟲算法;啟發(fā)信息;全局最優(yōu);貝葉斯估計(jì);數(shù)值優(yōu)化

DOI：10.15938/j.jhust.2019.01.015

中圖分類號： TP18

文獻(xiàn)標(biāo)志碼： A

文章編號： 1007-2683（2019）01-0092-07

Improved Firefly Algorithm Based on Heuristic Information

CUI Jia?rui，LI Qing，YANG Liu?yi，WANG Heng，ZHANG Bo?yu

（School of Automation and Electrical Engineering， University of Science and Technology Beijing， Beijing 100083， China）

Abstract：Firefly Algorithm （FA） is an optimization algorithm based on swarm intelligence which mimics the social behavior of fireflies based on the flashing and attraction characteristics of fireflies?With the aim to address the disadvantages of the firefly algorithm of slow convergence speed and ease of falling into the local optimum in the later period of the evolution process， the firefly algorithm is improved herein?Two kinds of heuristic information are proposed into the algorithm to guide the convergence of the algorithm?The first one takes the current global best as the heuristic information referencing the “global optimal” idea in particle swarm optimization， therefore， an algorithm called FAGO （Firefly Algorithm based on Global Optimization） is formed?The second one is called FABE （Firefly Algorithm based on Bayesian Estimation） using the optimal moving direction calculated by Bayesian estimation as heuristic information?The improved algorithms in this study are applied to numerical simulations of several classical test functions and compared with traditional FA and some other′s research are carried out?The simulation results show that the proposed algorithms can well accelerate the convergence speed and improve the convergence accuracy

Keywords：firefly algorithm; heuristic information; global optimal; Bayesian estimation; numerical optimization

0引言

螢火蟲算法（Firefly Algorithm，F(xiàn)A）是一種典型的啟發(fā)式優(yōu)化算法，由Yang XS于2008年提出[1]，在圖像處理[2]、光譜數(shù)據(jù)分類[3]、流水線調(diào)度[4]等方面得到廣泛應(yīng)用。經(jīng)典螢火蟲算法參數(shù)少、原理清晰且易于實(shí)現(xiàn)，同時(shí)也存在后期收斂速度慢、收斂精度不高、易陷入局部最優(yōu)的缺陷，為彌補(bǔ)這種缺陷，大量學(xué)者對其進(jìn)行了改進(jìn)，并取得了一些研究成果。具有代表性的改進(jìn)方法包括基于參數(shù)動(dòng)態(tài)調(diào)整的改進(jìn)算法和基于融合思想的改進(jìn)算法。文[5]介紹了典型的動(dòng)態(tài)調(diào)整參數(shù)方法，將螢火蟲算法和Levy飛行策略結(jié)合，利用Levy飛行重尾分布的特性，對螢火蟲算法的隨機(jī)移動(dòng)步長進(jìn)行了改進(jìn)，提出了Levy飛行螢火蟲算法（Levy?flight Firefly Algorithm，LFA）;文[6]提出了將螢火蟲算法與差分進(jìn)化方法融合的思路，將較差的螢火蟲個(gè)體組成新種群，利用差分進(jìn)化方法進(jìn)行迭代，較優(yōu)個(gè)體保持原算法不變，提高了算法擺脫局部最優(yōu)的能力，稱為混合進(jìn)化螢火蟲算法（Hybrid Evolutionary Firefly Algorithm，HEFA）。

本文借鑒粒子群算法，引入全局最優(yōu)位置作為啟發(fā)信息;結(jié)合貝葉斯公式基于先驗(yàn)概率能最大化后驗(yàn)概率的優(yōu)點(diǎn)，引入計(jì)算出的最優(yōu)移動(dòng)方向作為啟發(fā)信息。實(shí)驗(yàn)結(jié)果表明，兩種啟發(fā)信息各有優(yōu)勢和適用環(huán)境，但都能在一定程度上解決后期易陷入局部最優(yōu)的問題。與現(xiàn)有算法相比，本文所提出的改進(jìn)方法在很大程度上提高了算法最優(yōu)解和整體平均解的收斂精度，減少了達(dá)到最優(yōu)解所需的迭代次數(shù)。

1經(jīng)典螢火蟲算法

螢火蟲算法模擬自然界中螢火蟲個(gè)體發(fā)光的生物學(xué)特性發(fā)展而來，其核心思想是：分布在解空間中的螢火蟲基于適應(yīng)度的大小發(fā)出不同亮度的光，亮度高的螢火蟲會(huì)吸引亮度低的螢火蟲向其靠攏[7]，若將螢火蟲個(gè)體的位置作為其對應(yīng)的解，亮度作為該解的適應(yīng)度，亮度高的個(gè)體持續(xù)吸引亮度低的個(gè)體從而進(jìn)行迭代，在迭代的最后，亮度最高的個(gè)體所處的位置即為得到的最優(yōu)可行解（以下簡稱最優(yōu)解）。

經(jīng)典螢火蟲算法步驟如下：

步驟1：初始化，定義算法參數(shù)，包括迭代次數(shù)、螢火蟲群體規(guī)模等;

步驟2：在解空間的不同位置隨機(jī)生成螢火蟲，給出初始亮度;

步驟3：對一只螢火蟲，觀察其他螢火蟲到自身的相對亮度，向吸引度大于自身亮度的螢火蟲個(gè)體進(jìn)行移動(dòng)，完成一只螢火蟲的一次迭代過程;

螢火蟲到其自身距離r處的相對亮度I?r由下式表示：

I?r=I?0?e??-γr?2?（1）

上式中，I?0表示螢火蟲在自身位置處的亮度（即適應(yīng)度），與待優(yōu)化問題有關(guān)，γ為光吸收因子，表征了傳播媒介對于光強(qiáng)的吸收能力。

k+1時(shí)刻，螢火蟲i向著螢火蟲j移動(dòng)，其位置更新公式為：

s?k+1?i=s?k?i+β?0?e??-γr?ij?2?（s?k?j-s?k?i）+αε?k+1?i（2）

上式中，r?ij?為螢火蟲i與j之間的歐式距離，α是步長因子，取值范圍一般為[0，1]，服從高斯分布或者均勻分布;ε?k+1?i是該時(shí)刻螢火蟲i對應(yīng)的隨機(jī)向量，決定了在每個(gè)維度上進(jìn)行移動(dòng)的方向。

步驟4：對所有螢火蟲個(gè)體執(zhí)行步驟3中操作，完成整個(gè)螢火蟲群體的一次迭代;

步驟5：根據(jù)情況選擇合適的終止條件，判斷是否滿足，不滿足則轉(zhuǎn)步驟3;

步驟6：滿足終止條件時(shí)，找出此時(shí)亮度最大的螢火蟲所處的位置，即為得到的最優(yōu)解。

2螢火蟲算法的改進(jìn)

2.1啟發(fā)信息引入的必要性

標(biāo)準(zhǔn)螢火蟲算法中，個(gè)體的移動(dòng)以亮度作為依據(jù)，向更亮個(gè)體移動(dòng)的策略保證了算法能夠收斂至一個(gè)較小的區(qū)域內(nèi)，但無法保證解空間的多樣性，極易陷入局部最優(yōu)，為此，算法提出者在螢火蟲個(gè)體的移動(dòng)策略中增加了隨機(jī)移動(dòng)項(xiàng)以擴(kuò)展其全局搜索能力。但現(xiàn)有的隨機(jī)移動(dòng)機(jī)制導(dǎo)致螢火蟲個(gè)體容易丟失其已經(jīng)獲得的最優(yōu)解優(yōu)勢，降低搜索效率，導(dǎo)致算法收斂速度過慢。

基于此，有必要引入其他啟發(fā)信息，為螢火蟲個(gè)體提供除亮度外的移動(dòng)依據(jù)。本文設(shè)計(jì)了兩種不同的啟發(fā)信息，形成了兩種不同的改進(jìn)螢火蟲算法。兩種引入啟發(fā)信息的螢火蟲算法步驟相同，如圖1所示：

2.2基于全局最優(yōu)引導(dǎo)的螢火蟲算法

在粒子群優(yōu)化算法中，每個(gè)粒子的速度更新利用了其自身的歷史最佳位置?p?best?和整個(gè)種群的歷史最佳位置g?best?[8]，也就是說，粒子群算法中的粒子是有記憶的，這大大加快了粒子群算法的收斂速度?；谝陨侠碚?，本文為螢火蟲算法引入“全局最優(yōu)”概念，認(rèn)為歷史中出現(xiàn)過的最亮螢火蟲的位置對群體有著持續(xù)的吸引力，使螢火蟲個(gè)體不但朝著當(dāng)前最優(yōu)移動(dòng)，還向著當(dāng)前全局最優(yōu)移動(dòng)一定距離，這就是基于全局最優(yōu)的螢火蟲算法（Firefly Algorithm Based on Global Optimization，F(xiàn)AGO）的基本思路。具體到算法本身，將原位置更新公式（2）改為

s?k+1?i=s?k?i+β?0?e??-γr?ij?2?（s?k?j-s?k?i）+

w（g?k?best?-s?k?i）+αε?k+1?i（3）

式中：g?k?best?為k時(shí)刻記錄的全局最優(yōu)解的位置;w為隨迭代次數(shù)增加而減小的系數(shù)：

w=k??max?-kk??max?（4）

式中：k為當(dāng)前迭代次數(shù);k??max?為最大迭代次數(shù)。

2.3基于貝葉斯估計(jì)的螢火蟲算法

螢火蟲的移動(dòng)行為由方向和在該方向上的位移組成。在標(biāo)準(zhǔn)螢火蟲算法中，個(gè)體隨機(jī)移動(dòng)項(xiàng)的移動(dòng)方向是完全隨機(jī)的，這保證了算法跳出局部最優(yōu)解的可能，然而，在既定情境下，最優(yōu)解所處方向一般是固定的，完全隨機(jī)的移動(dòng)方式未考慮最優(yōu)解的方向信息，相當(dāng)程度上減緩了算法收斂速度。由此，本文考慮為隨機(jī)移動(dòng)的方向增加啟發(fā)信息，保證算法跳出局部最優(yōu)能力的同時(shí)加快收斂速度。

分析算法中螢火蟲的移動(dòng)過程，每只螢火蟲個(gè)體進(jìn)行移動(dòng)后，可以統(tǒng)計(jì)出在每個(gè)方向進(jìn)行移動(dòng)的概率值，適應(yīng)度的變化情況也可通過適應(yīng)度函數(shù)計(jì)算得知，這樣，得知了螢火蟲在某個(gè)方向上移動(dòng)的概率和在該方向上移動(dòng)后適應(yīng)度增加的概率，要求得適應(yīng)度增加的前提下向該方向移動(dòng)的概率，就是根據(jù)先驗(yàn)概率計(jì)算后驗(yàn)概率的問題，貝葉斯估計(jì)（Bayesian estimation）正是解決這一問題的方法。貝葉斯估計(jì)[9]指出，若存在?∪?n?i=1?A?i=?Ω?，A?iA?j=，?P（A?i）?>0，則稱A?1，…，A?n為完備事件組，可由貝葉斯公式計(jì)算出事件B發(fā)生的情況下A?i?發(fā)生的概率：

P（A?i|B）=P（A?i）*P（B|A?i）∑n?i=1?P（B|A?i）*P（A?i）（5）

擴(kuò)展到螢火蟲算法，記解空間的維度數(shù)為m，螢火蟲總個(gè)數(shù)為N，在一次迭代中相對亮度大于螢火蟲j的個(gè)體數(shù)為n，則螢火蟲移動(dòng)的方向集合c?1，c?2，…，c?2m?為一個(gè)完備事件組，對于螢火蟲個(gè)體j，在方向i上，若有p只螢火蟲亮度大于其自身，則螢火蟲j會(huì)在方向i上移動(dòng)p次，認(rèn)為螢火蟲數(shù)量足夠多，可根據(jù)大數(shù)定理，用螢火蟲向方向i移動(dòng)的頻率近似代替概率，有：

P（A=c?i）=∑?N-1?k=1?I（A?k=c?i）n=∑p?k=1?I（A?k=c?i）n

i=1，2，…，2m（6）

I（·）為指示函數(shù)，在·為真和假時(shí)分別取值1和0。

同理，記螢火蟲適應(yīng)度增加為事件B，若統(tǒng)計(jì)出

螢火蟲j向每個(gè)方向移動(dòng)后適應(yīng)度是否增加，就可以計(jì)算出條件概率P（B|A=c?i）的值：

P（B|A=c?i）=∑p?k=1?I（B，A?k=c?i）∑K?k=1?I（A?k=c?i）（7）

將式（6）和式（7）的結(jié)果代入式（5），就可以計(jì)算出螢火蟲j在適應(yīng)度增加的前提下向方向i移動(dòng)的概率P（A=c?i|B），選擇使得該概率最大的前m?項(xiàng)所對應(yīng)的方向進(jìn)行移動(dòng)，為螢火蟲個(gè)體的移動(dòng)帶來啟發(fā)信息。這就是基于貝葉斯估計(jì)的螢火蟲算法（firefly algorithm based on Bayesian estimation，F(xiàn)ABE）的核心思想。

另外，注意到式（5）中分母部分對于所有i均相同，是常數(shù)項(xiàng)，因此可以省略這一部分，以分子代替整體值，這樣可以大大減小計(jì)算量，減少算法運(yùn)行時(shí)間。

3仿真實(shí)驗(yàn)

為說明本文提出改進(jìn)算法的有效性，對4種典型的測試函數(shù)進(jìn)行了測試[10]，如表1所示。

仿真實(shí)驗(yàn)在Anaconda3 Spyder平臺(tái)下運(yùn)行，運(yùn)行環(huán)境為Win10系統(tǒng)下Intel（R） Core（TM） i5?7300HQ處理器。螢火蟲個(gè)數(shù)?N?=25，算法終止條件為滿足最大迭代次數(shù)?k??max?=200。除Schaffer函數(shù)外，x的維度均選取為20維，根據(jù)文獻(xiàn)[1]給出的建議，算法參數(shù)選取為：?α=0?6，β=1，γ?值由函數(shù)定義域確定，Griewank選取為0?001，其余函數(shù)中均取0?01。對4個(gè)函數(shù)分別采用FA、LFA、HEFA、FAGO、FABE進(jìn)行對比實(shí)驗(yàn)，為克服實(shí)驗(yàn)的隨機(jī)性，每個(gè)函數(shù)分別以不同的初始隨機(jī)值運(yùn)行10次，每種方法采用相同初始隨機(jī)值以進(jìn)行對比。

各函數(shù)的具體情況分析如下。

3?1Sphere函數(shù)

Sphere函數(shù)是簡單的單峰函數(shù)，五種算法在同一維度下的最優(yōu)值、平均值、耗時(shí)及對應(yīng)方差如表2所示。

圖2展示了最優(yōu)值和平均值的變化曲線，橫軸為迭代次數(shù)，縱軸為函數(shù)值的對數(shù)。

從表2中可以看出：

1）在最優(yōu)值和平均值方差上，LFA較大，F(xiàn)AGO和FABE相對較小，說明FAGO和FABE更為穩(wěn)定;

2）在最優(yōu)解收斂精度上， FAGO、 FABE比其他算法提升1～2個(gè)數(shù)量級，F(xiàn)AGO略優(yōu)于FABE;

3）在平均解收斂精度上，F(xiàn)AGO和FABE優(yōu)勢較為明顯，比其他算法提升2～3個(gè)數(shù)量級;LFA通過動(dòng)態(tài)修改螢火蟲算法的參數(shù)，提高了算法最優(yōu)值的收斂速度和精度，但無法保證整體均值收斂速度和精度增加。

4）在耗時(shí)上，五種算法均處于同一數(shù)量級，F(xiàn)A耗時(shí)最短，F(xiàn)ABE次之，F(xiàn)AGO和LFA耗時(shí)長度相近，HEFA耗時(shí)最長。

從圖2中可以看出，F(xiàn)A最早收斂但過早陷入局部最優(yōu)，F(xiàn)AGO收斂速度較快且取得了較高的精度。

3?2Schaffer函數(shù)

Schaffer函數(shù)是多峰函數(shù)，局部極小值分布較為集中。測試結(jié)果如表3及圖3所示，為方便展示，圖3最優(yōu)值變化曲線縱坐標(biāo)為函數(shù)值的對數(shù)，平均值變化曲線縱坐標(biāo)為函數(shù)值本身。

從表3中可以看出：

1）五種算法中，在最優(yōu)值和平均值上，F(xiàn)ABE均最為穩(wěn)定;

2）在最優(yōu)值斂精度上，F(xiàn)AGO最優(yōu)值精度最高，F(xiàn)ABE次之，僅低于FAGO一個(gè)數(shù)量級，平均值的精度方面FAGO和FABE基本相同，均領(lǐng)先其他算法約4個(gè)數(shù)量級;

3）在耗時(shí)上，F(xiàn)AGO、FABE、 LFA三者較為接近，且均短于HEFA。圖3中可以看出，F(xiàn)ABE最快收斂，F(xiàn)AGO收斂速度略慢于FABE。

3?3Griewank函數(shù)

Griewank函數(shù)是多峰函數(shù)，局部極小值分布較為廣泛。五種算法在20維下最優(yōu)值、平均值、耗時(shí)的測試結(jié)果如表4和圖4所示。

從表4中可以看出：

1）相比上文中提到的兩個(gè)函數(shù)，5種算法的方差均有所增加，說明測試Griewank函數(shù)時(shí)穩(wěn)定性有所下降，相對而言，F(xiàn)AGO和FABE穩(wěn)定性較好;

2）在最優(yōu)值收斂精度上，F(xiàn)ABE最高，LFA其次，F(xiàn)AGO低于FABE近兩個(gè)數(shù)量級且收斂速度快于FABE，說明過早陷入局部最優(yōu)，分析原因， FAGO采用當(dāng)前全局最優(yōu)作為啟發(fā)信息，容易被分布較為廣泛且彼此相差不大的局部極小值迷惑，尋優(yōu)能力相對較差;

3）在耗時(shí)上，F(xiàn)ABE和LFA接近，F(xiàn)AGO耗時(shí)較短，三者均明顯快于HEFA。

從圖4中可以看出，F(xiàn)A過早收斂于較差的局部最優(yōu)解，HEFA、FAGO收斂速度較快但精度較差，F(xiàn)ABE收斂精度大于HEFA，但收斂速度略慢。

3?4Rosenbrock函數(shù)

Rosenbrock函數(shù)是常見的復(fù)雜單峰函數(shù)，在其空間內(nèi)走勢平緩，全局最優(yōu)點(diǎn)處于拋物線的頂點(diǎn)，所以很難收斂到全局最優(yōu)。測試結(jié)果如表5及圖5所示。從表5可以看出：

1）對于Rosenbrock函數(shù)，幾種算法穩(wěn)定性均較差，F(xiàn)ABE和HEFA穩(wěn)定性最好，F(xiàn)AGO次之，LFA穩(wěn)定性較差;

2）在收斂精度上，最優(yōu)值中FABE和FAGO精度最高且結(jié)果相似，在平均值中FABE精度略高于FAGO;

3）在耗時(shí)上與Griewank函數(shù)中的結(jié)論類似，HEFA耗時(shí)最長，F(xiàn)ABE和LFA其次，F(xiàn)AGO耗時(shí)較短，F(xiàn)A最快。

從圖5可以看出，在收斂速度上，F(xiàn)AGO、FABE收斂速度均快于其他算法。

4結(jié)論

本文為螢火蟲算法引入了全局最優(yōu)和貝葉斯估計(jì)兩種啟發(fā)信息，提高了算法最優(yōu)值和平均值的收斂精度，在一定程度上加快了算法收斂速度。仿真實(shí)驗(yàn)結(jié)果表明：

LFA、HEFA、FAGO、FABE最優(yōu)值的求解精度均優(yōu)于經(jīng)典螢火蟲算法，F(xiàn)AGO、FABE精度普遍高于LFA、HEFA，且具有良好的穩(wěn)定性，LFA方差較大。無論是單峰還是多峰函數(shù)，F(xiàn)AGO、FABE平均值精度明顯高于LFA、HEFA和FA，且穩(wěn)定性強(qiáng)于其他算法。

在完成固定迭代次數(shù)情況下，F(xiàn)AGO與LFA耗時(shí)接近， FABE耗時(shí)略長，但明顯快于HEFA。不考慮過早陷入局部最優(yōu)的情況，F(xiàn)AGO、FABE兩種算法平均值、最優(yōu)值達(dá)到各自的最小值所需迭代次數(shù)均小于其他算法，即收斂速度較快，在多數(shù)情況下，F(xiàn)AGO比FABE更快。FAGO更適合處理單峰問題和局部極小值分布較為集中的多峰問題，極小值分布相對分散的多峰問題更適合選用FABE。

參 考 文 獻(xiàn)：

[1]YANG X S. Firefly Algorithms for Multimodal Optimization[C]// Berlin， Heidelberg， International symposium on stochastic algorithms. Springer， 2009： 169.

[2]HUSSELMANN A V， HAWICK K A. Parallel Parametric Optimization with Firefly Algorithms on Graphical Processing Units[C]// Las Vegas， USA， CSREA （16-19 July 2012）. 2012： 77.

[3]ATTIA K A M， NASSAR M W I， El?ZEINY M B， et al. Firefly Algorithm Versus Genetic Algorithm as Powerful Variable Selection Tools and Their Effect on Different Multivariate Calibration Models in Spectroscopy： A Comparative Study[J]. Spectrochemical Acta Part A： Molecular and Biomolecular Spectroscopy， 2017， 170： 117.

[4]劉長平， 葉春明. 置換流水車間調(diào)度問題的螢火蟲算法求解[J]. 工業(yè)工程與管理， 2012（3）： 56-59+ 65.

[5]YANG X S. Firefly Algorithm， Levy Flights and Global Optimization[C]// London， Springer， 2010： 209.

[6]ABDULLAH A，DERIS S， MOHAMAD M S， et al. A New Hybrid Firefly Algorithm for Complex and Nonlinear Problem[C]// Berlin， Heidelberg， Springer， 2012： 673.

[7]YANG X S，Nature?Inspired Optimization Algorithms[M]. Amsterdam， Elsevier Science Publishers， 2014.

[8]CHENG S， LU H， LEI X， et al. A Quarter Century of Particle Swarm Optimization[J]. Complex & Intelligent Systems， 2018，1（3）： 1.

[9]AlMUTAIRI A O. Bayesian Estimation Using （Linex） for Generalized Power Function Distribution[J]. Lobachevskii Journal of Mathematics， 2018， 39（3）： 297.

[10]Surjanovic， S. Bingham， D. Virtual Library of Simulation Experiments： Test Functions and Datasets[EB/OL]. http：//www.sfu.ca/～ssurjano 2017-08-01 / 2018-09-01.