融合多種策略的改進粒子群算法①

胡 佳

(中國市政工程中南設計研究總院有限公司,武漢 430010)

粒子群優化算法(Particle Swarm Optimization,PSO)是由Kennedy和Eberhart[1]提出的模擬鳥群覓食行為的一種群體協作隨機優化方法.PSO 算法中每個粒子都代表一個問題的候選解,通過粒子個體的簡單行為及群體內的信息交互實現問題求解的智能性.其概念簡單、實現容易、魯棒性強、優化性能好,常用于解決多峰值、非線性等問題,并在函數優化[2]、圖像處理[3]、系統辨識[4]、神經網絡[5]、有限元模型修正[6]等工程和科學領域得到廣泛應用.

雖然PSO 算法優化性能較好,但也存在早熟收斂、容易陷入局部極值、迭代后期收斂速度慢等問題.對此,國內外研究學者從調整算法自身參數、改變粒子學習模式、結合其他優化算法等方向提出諸多改進的方法.吳靜等人[7]通過動態調整慣性權重,提高了算法收斂速度及穩定性.張繼榮等人[8]提出一種慣性權重余弦調整的PSO 算法,提高了算法的精度.李龍澍等人[9]為平衡粒子的搜索行為提出了一種新的自適應慣性權重混沌PSO 算法,提高算法全局探索能力.譚陽等人[10]改變粒子學習模式,將PSO中指導粒子群進化的全局最優解擴展為由多個精英粒子組成的精英子群,提高了算法跳出局部極值的能力.Liang 等人[11]提出了一種綜合學習PSO 算法,在多峰函數上具有較好的優化效果.Jiang 等人[12]將遺傳算法中雜交算子引入到PSO 算法中,有效提高了算法的收斂性.Xia 等人[13]在PSO 算法中引入變異算子對人行橋進行模型修正,算法收斂速度和精度得到提高,得到令人滿意的修正結果.劉波等人[14]提出了一種混合模擬退火算法的改進PSO 算法,提高了算法收斂到全局最優解的速度和精度.張庭場等人[15]提出一種融合裂變和變異操作的分合群PSO 算法,提高了算法局部收斂能力.這些改進算法大都要么提高了算法的收斂速度和精度,即提高算法局部挖掘能力,要么增強算法跳出局部極值的能力,即提高算法全局探索能力,很難同時兼顧兩者.基于以上研究,為有效地兼顧了全局探索與局部挖掘能力,提出了一種融合多種策略的改進粒子群算法(Improved Particle Swarm Optimization Algorithm,IPSO).實驗結果表明,IPSO 同其他PSO 算法相比,收斂速度快、求解精度高且容易跳出局部最優解.

1 基本PSO 算法

PSO 算法是一種基于群智能的隨機搜索算法,源于對鳥群捕食行為的研究.PSO 算法由一群粒子組成,每個粒子可視為D 維搜索空間中的一個搜索個體,具有自身的位置和速度,并且能夠保留迄今為止所找到的最優位置以及所有粒子目前找到的全局最優位置.算法迭代過程中,每個粒子根據個體最優位置和全局最優位置來更新自己的速度和位置,通過目標函數適應度值來評價粒子更新的位置是否更優,從而不斷進化來獲得新的個體最優和全局最優位置.在標準PSO 算法中,粒子迭代更新公式如下:

式中,xti表示第t次迭代第i個粒子的位置,vti表示第t次迭代第i個粒子的速度,表示第t+1次迭代粒子的速度,表示第t+1次 迭代粒子的位置,pti表示第i個粒子搜索至第t代時歷史最優位置,即個體最優,ptg表示搜索至第t代時整個種群歷史最優位置,即全局最優,ω是慣性權重,決定前一時刻的速度對下次移動的影響,c1、c2為學習因子,通常取2,r1、r2為[0,1]內隨機數,代表擾動因子.

慣性權重 ω對平衡算法的收斂速度和全局搜索能力有著重要的作用.ω取值大有利于全局探索,并增加種群的多樣性,而較小的ω則可以提高算法的局部挖掘能力,加快收斂速度.為提高算法的前期全局探索能力和后期局部挖掘能力,本文采用常用的線性遞減權重策略[2],如式(3)所示:

其中,t為當前迭代次數,Gmax為最大迭代次數,ωmax為初始慣性權重,通常取0.9,ωmin為最大迭代次數時的慣性權重,通常取0.4.

