基于利維飛行和變異算子的螢火蟲算法

何 櫟，姚青山，李 鵬，姜天琳

(1. 河南工程學院 計算機學院，河南 鄭州 451191；2. 河南省智慧建筑物聯(lián)網(wǎng)工程研究中心，河南 鄭州 451191)

0 引 言

受螢火蟲社會行為的啟發(fā)，標準螢火蟲算法(stan-dard firefly algorithm，SFA)由Xin-She Yang[1]提出。SFA是一種基于螢火蟲閃光特性行為的群體技術(shù)。由于螢火蟲算法(firefly algorithm，F(xiàn)A)操作簡單，參數(shù)設置較少，在優(yōu)化工程實踐中得到了廣泛的應用。為提升螢火蟲算法性能，多種策略被用于調(diào)節(jié)算法的控制參數(shù)，多種優(yōu)化方法與SFA結(jié)合[2]。光強差用于自適應調(diào)節(jié)FA參數(shù)[3]；鄰域吸引力用來防止搜索過程中的振蕩和較高的計算時間復雜度[4]；潮汐力公式已被用于修改FA，并在功能適應性的探索與開發(fā)之間保持平衡[5]。FA的理論分析已經(jīng)開展[6]。

為了進一步加強FA算法的全局搜索能力和避免陷入局部最優(yōu)，提出了一種基于利維飛行和變異算子的螢火蟲算法(levy flight and mutation operator based firefly algorithm，LMFA)。當螢火蟲不能提高自身解的質(zhì)量超過一定的次數(shù)后，螢火蟲的位置將借助利維飛行進行重分布，若結(jié)果依然沒有改善，變異算子將用于擴大螢火蟲的多樣性并改進解的質(zhì)量。LMFA在廣泛采用的基準函數(shù)上的測試結(jié)果在多數(shù)情況下優(yōu)于其它5種代表性的FA算法。

1 FA,利維飛行和變異算子

1.1 FA

螢火蟲通過有效化學反應發(fā)光。光線被用來吸引獵物和異性成員，并警告食肉動物。雄性螢火蟲在尋找配偶時，會以一定的模式進行閃光，吸引周圍雌性螢火蟲。感興趣的雌性螢火蟲會回答，幫助雄性螢火蟲找到其休息的地方。螢火蟲的閃光是一個信號系統(tǒng)，可以與待優(yōu)化的目標函數(shù)相關(guān)聯(lián)[1]。

我們首先描述標準螢火蟲算法SFA，然后介紹其改進算法。

在SFA[1]中，每個螢火蟲都向更亮的螢火蟲學習以更新自己的位置。令Xi=[xi,1,xi,2,…,xi,D] 表示第i個螢火蟲的位置，其中i=1,2,…,N。 令G=[g1,g2,…,gD] 表示種群中最優(yōu)的螢火蟲位置。螢火蟲的亮度由目標函數(shù)決定。螢火蟲的吸引力與相鄰螢火蟲的光強度成正比。吸引力β定義為

(1)

其中，β0,γ,rij分別是預定義的吸引力，光吸收系數(shù)，螢火蟲i和j之間的距離[1]。第i個螢火蟲被另一只更亮的第j個螢火蟲所吸引。第i個螢火蟲的位置更新如式所示

xi,d=xi,d+β·(xj,d-xi,d)+α·sd·εi,d

(2)

其中，α表示一個隨機參數(shù)，sd表示一個參數(shù)，εi,d服從某種隨機分布，缺省情況下服從均勻分布。

SFA的流程如算法1所示，其中f(X)是目標函數(shù)，N是種群大小，F(xiàn)Es是適應度評估次數(shù)，MAX_FEs是適應度最大評估次數(shù)。

算法1：標準螢火蟲算法FA

(1) 目標函數(shù)f(X),X=[x1,x2,…,xD];

(2) 螢火蟲種群初始化Xi(i=1,2,…,N);

(3) 計算每個螢火蟲的適應度值f(Xi);

(4)FEs=N;

(5)whileFEs≤MAX_FEsdo

(6)fori=1 toNdo

(7)forj=1 toNdo

(8)iff(Xi)>f(Xj)then

(9) 根據(jù)式(2)將Xi移向Xj；

