螢火蟲粒子群混合算法

楊小東 蔡澤凡 牛俊英

順德職業技術學院電子與信息工程學院 廣東佛山 528333

螢火蟲粒子群混合算法

楊小東 蔡澤凡 牛俊英

順德職業技術學院電子與信息工程學院 廣東佛山 528333

本文把螢火蟲算法和粒子群優化算法進行混合，在兩種算法平行進化的基礎上引入共享機制，使兩種算法優點互補。仿真證明，混合算法提升了算法的全局搜索能力和收斂速度，適應性更強，可以應用于復雜的優化問題。

螢火蟲算法；粒子群優化算法；混合算法；混沌

一、引言

螢火蟲算法[1-2]（Firefly Algorithm，FA）是一種啟發式算法，由劍橋大學的XinsheYang于2008年提出，靈感來自于螢火蟲閃爍的行為。螢火蟲的閃光，其主要目的是作為一個信號系統，以吸引其他的螢火蟲。

粒子群優化算法[3-5]（ParticleSwarmOptimiztion，PSO）是模仿鳥群覓食行為的一種群體智能算法，該算法1995年由美國學者J.Kennedy和R.C.Eberhart提出。PSO算法包括一個速度更新方程和一個位置更新方程，需要調整的參數較少，程序容易實現。

不管是FA還是PSO，得益于它們的簡單性和有效性，它們從誕生之日起就引起了國內外學者的關注，并掀起了研究熱潮，在諸多領域得到了成功的應用。[6-16]它們對于某些復雜問題，都存在搜索不到滿足精度要求的最優解，其性能需要進一步的改善。本文結合FA和PSO的優點，引入兩種算法的共享機制，形成了螢火蟲粒子群混合算法（Firefly Algor ithm and Particle Swarm Optimization Mixed Algorithm，FAPSOMA），FAPSOMA大大提升了全局搜索能力和收斂速度。

二、螢火蟲算法

FA是一種仿生的群體智能算法，該算法模擬了自然界中螢火蟲靠發光來尋找食物的行為，是一種隨機優化算法。螢火蟲個體利用發光特性來搜索附近某個區域，并向區域內位置較優的螢火蟲移動，從而實現位置進化。在尋優過程中，螢火蟲亮度和吸引度是螢火蟲進化的兩個關鍵因素。其中，螢火蟲的亮度取決于自身位置的優劣性，在實際應用中，亮度用目標函數值代替，亮度越高說明螢火蟲的位置越好。螢火蟲的吸引度決定了螢火蟲的移動方向，螢火蟲的吸引度越大，則越容易吸引四周的螢火蟲向著自身的位置靠近。螢火蟲的亮度和吸引度與螢火蟲個體之間的距離成反比，都隨著距離的增長而減小。通過吸引度與亮度的不斷更新變化，從而使算法達到尋優的效果。[1-2,6]

假設有N只螢火蟲，搜索空間的維度為D維，那么第i只螢火蟲在D維空間的初始位置可表示為 。

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

其中 ，表示光強吸引因子，取值與區域面積相關，一般設為常數，表示第i只螢火蟲和第j只螢火蟲的空間距離，的值隨著 的增大而減少，當 時達到最大的亮度

的值一般正比于目標函數。

定義2螢火蟲的相對吸引度。

其中，表示第i只螢火蟲的最大吸引度，表示螢火蟲i對螢火蟲j的吸引度，隨著距離的增大而減少。

定義3尋優過程中螢火蟲i被螢火蟲j吸引的位置更新公式。

其中，為步長因子，rand為[0，1]上服從均勻分布的隨機因子。為了加大搜索空間范圍，提高群體的多樣性，防止過早收斂，加入了隨機擾動項 。

基本螢火蟲的算法步驟如下：[1-2,6-7]

（1）隨機初始化螢火蟲種群；

（2）計算各只螢火蟲的目標函數值（代表了亮度）；

