具備生命周期和信息共享機制的螢火蟲算法設計

陳國保，楊 波，謝智峰

（1江西科技學院信息工程學院 江西 南昌 330098）

（2江西科技學院人工智能學院 江西 南昌 330098）

0 引言

群智能算法是一種隨機優(yōu)化算法族，包含各類仿生算法。如1995年，Kennedy與Eberhart模擬鳥群捕食行為提出的螢火蟲算法（Particle Swarm Optimization,PSO）、2005年，Karaboga模擬蜜蜂采蜜提出的人工蜂群算法（Artificial Bee Colony,ABC）以及2018年，Yang模擬螢火蟲發(fā)光特性提出的螢火蟲算法（Firfly Algorithm, FA）。

群智能算法在解決各領域的優(yōu)化問題時表現(xiàn)出良好性能，但依然存在不足之處，如對參數(shù)敏感、收斂速度慢及易陷入局部最優(yōu)。針對其存在的問題，學者們提出了各種改進策略來提高群智能算法的性能。

針對粒子群優(yōu)化算法的不足，吳大飛等[1]通過制定游離粒子位置更新和精英粒子附近衍生爆炸粒子策略，通過二者策略融合，對比實驗表明，算法的尋優(yōu)性能有較大改善；王曉艷等[2]為了克服粒子群優(yōu)化算法過早停滯、尋優(yōu)精度低等缺點，將種群劃分為進步和停退子種群，進步子種群保持固有的進化方式，停退子種群依據(jù)適應值采取不同更新方式，結(jié)合動態(tài)優(yōu)化的權(quán)重，提高算法全局探索和局部開采的能力；TAO等[3]設計了交叉操作來更新粒子位置，并采用變異機制避免算法陷入局部最優(yōu)，通過計算得到的最短運輸時間，將改進算法與其他智能優(yōu)化算法進行比較。實驗結(jié)果表明，該算法能夠提高AGV在物料運輸中的效率，并驗證了相關改進機制的有效性；LIU等[4]為了解決旅行商問題，研究了一種基于遷移學習的粒子群優(yōu)化算法，該算法利用歷史問題的最優(yōu)信息來引導群體快速找到最優(yōu)路徑，引入具有自適應交叉和聚類引導變異的粒子更新策略，以增強所提出算法的搜索能力；XIA等[5]為粒子的更新添加了一個“亞社會學習”部分的新組件，并基于其適應度為每代粒子分配了三個角色，針對不同角色引入了三種不同學習權(quán)重，在進化過程中，引入了兩個調(diào)整運算符來調(diào)整粒子以求得最優(yōu)解，提出基于適應度的多角色粒子群優(yōu)化算法；WANG等[6]為解決粒子群算法存在計算量大、精度不高、容易陷入局部最優(yōu)等問題，提出了動態(tài)變化速度衰減因子和慣性權(quán)重因子的特殊表達形式，并在算法中在迭代公式中加入一些隨機參數(shù)，應用于算法迭代公式中，以提高算法的優(yōu)化速度和優(yōu)化效果，通過計算機仿真實驗證明了算法的有效性和正確性，算法迭代初期獲得高效的全局搜索能力和迭代后期獲得更好的局部優(yōu)化性能，實驗結(jié)果表明算法優(yōu)化性能表現(xiàn)優(yōu)異。

