劉彥伶，樊棠懷，王 暉，康 平，趙 嘉

(南昌工程學院 信息工程學院，江西 南昌 330099)

0 引 言

螢火蟲算法(firefly algorithm，F(xiàn)A)[1]是Yang等提出的一種群智能優(yōu)化算法(swarm intelligent algorithm，SIA)[2]，由于其思想簡單、易于實現(xiàn)并擁有較好的優(yōu)化性能，受到了廣泛關(guān)注。但FA采用全吸引模型，即每只螢火蟲都會被任意一只更亮的螢火蟲吸引，導致螢火蟲在移動過程中發(fā)生振蕩而使算法收斂速度減慢。為提高螢火蟲算法的優(yōu)化性能，許多學者從吸引模型角度對FA提出改進。Wang等[3]提出了一種隨機吸引模型來有效減少個體的移動次數(shù)，避免運動過程中的粒子振蕩，加快算法收斂速度。文獻[4]讓每只螢火蟲與鄰域內(nèi)的螢火蟲進行比較，通過調(diào)整鄰域范圍來有效平衡算法的探索與開發(fā)能力。Zhou等[5]提出了一種部分吸引模型，即螢火蟲隨機地從種群中選擇3只優(yōu)于自身的螢火蟲進行學習。與全吸引模型相比，上述提到的吸引模型減少了粒子運動次數(shù)，避免了算法運行過程中的粒子振蕩，但均采用了統(tǒng)一的進化方式且都向最好的粒子靠近，當最優(yōu)粒子陷入局部最優(yōu)，算法將快速收斂到局部極值，導致算法精度不高。

策略協(xié)同是螢火蟲算法的研究熱點，通過結(jié)合其它方法的優(yōu)勢來挖掘FA更好的優(yōu)化性能。Lv等[6]將高斯擾動與螢火蟲算法相融合，提出了具有高斯擾動和局部搜索的螢火蟲算法。文獻[7]中使用韋伯分布和步長單調(diào)遞減方式，來對螢火蟲的移動公式進行改進，以提高算法前期全局探索能力和后期的局部開發(fā)能力。文獻[8]構(gòu)建廣義中心粒子進行單維深度學習，再讓其它粒子使用隨機吸引模型向其進行學習。上述提出的各改進算法對算法性能有了較大提升，但由于使用的學習策略單一，算法的普適性不強。

基于上述分析，為提高FA優(yōu)化性能，本文提出了一種基于金字塔模型和多策略協(xié)同的螢火蟲算法(firefly algorithm based on pyramid model and multiply cooperative strategies，PMFA-MCS)。借鑒金字塔分層結(jié)構(gòu)和三角穩(wěn)定性，PMFA-MCS將螢火蟲種群按適應(yīng)度排序后分為4層，每層螢火蟲分別使用相對應(yīng)的策略向自身或更高層粒子學習一次，形成金字塔模型，提高了群體的多樣性且避免發(fā)生振蕩。每層粒子使用不同的學習策略，構(gòu)成了多策略協(xié)同，平衡了探索與開發(fā)能力。算法在每一次迭代后將種群重新排序，保證了信息共享與傳遞。實驗部分，測試了兩組函數(shù)集，將PMFA-MCS的結(jié)果與其它改進螢火蟲算法及其它群智能算法進行了比較。

1 螢火蟲算法

螢火蟲算法是一種群智能隨機搜索技術(shù)，它基于螢火蟲的閃光和吸引特性來模擬螢火蟲的社會行為。其算法的數(shù)學描述如下：

設(shè)螢火蟲種群大小為N，維度為D，則第i(i=1，2，…，N) 個螢火蟲可行域空間中的位置可以表示為Xi=(xi1，xi2，…，xiD)。 螢火蟲的光亮強度I定義如下

I=I0e-γrij2

(1)

式中：I0為螢火蟲在r=0時的光亮強度，γ為光吸收系數(shù)，通常設(shè)置為1，rij為螢火蟲i與j之間的歐式距離，它的計算公式如下

(2)

式中：xid和xjd為螢火蟲i和螢火蟲j的第d維位置。

