優(yōu)化算法之螢火蟲算法
? ? 仿生群智能優(yōu)化算法是近些年來國內(nèi)外學者研究的熱點問題，其主要的思想是研究或者模仿自然界群體生活的生物的社會行為而構(gòu)造的隨機搜索方法。目前研究比較多的有兩種算法：蟻群算法（ACO）和粒子群算法（PSO）。有研究結(jié)果表明，仿生群智能優(yōu)化算法為許多應用領域提供了新思路和新方法。
? ??2005年，印度學者K.N.Krishnanand和D.Ghose在IEEE群體智能會議上提出了一種新的群智能優(yōu)化算法，人工螢火蟲群優(yōu)化（Glowworm Swarm Optimization, GSO）算法。2009年，劍橋?qū)W者Xin-She Yang根據(jù)自然界中螢火蟲的發(fā)光行為提出螢火蟲算法（Firefly Algorithm, FA）。自這兩種螢火蟲算法提出以來，各國學者對這兩種算法進行了研究、改進和應用。經(jīng)過幾年的發(fā)展，在連續(xù)空間的尋優(yōu)過程和一些生產(chǎn)調(diào)度方面螢火蟲算法具有良好的應用前景。
? ??GSO和FA有相似的方面，但在具體實現(xiàn)方面有一定差異。本文具體介紹和分析了這兩種算法及其改進算法。
GSO算法
? ??在GSO算法中，每一只人工螢火蟲散步在解空間中，這些螢火蟲帶著熒光，并且擁有各自的視線范圍，稱為決策域（local-decision range）。它們的亮度與自己所在位置上的目標值有關。越亮的螢火蟲表示它所在的位置越好，即有較優(yōu)的目標函數(shù)值。螢火蟲會在決策域范圍內(nèi)尋找鄰居集合，在集合當中，越亮的鄰居擁有越高的吸引力吸引此螢火蟲往這個方向移動，每一次的飛行方向會隨著挑選的鄰居不同而改變。此外，決策域范圍的大小會受到鄰居數(shù)量的影響，當鄰居密度越低，螢火蟲的決策半徑會加大以尋找更多的鄰居；當鄰居密度越高，它的決策半徑會縮小。最后，大部分螢火蟲會聚集在多個位置上，即達到極值點。簡單的說，GSO算法主要包含四個階段：螢火蟲的部署（初始化）、熒光素更新、位置更新階段和決策半徑更新階段。
算法數(shù)學描述
（1）初始化
? ??在可行域中隨機放置n個螢火蟲，并賦予每個螢火蟲的熒光素為l0，動態(tài)決策域為r0。初始化步長s，領域閾值nt，熒光素消失率ρ，熒光素更新率γ，動態(tài)決策域更新率β，螢火蟲感知域rs，迭代次數(shù)M。
（2）更新螢火蟲i的熒光素
li(t)=(1?ρ)li(t?1)+γJ(xi(t))
? ??其中J(xi(t))表示螢火蟲i在t時刻所在位置的目標函數(shù)值；li(t)表示螢火蟲i在t時刻熒光素值。
（3）尋找螢火蟲i的鄰居
Ni(t)={j:||xj(t)?xi(t)||
? ??其中Ni(t)表示螢火蟲i在t時刻鄰居的集合；rid(t)表示螢火蟲i在t時刻動態(tài)決策域。
（4）確定螢火蟲i動作移動方向
j=max(pi)
? ??其中pi=(pi1,pi1,...,piNi(t))，其中pij(t)=lj(t)?li(t)∑k∈Ni(t)(lk(t)?li(t))為轉(zhuǎn)移概率。
（5）更新螢火蟲i的位置
Xi(t+1)=Xi(t)+s(Xj(t)?Xi(t)||Xj(t)?Xi(t)||)
（6）更新動態(tài)決策域
rid(t+1)=min{rs,max{0,rid(t),β(nt?|Ni(t)|)}}
算法基本流程
初始化各個參數(shù)；
隨機初始化第i(i=1,2,...,n)個螢火蟲在目標函數(shù)搜索范圍內(nèi)的位置；
計算螢火蟲i在t時刻的熒光素值li(t)；
每只螢火蟲在其動態(tài)決策域半徑rid(t+1)，選擇熒光素值比自己高的個體組成其領域集Ni(t)，其中0
計算螢火蟲i移向鄰域集內(nèi)個體j的概率pij(t);
利用輪盤賭的方式算則個體j，然后移動，更新位置；
更新螢火蟲動態(tài)決策域半徑的值；
是否到達最大迭代次數(shù)或者要求精度，如果達到這轉(zhuǎn)下一步驟，否則轉(zhuǎn)向步驟4；
輸出全局極值點和最優(yōu)個體值。
FA算法
算法應用原理
? ? 把空間各點看成螢火蟲，利用發(fā)光強的螢火蟲會吸引發(fā)光弱的螢火蟲的特點。在發(fā)光弱的螢火蟲向發(fā)光強的螢火蟲移動的過程中，完成位置的迭代，從而找出最優(yōu)位置，即完成了尋優(yōu)過程。
? ? 螢火蟲算法有以下條件：
1. 假設所有螢火蟲都是同一性別且相互吸引;
2. 吸引度只與發(fā)光強度和距離有關，發(fā)光強的螢火蟲會吸引周圍發(fā)光弱 的螢火蟲，但是隨著距離的增大吸引度逐漸減小，發(fā)光強的螢火蟲會做隨機運動;
3. 發(fā)光強弱由目標函數(shù)決定，在制定區(qū)域內(nèi)與指定函數(shù)成比例關系。
? ? 搜索過程和螢火蟲的兩個重要參數(shù)有關:螢火蟲的發(fā)光亮度和相互吸引度，發(fā)光亮的螢火蟲會吸引發(fā)光弱的螢火蟲向它移動，發(fā)光越亮代表其位置越好，最亮螢火蟲即代表函數(shù)的最優(yōu)解。發(fā)光越亮的螢火蟲對周圍螢火蟲的吸引度越高，若發(fā)光亮度一樣，則螢火蟲做隨機運動，這兩個重要參數(shù)都與距離成反比，距離越大吸引度越小。
算法的數(shù)學描述
（1）螢火蟲的相對熒光亮度：
I=I0e?γrij
? ? 其中，I0表示最亮螢火蟲的亮度，即自身（r=0處）熒光亮度，與目標函數(shù)值相關，目標函數(shù)組越優(yōu)，自身亮度越高；γ表示光吸收系數(shù)，因為熒光會隨著距離的增加和傳播媒介的吸收逐漸減弱，所以設置光強吸收系數(shù)以體現(xiàn)此特性，可設置為常數(shù)；rij表示螢火蟲i與j之間的距離。
（2）相互吸引度β
β(r)=β0e?γr2ij
其中，β0表示最大吸引度，即光源處（r=0處）的吸引度。
（3）最優(yōu)目標迭代
xi(t+1)=xi(t)+β(xj(t)?xi(t))+α(rand?1/2)
? ??其中，Xi與Xj表示i、j兩個螢火蟲的空間位置，α為步長因子，rand為[0,1]上服從均勻分布的隨機因子。
算法基本流程
初始化算法基本參數(shù)。設置螢火蟲數(shù)目n，最大吸引度β0，光強吸收系數(shù)γ，步長因子α，最大迭代次數(shù)MaxGeneration或搜索精度ε；
隨機初始化螢火蟲的位置，計算螢火蟲的目標函數(shù)值作為各自最大熒光亮度I0；
計算群體中螢火蟲的相對亮度I和吸引度β，根據(jù)相對亮度決定螢火蟲的移動方向；
更新螢火蟲的空間位置，對處在最佳位置的螢火蟲進行隨機移動；
根據(jù)更新后螢火蟲的位置，重新計算螢火蟲的亮度；
當滿足搜索精度或達到最大搜索次數(shù)，則轉(zhuǎn)下一步；否則，搜索次數(shù)增加1，轉(zhuǎn)第3步，進行下一次搜索。
輸出全局極值點和最優(yōu)個體值。
算法不足
發(fā)現(xiàn)率低、求解精讀不高、求解速度慢。
螢火蟲算法改進實例
混沌螢火蟲算法
混沌算法步驟
令t=0，將螢火蟲位置信息Xtj，j=1,2,...,n按下式映射為0到1之間的混沌參量cxtj.
cxtj=xtj?xmin,jxmax,j?xmin,j,j=1,2,...,n
映射公式中：變量xmax,j和變量xmin,j分別為搜索空間中第j維的上界和下界。
根據(jù)cxtj，計算得到下一步迭代的混沌參量cxt+1j.
將混沌參量cxt+1j轉(zhuǎn)換為位置信息xt+1J
xt+1j=xmin,j+cxt+1j(xmax,j?xmin,j),j=1,2,...,n
根據(jù)位置信息xt+1j，j=1,2,...,n，對所得新解進行性能評價。
若所得新解優(yōu)于初始解X(0)=[x0i,...,x0n]或者混沌搜索已到預先設定的精度或迭代次數(shù)，則新解作為算法的最終結(jié)果，否則令t=t+1并返回步驟2。
改進混沌螢火蟲算法流程
系統(tǒng)初始化，生成螢火蟲初始種群的規(guī)模、位置信息，設置光強吸收系數(shù)、最大吸引因子和步長因子等參數(shù)
計算群體中每個螢火蟲的熒光亮度
更新權(quán)重公式計算慣性權(quán)重
根據(jù)位置更新公式更新螢火蟲位置，最亮的螢火蟲個體隨機移動
計算位置更新后群體中每個螢火蟲的熒光亮度
計算位置更新后群體中適應度最高的10%的個體，進行混沌局部搜索
計算位置更新后群體中每個螢火蟲的熒光亮度
判斷是否滿足終止條件，如果滿足終止條件則跳出循環(huán)并輸出全局最優(yōu)解，如果不滿足條件則繼續(xù)
按下列兩式收縮搜索區(qū)域：
xmin,j=max{xmax,j,xmaxlight,j?r(xmax,j?xmin,j)},0
xmax,j=min{xmax,j,xmaxlight,j+r(xmax,j?xmin.j)},0
其中，xmaxlight,j表示當前最亮螢火蟲個體的第j為變量的值。
在收縮后的新搜索區(qū)域內(nèi)隨機產(chǎn)生群體中剩余80%的螢火蟲，然后返回步3
變步長螢火蟲算法
? ? 螢火蟲i被亮度更大的螢火蟲j吸引向其移動而更新自己的位置，位置更新公式如下：
xi(t+1)=xi(t)+β?(lij)(xj(t)?xi(t))+α?(rand?1/2)式中，α為步長因子，一般取[0,1]上的常數(shù)；rand為[0,1]上服從均勻分布的隨機因子。
? ? 螢火蟲算法尋優(yōu)是通過螢火蟲之間的相互吸引來實現(xiàn)的，而隨著迭代次數(shù)的增加，螢火蟲群會在最優(yōu)值附件聚集。此時螢火蟲個體與最優(yōu)值之間的距離已經(jīng)非常小，在個體向最優(yōu)值趨近的過程中，很可能會出現(xiàn)螢火蟲移動的距離大于個體與最優(yōu)值間距的情況，而導致個體更新自己位置時跳過了最優(yōu)值，出現(xiàn)震蕩，將會導致最優(yōu)值發(fā)現(xiàn)率降低，影響算法的收斂精度和速度。
? ? 為了盡量避免由上述原因造成的收斂較慢情況，在算法開始時，將初始步長設定為相對較大值，而后隨著迭代次數(shù)以及螢火蟲之間距離增加設定一個判定條件：當個體距離小于某一固定步長時，使步長減小。則螢火蟲算法將在開始時具有較好的全局尋優(yōu)能力，迅速定位在接近全局最優(yōu)解的區(qū)域，而后期也具有良好的局部搜索能力，能精確得到全局最優(yōu)解。
? ? 初始步長α設定為0.25，當?shù)芽柧嚯xl>0.25時，位置更新公式變?yōu)椋?/span>
xi(t+1)=xi(t)+β?(lij)(xj(t)?xi(t))+k?lij?(rand?1/2)式中，k為根據(jù)實際情況可調(diào)整的正相關系數(shù)，即用klij代替固定步長α。