粒子的飛行速度 v影響粒子位置更新的步長.最大飛行速度vmax一般取變量可行域的10%～20%.迭代過程中,粒子的飛行速度將被約束在[?vmax,vmax]的范圍內.

2 改進粒子群算法

本文融合了多種策略對基本PSO 進行改進.首先,受達爾文 “優勝劣汰、適者生存”生物進化思想[16]的啟發,對種群粒子進行選擇,適應度值小的優良種群被保留,其它粒子則被淘汰,具體實施中采取了分組策略和精英策略.按適應度值從小到大排序將種群分為優解組和劣解組,優解組進行遺傳交叉操作,劣解組進行變異操作;然后將經過交叉變異后的種群和當前迭代次數下的初始種群按適應度值從小到大進行排序,選出前一半粒子作為更新種群.其次,采取改進粒子學習模式的策略,充分利用了群體信息,保證了種群的多樣性,提高了算法全局探索的能力.最后,采取了控制概率的策略,通過引入決策數P,控制進入交叉變異等操作的概率,使算法在迭代初期小概率執行交叉變異等操作,盡量增加種群多樣性,保證算法的全局探索的能力;隨迭代次數的增加,進入交叉變異等操作的概率逐漸增大,迭代后期的收斂速度顯著加快,算法的局部挖掘能力得到增強.通過多種策略的融合,IPSO 算法能有效兼顧全局探索和局部挖掘能力,具有收斂速度快、求解精度高、避開局部最優解的優點.

2.1 分組策略

根據目標函數的適應度值對種群進行分組.首先生成包含N個粒子的初始種群,計算種群內所有粒子目標函數的適應度值fit(xi)并排序,根據排序結果選擇適應度值小的前一半粒子作為優解組,其他粒子作為劣解組,優解組粒子進行交叉操作,產生新的優良子代種群,如式(4)所示:

劣解組進行變異操作,通過變異生成優良基因,充分利用每個粒子信息,如式(5)所示:

2.2 精英策略

2.3 改進粒子學習模式

個體除總結自身的實踐經驗和向最優個體學習外,也學習其他優秀同伴的行為,尤其在進化初期,這種行為在個體的學習中應處于主導地位.為充分利用群體信息,從排序后的種群中選出前1/4 粒子,以這些粒子的均值代替個體最優指導粒子搜索,以保證種群的多樣性.對基本PSO 算法中的個體極值 pt按式(6)改進:

其中,m=N/4 (取整),pt1,pt2,···,ptm為適應度值從小到大排序的前1/4 粒子對應的個體極值,改進后的速度更新公式為:

2.4 概率控制

引入一個隨機決策數P,P是以迭代次數t為變量構建的函數,在迭代初期取大值,在迭代后期取小值,如式(8)所示:

若rand(0,1)≥P,則進行交叉變異等操作,否則不進行.

2.5 算法流程

對IPSO 算法流程描述如下,圖1給出了IPSO 算法流程圖.

圖1 IPSO 算法流程圖

Step 1.設置算法參數;

Step 2.隨機初始化種群;

Step 3.計算每個粒子適應度值;

Step 4.判斷是否進入交叉變異操作,若rand(0,1)≥P,進入Step 5,否則跳至Step 7;

Step 5.根據適應度值按升序排列粒子,前50%個粒子被定義為優解組,其余為劣解組,優解組進行交叉操作,劣解組進行變異操作,產生新的種群;

Step 6.將經過交叉變異后新產生的種群與當前迭代次數下的初始種群合并形成擴大種群,按適應度值升序排列,選出前一半粒子作為精英種群用于更新迭代;

Step 7.按式(6)更新個體最優,更新全局最優;

Step 8.更新粒子位置和速度;

Step 9.判斷是否滿足迭代中止標準,若迭代次數達到最大迭代次數Gmax,算法停止;否則跳至Step 3.

3 算法仿真測試

3.1 實驗環境及參數設置

實驗環境為:Matlab R2014b,CPU為i7-6500U@2.5 GHz,選取基本PSO[1],BreedPSO[12],SimuAPSO[14]三種算法與本文提出的IPSO 算法進行比較.算法參數的設置同原文獻相同,對于BreedPSO,雜交概率取0.9,雜交池的大小取0.2;對于SimuAPSO,退火常數取0.5.各優化方法共有參數均保持一致,種群規模取400,最大迭代次數為200,學習因子均取2.

3.2 測試函數

