多策略融合的改進(jìn)螢火蟲算法

雍 欣，高岳林，2，赫亞華，王惠敏

（1.北方民族大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，銀川 750021；2.寧夏智能信息與大數(shù)據(jù)處理重點(diǎn)實(shí)驗室（北方民族大學(xué)），銀川 750021）

0 引言

受到生物智能群體行為的啟發(fā)提出的智能優(yōu)化算法在解決全局優(yōu)化問題中具有重要的地位，近年來逐漸發(fā)展并得到了廣泛應(yīng)用，成為了優(yōu)化領(lǐng)域的熱點(diǎn)研究問題之一。針對傳統(tǒng)優(yōu)化算法在實(shí)際工程領(lǐng)域中的應(yīng)用存在的算法規(guī)模龐大和復(fù)雜度過高等問題，群智能優(yōu)化算法通過智能個體的群體行為進(jìn)行移動尋找全局最優(yōu)解，擁有更為強(qiáng)大的計算能力和解空間的搜索能力，因此能夠用于解決諸多應(yīng)用問題且已得到了豐富的研究成果［1-4］。典型的群智能優(yōu)化算法有模擬鳥群飛行覓食行為的粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法［1］、模擬蟻群尋找最優(yōu)路徑的蟻群優(yōu)化算法［2］、模擬灰狼群體捕食行為的灰狼優(yōu)化算法［3］等，對于群智能算法的研究主要集中在對現(xiàn)有算法的改進(jìn)和應(yīng)用，以及模仿生物群體行為的新型算法的提出和理論研究。

螢火蟲算法（Firefly Algorithm，F(xiàn)A）是群智能優(yōu)化算法的一種，由Yang［5］于2008 年提出。該算法通過模擬自然界中螢火蟲的發(fā)光行為進(jìn)行尋優(yōu)，將螢火蟲個體的亮度同目標(biāo)函數(shù)值相關(guān)聯(lián)。在算法中，螢火蟲的飛行行為抽象為僅由亮度吸引彼此，它們之間的吸引度則和距離密切相關(guān)，螢火蟲們總是趨向于最亮的個體，即最終收斂到最優(yōu)解。自提出以來，螢火蟲算法得到了領(lǐng)域內(nèi)廣泛的應(yīng)用和研究［6-11］，取得了豐富的研究成果；然而，傳統(tǒng)的螢火蟲算法仍存在一些不足，例如易陷入局部最優(yōu)、收斂速度慢且收斂精度低等問題。

針對以上問題，本文把萊維飛行、精英參與的交叉算子及精英反向?qū)W習(xí)機(jī)制融入到傳統(tǒng)的螢火蟲算法中，提出了一種多策略融合的改進(jìn)螢火蟲算法LEEFA（Levy flight-Elite participated crossover-Elite opposition-based learning Firefly Algorithm）。引入萊維飛行機(jī)制能夠有效地進(jìn)行全局搜索，提升解的多樣性；精英參與的交叉算子提供的跳出局部最優(yōu)的能力和優(yōu)良個體保留的能力能夠避免螢火蟲算法陷入局部最優(yōu)，進(jìn)而提升算法的表現(xiàn)和收斂精度等；引入精英反向?qū)W習(xí)機(jī)制能夠在算法陷入局部最優(yōu)區(qū)域時，通過構(gòu)建反向解保留精英個體使得種群解的多樣性增加和收斂精度提升，讓算法朝著最優(yōu)解的方向進(jìn)行進(jìn)化。

本文在基準(zhǔn)測試函數(shù)上進(jìn)行了對比仿真實(shí)驗，結(jié)果表明所提算法相比傳統(tǒng)智能優(yōu)化算法及其他改進(jìn)螢火蟲算法提升了螢火蟲算法的性能，在收斂速度和精度上表現(xiàn)均優(yōu)于對比算法。

1 相關(guān)工作

螢火蟲算法自提出以來便受到國內(nèi)外學(xué)者的廣泛關(guān)注，為了解決螢火蟲算法存在的局部開發(fā)能力不足、容易陷入局部極值、收斂精度低且過早收斂的問題，近年來不同的改進(jìn)和優(yōu)化方向的提升算法不斷被提出。相關(guān)研究提出的算法在螢火蟲算法的基礎(chǔ)上，不同程度提升了算法的全局搜索能力和局部尋優(yōu)能力，且對于兩方面的能力如何平衡做出了改進(jìn)。