針對人工蜂群算法的不足，REN等[7]提出了一種基于柯西OBL的人工蜂群算法，在初始化和鄰域搜索階段，分別使用柯西OBL群與傳統(tǒng)初始群競爭，選擇優(yōu)秀個體形成改進的初始群和加入柯西OBL過程，提高種群的質(zhì)量、多樣性、全局探索能力，同時為了加快收斂速度，引入了全局最優(yōu)解和多維更新策略，仿真結(jié)果表明，改進后的算法易于跳出局部優(yōu)化，具有更高的搜索精度和更快的收斂速度；CAO等[8]提出了基于對立學習蜂群算法，采用解搜索方程對蜜蜂相位進行改進，以此保證迭代過程中種群的多樣性，當新生成的解的適應度值小于當前解時，生成相反的解，然后應用貪心選擇策略更新解，并且采用自適應權(quán)重策略動態(tài)調(diào)整權(quán)重，平衡算法的全局探索和局部探索能力，基準函數(shù)實驗表明算法具有更好的收斂速度和優(yōu)化精度；YANG等[9]提出一種改進搜索策略的人工蜂群算法，為了提高初始種群質(zhì)量，增強整體搜索能力，采用混沌映射和逆向?qū)W習的方法對種群進行初始化和基于局部最優(yōu)和全局最優(yōu)的位置更新公式來提高迭代優(yōu)化過程的效率，標準測試函數(shù)仿真實驗表明算法尋優(yōu)性能取得較好表現(xiàn)；LIN等[10]引入交叉和變異算子對采用的蜜蜂和旁觀蜂相位進行修改，對每個解的多個維度進行修改，既省去了將連續(xù)值轉(zhuǎn)換為離散值的過程，又減少了計算資源。此外，一種新穎的貪心選擇策略可以選擇具有更高準確性和更少特征的特征子集，有助于算法快速收斂；ZHOU等[11]提出的改進算法使用多精英指導，其優(yōu)點是利用精英個體的有價值信息來指導搜索，同時又不失種群多樣性。首先，通過選擇一些精英個體來構(gòu)建精英群體，然后在精英群體的基礎上分別將兩個改進的解搜索方程引入雇傭蜂階段和旁觀蜂階段，最后，還利用精英群體開發(fā)了一個改進的鄰域搜索算子，旨在實現(xiàn)探索能力和開發(fā)能力之間的更好權(quán)衡，測試結(jié)果說明改進算法整體性得到極大改善。

針對螢火蟲算法的不足，LI等[12]在FA的更新公式中加入了自適應對數(shù)慣性權(quán)重，分別引入螢火蟲的最小吸引力和一個步長減小因子來動態(tài)調(diào)整隨機步長項，仿真結(jié)果表明改進算法對于許多優(yōu)化問題也具有高性能和最佳效率；ElSHORBAGY等[13]提出了遺傳算法和FA兩種元啟發(fā)式算法的混合算法，以克服FA的缺陷，新一代的個體不僅通過遺傳算法過程形成，而且通過FA機制形成，以防止陷入局部最優(yōu)。引入足夠的解的多樣性，并在探索之間取得平衡趨勢，計算結(jié)果表明，混合算法具有競爭力。

螢火蟲算法參數(shù)少、模型簡單、易于實現(xiàn)，已廣泛應用于優(yōu)化、分類和工程實踐等領域。如在優(yōu)化領域，主要應用于連續(xù)、組合、約束和多目標優(yōu)化等；在分類領域，主要應用于數(shù)據(jù)挖掘、機器學習和神經(jīng)網(wǎng)絡等；在工程實踐領域，主要應用于工業(yè)、農(nóng)業(yè)和商業(yè)優(yōu)化等。

1 標準螢火蟲算法

螢火蟲算法是一種基于群智能的隨機搜索技術(shù)，其思想源于螢火蟲向比自身更亮的螢火蟲移動這一生物學特性。在搜索空間，螢火蟲的位置表示優(yōu)化問題的解，亮度對應優(yōu)化問題的適應值。螢火蟲不斷向更亮的螢火蟲移動，直至達到預設的算法終止條件，完成尋優(yōu)任務。算法可以描述為：群體規(guī)模為N，N個螢火蟲構(gòu)成種群PN，第i（i=1，2，…，N）個螢火蟲在D維空間中的位置可以表示為Xi=（xi1，xi2，…，xiD）。每只螢火蟲都具備光亮強度I和吸引度β。其中，光亮強度決定螢火蟲學習行為，即學習或被學習；吸引度決定螢火蟲的學習距離。通過迭代尋優(yōu)，當滿足一定的終止條件時，輸出全局最優(yōu)螢火蟲，完成種群尋優(yōu)任務。

對于任意兩只螢火蟲和，它們之間的歐氏距離定義如下：

其中，定義螢火蟲的總維度，分別定義螢火蟲和當前的位置。

螢火蟲的光亮強度和吸引度定義如下：

其中，分別定義螢火蟲距離時的光亮強度和吸引度，是光吸收系數(shù)。

螢火蟲在第代的位置定義如下：

其中，t定義種群當前進化代數(shù)，xid（t）和xjd（t）表示螢火蟲i和j在當前的位置，參數(shù)ε=（rand()-1/2）是隨機值，rand()取值空間為[0,1]，a（t）參數(shù)是步長因子，取值空間為[0,1]。

