融合多種策略的改進(jìn)粒子群算法①

胡 佳

(中國(guó)市政工程中南設(shè)計(jì)研究總院有限公司,武漢 430010)

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

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

1 基本PSO 算法

PSO 算法是一種基于群智能的隨機(jī)搜索算法,源于對(duì)鳥(niǎo)群捕食行為的研究.PSO 算法由一群粒子組成,每個(gè)粒子可視為D 維搜索空間中的一個(gè)搜索個(gè)體,具有自身的位置和速度,并且能夠保留迄今為止所找到的最優(yōu)位置以及所有粒子目前找到的全局最優(yōu)位置.算法迭代過(guò)程中,每個(gè)粒子根據(jù)個(gè)體最優(yōu)位置和全局最優(yōu)位置來(lái)更新自己的速度和位置,通過(guò)目標(biāo)函數(shù)適應(yīng)度值來(lái)評(píng)價(jià)粒子更新的位置是否更優(yōu),從而不斷進(jìn)化來(lái)獲得新的個(gè)體最優(yōu)和全局最優(yōu)位置.在標(biāo)準(zhǔn)PSO 算法中,粒子迭代更新公式如下:

式中,xti表示第t次迭代第i個(gè)粒子的位置,vti表示第t次迭代第i個(gè)粒子的速度,表示第t+1次迭代粒子的速度,表示第t+1次 迭代粒子的位置,pti表示第i個(gè)粒子搜索至第t代時(shí)歷史最優(yōu)位置,即個(gè)體最優(yōu),ptg表示搜索至第t代時(shí)整個(gè)種群歷史最優(yōu)位置,即全局最優(yōu),ω是慣性權(quán)重,決定前一時(shí)刻的速度對(duì)下次移動(dòng)的影響,c1、c2為學(xué)習(xí)因子,通常取2,r1、r2為[0,1]內(nèi)隨機(jī)數(shù),代表擾動(dòng)因子.

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

其中,t為當(dāng)前迭代次數(shù),Gmax為最大迭代次數(shù),ωmax為初始慣性權(quán)重,通常取0.9,ωmin為最大迭代次數(shù)時(shí)的慣性權(quán)重,通常取0.4.

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

2 改進(jìn)粒子群算法

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

2.1 分組策略

根據(jù)目標(biāo)函數(shù)的適應(yīng)度值對(duì)種群進(jìn)行分組.首先生成包含N個(gè)粒子的初始種群,計(jì)算種群內(nèi)所有粒子目標(biāo)函數(shù)的適應(yīng)度值fit(xi)并排序,根據(jù)排序結(jié)果選擇適應(yīng)度值小的前一半粒子作為優(yōu)解組,其他粒子作為劣解組,優(yōu)解組粒子進(jìn)行交叉操作,產(chǎn)生新的優(yōu)良子代種群,如式(4)所示:

劣解組進(jìn)行變異操作,通過(guò)變異生成優(yōu)良基因,充分利用每個(gè)粒子信息,如式(5)所示:

2.2 精英策略

2.3 改進(jìn)粒子學(xué)習(xí)模式

個(gè)體除總結(jié)自身的實(shí)踐經(jīng)驗(yàn)和向最優(yōu)個(gè)體學(xué)習(xí)外,也學(xué)習(xí)其他優(yōu)秀同伴的行為,尤其在進(jìn)化初期,這種行為在個(gè)體的學(xué)習(xí)中應(yīng)處于主導(dǎo)地位.為充分利用群體信息,從排序后的種群中選出前1/4 粒子,以這些粒子的均值代替?zhèn)€體最優(yōu)指導(dǎo)粒子搜索,以保證種群的多樣性.對(duì)基本PSO 算法中的個(gè)體極值 pt按式(6)改進(jìn):

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

2.4 概率控制

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

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

2.5 算法流程

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

圖1 IPSO 算法流程圖

Step 1.設(shè)置算法參數(shù);

Step 2.隨機(jī)初始化種群;

Step 3.計(jì)算每個(gè)粒子適應(yīng)度值;

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

Step 5.根據(jù)適應(yīng)度值按升序排列粒子,前50%個(gè)粒子被定義為優(yōu)解組,其余為劣解組,優(yōu)解組進(jìn)行交叉操作,劣解組進(jìn)行變異操作,產(chǎn)生新的種群;

Step 6.將經(jīng)過(guò)交叉變異后新產(chǎn)生的種群與當(dāng)前迭代次數(shù)下的初始種群合并形成擴(kuò)大種群,按適應(yīng)度值升序排列,選出前一半粒子作為精英種群用于更新迭代;

Step 7.按式(6)更新個(gè)體最優(yōu),更新全局最優(yōu);

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

Step 9.判斷是否滿(mǎn)足迭代中止標(biāo)準(zhǔn),若迭代次數(shù)達(dá)到最大迭代次數(shù)Gmax,算法停止;否則跳至Step 3.

3 算法仿真測(cè)試

3.1 實(shí)驗(yàn)環(huán)境及參數(shù)設(shè)置

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

3.2 測(cè)試函數(shù)

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

表1 測(cè)試函數(shù)f1 優(yōu)化的結(jié)果

圖2 Ackley’s Path 二維函數(shù)圖像

圖3 Griewank 二維函數(shù)圖像

圖4 f1 平均適應(yīng)度值的對(duì)數(shù)迭代曲線

圖5 f2 平均適應(yīng)度值的對(duì)數(shù)迭代曲線

圖6 f3 平均適應(yīng)度值的迭代曲線

圖7 f4 平均適應(yīng)度值的迭代曲線

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

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

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

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

3.3 仿真結(jié)果分析

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

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

4 結(jié)論

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