何櫟等［6］提出了一種基于萊維飛行和變異算子的螢火蟲算法（Levy flight and Mutation operator based Firefly Algorithm，LMFA），該算法側(cè)重于在傳統(tǒng)螢火蟲算法陷入局部最優(yōu)時增加跳出局部最優(yōu)解的概率，當(dāng)種群無法通過初始尋優(yōu)算法提升解的質(zhì)量時，萊維飛行和變異算子將被用來進(jìn)行種群解的更新；然而，直到相對停滯再進(jìn)行種群更新極大地影響了種群多樣性的提升速度，因此也限制了算法收斂速度和精度一定程度的上升空間。值得注意的是，針對螢火蟲算法的研究不僅注重提升其局部尋優(yōu)能力，也關(guān)注如何平衡并盡可能同時提升全局搜索能力和局部尋優(yōu)能力，這也是當(dāng)下的研究熱點(diǎn)。Wu 等［7］使用自適應(yīng)開關(guān)的方式在迭代中進(jìn)行選擇以平衡萊維飛行進(jìn)行全局探索及對數(shù)螺旋路徑進(jìn)行局部開發(fā)的兩種模式，提出了自適應(yīng)對數(shù)螺旋-萊維飛行螢火蟲優(yōu)化算法（ADaptive logarithmic spiral-Levy Improved Firefly Algorithm，ADIFA），取得了一定的成果，但在某些問題上表現(xiàn)不足。Wang 等［8］提出了基于性別差異的改進(jìn)螢火蟲算法（improved Firefly Algorithm based on Gender Difference，GDFA），其中，雄螢火蟲通過隨機(jī)選擇和方向判斷進(jìn)行全局搜索，雌螢火蟲通過局部搜索找到高質(zhì)量的解，有效地平衡了算法的全局和局部尋優(yōu)，算法引入的混沌搜索進(jìn)一步提高了搜索能力。Yelghi 等［9］將潮汐力公式引入螢火蟲算法框架，其靈活性為算法平衡全局和局部搜索提供了新的見解。劉振等［10］提出的混合螢火蟲算法通過調(diào)節(jié)參數(shù)在算法迭代前期進(jìn)行全局范圍內(nèi)的搜索，后期則聚焦于局部收斂區(qū)域；該算法提升種群多樣性的方式是構(gòu)造分布式協(xié)同進(jìn)化種群框架，引入優(yōu)良精英個體進(jìn)行指導(dǎo)，采用兩階段混沌進(jìn)化方式，提升了收斂精度，但仍然存在進(jìn)化速度的缺陷。劉磊等［11］提出了基于精英個體劃分的變步長螢火蟲優(yōu)化算法（Elite-individual-dipartition Dynamic Step Firefly Algorithm，EDSFA），對精英和非精英個體采用不同的步長調(diào)整策略，兼顧了算法在解搜索空間的全局搜索和局部開發(fā)能力并提升了種群的多樣性，然而個體差異造成的收斂效果仍然存在不穩(wěn)定性。

本文提出了一種引入萊維飛行、精英參與的交叉算子和精英反向?qū)W習(xí)機(jī)制多策略融合的改進(jìn)螢火蟲算法（LEEFA）。通過在基準(zhǔn)函數(shù)上的實(shí)驗結(jié)果表明，本文提出的改進(jìn)螢火蟲算法能夠增強(qiáng)算法的全局搜索能力并且有效地避免算法陷入局部最優(yōu)值和過早收斂，算法的收斂速度和精度得到了提升。

2 傳統(tǒng)螢火蟲算法

螢火蟲算法通過模擬自然界中螢火蟲的發(fā)光行為來尋找最優(yōu)解。算法本身僅抽象化螢火蟲的發(fā)光特性來搜索解空間區(qū)域，在這過程中不斷向解空間內(nèi)位置較優(yōu)的螢火蟲遷移，最終收斂到最優(yōu)解。

螢火蟲算法的關(guān)鍵在于螢火蟲的亮度和吸引度，其中：螢火蟲的亮度決定種群中每個個體的移動方向，吸引度決定其移動距離。在算法迭代過程中，螢火蟲自身所在位置解的質(zhì)量越好，亮度就越高；然而在每只螢火蟲視野中所看見的其他螢火蟲的亮度亦受到相對位置距離的影響，因此螢火蟲之間相對距離越短相對亮度越高，即相對亮度與螢火蟲個體之間的距離成反比。螢火蟲種群通過亮度交換信息并通過吸引度移動尋覓最優(yōu)解，每只個體對于其他螢火蟲的吸引度和相對亮度有關(guān)且與距離成反比，即對每只螢火蟲來說更容易受周圍的亮度較高的螢火蟲吸引而向其靠近，通過這種機(jī)制最終收斂到最優(yōu)位置。