（3）比較目標函數值的優劣性，如果螢火蟲j優于螢火蟲i，則根據式（3）移動螢火蟲i的位置并使其位置落在限定的區域；

（4）更新螢火蟲的最優位置和目標函數值；

（5）如果迭代次數達到最大值或者目標函數達到設定的精度則終止，否則跳到步驟（2）繼續執行。

三、粒子群優化算法

PSO的基本思想是將每個粒子視為優化問題的一個可行解，粒子的好壞由一個事先設定的目標函數值函數來確定。每個粒子在可行解空間中運動，并由一個速度變量決定其方向和距離。在每一代進化中，粒子跟蹤兩個極值：一個是粒子本身迄今為止找到的最優解，另一個是整個群體迄今為止找到的最優解，最終獲得問題的全局最優解。

假設粒子群的規模為N，搜索空間為D維，則粒子i在t時刻的狀態屬性設置如下：

粒子i在t+1時刻的位置通過式（4）和（5）更新，

式中，r1、r2為[0，1]區間均勻分布的隨機數；c1、c2為學習因子，一般c1=c2=2。

原始PSO算法具有四個步驟：

（1）粒子群初始化。設定PSO算法中涉及的各類參數，初始化各個粒子的位置xi和速度vi，計算其目標函數值Fi；初始化個體自身極值和全局極值。

（2）評價粒子群。計算每個粒子的目標函數值Fi，更新粒子的目標函數值極值、位置極值pi，更新全局目標函數值極值、位置極值pg。

（3）更新粒子群。用式（4）和（5）對每一個粒子的速度和位置進行更新，并對速度的范圍進行限制。

（4）判斷是否滿足結束條件。判斷是否達到精度或迭代終止條件，若達到，則停止迭代，輸出最優解，否則轉到步驟（2）。

四、FA、PSO混合算法FAPSOMA

單一的仿生優化群算法的適應性是有限的，某種算法在解決某個問題時很成功，在處理另外一個問題時則有可能捉襟見肘，而另外一種算法的適應情況可能恰好相反。把兩種性能上具有互補性的優化算法進行混合，能夠彼此取長補短，提升算法的總體性能。

（一）FAPSOMA算法模型

在FAPSOMA算法中，FA和PSO既有分工也有合作，它們首先平行地單獨進化，然后每隔一定的代數彼此共享最優個體，從而改善算法的全局搜索能力。FAPSOMA的流程如圖1所示，主要包含以下7個步驟：

（1）初始化。分別初始化FA和PSO，FA和PSO的族群數和個體的維數相同，目標函數也一致。

（2）平行進化。利用FA和PSO分別搜索最優值，兩種算法獨立的進化，FA和PSO各自保存自己族群的最優個體。

（3）選擇共享時刻。判斷是否到達FA和PSO共享的時刻，這里規定每當算法迭代mg代以后，FA和PSO就進行共享。若到達共享的時刻則進入步驟（4），否則跳到步驟（5）。

（4）共享優秀個體。把FA和PSO兩者最好的m個個體替換對方最差的m個個體，注意m的值不能超過族群規模的一半，以免發生交換過去的個體又被原封不動的交換回來的現象。隨著算法的進化，FA和PSO都可能發生聚集的情況，所以隨著算法的進行應該進一步提高族群的多樣性，所以m的值宜采取遞增的情況，這里采用式（6）進行計算，

其中，N為族群大小；t為當前迭代數，tmax為最大迭代數；r0為比例控制常數，1r0＞0.51；符號 表示向下取整數。

交換時，需要注意FA和PSO兩種算法的不同，在FA中，只需要保存位置和目標函數值，而在PSO中，除了需要保存位置和目標函數值以外，還需要保存速度。因此當用FA優秀的個體替換PSO中差的個體時，位置和目標函數值可以直接替換，但是FA中沒有速度信息，我們利用PSO本身最優個體的速度采用混沌模式產生相應的速度序列替換PSO這些較差個體的速度，混沌模式[17-19]采用式（7）的形式。

