基于螢火蟲算法和高斯擾動的飛蛾優(yōu)化算法

李 榮，賀興時，楊新社

(1.西安工程大學 理學院,陜西 西安 710048;2.密德薩斯大學 科學與技術學院,英國 倫敦 NW4 4BT)

0 引 言

最優(yōu)化問題是研究在眾多候選解中找出最優(yōu)解的過程[1]，也是人類實踐活動中十分普遍的問題。傳統(tǒng)的優(yōu)化方法在解決高維、復雜的、非線性特點的優(yōu)化問題時，搜索精度和收斂速度等方面均不能滿足實際的需求，費時費力且成本高，還會導致算法陷入局部最優(yōu)，因而迫切需要有新的優(yōu)化方法。啟發(fā)式算法(heuristic algorithm，HA)提供了解決復雜優(yōu)化問題的有效工具[2]，在群體智能算法的研究領域獲得了更多的關注，成為國內外研究的熱點，已廣泛應用于復雜系統(tǒng)的圖像閾值分割[3]、多目標優(yōu)化[4]、網絡入侵檢測[5]、工程結構設計[6]、水資源優(yōu)化配置[7]等領域。

飛蛾優(yōu)化(moth-flame optimization,MFO)算法是由MIRJALILI于2015年提出的一種新型群智能算法[8]。該算法在收斂速度和收斂精度等方面均優(yōu)于傳統(tǒng)智能仿生算法，且具有結構簡單、易于實現(xiàn)和適用范圍廣等優(yōu)點，許多學者和研究人員對飛蛾優(yōu)化算法做出了各種改進并在多個領域進行了應用。例如，YAMANY等將飛蛾優(yōu)化算法應用于訓練多層感知器, 能夠獲得更高質量的優(yōu)化解[9]；JANGIR等將飛蛾優(yōu)化算法應用于電力系統(tǒng)有功和無功優(yōu)化調度問題，提供更好的優(yōu)化調度方案并產生巨大的經濟效益[10]；JANGIR等基于不同的懲罰因子下，提高了飛蛾優(yōu)化算法的求解精度,得到了更好的優(yōu)化性能并成功解決了混合經濟排放調度問題[11]；李志明等引入了Lévy飛行策略和單純形法，將改進的飛蛾撲火優(yōu)化算法應用于求解工程優(yōu)化和聚類分析等問題中，拓寬了算法的應用領域[12]；徐慧等提出一種融合粒子群優(yōu)化的二進制飛蛾撲火優(yōu)化(BPMFO)算法,并應用于網絡入侵檢測的特征選擇中，與其他改進算法相比獲得了更高的模擬精度[13]；李偉琨等提出一種多目標飛蛾撲火算法，更加合理有效地解決電力系統(tǒng)的無功優(yōu)化問題，展示了該算法在電力系統(tǒng)優(yōu)化問題上的良好應用前景[14]；崔東文等通過MFO算法，為精確估計馬斯京根模型參數(shù)提供了有效可行工具[15]。上述不同改進策略的飛蛾優(yōu)化算法均在不同程度上提高了算法整體優(yōu)化性能，但仍未徹底解決飛蛾優(yōu)化算法易陷入局部最優(yōu)，復雜條件下收斂精度低的問題。

MFO在處理復雜函數(shù)問題時，易發(fā)生早熟收斂并陷入局部最優(yōu)。為了提升MFO算法的優(yōu)化性能，本文提出了一種基于螢火蟲算法和高斯擾動的飛蛾優(yōu)化算法(moth-flame optimization algorithm with firefly algorithm and Gaussian disturbance,FGMFO)。測試結果表明，F(xiàn)GMFO算法具有更高的搜索精度和更快的收斂速度。

1 基本飛蛾優(yōu)化算法

在基本飛蛾優(yōu)化算法中，M是飛蛾位置矩陣，F(xiàn)是火焰位置矩陣；λM表示飛蛾所對應的適應度值，λF表示火焰所對應的適應度值。初始時刻火焰矩陣和飛蛾矩陣維度相同,其表達式為

(1)

(2)

式中:n為飛蛾的種群大小;d為優(yōu)化問題的維度。