螢火蟲的吸引力公式通過以下公式計算

β=β0e-γrij2

(3)

式中：β0為最大吸引度，即r=0時的吸引度。螢火蟲i向螢火蟲j移動的位置更新公式為

xid(t+1)=xid(t)+β(xjd(t)-xid(t))+αid(t)*ε

(4)

式中：xid(t)、xjd(t) 為第t代螢火蟲i和j在第d維的位置；αi(t) 表示第t代螢火蟲i的步長因子；ε是區(qū)間[-0.5，0.5]上的隨機數(shù)。

2 基于金字塔模型和多策略協(xié)同的螢火蟲算法

FA采用全吸引模型，每只螢火蟲均會被其它優(yōu)于自身的螢火蟲吸引，但過多的移動容易發(fā)生振蕩。使用單一策略，種群多樣性缺失，且隨著算法不斷迭代進行，粒子之間逐漸靠近成為相似個體，算法陷入局部最優(yōu)而出現(xiàn)停滯，提前收斂。為了保持種群的多樣性以及算法整體尋優(yōu)，本文提出了一種基于金字塔模型和多策略協(xié)同的螢火蟲算法，從吸引模型和學習策略兩個方面來提高算法性能。

2.1 金字塔模型

金字塔是世界七大奇跡之一，距今已有五千多年的歷史，其數(shù)量眾多、分布廣泛。金字塔屹立千年而不倒的原因在于其斜面與地面的夾角為52度，這與物體自然塌落時的極限角和穩(wěn)定角相近。生態(tài)系統(tǒng)中也存在類似金字塔結(jié)構(gòu)的錐體，層與層之間的有機體相互制約，維持了自然界物種間的平衡，保證了生態(tài)系統(tǒng)的穩(wěn)定。因此，金字塔結(jié)構(gòu)被后人廣泛應(yīng)用于生活中。

螢火蟲種群中，同樣存在著類似金字塔的吸引模式。螢火蟲的發(fā)光強度存在差別，最亮的一部分螢火蟲數(shù)量較少，只在空中小范圍內(nèi)飛翔，并釋放信號等待其它螢火蟲靠近。亮度較差的螢火蟲數(shù)量相對較多，在區(qū)域內(nèi)隨機地選擇更亮的螢火蟲靠近。亮度一般的螢火蟲數(shù)量中等，既吸引亮度較差的螢火蟲同時自身又向最亮的螢火蟲移動。

在該模型中，第一層為適應(yīng)度最好的粒子，數(shù)量占種群的1/10，我們稱其為領(lǐng)導層。在算法運行前期，螢火蟲種群由最高領(lǐng)導層的粒子同時引領(lǐng)，有效延緩種群中其它粒子向最優(yōu)粒子聚集的速度。為了保持這些“領(lǐng)導者”的信息不被丟失且獲取更為有用的信息，需要賦予最高層螢火蟲一種方法，讓其在自身周圍運動。第二和第三層統(tǒng)稱為過渡層，數(shù)量分別為種群數(shù)的2/10和3/10。第二層粒子的適應(yīng)度僅次于最高領(lǐng)導層，螢火蟲個體仍然攜帶一部分優(yōu)勢信息，需要賦予第二層粒子一種策略使其在保持優(yōu)勢信息的同時又能向更優(yōu)粒子學習。第三層粒子的適應(yīng)度中等，需要賦予一種方法來兼顧種群的探索與開發(fā)能力的平衡。最后一層稱之為探索層，數(shù)量占種群數(shù)的4/10。由于該層中粒子的適應(yīng)度較差，導致其開發(fā)能力弱而探索能力強，因此探索層主要負責跟隨優(yōu)秀粒子探索更多的未知空間，即種群的探索工作。

金字塔學習模型有如下優(yōu)點：

(1)每只螢火蟲都只需要運動一次，有效解決了多次運動產(chǎn)生振蕩的問題。且越高層的螢火蟲被學習的機會越多，符合螢火蟲向更亮個體移動的特性。

