逃逸均值簡化粒子群優(yōu)化算法

陸松建，司偉立，韓 娟,3,4，李質(zhì)彬

(1.重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065；2.中國科學(xué)院計算技術(shù)研究所 移動計算與新型終端北京市重點實驗室，北京 100190；3.中國科學(xué)院計算技術(shù)研究所 無線通信技術(shù)研究中心，北京 100190；4.中國科學(xué)院大學(xué) 計算機與控制學(xué)院，北京 100049)

0 引 言

粒子群優(yōu)化(particle swarm optimization，PSO)算法存在易陷入局部極值、過早收斂和收斂精度低等問題[1-4]。為解決PSO算法存在的問題，目前提出的改進方法大致分為4類：基于粒子初始化的改進，如文獻[5]中利用Hammersley對粒子位置進行初始化，使初始種群能夠均勻覆蓋整個搜索空間；基于粒子群速度更新公式的改進，包括參數(shù)調(diào)節(jié)和公式自身改進二種方式，如動態(tài)調(diào)整慣性權(quán)重粒子群算法[6]、二階振蕩策略粒子群算法[7]，該類方法通過均衡算法全局與局部尋優(yōu)能力，加強算法跳出局部最優(yōu)的能力；基于分群策略的改進，如文獻[8]將整個種群分為PSO機制迭代分群和混沌機制迭代分群，有利于增強種群多樣性避免陷入局部極值中；基于混合機制的改進，利用其它算法優(yōu)勢幫助粒子群算法跳出局部最優(yōu)，如模擬退火粒子群算法[9]、混沌粒子群算法[10]、免疫粒子群算法[11]等，混合算法尋優(yōu)性能較好，但混合機制使得算法變得更加的復(fù)雜與繁瑣。

本文基于前人的研究，提出了一種逃逸均值簡化粒子群優(yōu)化(escape mean simplified particle swarm optimization，EMSPSO)算法，EMSPSO算法不使用速度更新公式，在簡化粒子群優(yōu)化算法的基礎(chǔ)上，加入均值搜索策略和逃逸策略，保證極快收斂速度的同時有效地改善PSO算法易陷入局部最優(yōu)的問題。仿真實驗中，引入5個標準測試函數(shù)，將本文算法與其它改進算法進行對比實驗，驗證EMSPSO算法的有效性。

1 標準粒子群優(yōu)化算法

(1)

(2)

其中，x=1,2,…,n；d=1,2,…,D；t=1,2,…,M；r1和r2為區(qū)間[0,1]上均勻分布的隨機數(shù)；M為種群最大進化代數(shù)；c1和c2為學(xué)習(xí)因子，分別代表個體的“自我認知”能力和群體的“社會引導(dǎo)”功能，c1,c2∈[0,2]；w為慣性權(quán)重，可以均衡種群的全局和局部尋優(yōu)能力，w∈[0,1]； 為了預(yù)防粒子跳出解空間的搜索區(qū)間，一般設(shè)置vid∈[-vmax,vmax]，vmax為用戶自行設(shè)置的常數(shù)，代表粒子的最大飛行速度；進化停止條件為預(yù)設(shè)的最大進化代數(shù)或(和)預(yù)設(shè)的目標精度閥值。

2 逃逸均值簡化粒子群優(yōu)化算法

2.1 簡化粒子群優(yōu)化算法

標準PSO算法包含速度和位置更新項，大多數(shù)改進PSO算法對速度、位置更新項增加某些操作算子，例如混沌[10]、自適應(yīng)調(diào)節(jié)參數(shù)[12]、變異[13]等操作提高算法的收斂速度和精度，使得PSO算法的描述越來越復(fù)雜，同時，也使得定量分析算法的收斂性變得更加的復(fù)雜。

文獻[12]嘗試舍棄PSO算法中速度更新項，使算法達到最簡化，仿真實驗結(jié)果表明這種改進對算法穩(wěn)定性影響不大，同時提高了算法的搜索效率。本文同樣舍棄標準PSO算法中速度更新項，僅由位置更新項的指導(dǎo)進行全局尋優(yōu)，得到簡化粒子群優(yōu)化算法(simplified particle swarm optimization，SPSO)，其公式如下

(3)

SPSO算法沒有粒子速度更新概念，避免了人為設(shè)置 [-vmax,vmax] 而影響粒子的收斂速度和精度，同時，使得算法更加的簡化便于對算法的進化過程進行分析。

2.2 均值搜索策略