雖然飛蛾與火焰都是候選解，但是二者的根本區(qū)別在于每次迭代過程中位置的更新方式不同。在搜索空間里，飛蛾是實際移動的主體，火焰是飛蛾當前迭代所獲得的最優(yōu)位置[16]。

飛蛾位置的更新公式用對數(shù)螺旋函數(shù)表示，即

Mi=S(Mi,Fj)

(3)

S(Mi,Fj)=Di·exp(bt)·cos(2πt)+Fj

(4)

Di=|Fj-Mi|

(5)

式中:Mi表示第i只飛蛾新的位置;Fj表示第j個火焰;S是螺旋形函數(shù);Di表示第j個火焰和第i個飛蛾間的距離;b是用來確定對數(shù)螺旋函數(shù)形狀的常數(shù)系數(shù);t是范圍在r到1之間的隨機數(shù)。為了加速飛蛾在火的周圍進行探索的尋優(yōu)速度,r在迭代過程中一般由-1線性地遞減到-2。

為保證MFO算法獲得較快的收斂速度, 提出自適應火焰數(shù)量更新機制[8]，即利用在迭代過程中自適應地減少火焰數(shù)目N：

(6)

式中:[·]表示取整數(shù)部分；l為當前迭代次數(shù);Nmax為最大火焰數(shù)量;T為最大迭代次數(shù)。

2 改進的飛蛾優(yōu)化算法

2.1 基于螢火蟲算法的種群初始化

飛蛾優(yōu)化算法在種群初始化階段，搜索范圍完全依賴隨機性，難以保證全局最優(yōu)解一定在搜索范圍內，以致算法最終找到的全局最優(yōu)解的精度不高，甚至導致算法陷入局部最優(yōu)[17]。已有研究表明，初始種群的位置很大程度會影響算法的尋優(yōu)精度和搜索速度，因此本文利用螢火蟲算法對飛蛾優(yōu)化算法進行種群初始化。

螢火蟲算法(firefly algorithm，F(xiàn)A)是文獻[18]提出的一種元啟發(fā)式算法，通過模擬螢火蟲的發(fā)光行為實現(xiàn)位置優(yōu)化。螢火蟲的相對熒光亮度I為

I=I0·exp(-γrij)

(7)

式中:I0為螢火蟲的最大螢光亮度;γ為光強吸收系數(shù);rij為螢火蟲i與j之間的空間距離。螢火蟲的吸引度β為

(8)

式中:β0為最大吸引度;γ為光強吸收系數(shù)。螢火蟲i被吸引向螢火蟲j移動的位置更新式為

xi+1=xi+β(xj-xi)+α(rand(·)-1/2)

(9)

式中:xi、xj為螢火蟲i和j所處的空間位置;α為步長因子,是[0，1]之間的常數(shù);rand(·)為[0，1]上服從均勻分布的隨機數(shù)。

螢火蟲算法的概念簡單、易于實現(xiàn)而且具有較高的尋優(yōu)精度和收斂速度，是一種可行有效的優(yōu)化方法，被廣泛地應用于各種優(yōu)化問題的求解，為智能優(yōu)化提供了新思路[18]。

從飛蛾種群的初始化角度研究飛蛾性能，利用螢火蟲算法對飛蛾算法的初始位置選擇進行優(yōu)化，獲取飛蛾的最優(yōu)初始位置，使初始種群個體盡可能均勻分布在解空間[19]。將螢火蟲的最優(yōu)位置作為MFO算法中飛蛾的初始位置，進而改善飛蛾優(yōu)化算法的初始種群質量，增強飛蛾種群的多樣性，提高了算法的收斂精度。FAMFO算法步驟如下：

1)初始化螢火蟲種群，設置螢火蟲數(shù)目m, 最大吸引度β0, 光強吸收系數(shù)γ, 步長因子α, 最大迭代次數(shù)T和搜索精度ε。

2)將隨機初始化螢火蟲的位置,計算得出的螢火蟲目標函數(shù)值作為各自最大螢光亮度I0。

3)由式(7)～(8)計算群體中螢火蟲的相對亮度I和吸引度β。按相對亮度決定螢火蟲的移動方向,按照式(9)更新螢火蟲的空間位置, 對處在最佳位置的螢火蟲進行隨機擾動。