(2)不同層螢火蟲的開發(fā)與探索能力存在差別。L1層粒子適應(yīng)度最好，開發(fā)能力最強，L4層粒子適應(yīng)度最差，探索能力最強。每一層粒子根據(jù)自身特點選擇相應(yīng)的策略進行學習，在尋優(yōu)的同時有效維持了算法探索與開發(fā)間的平衡。

2.2 多策略協(xié)同

PMFA-MCS中，按金字塔結(jié)構(gòu)將種群分為了4層，每一層螢火蟲使用不同的策略進行更新。4種策略有機結(jié)合，在不同特征的層上實施，以協(xié)同提高螢火蟲算法的整體性能。迭代一次完成后，種群依據(jù)適應(yīng)度進行重新排序，保證種群內(nèi)的信息共享。下面詳細介紹每一層螢火蟲的特點及更新策略。

2.2.1 領(lǐng)導層

螢火蟲種群按金字塔結(jié)構(gòu)分層后，最高層由適應(yīng)度最好的N/10個粒子組成(設(shè)種群數(shù)量為N)，儲存了種群的優(yōu)勢信息。為保持這些優(yōu)勢信息不被丟失且還能尋得更有用的信息，讓最高領(lǐng)導層的粒子只在自身周圍運動進行局部開發(fā)。因此，在第一層螢火蟲的移動公式上引入貪婪柯西突變策略。柯西變異算子可以幫助粒子迅速逃離局部最優(yōu)，而貪婪策略可以保存種群的優(yōu)勢信息。加入柯西變異進行隨機擾動后螢火蟲的移動公式為

(5)

cauchy() 是柯西變異生成的隨機數(shù)。如果粒子使用該策略后的適應(yīng)值比原來更優(yōu)，則用當前位置取代之前的位置，引導其余個體進化。反之則繼續(xù)保留原來的位置，儲存種群原有的信息。

2.2.2 過渡層

根據(jù)分組規(guī)則，中間過渡層由L2和L3層組成。L2中螢火蟲的適應(yīng)度僅次于L1，其開發(fā)能力強于探索能力，并且儲存有一部分的優(yōu)勢信息。為保持優(yōu)勢信息不被丟失的同時還能向更優(yōu)粒子學習，提出一種雙領(lǐng)導機制，即L2中的螢火蟲在自身周圍運動的同時，由L1中的兩個粒子引導，向更優(yōu)空間進行探索。具體的移動公式如下

xid(t+1)=r1*xid(t)+r2*β1*(xjd-xid(t))+r3*β2*(xkd-xid(t))+α*ε

(6)

式中：j和k是L1中的兩個粒子，r1、r2和r3是(0，1)之間服從均勻分布的隨機數(shù)，且r1+r2+r3=1。

第三層由適應(yīng)度中等的粒子組成，只儲存了少部分的優(yōu)勢信息，需兼顧開發(fā)與探索能力的平衡。為加快收斂速度和開發(fā)精度，將精英鄰域搜索策略分配給L3層粒子。鄰域搜索策略是指給種群中的粒子指定一個優(yōu)化區(qū)間，令該粒子只在這一特定區(qū)間內(nèi)進行進化。許多學者對此進行了深入研究，Wang等[10]將一種全局鄰域搜索機制引入PSO，獲得了不錯的優(yōu)化效果。全局鄰域搜索機制的定義如下

Xi=r1*Xi+r2*gbest+r3*(Xa-Xb)

(7)

式中：gbest為全局最優(yōu)粒子，Xa和Xb為種群中隨機選取的兩個粒子，r1、r2和r3是(0，1)內(nèi)的隨機數(shù)，且r1+r2+r3=1。 隨后，Wang等[11]在全局鄰域搜索機制的基礎(chǔ)上，將兩個粒子的選取方式由全部種群中隨機選擇改為在當前粒子的k鄰域中隨機選擇，這一改進有效提高了FA的性能。

本算法中，根據(jù)金字塔模型的吸引方式，L3層中的個體要向前兩層隨機選擇樣本學習，而L2中粒子數(shù)多于L1，故大概率學習對象在L2層中。本文在該搜索機制的基礎(chǔ)上，將最高層和第二層的領(lǐng)域稱為精英領(lǐng)域，提出一種精英鄰域搜索策略。搜索公式如下所示