算法具體描述如下：假設(shè)有N只螢火蟲，搜索空間的維度為D維，那么第i只螢火蟲在D維空間中的初始位置可表示為Xi=[xi，1，xi，2，…，xi，n] 。

定義1第i只螢火蟲的熒光亮度。

其中：f(Xi)表示第i只螢火蟲對所在位置的目標(biāo)適應(yīng)度值。

定義2第i只螢火蟲的相對亮度。

其中：γ表示光強(qiáng)吸引因子，其取值與區(qū)域面積有關(guān)，一般設(shè)置為常數(shù)；rij=|Xi-Xj|，表示第i只螢火蟲與第j只螢火蟲之間的空間距離的大小。

定義3螢火蟲的吸引度。

其中β0表示最大吸引度因子。式（3）描述了最大亮度的螢火蟲對其他螢火蟲的吸引度隨著距離的增大而減小。

定義4尋優(yōu)過程位置更新。

其中：α為步長因子，rand為[0，1]上服從均勻分布的隨機(jī)因子。對于某螢火蟲個體i來說，若螢火蟲個體j吸引了它，則采用式（4）進(jìn)行更新，循環(huán)執(zhí)行每個螢火蟲個體。為了加大搜索域空間范圍，防止算法陷入過早收斂，式（4）中加入了α·(rand-12)。

3 多策略融合的改進(jìn)螢火蟲算法

本文提出的改進(jìn)螢火蟲算法作出了以下改進(jìn)：1）在傳統(tǒng)螢火蟲算法的尋優(yōu)基礎(chǔ)上添加了篩選機(jī)制，僅對能夠引導(dǎo)某螢火蟲個體趨向更優(yōu)位置的移動進(jìn)行保留，從而逐步提升解的質(zhì)量；2）引入萊維飛行機(jī)制，增加種群多樣性并提升種群解的質(zhì)量；3）采用精英參與的交叉算子，使用精英個體進(jìn)行交叉且在獲得優(yōu)于原有解的子代解后選擇優(yōu)良個體留在原有種群內(nèi)；4）引入精英反向?qū)W習(xí)機(jī)制，在算法陷于局部最優(yōu)區(qū)域時，提供反向解增加可能解的選擇范圍，并從中選擇精英個體進(jìn)行下一次迭代。通過以上改進(jìn)，讓算法朝著更好的進(jìn)化方向進(jìn)行，最終收斂到全局最優(yōu)解。

3.1 篩選機(jī)制的螢火蟲移動行為

在傳統(tǒng)螢火蟲算法中，熒光亮度較高的螢火蟲個體一般情況下只對相對距離較小的螢火蟲個體具有較強(qiáng)的吸引效果，使鄰域內(nèi)的螢火蟲改變移動方向和距離，從而更趨向自己。然而，這種共同的吸引作用往往存在引導(dǎo)周圍的螢火蟲移動到解的質(zhì)量不佳的位置上，容易導(dǎo)致傳統(tǒng)螢火蟲算法收斂精度不高且易陷入局部最優(yōu)解而過早收斂的問題。因此，本文通過添加篩選機(jī)制保證進(jìn)入下一次迭代的螢火蟲個體都是改善后的優(yōu)良個體。以求解極小值問題為例，螢火蟲位置更新公式改進(jìn)如下：

3.2 萊維飛行

萊維飛行是一種模擬自然界隨機(jī)現(xiàn)象行為的行走方式，已經(jīng)廣泛被用于優(yōu)化算法研究的改進(jìn)策略中，例如與PSO 算法［12］、灰狼優(yōu)化算法［13］、原子搜索算法［14］等結(jié)合的算法設(shè)計都在一定程度上提升了算法表現(xiàn)。萊維飛行特點(diǎn)在于其步長服從萊維穩(wěn)定分布，是一個非高斯隨機(jī)過程。

本文中符合萊維分布的隨機(jī)步長通過式（6）進(jìn)行計算：

其中μ和v服從正態(tài)分布：

其中σμ和σv定義如下：