4)根據更新后螢火蟲的位置, 重新計算螢火蟲的亮度。

5)判斷是否滿足結束條件：若不滿足，則返回2)重新運行; 若滿足，則跳出循環(huán)，輸出最優(yōu)位置。

6)將螢火蟲算法得到的最優(yōu)位置作為飛蛾算法的初始位置，計算飛蛾個體適應度函數(shù)值；找到當前最好飛蛾個體位置并將其保存為火焰適應度值矩陣。

7)利用式(6)更新火焰數(shù)量，計算火焰與飛蛾間的距離,并利用式(4)更新飛蛾-火焰位置；利用式(1)、式(2)分別保存飛蛾及火焰空間位置。

8)找到當前最好飛蛾個體空間位置。

9)判斷算法迭代終止條件是否滿足：若滿足則轉至10)；否則，令l=l+1并執(zhí)行7)～8)。

10)輸出最優(yōu)個體值和全局極值,即火焰最終所處的空間位置及所對應的適應度值,算法結束。

2.2 指數(shù)遞減的飛蛾位置更新策略

在基本MFO算法的迭代過程中，選擇對數(shù)螺旋函數(shù)作為飛蛾位置更新機制，但該函數(shù)只是定義飛蛾飛向火焰，易使飛蛾陷入局部最優(yōu)。在全局尋優(yōu)時有一定的不足，會出現(xiàn)陷入局部最優(yōu)的情況，而且在算法迭代后期，粒子始終會圍繞當前適應度較高的粒子進行局部搜索，導致算法難以跳出最優(yōu)解的吸引，從而早熟收斂[20]。文獻[21]受線性遞減權重策略的啟發(fā)，構造3種不同策略對粒子群算法改進。實驗結果表明，指數(shù)遞減策略效果最佳。因此，本文采用指數(shù)遞減策略，來平衡全局搜索能力和局部搜索能力。當飛蛾在靠近火焰尋找最優(yōu)解時，用指數(shù)遞減策略改進飛蛾算法，指數(shù)遞減策略因子w的表達式為

(10)

式中:wmax、wmin分別代表w的最大值和最小值;l代表當前迭代次數(shù);T代表最大迭代次數(shù)。參數(shù)選取與文獻[20]一致，c=10,wmax=0.9,wmin=0.4。將w應用到更新飛蛾位置S(Mi,Fj)的對數(shù)螺旋線函數(shù)中,則

S(Mi,Fj)=Di·exp(bt)·cos(2πt)+w·Fj

(11)

在基本MFO算法中，w為恒定值1，容易造成算法在迭代前期陷入局部最優(yōu)，在迭代后期收斂速度變慢。因此，將指數(shù)遞減策略因子w加入到速度更新公式中，指數(shù)遞減策略因子w和第j支火焰Fj相乘。因為w值是隨著迭代次數(shù)的增加而減小的，當飛蛾接近火焰時，w值就會減小，提高了飛蛾的局部尋優(yōu)能力，避免飛蛾錯過最優(yōu)解[20]。這樣一來，可以使算法避免陷入局部尋優(yōu)，并有效展開精確搜索，確保找到最優(yōu)解。既有利于提高算法的收斂速度，又有利于提高算法的尋優(yōu)精度。

2.3 基于高斯擾動過程的飛蛾優(yōu)化算法

對當前火焰最優(yōu)解增加高斯擾動，可以產生新解，有效地利用當前全局最優(yōu)位置的信息保證新解中所有火焰之間的信息交流與學習，防止陷入局部最優(yōu)。通過在產生局部新解的公式中加入均值為 0、方差為當前迭代次數(shù)的最優(yōu)解絕對值的高斯擾動項，并加入步長控制因子確保擾動幅度，既提高了算法的精確搜索能力又增加種群多樣性與活躍性，還能進一步挖掘飛蛾優(yōu)化算法的仿生性能[20]。

S(Mi,Fj)=Di·exp(bt)·cos(2πt)+w·Fj+

a⊕N(μ,σ2)

(12)

高斯擾動項能有效利用當前全局最優(yōu)位置的信息保證新解中所有飛蛾之間的信息交流與學習:一方面可以有效幫助飛蛾避免陷入局部最優(yōu)，提高算法搜索精度；另一方面提高了種群多樣性，加快了算法收斂速度，可以有效提高算法的尋優(yōu)性能[22]。