xid(t+1)=r1*xid(t)+r2*gbest+r3*(xjd-xkd)+α*S*ε

(8)

式中：gbest是全局最優(yōu)粒子，可以增大L3中的粒子向L1區(qū)域?qū)W習的概率；j和k是從L1和L2中隨機選取的兩個粒子 (j≠k)；r1、r2、r3為3個取值在(0，1)之間的隨機數(shù)，且r1+r2+r3=1。

2.2.3 探索層

PMFA-MCS中，底部探索層中的粒子適應(yīng)度最差，儲存的優(yōu)勢信息最少，側(cè)重于算法的全局探索。FA中每只螢火蟲更新時只選擇一個對象進行學習，種群因此較難逃脫局部極值。因此，為讓L4中螢火蟲能夠較快速地跳出局部最優(yōu)，令其從更高層中隨機選擇3個粒子進行學習，提高螢火蟲個體運動的多樣性并探索到更多的搜索區(qū)域。L4層螢火蟲選擇3個樣本學習的公式如下所示

xid(t+1)=xid(t)+r1*β1*(xjd-xid(t))+r2*β2*(xkd-xid(t))+r3*β3*(xzd-xid(t))+α*ε

(9)

式中：j、k和z是從前面3層中隨機選擇的3個粒子，r1、r2和r3是(0，1)內(nèi)服從均勻分布的隨機數(shù)，且r1+r2+r3=1。

2.3 算法流程

由上述算法思想，給出PMFA-MCS的流程如下：

步驟1 初始化PMFA-MCS參數(shù)，設(shè)置維度為D，螢火蟲種群為N，最大評估次數(shù)MAX_FEs；

步驟2 隨機初始化螢火蟲的位置，并計算每個粒子的目標函數(shù)值。

步驟3 將螢火蟲按照亮度進行排序，并按照金字塔模型分成4層；

步驟4L1螢火蟲按式(5)更新位置，從L2開始至L4，分別按照式(6)、式(8)和式(9)更新位置；

步驟5 檢驗是否滿足終止條件。滿足則運行結(jié)束并輸出結(jié)果，不滿足跳轉(zhuǎn)到步驟3。

3 仿真實驗與分析

3.1 基準測試函數(shù)

本文將使用兩組測試函數(shù)來檢測PMFA-MCS的性能，各測試函數(shù)的最優(yōu)解都是其在定義域內(nèi)的最小值。所有實驗均使用VC++6.0軟件，基于win10系統(tǒng)進行，處理器為Intel(R)Core(TM)i7-6700。

第一組經(jīng)典測試集由12個函數(shù)組成，該組函數(shù)在文獻[8]中被使用，其中f1～f7為單峰函數(shù)，一般用于測試算法的開發(fā)能力；f8～f12為多峰函數(shù)，適用于測試算法的全局探索能力。第二組包含20個測試函數(shù)，每個函數(shù)的定義分類參見文獻[12]。

3.2 與改進螢火蟲算法比較

在本節(jié)中，為了驗證提出的算法的性能，使用12個經(jīng)典的基準測試集函數(shù)，將PMFA-MCS與FA[1]、MFA[13]、WSSFA[14]、VSSFA[15]、RaFA[3]、ApFA[16]和LVFA[17]進行比較。比較的算法使用相同的參數(shù)，維度D設(shè)置為30，最大評估次數(shù)MAX_FEs設(shè)置為5×105，螢火蟲種群個數(shù)N=20。 PMFA-MCS算法中參數(shù)，γ=1/Γ2，Γ為優(yōu)化函數(shù)的域長度，衰減因子C設(shè)置為10。所有算法運行30次，尋優(yōu)結(jié)果的平均值和標準差見表1。

表1 8種算法在12個測試函數(shù)上的實驗對比結(jié)果