其中：β的取值范圍為[0，2]，通常取β=32。此前的文獻(xiàn)研究表明萊維飛行的搜索路徑能夠提升算法在全局搜索空間的搜索能力，擴(kuò)大搜索范圍，讓算法更容易跳出局部極值點(diǎn)。Yang［15］在2010 年提出的萊維飛行螢火蟲算法（Levy Flight Firefly Algorithm，LFFA）通過將萊維飛行引入到螢火蟲算法中，增強(qiáng)了螢火蟲算法的全局探索能力，且保留了部分原算法局部空間勘探能力。引入萊維飛行的螢火蟲算法更新公式如下：

其中：式（4）中的α·(rand-12)隨機(jī)步長由萊維分布生成的隨機(jī)步長代替，故式（7）中的sign(rand-12)作用為給出一個隨機(jī)方向；Levy表示由式（6）生成的隨機(jī)步長，此時螢火蟲的運(yùn)動即為基于重尾概率分布的隨機(jī)行走。Levy 隨機(jī)步長相較于早先使用的隨機(jī)步長有效提高了算法跳出局部最優(yōu)解的概率，從而整體上提升算法全局搜索的能力及獲得最優(yōu)解的能力。數(shù)值實(shí)驗結(jié)果表明LFFA 表現(xiàn)更優(yōu)，具有更高的成功率和更少的計算時間。本文引入的萊維飛行機(jī)制正是基于以上改進(jìn)算法，然而萊維飛行的引入會在提升算法全局搜索能力的同時，在算法迭代后期一定程度上削弱算法的局部尋優(yōu)能力，即在需要更小區(qū)域搜索時算法仍可能處于全局搜索狀態(tài)，導(dǎo)致收斂精度降低。

3.3 精英參與的交叉算子

為解決引入的萊維飛行機(jī)制導(dǎo)致的局部最優(yōu)解欠佳問題，引入精英參與的交叉算子。對于群智能優(yōu)化算法來說，種群中的精英個體具有重要的指引作用和尋找最優(yōu)解的潛力，種群越趨向于迭代中產(chǎn)生的精英個體，越容易接近最優(yōu)解，例如灰狼優(yōu)化算法中的金字塔尖個體的作用；然而過度的趨同性同樣也會導(dǎo)致算法停滯于局部最優(yōu)解?？紤]遺傳算法中通過精英策略選擇較優(yōu)個體交叉并保留較優(yōu)個體的策略，增加了種群解的多樣性，提供了跳出局部最優(yōu)解的可能，同時也保留了優(yōu)良個體使得種群向著最優(yōu)解的位置進(jìn)化。考慮到精英個體的解的優(yōu)勢在于相較于非精英個體部分基因表達(dá)位置的效果更佳，使用精英個體參與交叉運(yùn)算散播其優(yōu)勢基因片段相較于傳統(tǒng)在迭代過程中僅保留精英個體直接應(yīng)用于交叉算子，收斂速度將大幅提升。通過擴(kuò)大含有精英個體的基因在種群中的比例，將更有可能獲得一個產(chǎn)生最大限度提升解的質(zhì)量的種群。鑒于此，本文提出了精英參與的交叉算子，將種群中的非精英個體與現(xiàn)有的最佳精英個體進(jìn)行交叉，在獲得的子代和父代中保留較優(yōu)個體，替代原有非精英個體的螢火蟲。該算子實(shí)現(xiàn)簡易且效果顯著，能夠較快地更新螢火蟲個體的位置，易獲得相對更優(yōu)解。算法具體描述如下。

設(shè)所求問題為求解極小值問題，種群中有N個螢火蟲個體，則種群中的精英個體為，其定義為：

步驟4 通過將子代個體的基因型代入目標(biāo)函數(shù)求解f(c1)和f(c2)。

步驟5 對比子代與父代函數(shù)值，選擇較優(yōu)個體進(jìn)入種群替代原有非精英個體。

3.4 精英反向?qū)W習(xí)機(jī)制

Tizhoosh［16］在2005 年提出 并驗證 了反向 學(xué)習(xí)機(jī) 制（Opposition-Based Learning，OBL）的擴(kuò)展對原有算法的有效性，該方法指出反向解比當(dāng)前解逼近最優(yōu)解的概率高于50%。反向?qū)W習(xí)機(jī)制能夠提升算法迭代過程中解的質(zhì)量，其具體定義如下。

定義5反向解。設(shè)在D維搜索空間中，當(dāng)前種群的某個個體 所在位 置的一 個可行解為=[x1，x2，…，xD]，xk∈[ak，bk]，(k=1，2，…，D)，其反向解定義為其中是[0，1]的隨機(jī)數(shù)。