飛蛾的最優(yōu)位置在當前全局最優(yōu)粒子周圍調整產生，具有很大的隨機性，往往使新解偏離當前全局最優(yōu)解;或者粒子調整范圍太小，導致飛蛾種群多樣性的喪失，從而出現(xiàn)求解不穩(wěn)定和精度不高的缺點。因此,這里設計擾動控制因子a控制高斯擾動項的干擾范圍，增強算法穩(wěn)定性和增加種群多樣性?；诟咚箶_動過程的飛蛾優(yōu)化算法步驟如下：

1)初始化算法參數(shù)，設置飛蛾種群大小n，優(yōu)化變量的維數(shù)d，最大迭代次數(shù)T以及初始火焰數(shù)量N;

2)采用螢火蟲算法進行初始化，將螢火蟲的最優(yōu)位置作為FGMGO算法初始位置;

3)計算每只飛蛾的適應度值，將飛蛾位置按適應度值從小到大進行排序，找出最優(yōu)個體賦給火焰;

4)利用式(12)更新每只飛蛾與火焰的位置；

5)記錄當前最優(yōu)火焰適應度值;

6)根據式(6)減少火焰數(shù)量，迭代次數(shù)l=l+1;

7)判斷是否達到最大迭代次數(shù)，若達到則輸出整個迭代過程中最優(yōu)火焰位置以及對應的適應度值，算法結束。

3 實驗及其結果分析

3.1 實驗設計

在仿真實驗中,仿真環(huán)境的硬件配置為Windows7旗艦版操作系統(tǒng), CPU為Intel(R)Core i3 1.70 GHz處理器, 4.00 GB內存,仿真環(huán)境的軟件配置為Matlab R2017a。

為了測試改進算法的有效性與可行性,將FGMFO算法與MFO[8]、IMFO[23]、DEPSO[24]、CMFO[25]等算法進行初始參數(shù)設定和結果對比分析。其中4種算法的初始參數(shù)設定如下:MFO算法中,a=[-1,-2],b=1;IMFO算法,設置局部尋優(yōu)的啟動時機A值為0.92;DEPSO算法中,加速因子c1=2,c2=2,w=1，最大運行速度vmax=6，F(xiàn)=0.5,CR=0.9;CMFO算法中,a=[0，2],w=[0.9，0.2]。

3.2 測試函數(shù)

選取10個經典基準測試函數(shù)測試算法尋優(yōu)性能，每個測試函數(shù)的求解維數(shù)都是100維，最優(yōu)值均為0。其中函數(shù)F1～F6是平滑的單模態(tài)函數(shù)，只有一個全局最小值沒有局部最優(yōu)，用于測試算法的收斂速度；函數(shù)F7～F10都是復雜的多模態(tài)函數(shù)，有多個局部極小值，主要用于測試算法的尋優(yōu)精度，使之跳出局部極值，避免早熟收斂[8]。測試函數(shù)如表1所示。

表1 測試函數(shù)

3.3 擾動控制因子

基本的MFO算法易陷入局部最優(yōu)、尋優(yōu)精度不高，這里設計擾動控制因子a控制高斯擾動項的干擾范圍，增強算法穩(wěn)定性[20]。參照文獻[20]，各控制因子a的參數(shù)設置分別取 0.01、0.05、0.1、0.5、1，用FGMFO算法對測試函數(shù)迭代1 000次，分別獨立運行50次，求解結果如表2所示。

表2 控制因子的不同取值測試結果對比

通過觀察表2可以發(fā)現(xiàn)，若FGMFO算法能夠尋找到最優(yōu)解，控制因子不影響解的精度；若未尋找到最優(yōu)解，在a=0.05時，F(xiàn)GMFO算法對函數(shù)的求解精度比a的其他取值結果高。所以，本文中a取值為0.05，以保證算法的最優(yōu)性能。

3.4 尋優(yōu)性能分析