SPSO算法無速度更新項，僅由個體粒子最優(yōu)解和全體粒子最優(yōu)解引導(dǎo)粒子進行位置更新，進化過程中，無速度因子的牽制，避免了粒子在收斂后期由于速度更新出現(xiàn)“發(fā)散”現(xiàn)象，導(dǎo)致粒子收斂速度慢、收斂精度低的問題。解決單峰值問題時，SPSO算法的收斂速度快、收斂精度高，但對于復(fù)雜的多峰值多局部解問題，由于無速度因子的牽制，粒子位置趨向于全局最優(yōu)解更新幅度過大，導(dǎo)致粒子種群多樣性差，全局尋優(yōu)能力低，易陷于局部最優(yōu)解。

(4)

式中：第一項舍棄SPSO算法中慣性權(quán)重因子w， 利用均值策略替代其它改進SPSO算法中通過調(diào)節(jié)w的方式均衡算法全局與局部尋優(yōu)能力，簡化了算法的操作；第二項和第三項為粒子個體最優(yōu)位置和全體最優(yōu)位置的線性組合。

MSPSO算法和SPSO算法進化過程如圖1所示。

圖1 MSPSO算法和SPSO算法進化過程對比

(5)

到了進化后期t→∞時，根據(jù)式(5)關(guān)系式，式(4)可變?yōu)?/p>

(6)

2.3 逃逸策略

粒子進化過程中，無論是早熟收斂還是全局收斂，群體中的粒子都會出現(xiàn)嚴重“聚集”現(xiàn)象，此時種群多樣性匱乏[13]，如果粒子早熟收斂陷入局部最優(yōu)解，因周圍已經(jīng)過高密度搜索，難以突破局部最優(yōu)解。因此，當出現(xiàn)早熟收斂時，需提供一種機制，跳出當前局部最優(yōu)解。

(7)

式中：r3為區(qū)間[0,1]上均勻分布的隨機數(shù)；kt為逃逸控制因子，當不滿足逃逸條件下，其值為0，否則代表逃逸的半徑，即

(8)

式中：t為當前進化代數(shù)；M為最大總進化代數(shù)；R為半徑控制因子，控制粒子逃逸的半徑，本文算法R取值為1；tI,tG分別為個體最優(yōu)解停滯代數(shù)和全體最優(yōu)解停滯代數(shù)；EI,EG為個體最優(yōu)解最大停滯代數(shù)閥值和全體最優(yōu)解最大停滯代數(shù)閥值，一般取值范圍為3～8。

分析式(8)可知，當不滿足逃逸條件時，公式退化為式(4)；當滿足逃逸條件時，在進化前期，kt為較大值，粒子逃逸半徑較大，加強全局尋優(yōu)能力；在進化后期，kt為較小值，加強后期收斂能力。

2.4 算法步驟

EMSPSO算法實現(xiàn)步驟如下：

步驟3 進入進化過程，根據(jù)式(8)計算逃逸控制因子kt。

步驟4 根據(jù)式(7)更新各粒子位置，并計算各粒子位置更新后的適度值，更新個體最優(yōu)解和全體最優(yōu)解。

步驟5 判斷個體最優(yōu)解或全體最優(yōu)解是否處于停滯狀態(tài)，如果處于停滯狀態(tài)，則分別累加各自的停滯代數(shù)tI或tG。 否則，直接執(zhí)行步驟6。

步驟6 如果當前進化代數(shù)小于預(yù)設(shè)的最大進化代數(shù)或(和)當前全體最優(yōu)解適度值未達到預(yù)設(shè)的目標精度閥值，則重復(fù)執(zhí)行步驟3～步驟6。否則，執(zhí)行步驟7。

步驟7 輸出種群搜索到的最優(yōu)解，進化停止，算法尋優(yōu)結(jié)束。

3 仿真實驗及對比分析

3.1 測試函數(shù)

為全面體現(xiàn)改進算法的有效性，本文從所有常用標準測試函數(shù)中挑選出5個具代表性的測試函數(shù)進行仿真對比。其中包括以Sphere為代表的單峰值函數(shù)、以Rastrigin為代表的這一類復(fù)雜多峰多局部解函數(shù)、提供極少優(yōu)化信息難以極小化的Rosenbrock病態(tài)單峰二次函數(shù)、含噪聲影響的Quartic函數(shù)及最優(yōu)值為負數(shù)的Inverted Consine Wave函數(shù)。函數(shù)具體表達式見表1，其中D代表函數(shù)的維數(shù)。

3.2 實驗設(shè)計及參數(shù)設(shè)置