在此基礎(chǔ)上，為應(yīng)對反向?qū)W習(xí)機(jī)制可能帶來的部分解的質(zhì)量不升反降的現(xiàn)象，精英反向?qū)W習(xí)機(jī)制被提出并用于優(yōu)化算法的改進(jìn)，諸多研究顯示引入精英反向?qū)W習(xí)能夠有效提升算法的搜索能力［17-19］，提高種群解的多樣性和質(zhì)量。

設(shè)待優(yōu)化問題為最小問題，適應(yīng)度函數(shù)為f(X)，若存在某個可行解X，其反向解為。

精英反向?qū)W習(xí)機(jī)制具體更新步驟如下。

步驟3 排序完成后，選取前N個個體作為下次迭代使用的新種群。

在傳統(tǒng)螢火蟲算法中，迭代一定次數(shù)后，螢火蟲種群將會出現(xiàn)較為密集的狀態(tài)，此時螢火蟲的收斂速度將逐漸遲緩，甚至讓算法陷入局部極值點(diǎn)。為應(yīng)對此問題而引入的精英反向?qū)W習(xí)機(jī)制，通過構(gòu)建反向解并保留精英個體的方法增加了種群的多樣性，提高了存留解的質(zhì)量，為算法提供了跳出局部最優(yōu)解的可能性。

3.5 算法具體描述

螢火蟲算法的有效性在于某螢火蟲個體受到其他比自身亮度更高的螢火蟲吸引而獲得的多次一定程度上進(jìn)行修正的移動方向和位移，這就有可能造成在初始階段的迭代中，部分表現(xiàn)次優(yōu)但距離更近的螢火蟲個體會對某些個體的移動造成影響，導(dǎo)致收斂速度的降低。

基于以上問題的考量，引入相當(dāng)于貪婪算法的篩選機(jī)制能夠有效降低這種影響，但這種機(jī)制卻有可能造成解的多樣性，減少導(dǎo)致算法全局搜索能力降低而陷入局部最優(yōu)值的后果。而已知萊維飛行機(jī)制的引入能夠有效提升算法的全局搜索能力，因此在螢火蟲添加篩選移動后通過萊維飛行的改進(jìn)來擴(kuò)大算法的搜索范圍，彌補(bǔ)此前可能損失的潛在搜索范圍的解。然而萊維飛行仍存在無法隨著算法迭代次數(shù)的增加而自適應(yīng)地降低精度的問題，局部搜索能力較差，具體表現(xiàn)為隨著算法到達(dá)迭代后期，萊維飛行更新的個體無法再提升解的質(zhì)量。此時考慮到精英個體的領(lǐng)導(dǎo)作用，使用精英參與的交叉算子更新個體，使得有更大的可能性獲得相對優(yōu)解。進(jìn)一步考慮該算子，伴隨著與精英個體相像或精英個體本身的個體在螢火蟲群體中逐漸占優(yōu)，可能會在迭代后期陷入局部最優(yōu)解且無法跳出。因此設(shè)置閾值判斷群體中若存在超過閾值限度比例的個體的更新都停滯時則認(rèn)為有可能陷入了局部最優(yōu)狀態(tài)，此時應(yīng)用精英反向?qū)W習(xí)機(jī)制進(jìn)行更新，則更容易使算法突破局部最優(yōu)狀態(tài)，最終收斂到最優(yōu)解。

算法具體步驟表述如下。

步驟3 通過目標(biāo)函數(shù)值求解螢火蟲個體的亮度，使用添加篩選機(jī)制的移動公式（5）移動各螢火蟲位置。

步驟4 設(shè)置未能成功改善的螢火蟲數(shù)目count=0，對每只螢火蟲個體應(yīng)用萊維飛行機(jī)制，應(yīng)用式（7），若得到的個體未能改善解的質(zhì)量，則執(zhí)行步驟5；否則，轉(zhuǎn)至執(zhí)行步驟6。

步驟5 使用精英參與的交叉算子對螢火蟲個體進(jìn)行運(yùn)算，應(yīng)用式（8），用得到的較優(yōu)子代個體更新該個體所在的位置和解，若得到的個體仍未能改善解的質(zhì)量，則count+=1，且原螢火蟲個體保持不變。

步驟6 判斷count≥ethreshold·N，若滿足則認(rèn)為種群移動不活躍，有陷入局部最優(yōu)值的可能，使用精英反向?qū)W習(xí)機(jī)制進(jìn)行種群的更新；否則不進(jìn)行操作。ethreshold代表未能獲得更新的種群內(nèi)個體數(shù)目占種群總體規(guī)模的比例閾值，一旦超過此數(shù)值，則進(jìn)行精英反向?qū)W習(xí)機(jī)制的更新。