應用基準函數(shù)F1～F10測試FGMFO、MFO、IMFO、DEPSO、CMFO等算法。所有算法的最大迭代次數(shù)為1 000，種群大小為30，分別從標準差、最好值、均值、最差值評估該算法的性能。其中解的質量由最好值和最差值反應，算法所能達到的精度由平均值反應，算法的魯棒性及穩(wěn)定性由標準差所反應。函數(shù)測試結果如表3所示。表3中，“①”表示求解精度最高的解。

表3 函數(shù)測試結果

由表3可知，10個測試函數(shù)經過1 000次迭代，MFO算法、DEPSO算法性能一般，IMFO、CMFO算法性能較好，F(xiàn)GMFO算法最優(yōu)。對于函數(shù)F1、F3、F7、F9，F(xiàn)GMFO算法可以找到最優(yōu)解，標準差、均值、最差值均為0，而IMFO、MFO、DEPSO、CMFO算法均不能找到最優(yōu)解。說明FGMFO算法在求解高維復雜函數(shù)F1、F3、F7、F9時，展示了更高的尋優(yōu)性能。對于函數(shù)F2、F4、F6、F8、F10，雖然 FGMFO尋找到的最優(yōu)解沒有達到理論最優(yōu)值，但是FGMFO算法的尋優(yōu)精度要優(yōu)于其他4種算法，在標準差、均值方面的求解精度更高。尤其是對于函數(shù)F2和F4，F(xiàn)GMFO算法的求解精度要比其他算法高出200個數(shù)量級，而且FGMFO算法的求解方差結果為0，說明FGMFO算法的穩(wěn)定性更強;而對于函數(shù)F5，由于高維、復雜條件的環(huán)境，F(xiàn)GMFO算法的精度并不高，但5種算法均沒有求到最優(yōu)解，且出現(xiàn)收斂精度低的問題，需要進一步研究。

綜合以上分析，本文設計的FGMFO算法在高維、復雜條件的環(huán)境下尋優(yōu)性能方面明顯優(yōu)于其他4種算法，顯示了更高的尋優(yōu)精度和更高的穩(wěn)定性。

3.5 收斂性能

算法的收斂速度是衡量算法性能的重要指標，算法的收斂圖可以更加直觀地對比各種算法的收斂性能。圖1～10為FGMFO、MFO、IMFO、DEPSO、CMFO等5種優(yōu)化算法在求解10個標準測試函數(shù)時的適應度值。

圖3 函數(shù)F3的收斂曲線 圖4 函數(shù)F4的收斂曲線

由圖1～10可知，通過螢火蟲算法獲取飛蛾的初始最優(yōu)位置，在開始迭代時FGMFO算法就已經處于領先位置，使得收斂速度更快，尋優(yōu)性能更高。說明FGMFO算法具有更好的搜索能力和更穩(wěn)定的性能，同時證明用螢火蟲算法初始種群方法能夠顯著改善MFO算法的尋優(yōu)性能。由圖1～4可知，在求解函數(shù)F1～F4時，F(xiàn)GMFO算法迭代效果一直保持領先，IMFO、MFO、DEPSO、CMFO算法由于搜索能力較弱都陷入局部最優(yōu)且出現(xiàn)收斂精度低的問題。在求解函數(shù)F1和F3時，F(xiàn)GMFO算法在迭代600多次時收斂到全局最優(yōu)(圖1、3)。在圖2中，IMFO、MFO、DEPSO、CMFO等4種算法在收斂過程中出現(xiàn)了不同程度的階梯狀，但FGMFO算法收斂曲線迅速下降。由圖5可知，在開始迭代時FGMFO算法的搜索精度比其他算法更高。但是，在迭代前期出現(xiàn)了劇烈振蕩，呈階梯狀下降；在迭代后期，F(xiàn)GMFO算法收斂速度變得緩慢，最后收斂曲線一直保持水平不再收斂，未獲得全局最優(yōu)解。不過，MFO算法的收斂曲線要比其他4種算法光滑。由圖6可知，其他4種算法在收斂過程中出現(xiàn)了不同程度的階梯狀，在迭代前期出現(xiàn)了劇烈振蕩，迭代后期出現(xiàn)停滯的情況下，F(xiàn)GMFO算法仍保持著很快的收斂速度。觀察圖7和圖9，F(xiàn)GMFO算法的收斂曲線迅速下降，收斂較快，在迭代不到100次時就收斂到最優(yōu)解，遠遠優(yōu)于其他算法；觀察圖8和圖10，在開始迭代時FGMFO算法就已經處于領先位置，F(xiàn)GMFO算法的收斂曲線遠遠優(yōu)于其他算法。