表1列出了所有算法的平均最優(yōu)值、標準方差和w/t/l的結(jié)果。其中，符號w表示PMFA-MCS在函數(shù)上優(yōu)于比較算法；符號t表示PMFA-MCS在函數(shù)上與比較算法相當；符號l表示PMFA-MCS結(jié)果不如其它比較算法。從表中可知，PMFA-MCS尋優(yōu)性能總體上優(yōu)于其它7種算法。在所測試的12個基本測試函數(shù)上，PMFA-MCS的性能比FA、WSSFA和VSSFA都要好。與MFA相比，僅在f5和f12上結(jié)果更差，在f6上結(jié)果與MFA一致，而在其余9個測試函數(shù)上都要比MFA的結(jié)果更好；與RaFA相比，PMFA-MCS在除f6外所有單峰函數(shù)上尋優(yōu)精度都要更高，表明算法局部開發(fā)能力較強，多峰函數(shù)中，在f9和f10上結(jié)果更優(yōu)，在f11上結(jié)果相當；與ApFA相比，PMFA-MCS僅在f12上結(jié)果更差，在f6上結(jié)果相當，在剩余測試函數(shù)上結(jié)果更好；與LVFA相比，單峰函數(shù)方面情況與RaFA類似；多峰函數(shù)上，PMFA-MCS僅在f12效果更差。整體而言，PMFA-MCS與各比較算法相比具有較高的尋優(yōu)精度和穩(wěn)定性。

為了進一步比較算法的性能差距，對算法結(jié)果進行Friedman檢驗。表2列出了以上8種算法的Friedman檢測結(jié)果。從表中可以看出，PMFA-MCS秩均值均小于其它比較算法，即PMFA-MCS和其它7種螢火蟲算法相比，性能最優(yōu)。

表2 8種算法在測試函數(shù)上的Friedman檢驗結(jié)果

圖1展示了8種算法在給定的12個基準測試函數(shù)上的收斂過程。從圖中可以看出，PMFA-MCS該組測試函數(shù)上的收斂速度比FA、WSSFA、VSSFA、MFA快。在函數(shù)f1、f2、f3、f4、f7、f9、f10和f11上，PMFA-MCS的尋優(yōu)過程均要快于其它7種算法，且在f1、f3、f9、f11上，PMFA-MCS提前收斂。對于函數(shù)f6，MFA、RaFA、ApFA和PMFA-MCS均提前收斂。而在函數(shù)f5、f10上，PMFA-MCS后來居上，最終在尋優(yōu)結(jié)果上實現(xiàn)了對其它比較算法的超越，驗證了該分層結(jié)構(gòu)學習模型具有提高粒子逃逸局部最優(yōu)的能力。

圖1 8種螢火蟲算法收斂曲線

3.3 時間復雜度分析

對于給定問題f，計算其函數(shù)值的時間復雜度為O(f)，Gmax為算法的最大迭代次數(shù)。對于FA、VSSFA、WSSFA、MFA和ApFA，螢火蟲需要向剩余所有個體學習，故需兩個循環(huán)來遍歷種群，時間復雜度為O(Gmax*N2*(D+f))。 而算法RaFA中，每個粒子只需要在迭代過程中移動一次，所以其復雜度為O(Gmax*N*(D+f))。 LVFA使用分層學習模型，每一層粒子只需運動一次且最高層粒子不運動，故其時間復雜度為O(Gmax*N*(k-1)/k*(D+f))，k為層數(shù)。本文提出的PMFA-MCS算法中，每只螢火蟲只需要運動一次，其時間復雜度與ApFA算法一致，為O(Gmax*N*(D+f))。 表3列出了比較算法的時間復雜度，從中可以看出，本文提出的算法的時間復雜度要優(yōu)于FA、VSSFA、WSSFA、MFA和ApFA，與RaFA相當，比LVFA差。由于LVFA中最高層的優(yōu)勢粒子不運動，而PMFA-MCS中領(lǐng)導層使用柯西突變策略來發(fā)掘更有用的信息，所以PMFA-MCS在性能上優(yōu)于LVFA。

表3 8種算法時間復雜度

3.4 與相關(guān)算法比較