步驟7 重新根據(jù)目標(biāo)函數(shù)進(jìn)行計算，更新精英個體，判斷是否滿足迭代結(jié)束條件，若滿足則輸出f()；否則，返回步驟3。

3.6 算法復(fù)雜度分析

時間復(fù)雜度是衡量算法運(yùn)算效率的重要指標(biāo)。設(shè)種群規(guī)模為N，問題維度為D，最大迭代次數(shù)為Titeration，計算適應(yīng)度函數(shù)所需時間為f(D)。

步驟1～2 初始化階段設(shè)置算法參數(shù)需要時間為x1，隨機(jī)生成種群個體的位置需要時間為O(N×D)，計算適應(yīng)度函數(shù)值需要時間為O(N×f(D))，找到最優(yōu)解個體并設(shè)置為精英個體需要時間為O(N)，則此階段時間復(fù)雜度應(yīng)為O((D+f(D)+1)N+x1)。

步驟3 移動篩選階段的篩選判斷機(jī)制需要時間O(N)，移動需要的總時間與傳統(tǒng)螢火蟲算法相同，即O(N2)，則此階段時間復(fù)雜度應(yīng)為O(N2)。

步驟4～5 設(shè)對一只螢火蟲進(jìn)行萊維飛行操作需要的時間為l(D)，執(zhí)行一次精英交叉算子需要的時間為x2，此時，根據(jù)獲得結(jié)果的差異，螢火蟲可能的狀態(tài)有三種：1）更新為萊維飛行的結(jié)果；2）拒絕萊維飛行結(jié)果，執(zhí)行精英交叉算子并更新；3）拒絕萊維飛行和精英交叉算子結(jié)果。狀態(tài)1）執(zhí)行結(jié)束需要O(l(D))，狀態(tài)2）和3）執(zhí)行結(jié)束需要O(l(D) +x2)，最好情況下所有螢火蟲迭代過程中都只進(jìn)入狀態(tài)1），即此階段需要O(l(D) ×N)，最壞情況下所有螢火蟲迭代過程中都進(jìn)入狀態(tài)2）或3），即此階段需要O((l(D) +x2) ×N)。

步驟6 反向精英學(xué)習(xí)機(jī)制階段判斷是否執(zhí)行步驟需要O(1)。根據(jù)判斷結(jié)果，種群的狀態(tài)有兩種：1）執(zhí)行精英反向?qū)W習(xí)策略，更新種群；2）不執(zhí)行精英反向?qū)W習(xí)策略，進(jìn)入下一步驟。執(zhí)行反向精英學(xué)習(xí)機(jī)制共需要計算反向解、合并初始種群和反向解種群和更新種群3 個步驟，易知此3 個步驟的時間都取決于N的大小，故設(shè)置為g(N)。易知步驟4～5 的最好狀況下一定進(jìn)入步驟6 的最好狀況，步驟4～5 的最壞狀況下一定進(jìn)入步驟6 的最壞狀況，其他情況介于兩者之間則最好情況下進(jìn)入狀態(tài)1），此階段需要O(1)，最壞情況下進(jìn)入狀態(tài)2），此階段需要O(1 +g(N))。

步驟7 判斷及輸出需要的時間為常數(shù)時間x3，則時間復(fù)雜度為O(1)。

綜上，LEEFA 的時間復(fù)雜度最好情況下為：

而該算法在最壞情況下為：

即最好 情況下O(Titeration×N2+q1(D) ×N)，最壞情況下O(Titeration×N2+q2(D) ×N)（q1、q2為某關(guān) 于D的某函 數(shù)）。傳統(tǒng)螢火蟲算法的時間復(fù)雜度為O(Titeration×N2)，LEEFA 相較于傳統(tǒng)螢火蟲算法增加了N數(shù)量級的復(fù)雜度。本文通過實(shí)驗驗證了所提算法實(shí)施的可能性，盡管一定程度上增加了復(fù)雜度但算法能夠極快地收斂到精度合適的最優(yōu)解，在實(shí)際應(yīng)用中具有較大的價值。

4 仿真實(shí)驗與結(jié)果分析

4.1 實(shí)驗環(huán)境配置及測試函數(shù)

本文實(shí)驗環(huán)境配置為Intel Core i7-6700 CPU @3.40 GHz 3.40 GHz，8.00 GB，Windows 7 旗艦版 64 位操作系統(tǒng)，軟件環(huán)境為PyCharm 2018.2.4 Python 3.7（64-bit）。