算法流程如下所示。

a.初始化螢火蟲種群并記錄種群的初始位置和適應值；

b.利用式（4）對螢火蟲位置進行更新；

c.計算和評價螢火蟲亮度（適應值）；

d.累計種群適應值的評價次數(shù)；

e.檢驗是否滿足終止條件，若滿足，則停止迭代，輸出全局最優(yōu)位置及其對應的適應值，否則轉(zhuǎn)到b。

2 建立生命周期機制和信息共享機制

2.1 生命周期機制

在各類群智能算法中，種群的進化過程類似于人類不同生命周期階段的學習過程。在幼年生命周期階段，人類通過模仿外界的行為而學習；在少年生命周期階段，人類開始有自我意識，在外界的指導和自我意識下而學習；在中年生命周期階段，人類具備超強的自主意識，不斷地自主學習；在老年生命周期階段，人類積累了豐富的學習經(jīng)驗，向外界傳授學習經(jīng)驗。

在螢火蟲算法的種群進化過程中，主要為早期和后期2個進化階段。在早期進化階段，種群盲目地向外界種群探索式學習；在后期進化階段，種群以自我為中心，引導外界種群開采式學習。種群的早期階段對應于人類的幼年生命階段，后期階段對應于人類的老年生命階段。為使種群的進化過程更加地符合人類不同生命階段的學習過程，在早期和后期進化階段之間，設置了種群的類少年生命進化階段和類中年生命進化階段。

種群的早期和后期階段保持原有的進化策略——探索式進化和開采式進化。在種群的類少年生命周期階段，因種群已具備一定的學習能力，可為該階段制訂融合學習策略，即種群在自我學習的過程中，同時向外界種群學習。在種群的類中年生命周期階段，制訂貪婪式突變學習策略，即保留突變后優(yōu)異的種群。

其中，種群在早期和后期階段按照式（4）保持固有的進化方式，進行探索式進化和開采式進化；在類少年期，種群已具備一定的學習能力，可結(jié)合粒子群算法的進化方式，根據(jù)式（5）開展自我學習和社會學習；在后期，整個種群進入即將收斂的狀態(tài)，此階段采用貪婪策略，完成搜索全局最優(yōu)解任務。

其中，γ（xjd（t）-xbestd（t））表示社會學習項目，表示螢火蟲xi向最優(yōu)螢火蟲xbest學習，γ是外部學習因子。

2.2 信息共享機制

為增強種群間信息的充分交流，基于上述種群的四個生命進化周期，建立信息共享機制。在種群進化過程中，將前階段的優(yōu)勢信息作為輸入，傳遞給下階段，通過各階段的信息共享，最后篩選某個或者若干個子種群作為全局最優(yōu)解。基于生命周期機制，種群進化分為四個生命周期，各階段按照既定的進化方式執(zhí)行搜索。為充分利用各階段積累的優(yōu)勢信息，在種群協(xié)作進化過程中，通過各階段間的正負反饋策略，選擇性保留各階段的局部優(yōu)勢信息，最終完成后期進化，獲取全局最優(yōu)信息，即為整個種群的最優(yōu)解。

3 兩種機制設計

首先，以螢火蟲算法為群智能研究對象，分析其進化策略的搜索特征，選擇合適的進化策略來建立信息反饋機制；其次，針對群體在搜索過程中的不同狀態(tài)，建立種群生命周期機制；最后，通過數(shù)值實驗的反饋結(jié)果，修正算法，設計具備信息反饋和生命周期機制的螢火蟲算法。

4 結(jié)論

生命周期機制是對種群進化階段的劃分。在進化過程中，為每個階段設計獨特的搜索策略，保證各階段具有良好的進化特性，是提高算法性能的關鍵。種群在進化過程中，積累了大量的優(yōu)勢進化信息。為了充分利用種群間的優(yōu)勢信息，在劃分生命周期的基礎之上，引入信息共享機制。在各生命周期階段，種群通過協(xié)作和共享，加速種群進化。

針對各類群智能算法易陷入局部最優(yōu)、普適性差等問題，開展各類群智能算法的進化策略和種群信息傳遞機制研究，提出具備生命周期和信息共享機制的螢火蟲算法。下一步的研究重點工作是探求類少年期和類中年期的搜索策略，以期改進算法性能，拓展算法的應用領域。