本文使用Matlab R2014a進行仿真實驗，仿真環(huán)境為Windows 7系統(tǒng)運行下在Intel(R) Core(TM) i5-75003.4 GHz的處理器中進行。在相同仿真環(huán)境與參數(shù)設(shè)置條件下，將本文改進的算法與PSO算法、改進二階振蕩粒子群優(yōu)化算法(improved second-order oscillatory particle swarm optimization，ISOPSO)[7]、自適應(yīng)簡化粒子群優(yōu)化算法(self-adjusted simplified particle swarm optimization，SASPSO)[12]進行對比實驗，從收斂速度、收斂精度和穩(wěn)定度3個方面驗證EMSPSO算法的性能。

表1 5種標準測試函數(shù)

對比算法中各參數(shù)設(shè)置均如下：種群數(shù)量n=40； 最大總進化代數(shù)M=100； 學(xué)習(xí)因子c1=c2=2； 最小慣性權(quán)重wmin=0.4， 最大慣性權(quán)重wmax=0.9， 固定慣性權(quán)重w=0.8； 個體最優(yōu)解最大停滯代數(shù)閥值EI=3， 全體最優(yōu)解最大停滯代數(shù)閥值EG=5； 半徑控制因子R=1。 為保證測試結(jié)果不具隨機性，每個算法獨立運行50次，對測試結(jié)果取平均作為更可靠的依據(jù)。

性能評估采用如下方法：

(1)總進化代數(shù)設(shè)置為100，固定進化代數(shù)情況下評估各算法解決10維問題、50維問題時收斂速度和精度。

(2)總進化代數(shù)設(shè)置為1000，固定各測試函數(shù)的目標收斂精度，評估各算法解決50維問題時達到目標收斂精度所需的平均進化代數(shù)和50次搜索中能達到目標收斂精度的搜索成功率。

3.3 收斂速度和收斂精度對比

為體現(xiàn)不同算法的優(yōu)劣性，固定各算法總進化代數(shù)為100，從最優(yōu)值、平均值、標準差、平均運行時間(s)等統(tǒng)計特性對算法進行評估。每個算法獨立運行50次，最優(yōu)值指50次搜索中搜索結(jié)果的最優(yōu)值；平均值指50次搜索中搜索結(jié)果的平均值；標準差指各算法搜索結(jié)果偏離均值的程度，用于判斷算法的穩(wěn)定性；平均運行時間指平均運行一次算法所需要的時間。解決10維和50維的低高維度問題時，各算法搜索結(jié)果見表2。

觀察50次搜索中的最優(yōu)值和平均值，EMSPSO算法對函數(shù)F1的搜索結(jié)果均優(yōu)于其它對比算法；SASPSO、EMSPSO 算法均搜索到函數(shù)F2和F4的理論最優(yōu)解；對于極難極小化的病態(tài)函數(shù)F3，EMSPSO算法的搜索結(jié)果更加接近于函數(shù)F3的理論最優(yōu)解，而其它算法均完全偏離理論最優(yōu)解；EMSPSO算法對函數(shù)F5的搜索結(jié)果略差于SASPSO算法，其差距較小，收斂精度已達到很好的效果。

觀察標準差，EMSPSO算法除對函數(shù)F3和F5的搜索結(jié)果略差于SASPSO算法外，對其它函數(shù)搜索結(jié)果均優(yōu)于其它對比算法。而對于病態(tài)函數(shù)F3，雖然SASPSO算法標準差最小，但搜索到的最優(yōu)值已完全偏離F3函數(shù)的理論最優(yōu)解，因此，該算法對函數(shù)F3標準差性能的評估已失去意義。

觀察平均運行時間，SASPSO算法平均運行時間最長，其算法通過添加鎖定因子和自適應(yīng)調(diào)節(jié)慣性權(quán)重的方式取得較好的尋優(yōu)性能，但同時加大了算法運行時間，而 EMSPSO 算法取得更好性能的同時平均運行時間低于SASPSO算法，EMSPSO算法的平均運行時間更接近于其它3個算法，時間復(fù)雜度更低。

通過以上分析可知，改進算法無論解決低、高維度問題，都能保持良好的搜索性能，除對函數(shù)F5的搜索性能略差于SASPSO算法外，改進算法對其它函數(shù)的搜索，其收斂精度更高、結(jié)果波動性更??；對于含有較少尋優(yōu)信息的病態(tài)函數(shù)F3，EMSPSO算法通過逃逸操作跳出局部最優(yōu)解，使種群在解空間的其它區(qū)域繼續(xù)搜索從而搜索到了全局最優(yōu)解，搜索到的最優(yōu)解更加接近于函數(shù)F3的理論最優(yōu)解，而其它算法已經(jīng)完全偏離理論最優(yōu)解。綜上分析可知，EMSPSO算法的整體尋優(yōu)性能優(yōu)于其它對比算法。

