啟發(fā)信息引導的改進螢火蟲算法

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

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

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

DOI：10.15938/j.jhust.2019.01.015

中圖分類號： TP18

文獻標志碼： 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]、流水線調度[4]等方面得到廣泛應用。經(jīng)典螢火蟲算法參數(shù)少、原理清晰且易于實現(xiàn)，同時也存在后期收斂速度慢、收斂精度不高、易陷入局部最優(yōu)的缺陷，為彌補這種缺陷，大量學者對其進行了改進，并取得了一些研究成果。具有代表性的改進方法包括基于參數(shù)動態(tài)調整的改進算法和基于融合思想的改進算法。文[5]介紹了典型的動態(tài)調整參數(shù)方法，將螢火蟲算法和Levy飛行策略結合，利用Levy飛行重尾分布的特性，對螢火蟲算法的隨機移動步長進行了改進，提出了Levy飛行螢火蟲算法（Levy?flight Firefly Algorithm，LFA）;文[6]提出了將螢火蟲算法與差分進化方法融合的思路，將較差的螢火蟲個體組成新種群，利用差分進化方法進行迭代，較優(yōu)個體保持原算法不變，提高了算法擺脫局部最優(yōu)的能力，稱為混合進化螢火蟲算法（Hybrid Evolutionary Firefly Algorithm，HEFA）。

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

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

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

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

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

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

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

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

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

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

k+1時刻，螢火蟲i向著螢火蟲j移動，其位置更新公式為：

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是該時刻螢火蟲i對應的隨機向量，決定了在每個維度上進行移動的方向。

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

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

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

2螢火蟲算法的改進

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

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

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

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

在粒子群優(yōu)化算法中，每個粒子的速度更新利用了其自身的歷史最佳位置?p?best?和整個種群的歷史最佳位置g?best?[8]，也就是說，粒子群算法中的粒子是有記憶的，這大大加快了粒子群算法的收斂速度?；谝陨侠碚?，本文為螢火蟲算法引入“全局最優(yōu)”概念，認為歷史中出現(xiàn)過的最亮螢火蟲的位置對群體有著持續(xù)的吸引力，使螢火蟲個體不但朝著當前最優(yōu)移動，還向著當前全局最優(yōu)移動一定距離，這就是基于全局最優(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時刻記錄的全局最優(yōu)解的位置;w為隨迭代次數(shù)增加而減小的系數(shù)：

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

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

2.3基于貝葉斯估計的螢火蟲算法

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

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

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

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ù)，在·為真和假時分別取值1和0。

同理，記螢火蟲適應度增加為事件B，若統(tǒ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）的結果代入式（5），就可以計算出螢火蟲j在適應度增加的前提下向方向i移動的概率P（A=c?i|B），選擇使得該概率最大的前m?項所對應的方向進行移動，為螢火蟲個體的移動帶來啟發(fā)信息。這就是基于貝葉斯估計的螢火蟲算法（firefly algorithm based on Bayesian estimation，F(xiàn)ABE）的核心思想。

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

3仿真實驗

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

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

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

3?1Sphere函數(shù)

Sphere函數(shù)是簡單的單峰函數(shù)，五種算法在同一維度下的最優(yōu)值、平均值、耗時及對應方差如表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個數(shù)量級，F(xiàn)AGO略優(yōu)于FABE;

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

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

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

3?2Schaffer函數(shù)

Schaffer函數(shù)是多峰函數(shù)，局部極小值分布較為集中。測試結果如表3及圖3所示，為方便展示，圖3最優(yōu)值變化曲線縱坐標為函數(shù)值的對數(shù)，平均值變化曲線縱坐標為函數(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一個數(shù)量級，平均值的精度方面FAGO和FABE基本相同，均領先其他算法約4個數(shù)量級;

3）在耗時上，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)值、平均值、耗時的測試結果如表4和圖4所示。

從表4中可以看出：

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

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

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

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

3?4Rosenbrock函數(shù)

Rosenbrock函數(shù)是常見的復雜單峰函數(shù)，在其空間內走勢平緩，全局最優(yōu)點處于拋物線的頂點，所以很難收斂到全局最優(yōu)。測試結果如表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精度最高且結果相似，在平均值中FABE精度略高于FAGO;

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

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

4結論

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

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)定性強于其他算法。

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

參 考 文 獻：

[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]劉長平， 葉春明. 置換流水車間調度問題的螢火蟲算法求解[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.