從GEATbx中選取4個標準測試函數,測試函數維數取10 維,分別對IPSO 算法和其他改進PSO 算法性能進行了比較.其中f1、f2為單峰函數,f1用于檢驗算法的收斂速度和精度;f2最優位置是在一個狹長的,拋物線形的扁平山谷內,可認為擁有無數個局部極值,f3、f4為多峰函數,其二維函數圖像如圖2、圖3所示,其局部極值的個數隨維數的增加成幾何級增加,f2、f3、f4主要用于檢驗算法跳出局部極值,全局搜索的能力,同時也能檢驗其收斂速度和精度.f1、f3、f4函數的全局最優均為:當xi=0,(i=1:n),f(x)=0;f2的全局最優為:當xi=1,(i=1:n),f(x)=0.為消除隨機性對算法性能帶來的影響,對每個測試函數采用不同PSO算法進行100 次獨立運算,得到各測試函數迭代完成后的適應度值,以100 次適應度值的均值和方差作為評價指標,均值能最直觀反映優化結果的優劣,檢驗算法的收斂速度和精度,而方差從不確定性量化的角度反映優化結果的穩定性.f1為單峰球函數,xi越接近于0,適應度值越小,優化速度及精度越高,設置成功率來評判優化性能,表1顯示了不同優化方法對f1優化的結果.函數f2、f3、f4全局最優附近含有較多局部峰值,若最終的適應度值小于10?5,則認為成功搜索到全局最優解.各種不同優化算法對測試函數f2、f3、f4優化結果如表2所示.圖(4)–圖(7)分別為幾種不同PSO算法在對函數f1～f4尋優時的平均適應度值收斂曲線,能更全面直觀展示算法的迭代優化過程.

表1 測試函數f1 優化的結果

圖2 Ackley’s Path 二維函數圖像

圖3 Griewank 二維函數圖像

圖4 f1 平均適應度值的對數迭代曲線

圖5 f2 平均適應度值的對數迭代曲線

圖6 f3 平均適應度值的迭代曲線

圖7 f4 平均適應度值的迭代曲線

(1)Sphere 球函數:x∈[?5.12,5.12]

(2)Rosenbrock 函數:x∈[?2.048,2.048]

(3)Ackley’s Path 函數:x∈[?1.5,1.5]

(4)Griewank 函數:x∈[?8,8]

3.3 仿真結果分析

從表1和表2可知,IPSO 算法分別對4個測試函數進行100 次計算得到的適應度值均值和方差均小于其他PSO 算法,表明IPSO 算法收斂速度快,搜索精度高,穩定性好.對于測試函數f1,IPSO 算法計算得到適應度值均值為3.03E–25,相比其他PSO 算法,搜索精度顯著提高,在最佳目標成功率上,100%達到10?20數量級,優化到10?40以下成功率達到45%,遠遠優于其他PSO 算法.另外,在相同條件下運行時間,IPSO 算法要比基本PSO 耗時長,與SimuAPSO 相當,比BreedPSO耗時短,從取得的優化效果來看,增加的時間完全可以接受.

圖4–圖7中平均適應度值收斂曲線顯示了IPSO算法下降速度快,達到穩定時迭代次數少,穩定時平均適應度值遠低于其他PSO 算法,進一步證實IPSO 算法具有收斂速度快、精度高的特點.從表2可知,IPSO算法在提高收斂速度和精度的同時,跳出局部極值成功搜索到全局最優解的能力顯著提升,對于測試函數f2,搜索到全局最優 (1,…,1)附近位置,IPSO 算法成功率達到56%,而其他PSO 算法均小于30%,對于測試函數f3,搜索到全局最優 (0,…,0)附近位置,IPSO 算法成功率高達96%,而其他PSO 算法均小于30%.測試函數f4對比于f3,其局部極值與全局最優位置對應的適應度值相差很小且局部極值數量龐大,因此很難找到全局最優位置,IPSO 算法找到最優解(0,…,0)位置的成功率為90%,而其他PSO 算法均很難找到最優解位置.

4 結論

本文針對PSO 算法容易陷入局部極值及進化后期收斂速度慢、精度低等缺點,提出了一種融合多種策略的改進粒子群算法(IPSO).該算法采取了分組控制、精英選擇、改變學習模式、引入概率等策略,通過實驗仿真結果證明了IPSO 算法同其他PSO 算法相比,收斂速度快、求解精度高且容易跳出局部最優解.IPSO 算法的全局探索和局部挖掘能力均得到明顯提升,較為有效地兼顧了全局與局部尋優.