圖5 函數(shù)F5的收斂曲線 圖6 函數(shù)F6的收斂曲線

圖7 函數(shù)F7的收斂曲線 圖8 函數(shù)F8的收斂曲線

圖9 函數(shù)F9的收斂曲線 圖10 函數(shù)F10的收斂曲線

綜上分析，F(xiàn)GMFO算法在處理高維單模態(tài)、多模態(tài)的問題上，具有快速的收斂速度與更高的收斂精度，并且穩(wěn)定性高于其他算法，表明了FGMFO算法在尋優(yōu)精度、收斂速度和求解穩(wěn)定性方面比其他4種算法有顯著的優(yōu)越性，求解性能優(yōu)良。

3.6 運行速度和時間復雜度

算法運行速度和時間復雜度能間接反映算法的收斂速度，也是反映算法優(yōu)劣的重要度量標準。以單次循環(huán)為例,在每個基準函數(shù)上測試FGMFO、MFO、IMFO、DEPSO、CMFO算法運行速度，測試結果如表4 所示。

雖然FGMFO算法需要通過螢火蟲算法獲取飛蛾的初始最優(yōu)位置,但并沒有增加FGMFO算法的運行時間，且FGMFO與IMFO、MFO、DEPSO算法相比運行速度更快(表4)。出現(xiàn)這樣的結果是因為飛蛾位置的初始化的處理使得在開始迭代時FGMFO算法就已經處于領先位置，使得收斂速度更快，尋優(yōu)性能更高，顯著改善了MFO的尋優(yōu)性能。

表4 運行速度測試結果

基本飛蛾優(yōu)化算法的計算復雜度取決于飛蛾的數(shù)量n、搜索空間的維度d、最大迭代次數(shù)T以及螢火蟲群體的規(guī)模為m。以N*表示當前火焰數(shù)量，并以單次循環(huán)為例，MFO與FGMFO算法的計算復雜度見表5。

表5 算法的時間復雜度比較

MFO和FGMFO的迭代次數(shù)相同, 其時間復雜度差別在于初始化策略不同。MFO算法初始化復雜度為O(n)，F(xiàn)GMFO算法通過螢火蟲算法獲取飛蛾的初始最優(yōu)位置，其中螢火蟲初始化復雜度為O(m2),則FGMFO算法的初始化復雜度為O(m2)+O(n)=O(m2)。飛蛾圍繞火焰矩陣和最差火焰飛行,MFO算法的時間復雜度為

O(T·N*)+O(T·(N-N*))=O(T·n)

FGMFO算法的時間復雜度為

O(T·N*)+O(T·(N-N*))=O(T·n)

由以上分析，可以得出FGMFO算法的時間復雜度稍高于基本MFO算法，但是并沒有增加算法的難度，表明了算法的可行性。在后續(xù)研究中，應加強對種群初始化處理的研究，以進一步提高算法的性能。

4 結 語

針對飛蛾優(yōu)化算法存在易陷入局部最優(yōu)、尋優(yōu)精度不高的問題，提出了一種基于螢火蟲算法和高斯擾動的飛蛾優(yōu)化算法。該算法為了增強飛蛾種群的多樣性,利用螢火蟲算法優(yōu)化飛蛾的初始位置，在飛蛾位置更新上引入了指數(shù)遞減策略和高斯擾動項防止陷入局部最優(yōu)，通過控制因子控制高斯擾動的擾動范圍，增強算法的穩(wěn)定性。通過10個100維的測試函數(shù)驗證FGMFO算法性能。將FGMFO算法的結果與MFO、IMFO、DEPSO、CMFO算法進行比較發(fā)現(xiàn)，F(xiàn)GMFO算法的尋優(yōu)精度、收斂速度以及算法穩(wěn)定性方面均有較大程度的提升。下一步將研究FGMFO算法在復雜優(yōu)化問題中的應用，使其具有更大的實際應用價值。