(10) 計算更新后Xi對應的適應度值;

(11)FEs++;

(12)end

(13)end

(14)end

(15) 對螢火蟲進行排序并且找出種群中最佳螢火蟲;

(16)end

(17) 對螢火蟲進行后處理和可視化.

1.2 利維飛行

動物和昆蟲的飛行行為已經(jīng)在許多研究中得到了分析。這種飛行行為已經(jīng)應用于優(yōu)化和搜索算法中，研究結(jié)果表明其在搜索算法領(lǐng)域的重要性[7-9]。

利用利維飛行策略改進了許多算法的搜索過程。將式中εi,d設置為服從利維分布，結(jié)果表明，基于利維飛行的FA以更高概率更有效地找到全局最優(yōu)[10]。利維飛行搜索策略和反向?qū)W習(opposition based learning)應用于差分進化算法，在大多數(shù)情況下新算法在可信度、有效性、準確性優(yōu)于基本DE[8]。當粒子在有限時間內(nèi)不能改進自身解時，粒子在搜索空間中采用利維飛行方法進行重新分配[7]。

利維飛行是從利維穩(wěn)定分布中抽取的一類隨機漫步方法。利維飛行Levy(λ)可以如式進行計算[11]

(3)

(4)

其中，Г服從標準Gamma分布。

1.3 變異算子

遺傳算法是一種基于自然選擇的求解有約束和無約束優(yōu)化問題的方法。在從當前種群創(chuàng)建新種群的每個步驟中，有3種基本算子：選擇算子選擇對下一代群體有貢獻的個體；交叉算子將兩個父代結(jié)合起來，形成下一代個體；變異算子對父代個體應用隨機變化來形成子代。生物實驗結(jié)果表明，生物的行為和遺傳信息是相互影響的。變異算子引入隨機修改，其目的是保持種群的多樣性和抑制過早收斂[12,13]。變異算子在搜索空間中引入了隨機漫游。變異算子在遺傳算法、遺傳設計算法和混合遺傳算法等群體智能算法中都有應用[12,14]。

2 基于利維飛行和變異算子的螢火蟲算法(LMFA)

2.1 利維飛行和變異算子方法

我們提出一種算法，即基于利維飛行和變異算子的螢火蟲算法(Levy flight and mutation operator based firefly algorithm，LMFA)。一般情況下，螢火蟲位置用式進行更新。如果螢火蟲的適應度在一定次數(shù)(用sg表示)迭代后沒有改善，可以認為螢火蟲深深陷入了局部最優(yōu)狀態(tài)。此時，螢火蟲的新狀態(tài)可以這樣計算

Oi=xi+Levy(λ)·randn(0,1)

(5)

其中，Levy(λ)用式(3)表示，randn是標準正態(tài)分布函數(shù)。

算法2：基于利維飛行和變異算子的螢火蟲算法LMFA

(1)/*初始化 */

(2)fori=1toNdo

(3) 隨機初始化Xi,Oi;ci=0; 評估f(Xi);

(4)endfor

(5)

(6)/*主循環(huán)*/

(7)Repeat

(8)fori=1toNdo

(9)f(Oi)=inf;

(10)forj=1toNdo

(11)iff(xj)

(13)fork=1toDdo

(14)tempd=xi,d+β·(xj,d-xi,d)+α·sd·εi,d;

(15)endfor

(16) 評估f(temp);

(17)iff(temp)

(18)Oi=temp;f(Oi)=f(temp);

(19)endif

(20)endif

(21)endfor

(22)endfor

(23)fori=1toNdo

(24)iff(Oi)

(25)ci=0;xi=Oi;f(xi)=f(Oi);

(26)else

(27)ci=ci+1;

(28)endif

(29) /*經(jīng)過sg次，f(xi) 停止改進*/

(30) 根據(jù)過程1進行計算

(31)endfor

(32)until終止條件

過程1：利維飛行和變異策略

(1)/*經(jīng)過sg次，f(xi) 停止改進*/

(2)ifci>sgthen

(3) /*利維飛行*/

(4)Oi=xi+levy(λ)·randn(0,1); 評估f(Oi);

(5)iff(Oi)

(6)xi=Oi;f(xi)=f(Oi);ci=0;

(7)else