為進一步測試PMFA-MCS的性能，本節(jié)使用第二組測試函數(shù)，將PMFA-MCS與改進DE算法CoDE[18]、JADE[19]和jDEscop[20]，改進PSO算法CLPSO[21]和HCOPSO[12]，改進ABC算法AABCLS[22]、ABCVSS[23]和BABC[24]進行比較。測試函數(shù)的維度設(shè)置為D=50， 算法最大評估次數(shù)設(shè)置MAX_FEs=5000*D， 其它參數(shù)設(shè)置依據(jù)相應(yīng)參考文獻。算法在每個函數(shù)上獨立運行25次，實驗結(jié)果見表4。從表4中可知，PMFA-MCS和HCOPSO二者優(yōu)化性能大致相當。具體來看，相比于3種改進的差分算法，PMFA-MCS均分別在13個函數(shù)上勝出，在6個、6個、5個函數(shù)上處于劣勢。與CLPSO相比，PMFA-MCS僅在f8、f14、f17、f19以及f20上性能較差，在f7上性能相當，在其余14個函數(shù)上均能勝出。與HCOPSO相比，PMFA-MCS在10個函數(shù)上性能相當，在5個函數(shù)上處于劣勢，但差距都很小。而相對于3種改進人工蜂群算法，PMFA-MCS的優(yōu)化性能分別在12個、10個、9個函數(shù)上性能更優(yōu)，且僅在f8、f10、f14、f17及f19、f20處于劣勢，說明對于這些問題，ABC處理效果更優(yōu)?？偟膩砜?，在f1～f7、f9～f13、f18及f20上，PMFA-MCS現(xiàn)出較高的性能，其余函數(shù)性能處于劣勢甚至效果最差。

表4 9種算法在20個測試函數(shù)上的優(yōu)化結(jié)果

表5給出了9種算法在20個測試函數(shù)上的Friedman檢驗結(jié)果。其中，PMFA-MCS的秩均值最小，故PMFA-MCS的綜合性能最優(yōu)。

表5 9種算法在20個測試函數(shù)上的Friedman檢驗結(jié)果

3.5 算法策略分析

PMFA-MCS使用金字塔模型和多種策略協(xié)同來提高FA的性能。為了測試每一種策略對算法的影響，利用11個測試函數(shù)對每種策略進行了實驗。所涉及的算法描述見表6。

表6 不同策略的算法描述

表7給出了不同策略組合的算法運行結(jié)果。從表中可以看出，PMFA在11個函數(shù)上的結(jié)果都要優(yōu)于FA，驗證了金字塔分層模型性能要優(yōu)于全吸引模型。除了f4、f12外，PMFA+S1、PMFA+S2、PMFA+S3、PMFA+S4和PMFA-MCS在所有函數(shù)上的測試結(jié)果都要優(yōu)于PMFA，說明各種策略可以幫助PMFA獲得更好的解。其中，第二種策略對于PMFA性能的改善在總體上要優(yōu)于其它3種策略。對于f4，雖然PMFA+S1、PMFA+S3和PMFA+4的結(jié)果都要比PMFA差，但PMFA-MCS的結(jié)果卻優(yōu)于PMFA，說明通過融合4種策略后的算法將比使用單一策略時優(yōu)化性能更高。

表7 不同策略組合時的算法運行結(jié)果

表8給出了不同策略算法組合的Friedman檢驗結(jié)果。從表中可以看出，PMFA+S2的秩均值排第二，小于PMFA+S1、PMFA+S3和PMFA+S4，這與前文分析一致。

表8 不同策略算法秩均值檢驗結(jié)果

4 結(jié)束語

針對螢火蟲算法使用全吸引模型和單一策略而容易陷入局部最優(yōu)的問題，本文提出了基于金字塔模型和多策略協(xié)同的螢火蟲算法。PMFA-MCS將種群分成4層，每層粒子向更高層優(yōu)勢粒子和自身學習，形成金字塔模型，避免粒子多次運動產(chǎn)生的振蕩。每層粒子使用不同的策略進行學習，平衡了算法的探索與開發(fā)能力，提高了算法的尋優(yōu)精度。實驗部分，將本文算法與其它7種改進螢火蟲算法以及其它8種群智能算法進行比較，結(jié)果表明本文算法具有更好的優(yōu)化性能。