為了驗證算法的有效性，這一節(jié)將以求如表1 所示的基準(zhǔn)測試函數(shù)［20］的最小值為例，通過計算機(jī)仿真來評價比較所提LEEFA 以及傳統(tǒng)智能優(yōu)化算法和其他改進(jìn)螢火蟲算法的性能，對比算法為：PSO 算法、遺傳算法（Genetic Algorithm，GA）、人工蜂群算法（Artificial Bee Colony algorithm，ABC）、FA、LFFA、LMFA 和ADIFA。實(shí)驗均選取種群規(guī)模為100，研究問題維度為30 維，最大迭代次數(shù)設(shè)置為1 500，函數(shù)區(qū)間設(shè)置參考表1。LEEFA 的參數(shù)設(shè)置由仿真實(shí)驗進(jìn)行設(shè)置，傳統(tǒng)PSO算法和GA的參數(shù)遵循慣例設(shè)置，其他算法的參數(shù)設(shè)置均遵循相應(yīng)文獻(xiàn)，具體如表2 所示。其中，LEEFA 中α表示式（5）和式（7）中的步長因子，β0和γ分別代表基本螢火蟲算法中的最大吸引度因子和光強(qiáng)吸引因子，ethreshold表示步驟6中用于判斷算法是否陷入局部最優(yōu)的閾值參數(shù)。

表1 基準(zhǔn)測試函數(shù)Tab.1 Benchmark functions

表2 參數(shù)說明Tab.2 Parameter description

4.2 算法閾值參數(shù)選取

基于對LEEFA 的復(fù)雜度分析可知，參數(shù)對于LEEFA 的時間復(fù)雜度可能存在重要的影響：ethreshold值設(shè)置過大將導(dǎo)致算法在陷入局部最優(yōu)解時無法及時跳出，降低收斂速度；ethreshold值設(shè)置過小則會導(dǎo)致ethreshold的作用失效，算法復(fù)雜度提升。然而以上對于算法的分析僅在算法初次到達(dá)接近最優(yōu)解的地方才可能產(chǎn)生影響，由于LEEFA 能夠極快地收斂到最優(yōu)解附近，導(dǎo)致種群中存在較多接近最優(yōu)解而較難通過更新策略提升解的質(zhì)量的個體，因此隨著迭代次數(shù)的增加ethreshold值將很容易被達(dá)到，且算法本身存在一定的隨機(jī)性，以上分析的前期影響存在被抵消的可能。

鑒于此，首先需要通過實(shí)驗確定ethreshold的數(shù)值設(shè)置及其對算法的影響?；诔醪降膶?shí)驗觀察發(fā)現(xiàn)，當(dāng)種群中超過一半的個體都無法再獲得更新時，算法已經(jīng)處于停滯狀態(tài)。為達(dá)到提前預(yù)測并避免陷入局部最優(yōu)區(qū)域從而提升算法運(yùn)行效率的目的，將閾值分別設(shè)置為0.05、0.1、0.15、0.2、0.25、0.3、0.35、0.4、0.45，而其他參數(shù)的值保持不變。在實(shí)驗選擇的基準(zhǔn)測試函數(shù)上連續(xù)運(yùn)行30 次取得函數(shù)全局最優(yōu)解的平均值，不同參數(shù)的設(shè)置對于LEEFA 的影響如圖1 所示，其中，橫軸表示閾值參數(shù)的取值，縱軸表示函數(shù)連續(xù)運(yùn)行找到的全局最優(yōu)解均值的lg（函數(shù)值）。所選函數(shù)最優(yōu)解均為0，圖1 中可以看出算法在設(shè)置為不同值時獲得的最優(yōu)解平均值在基準(zhǔn)測試函數(shù)上的表現(xiàn)相近，在部分函數(shù)如f1(x) 和f4(x)上存在波動，但從整體上來看，ethreshold的取值對算法的收斂精度影響較小。根據(jù)前文分析ethreshold的選擇也在一定程度上影響算法的時間復(fù)雜度，因此經(jīng)過綜合考量實(shí)驗結(jié)果和算法的時間復(fù)雜度，本文實(shí)驗中將其設(shè)置為0.1。

圖1 閾值參數(shù)的選擇Fig.1 Threshold parameter selection

4.3 對比實(shí)驗