(8) /*變異*/

(9)Oi=xi;

(10)forj=1toDdo

(11)ifrand(0, 1)

(12)oi,d=rand(lbd,ubd)

(13)endif

(14)endfor

(15) 評估f(Oi);

(16)iff(Oi)

(17)ci=0;xi=Oi;f(xi)=f(Oi);

(18)else

(19)ci=ci+1;

(20)endif

(21)endif

(22)endif

接著更新螢火蟲的位置

(6)

如果利維飛行不能幫助螢火蟲逃離局部最優(yōu)狀態(tài)，變異算子將被用于更新螢火蟲的狀態(tài)信息

(7)

其中，lbd和ubd分別是螢火蟲第d維的下限和上限，pm是變異的概率。這種變異使螢火蟲探索的范圍更廣。式(6)決定螢火蟲位置是否更新。

通過利維飛行和變異算子，螢火蟲能夠迅速改變搜索方向，以便跳出局部最優(yōu)解。

簡言之，對于每個螢火蟲，它像SFA一樣在搜索空間中更新位置，當它遇到早熟時，采用利維飛行和變異算子尋找更優(yōu)解。LMFA的偽代碼如算法2所示，利維飛行和變異策略如過程1所示。可以看出，LMFA容易執(zhí)行。

LMFA保留了FA的基本框架，螢火蟲通過向周圍更加明亮的螢火蟲學習來更新自己的位置。LMFA的新穎之處在于，利用利維飛行和變異算子使螢火蟲保持種群多樣性，潛在地提高了螢火蟲的勘探和開發(fā)能力。

2.2 LMFA的復雜度分析

LMFA的計算開銷取決于螢火蟲初始化Tinit、函數(shù)評估Teval、SFA的位置更新Tupda、利維飛行算子T利維、變異算子Tmuta。假設D是搜索空間的維度，MaxFEs是算法允許的最大評估次數(shù)。在最壞的情況下，我們有Tupda=D，T利維=D，Tmuta=D。 此外，SFA的位置更新、利維飛行、變異算子都會消耗評估次數(shù)，這三者的最大迭代次數(shù)是MaxFEs/3。 因此，LMFA在最壞情況下時間復雜度為T(D)=Tinit+[(Teval+Tupda)+(Teval+T利維)+(Teval+Tmuta)]·(MaxFEs/3)=D+[(D+D)+(D+D)+(D+D)]·(MaxFEs/3)=D·(1+2·MaxFEs)。 因此，LMFA的時間復雜度為O(D*MaxFEs)，近似于MaxFEs。 由于參數(shù)MaxFEs通常設置為10000·D，所以LMFA的時間復雜度與空間維度D的二次方成正比。

3 實 驗

3.1 實驗設置

被廣泛采用的CEC2015評測函數(shù)[15]被用于測試所提出算法的性能。評測集包含15個函數(shù)，其中10個在表1中列出。所有函數(shù)都被表達為最小優(yōu)化問題。評測集包含4類函數(shù)，其中f1和f2是單模函數(shù)，f3-f5是簡單多模函數(shù)，f6-f8是混合函數(shù)，f9-f15是復合函數(shù)。函數(shù)f1到f15是由表2中列出的14個基本函數(shù)構(gòu)成的。

表1 來自CEC的評測函數(shù)

f(x)=g1(M1z1)+g2(M2z2)+…+
gN(MNzN)+f*(x)

(8)

復合函數(shù)的形式如式所示[15]

(9)

其中，gi(x)是用于構(gòu)造復合函數(shù)f(x)的第i個基本函數(shù)，N是基本函數(shù)的數(shù)量，biasi定義哪個是全局最優(yōu)，λi用于控制每個gi(x)的高度，ωi是每個gi(x)的權(quán)重。

為了驗證新算法的性能，LMFA與5種代表性的FA算法進行比較。這些算法的參數(shù)遵循相應文獻的設置，如表3所示，其中ubd和lbd表示螢火蟲在第d維移動的上限和下限。這些算法都在30維函數(shù)上進行測試，最大評估次數(shù)都設置為MaxFEs=10000D。

所有實驗都是在擁有AMD Core FMTM8350 CPU 4 GHz、8G內(nèi)存和安裝Windows 7操作系統(tǒng)的計算機運行。