其中，yit是[0,1]中的一個隨機數；t是迭代的代數；是一個控制參數，一般取4，這時系統將處于一個完全混沌的狀態。

（5）保存全局最優值。每次進化后，判斷FA和PSO兩者搜索到的最優值哪一個更優，把其中最優的那一個保存下來。

（6）判斷算法進程。判斷算法是否滿足結束條件（達到收斂精度或者最大迭代次數），滿足則進入下一步，否則返回步驟（2）。

（7）輸出結果。輸出最終的最優值結果，算法結束。

圖1 FAPSOMA流程圖

（二）FAPSOMA算法仿真測試

為了驗證FAPSOMA算法的有效性，對FAPSOMA進行仿真測試，仿真測試平臺為WIN7+MATLAB R2012b，測試函數采用表1所示的6個標準測試函數，f1～f3為單峰函數，f4～f6為多峰函數。仿真時，族群數N=30，個體維數D=20，各維變量的范圍為[-20,20]，函數的收斂精度設為 =10-5，最大迭代數設為tmax=2000，每個仿真單獨運行30次。替換代數間隔預設為mg=10，式（6）中的替換比例控制常數預設為r0=0.6，30次測試的結果如表2所示。從表2和表3可以看出，FA和PSO混合而成的新算法FAPSOMA在全局搜索能力和收斂精度這兩個方面都得到了提升。需要注意的是，對于有些問題，FAPSOMA仍然不能100%地搜索到滿足精度要求的最優解，這主要是因為對于這些問題，FA和PSO都不能夠100%地搜索到最優解，因此我們在選擇不同的算法進行混合時，應該盡可能地選擇在全局搜索能力方面能夠完全互補的算法。表3是對成功率和成功時的收斂速度來考察的，現在我

們再來看看它們的平均性能，以標準測試函數f2和f5為例，利用FA、PSO和FAPSOMA這3種算法迭代2000次，重復30次以后取平均值，對應的平均最好目標值曲線如圖2和圖3所示。

表1：標準測試函數

表2：FAPSOMA和PSO、FA的仿真對比情況

表3 函數f2～f6的仿真結果匯總表

由圖2可見，雖然PSO在能夠搜索到最優值所需要的迭代次數是最少的，但是因為其成功率最低，因此多次實驗所得的平均收斂速度是最慢的。FAPSOMA的收斂速度、收斂精度最快。圖3的情況有所差別，前1000次，FA的平均收斂速度最慢，FAPSOMA最快，1000次以后，PSO的平均收斂速度最慢，FA最快。

綜合表3、圖2和圖3的信息，我們可以得到這樣的結論：從總體性能上來看，這3種算法的排序為FAPSOMA＞FA＞PSO。

圖2 函數f2的平均最優目標值曲線

圖3 函數f5的平均最優目標值曲線

五、結論

單一的仿生優化群算法無法適應所有的優化問題，不同的優化算法具有各自適合的場合，將兩種或以上的仿生算法進行混合，可以做到揚長避短，提升算法的適應性。FAPSOMA結合了FA、PSO兩者的優點，六種標準測試函數仿真情況表明，FAPSOMA的性能明顯好于PSO和FA，不管是處理簡單的單峰函數，還是復雜的多峰函數，FAAPSO的全局搜索能力和收斂速度都更加優越，表現了良好的魯棒性。

[1]Yang X S.Nature-Inspired Metaheuristic Algorithm[M].Luniver Press,2008.

[2]Yang XS.Cuckoo Search and Firefly AlgorithmTheory and Applications[M].Springer,2014.

[3]Kennedy J,EberhartR.Particle swarm optimization[c].IEEE International Conference on Neral Networks,1995,4:1942-1948.

[4]Shi Y,Eberhart R.A Modified Particle Swarm Optimi-