為避免隨機(jī)性帶來的誤差，將連續(xù)運(yùn)行30 次所得函數(shù)全局最小值的平均值作為評價算法收斂性能的衡量指標(biāo)，實(shí)驗獲得的結(jié)果展示在表3，其中表現(xiàn)最好的用粗體表示。

從表3 可以看出，LEEFA 在所有基準(zhǔn)測試函數(shù)f1～f8上的表現(xiàn)都優(yōu)于其他對比算法，從算法最終得到的最優(yōu)值可以看出LEEFA 尋優(yōu)能力優(yōu)良，標(biāo)準(zhǔn)差則說明算法尋優(yōu)的穩(wěn)定性也較好。以f2為例，該函數(shù)存在多個局部極小值點(diǎn)，是典型的非線性多模態(tài)函數(shù)，通常被認(rèn)為是優(yōu)化算法很難處理的復(fù)雜多模態(tài)函數(shù)；而它的全局最小值為0，本文以10-4為誤差的容忍度判定算法成功。可以看出LEEFA 能夠成功地收斂到需要的精度，相比之下其他算法均無法跳出該函數(shù)的一些局部最優(yōu)值的位置。對于較難優(yōu)化的測試函數(shù)，LEEFA 都取得了較好的收斂結(jié)果，對比LEEFA 與傳統(tǒng)FA 可以看出，LEEFA 相較于FA 獲得了顯而易見的提升效果。然而，LEEFA 在f2、f5上的最優(yōu)值和最差值差距較大，算法仍有一些不穩(wěn)定的情況出現(xiàn)。對比f6、f7上的實(shí)驗結(jié)果，LEEFA 在獨(dú)立運(yùn)行的過程中，偶爾會取得無法達(dá)到收斂精度的解，在此類函數(shù)上表現(xiàn)仍有待提升。

表3 所提算法與其他改進(jìn)算法的實(shí)驗結(jié)果對比Tab.3 Experimental results comparison of the proposed algorithm and other improved algorithms

續(xù)表

為了更好地對比LEEFA 與其他算法的收斂能力，繪制了以上8 個算法在30 維尋優(yōu)問題進(jìn)行1 500 次迭代的收斂曲線，如圖2 所示。為便于說明，圖2 中橫軸表示迭代次數(shù)，縱軸表示適應(yīng)度值（lg）。

從圖2 中可以看出，LEEFA 在運(yùn)行過程中以極快的速度收斂，迅速到達(dá)最優(yōu)解附近開始搜尋，并且能夠收斂到最優(yōu)解。如圖2 所示的迭代曲線顯示，對比算法大多在迭代次數(shù)為200 代時就陷于局部最優(yōu)解，而LEEFA 引入的改進(jìn)策略能夠幫助算法跳出局部最優(yōu)區(qū)域，獲得更高收斂精度的最優(yōu)解，顯然LEEFA 相較于對比的傳統(tǒng)群智能優(yōu)化算法及改進(jìn)的螢火蟲算法表現(xiàn)更好，驗證了提出的改進(jìn)算法的有效性。

圖2 基準(zhǔn)測試函數(shù)上的收斂曲線對比Fig.2 Comparison of convergence curves on benchmark functions

5 結(jié)語

本文將萊維飛行機(jī)制引入傳統(tǒng)的螢火蟲算法中，提升算法的全局搜索能力；融合精英交叉算子，提升個體解的質(zhì)量，保留優(yōu)良個體；增加篩選機(jī)制，引導(dǎo)算法朝著更優(yōu)的方向進(jìn)化；引入精英反向?qū)W習(xí)機(jī)制，提升種群解的多樣性，提升算法跳出局部最優(yōu)的能力。隨著進(jìn)化過程的進(jìn)行，精英個體逐漸占據(jù)重要地位并引導(dǎo)算法的迭代，算法生成差解的概率逐漸減小，從而提高了收斂性能。所提算法增強(qiáng)了螢火蟲算法的全局尋優(yōu)能力，提高了算法的進(jìn)化速度，提高了收斂精度。計算機(jī)測試仿真結(jié)果表明，所提算法的性能優(yōu)于傳統(tǒng)群智能優(yōu)化算法PSO、GA、ABC、FA 及改進(jìn)的螢火蟲算法如LFFA、LMFA 和ADIFA；然而所提算法在某些函數(shù)問題上仍存在進(jìn)一步提升的空間，可能的原因是此類函數(shù)存在大量的局部極值點(diǎn)，存在一定的尋優(yōu)難度。未來將針對提升算法的穩(wěn)定性和時間復(fù)雜度進(jìn)行研究工作。