3.2 參數(shù)選取

變異概率pm和停止間隔sg可能是影響LMFA的重要因素。pm分別取值0,0.001,0.005,0.01,0.05,0.1,和0.2，此時其它參數(shù)的值與表3保持一致。單模函數(shù)f1和f2、簡單多模函數(shù)f3、f4、f5用來進行參數(shù)選取實驗。不同pm設置對于LMFA的影響如圖1所示，其中橫軸表示pm值，縱軸表示每個函數(shù)的平均誤差。可以看出，pm可以設置為0.05左右，此時LMFA在單模函數(shù)和簡單多模函數(shù)上都表現(xiàn)比較好。

進一步進行sg對LMFA影響的實驗。sg分別設置為1,2,…, 10，此時其它參數(shù)保持不變。從圖2可以看出，解的準確率對停止間隔sg不是很敏感，sg取不同值，算法都表現(xiàn)比較好的性能。這個參數(shù)決定螢火蟲的跳躍行為。一個小的sg將使得螢火蟲頻繁改變正常的搜索過程并導致種群震蕩，而一個大的sg會使螢火蟲長時間陷入局部最小值。綜合考慮，pm=0.05和sg=7適合于LMFA。

表2 來自CEC的基本函數(shù)[15]

表3 參數(shù)設置

圖1 變異概率pm對LMFA性能的影響

圖2 停止間隔sg對LFMA性能的影響

3.3 實驗結(jié)果和討論

在本節(jié)，我們將比較LMFA和其它FA算法，包括SFA[16], MSDN-FA[17], YARPIZ-FA[18], LFA[10], DEFA[19]。所有算法中一個種群由50個螢火蟲構(gòu)成。每個算法對每個函數(shù)測試30次，然后記錄平均最好適應度。

表4匯總了這6種算法的計算結(jié)果,6個算法中最好結(jié)果用粗體表示。LMFA與其它5種FA算法的比較結(jié)果用w/t/l表示，這意味著與競爭者相比較，LMFA在w個函數(shù)上勝出，在t個函數(shù)上沒有明顯優(yōu)勢，在l個函數(shù)上落后。結(jié)果表明，SFA、MSDN-FA和LFA幾乎沒有為所有問題找到較好的解，并且在所有函數(shù)上都陷入局部最小值。與SFA、MSDN-FA和LFA相比，LMFA取得了更好的結(jié)果。LMFA在12個評測函數(shù)上結(jié)果優(yōu)于YARPIZ-FA和DEFA，而YARPIZ-FA和DEFA分別在3個和2個評測函數(shù)上優(yōu)于LMFA。

表4 SFA, MSDN-FA, YARPIZ-FA, LFA, DEFA, and LMFA的平均誤差

表4(續(xù))

Friedman是非參數(shù)統(tǒng)計測試，用于單向重復測量的方差分析。Friedman測試用于比較所有6種FA算法在測試集上的性能。表5列出了Friedman測試中LMFA和其它5種FA算法的平均秩。最佳秩(具有最小秩)用粗體表示。可以看出，LMFA的秩最小，表明總體性能優(yōu)于其它5種FA算法。

表5 6個FA算法進行Friedman 測試的平均秩

如圖3所示LMFA和其它5種FA算法在多個函數(shù)上的收斂曲線。可以看出，在大多數(shù)函數(shù)上，LMFA收斂速度快于其它算法。

圖3 SFA, MSDN-FA, YARPIZ-FA, LFA, DEFA, LMFA對于多個函數(shù)的收斂曲線

4 結(jié)束語

提出了一種FA算法，該算法采用利維飛行和變異算子來防止螢火蟲陷入局部極小值。利維飛行帶來了隨機漫步，而變異算子則為螢火蟲注入了多樣化的信息，從而加強全局探索。如果螢火蟲不能改善自身解，則利用利維飛行和變異算子將螢火蟲重新分布到搜索空間。為了驗證LMFA的性能，使用了一組具備不同特征的數(shù)值基準評測函數(shù)，并將提出的算法與幾種具有代表性的FA算法進行了比較。實驗結(jié)果表明，該算法在全局搜索能力、求解精度和搜索速度等方面具有優(yōu)勢。