鑒于篇幅原因，以下選取其中3個50維函數(shù)的搜索進化曲線進一步觀察算法性能，其中橫坐標為進化代數(shù)，縱坐標為50次搜索結(jié)果平均適度值的對數(shù)。

各算法對Sphere函數(shù)的搜索進化曲線如圖2所示，當?shù)竭_最大進化代數(shù)時，EMSPSO算法更加接近于理論0值解，收斂精度最高。

表2 各算法解決10維和50維問題時搜索結(jié)果對比

圖2 50維Sphere函數(shù)搜索進化曲線對比

各算法對Rastrigin函數(shù)的搜索進化曲線如圖3所示，在第12代進化左右EMSPSO算法的搜索結(jié)果已達到該函數(shù)的理論最優(yōu)解，到達理論最優(yōu)解所需的進化代數(shù)最少，收斂速度最快。

圖3 50維Rastrigin函數(shù)搜索進化曲線對比

各算法對Rosenbrock函數(shù)的搜索進化曲線如圖4所示，EMSPSO算法對Rosenbrock函數(shù)的搜索一直在逐漸逼近函數(shù)理論最優(yōu)解，而其它對比算法在第15代進化左右就已陷入某個局部解中，處于搜索停滯狀態(tài)。

圖4 50維Rosenbrock函數(shù)搜索進化曲線對比

從圖2～圖4可看出，EMSPSO算法對各函數(shù)的搜索均能在20次進化代數(shù)內(nèi)達到較好的收斂精度，算法收斂速度快，且進化曲線位于其它算法的下方，收斂精度更高。

3.4 平均進化代數(shù)和搜索成功率對比

表3為總進化代數(shù)為1000、重復(fù)運行50次條件下，各算法解決50維問題時達到函數(shù)目標精度所需的平均進化次數(shù)和搜索成功率對比。其中，目標精度代表解決50維函數(shù)問題所期望達到的收斂精度；平均進化次數(shù)=達到函數(shù)目標收斂精度所需進化代數(shù)總和÷達到函數(shù)目標收斂精度運行次數(shù)；搜索成功率=達到函數(shù)目標收斂精度運行次數(shù)÷總運行次數(shù)；“-”表示超過最大進化代數(shù)仍未達到函數(shù)目標收斂精度。

從表3可看出，PSO算法搜索性能最差，只有對函數(shù)F4的搜索結(jié)果能達到目標精度值，且搜索成功率較低只有34%，平均進化次數(shù)高達513.59；ISOPSO算法搜索性能相對于PSO算法更好，除函數(shù)F1外對于其它函數(shù)的搜索結(jié)果都能達到目標精度值，但搜索成功率較低；SASPSO、EMSPSO算法搜索結(jié)果均能達到函數(shù)目標收斂精度，搜索成功率高達90%以上，算法穩(wěn)定性高，其中EMSPSO算法除函數(shù)F5外，達到函數(shù)目標精度所需的平均進化次數(shù)最少，搜索速度更快，性能更優(yōu)。

基于以上分析結(jié)果可知，PSO算法易陷于局部最優(yōu)解、收斂速度慢、收斂精度不高，其它改進算法均改善了PSO算法存在的不足，其中EMSPSO算法性能最優(yōu)，主要原因在于：EMSPSO算法利用均值策略加大算法搜索范圍使得算法在進化前期搜索到全局最優(yōu)解的可能性更大，并且無速度因子的牽制，使得算法收斂速度更快。如果算法陷入局部最優(yōu)解中，可通過逃逸策略在其它解空間繼續(xù)搜索，增大算法搜索到全局最優(yōu)解的幾率。

表3 解決50維問題時各算法在相同目標精度下性能評估

4 結(jié)束語

本文提出了一種逃逸均值簡化粒子群優(yōu)化算法，該算法在簡化粒子群優(yōu)化算法的基礎(chǔ)上加入均值搜索策略和逃逸策略。均值搜索策略通過個體最優(yōu)解和全體最優(yōu)解的線性組合引導(dǎo)粒子位置更新，可擴大搜索的區(qū)域范圍，提高算法的全局勘探能力。逃逸策略使進化停滯的粒子嘗試從其它解空間中繼續(xù)搜尋全局最優(yōu)解，增大粒子種群多樣性，有助于跳出局部最優(yōu)解，使算法更有可能搜尋到全局最優(yōu)解。最后，將改進算法應(yīng)用于5個標準測試函數(shù)中，并與其它改進粒子群優(yōu)化算法進行仿真對照實驗，結(jié)果表明，本文改進算法全局搜索能力更強、穩(wěn)定性更高，在相同目標收斂精度下所需進化次數(shù)更少，收斂速度更快。