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

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

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

0 引 言

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

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

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

1.1 FA

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

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

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

(1)

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

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

(2)

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

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

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

(1) 目標函數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) 根據式(2)將Xi移向Xj；

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

(11)FEs++;

(12)end

(13)end

(14)end

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

(16)end

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

1.2 利維飛行

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

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

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

(3)

(4)

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

1.3 變異算子

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

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

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

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

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

(5)

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

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

(1)/*初始化 */

(2)fori=1toNdo

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

(4)endfor

(5)

(6)/*主循環*/

(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) /*經過sg次，f(xi) 停止改進*/

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

(31)endfor

(32)until終止條件

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

(1)/*經過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)

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

(7)

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

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

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

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

2.2 LMFA的復雜度分析

LMFA的計算開銷取決于螢火蟲初始化Tinit、函數評估Teval、SFA的位置更新Tupda、利維飛行算子T利維、變異算子Tmuta。假設D是搜索空間的維度，MaxFEs是算法允許的最大評估次數。在最壞的情況下，我們有Tupda=D，T利維=D，Tmuta=D。 此外，SFA的位置更新、利維飛行、變異算子都會消耗評估次數，這三者的最大迭代次數是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。 由于參數MaxFEs通常設置為10000·D，所以LMFA的時間復雜度與空間維度D的二次方成正比。

3 實 驗

3.1 實驗設置

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

表1 來自CEC的評測函數

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

(8)

復合函數的形式如式所示[15]

(9)

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

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

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

3.2 參數選取

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

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

表2 來自CEC的基本函數[15]

表3 參數設置

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

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

3.3 實驗結果和討論

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

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

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

表4(續)

Friedman是非參數統計測試，用于單向重復測量的方差分析。Friedman測試用于比較所有6種FA算法在測試集上的性能。表5列出了Friedman測試中LMFA和其它5種FA算法的平均秩。最佳秩(具有最小秩)用粗體表示?？梢钥闯?，LMFA的秩最小，表明總體性能優于其它5種FA算法。

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

如圖3所示LMFA和其它5種FA算法在多個函數上的收斂曲線?？梢钥闯?，在大多數函數上，LMFA收斂速度快于其它算法。

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

4 結束語

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