一種多群協(xié)同進(jìn)化的粒子群優(yōu)化算法

一種多群協(xié)同進(jìn)化的粒子群優(yōu)化算法

1改進(jìn)的pso算法顆粒群優(yōu)化算法（pso）是基于團(tuán)隊(duì)智能的優(yōu)化算法。其算法易于實(shí)現(xiàn)、可調(diào)參數(shù)少、收斂速度快,已被廣泛用于函數(shù)尋優(yōu)、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、數(shù)字電路優(yōu)化和TSP問(wèn)題等優(yōu)化反演領(lǐng)域。但其存在2個(gè)弱點(diǎn):(1)和其他隨機(jī)優(yōu)化算法一樣,為了不易陷入局部極值而擴(kuò)大搜索范圍,導(dǎo)致相當(dāng)多的計(jì)算量用在差的適應(yīng)值的搜索上;(2)在整個(gè)迭代過(guò)程中,粒子群一直朝著“目前找到的全局最優(yōu)值位置”方向飛行,即使這個(gè)全局最優(yōu)值只是局部極值點(diǎn),此時(shí)微粒的速度將很快降為0而不再飛行,導(dǎo)致粒子群易收斂于局部極值點(diǎn)。針對(duì)上述缺陷,很多研究者提出了相應(yīng)的改進(jìn)方案。其中,標(biāo)志性的改進(jìn)有:對(duì)PSO算法的速度項(xiàng)引入慣性權(quán)重uf077。為了平衡收斂的全局性和收斂速度,文獻(xiàn)提出了線(xiàn)性遞減權(quán)重策略(LinearlyDecreasingWeightPSOLDI-PSO)和基于模糊系統(tǒng)的慣性因子動(dòng)態(tài)調(diào)整方法。文獻(xiàn)分析了不同的種群拓?fù)浣Y(jié)構(gòu)對(duì)PSO算法效能的影響,提出了構(gòu)造種群結(jié)構(gòu)的基本原則。在保持種群多樣性方面,文獻(xiàn)提出了分群思想,根據(jù)不同參數(shù)組對(duì)算法的影響,利用2個(gè)相同模型的分群共同進(jìn)化。為體現(xiàn)多分群多樣化的優(yōu)勢(shì),文獻(xiàn)借鑒了兩分群模型,并采用2個(gè)飛行方向不同的微粒群共同作用的方法?；谖墨I(xiàn),文獻(xiàn)增加了兩分群間交換粒子的功能,使得在遇到局部極值點(diǎn)時(shí)更易逃離,避免早熟收斂。文獻(xiàn)通過(guò)多樣性指標(biāo)和閾值來(lái)決定何時(shí)交換粒子。文獻(xiàn)則采用小生境技術(shù)和災(zāi)變?cè)慝@得自適應(yīng)分群的效果。在上述基于分群思想的算法中,文獻(xiàn)[6-7,10]采用相同的進(jìn)化模型,不能充分發(fā)揮多種群擁有多樣性粒子信息的優(yōu)勢(shì)。文獻(xiàn)雖然采用了不同進(jìn)化模型,但是第二分群采用的是“獨(dú)立認(rèn)知”模型,雖然增加了多樣性,但浪費(fèi)了過(guò)多計(jì)算量在非最優(yōu)值的搜索上,且分群間的粒子交換僅局限于最優(yōu)粒子和最差粒子間,粒子獲得新生命力的概率太小,在多峰函數(shù)尋優(yōu)時(shí)不能及時(shí)跳出局部極值點(diǎn)。本文提出了一種基于多種群多模型協(xié)同進(jìn)化的粒子群優(yōu)化算法(PSOalgorithmbasedonMulti-swarmandMultimodelcooperativeevolution,MSM-PSO)。算法建立了基于不同模型的多個(gè)分群,且分群間的信息交流擴(kuò)大到了所有粒子間,以更有效地提高種群的多樣性。同時(shí),采用動(dòng)態(tài)的自適應(yīng)慣性權(quán)重,根據(jù)適應(yīng)值的大小動(dòng)態(tài)調(diào)整慣性權(quán)重,使算法對(duì)不同優(yōu)化問(wèn)題具有更強(qiáng)的適應(yīng)性。2控制速度1,vid粒子群優(yōu)化算法是借鑒鳥(niǎo)類(lèi)尋找食物的自然現(xiàn)象提出的一類(lèi)基于種群隨機(jī)全局優(yōu)化的技術(shù)。在此算法中,待優(yōu)化問(wèn)題潛在的解對(duì)應(yīng)于搜索空間中一只鳥(niǎo)的位置,即“粒子”,每個(gè)粒子有自己的位置和速度。設(shè)搜索區(qū)域?yàn)閐維空間,粒子群的粒子數(shù)為n,則第i個(gè)粒子的位置表示為Xi=(Xi1,Xi2,…,Xid),速度表示為Vi=(Vi1,Vi2,…,Vid),i=1,2,…,n。微粒i在d維空間中的飛行速度和位置根據(jù)下式進(jìn)行調(diào)整:其中,w為慣性權(quán)重,決定前一時(shí)刻的速度對(duì)當(dāng)前時(shí)刻速度的影響大小。當(dāng)w較小時(shí),粒子探索能力弱,開(kāi)發(fā)能力強(qiáng),易陷入局部極值;當(dāng)w較大時(shí),粒子探索能力強(qiáng),開(kāi)發(fā)能力弱,易跳出局部極值,但收斂速度較慢。因此,需要調(diào)整w的大小以協(xié)調(diào)全局尋優(yōu)和局部尋優(yōu)能力,通常在迭代初期w取值較大,收斂速度較快,隨著迭代過(guò)程線(xiàn)性變小,在迭代后期使得跳出局部極值(LDI-PSO)。Pid(t)為t次搜索后第i個(gè)粒子自身找到的個(gè)體最優(yōu)值,Pgd(t)為t次搜索后得到的全局最優(yōu)值。同時(shí),群體利用記憶因子c1、c2調(diào)整粒子向Pid(t)、Pgd(t)學(xué)習(xí)的權(quán)重,并用rand()對(duì)粒子的狀態(tài)進(jìn)行隨機(jī)處理,以保持多樣性。3算法描述3.1歷史最優(yōu)位置MSM-PSO算法將粒子分成3個(gè)粒子數(shù)相同的分群:S1(基礎(chǔ)群),S2(基礎(chǔ)群),S3(綜合群)。分群中的粒子均在同一搜索空間中飛行,且在搜索過(guò)程中3個(gè)分群保持信息交流,以提高協(xié)同進(jìn)化的能力。分群間信息交流與合作模式如圖1所示。在圖1中,3個(gè)分群根據(jù)不同的更新公式各自產(chǎn)生新的速度、位置和分群歷史最優(yōu)位置。每一代更新完畢,即可從3個(gè)分群歷史最優(yōu)位置中產(chǎn)生全局歷史最優(yōu)位置。其中,綜合群S3中粒子的速度更新有賴(lài)于基礎(chǔ)群S1、S2的速度和適應(yīng)值,位置更新有賴(lài)于基礎(chǔ)群S1、S2歷史最優(yōu)位置和全局歷史最優(yōu)位置。3個(gè)分群按照如下方程迭代:基礎(chǔ)群S1、S2:綜合群S3:基礎(chǔ)群S1、S2的進(jìn)化式(3)、式(4)與標(biāo)準(zhǔn)粒子群算法相同。綜合群S3的速度公式式(5)引入了基礎(chǔ)群S1、S2的速度,其中,m=m1+m2;m1、m2是基礎(chǔ)群S1、S2當(dāng)前適應(yīng)度值,通過(guò)兩基礎(chǔ)群適應(yīng)值的大小比較,保證較好的那個(gè)基礎(chǔ)群對(duì)綜合群S3有更大的影響。位置式(6)引入了全局最優(yōu)解Pgd,其中,a1、a2、a3稱(chēng)為影響因子,且a1+a2+a3=1,本文將a1、uf0612、uf0613分別取為1/6、1/3、1/2,uf061值越大,對(duì)綜合群當(dāng)前位置的影響越大。由粒子群進(jìn)化方式可知,全局最優(yōu)解Pgd對(duì)粒子向最優(yōu)解飛行有著重要的引導(dǎo)作用,為了提高搜索能力,式(6)因此引入全局最優(yōu)解Pgd。至此,綜合群S3利用了所有分群的信息,沒(méi)有一個(gè)群是孤立存在的,這不僅提高了種群多樣性,而且增強(qiáng)了在已搜索到的全局最優(yōu)值附近的搜索性能。3.2改進(jìn)的msm-pso算法一般的,為獲得較好的算法性能,通常在搜索早期使uf077具有較大的值,以確保粒子群在較大的搜索空間范圍內(nèi)搜索,避免早熟收斂;隨著迭代次數(shù)增加,使uf077具有較小的值以確保粒子群在較小局部空間內(nèi)調(diào)節(jié)搜索,提高收斂精度。以線(xiàn)性遞減權(quán)重粒子群算法為典型(LDI-PSO),其慣性權(quán)重調(diào)節(jié)方式為:其中,uf077max和uf077min分別表示慣性權(quán)重最大值、最小值;i表示目前迭代次數(shù);max_gen表示最大迭代次數(shù)。但是PSO的實(shí)際搜索過(guò)程是非線(xiàn)性的,粒子軌跡動(dòng)態(tài)變化復(fù)雜,線(xiàn)性遞減慣性權(quán)重的方法并不能反映實(shí)際的優(yōu)化搜索過(guò)程,收斂速度及收斂精度仍不夠理想;同時(shí),慣性權(quán)重值線(xiàn)性減小的最優(yōu)斜率依賴(lài)問(wèn)題的不同而不同,不存在對(duì)所有優(yōu)化問(wèn)題普適的最優(yōu)變化斜率。因此,MSM-PSO算法提出一種根據(jù)適應(yīng)度值動(dòng)態(tài)調(diào)節(jié)慣性權(quán)重大小的方法,從而提高搜索多樣性,uf077取值由以下公式確定:其中,f、fmin和favg分別表示粒子當(dāng)前適應(yīng)度值、全局歷史最小適應(yīng)度值和全局當(dāng)前平均適應(yīng)度值。此方法將當(dāng)前信息和歷史信息充分利用到對(duì)未來(lái)的速度更新中,依賴(lài)不同的問(wèn)題做出相應(yīng)的大小調(diào)整,更好地降低了陷入局部極值的概率,其動(dòng)態(tài)調(diào)節(jié)能力如圖2所示。由圖2可知:uf077宏觀上沿著0.9-0.4的直線(xiàn)遞減,而在微觀上以此直線(xiàn)為軸上下波動(dòng),并且在早期波動(dòng)較大,全局尋優(yōu)能力增強(qiáng),后期波動(dòng)較小,局部收斂能力加強(qiáng),從而達(dá)到平衡探索能力和開(kāi)發(fā)能力的目的,避免陷入局部極值點(diǎn),同時(shí)顯著提高算法的多樣性。3.3方法三:進(jìn)行歷史最優(yōu)的自適應(yīng)組合,確保中央MSM-PSO算法步驟如下:步驟1設(shè)置粒子群數(shù)目、最大迭代次數(shù)、慣性權(quán)重最大最小值和學(xué)習(xí)因子。步驟2在滿(mǎn)足控制變量約束條件下隨機(jī)賦予粒子群中每個(gè)粒子初始速度和初始位置,計(jì)算每個(gè)粒子的適應(yīng)度值,并分別記錄個(gè)體最優(yōu)、分群最優(yōu)和全局最優(yōu)。步驟3根據(jù)式(3)、式(4)計(jì)算基礎(chǔ)群粒子的新速度、新位置,并對(duì)粒子的新速度和新位置進(jìn)行限幅處理,同時(shí)更新個(gè)體歷史最優(yōu)適應(yīng)度值、個(gè)體歷史最優(yōu)位置,更新分群歷史最優(yōu)適應(yīng)度值、分群歷史最優(yōu)位置。步驟4利用步驟3得到的基礎(chǔ)群速度、位置和個(gè)體適應(yīng)度值,根據(jù)式(5)、式(6)計(jì)算綜合群粒子的新速度、新位置,并對(duì)粒子的新速度和新位置進(jìn)行限幅處理。同時(shí)更新個(gè)體歷史最優(yōu)適應(yīng)度值、個(gè)體歷史最優(yōu)位置,更新分群歷史最優(yōu)適應(yīng)度值、分群歷史最優(yōu)位置。步驟5更新全局的歷史最優(yōu)適應(yīng)值和歷史最優(yōu)位置。步驟6判斷是否滿(mǎn)足終止條件(達(dá)到最大迭代次數(shù)),若滿(mǎn)足,則執(zhí)行步驟7;若不滿(mǎn)足,則返回執(zhí)行步驟3。步驟7搜索停止,輸出最優(yōu)位置。4實(shí)驗(yàn)與分析4.1測(cè)試函數(shù)的定義為驗(yàn)證MSM-PSO算法的性能,本文采用了6個(gè)經(jīng)典的測(cè)試函數(shù),其中,Sphere函數(shù)和Rosenbrock函數(shù)為單峰函數(shù),其余為多峰函數(shù)。各測(cè)試函數(shù)如表1所示。4.2算法性能測(cè)試在仿真實(shí)驗(yàn)中,將MSM-PSO算法和LDI-PSO算法及文獻(xiàn)的兩群微粒群優(yōu)化算法(TwoSub-swarmsPSO,TS-PSO)算法進(jìn)行對(duì)比。實(shí)驗(yàn)中最大迭代次數(shù)均為1000次,粒子總數(shù)32個(gè);LDI-PSO算法和MSM-PSO算法的慣性權(quán)重w的最大值都是0.9,最小值0.4;TS-PSO算法的慣性權(quán)重w的最大值是1.8,最小值0.02,參數(shù)N為20,C1=C2=C3=2,m1=m2=0.5;LDI-PSO算法中C1=C2=2,MSM-PSO算法中C1=1.7,C1=2.05。此處的參數(shù)設(shè)置是根據(jù)多次實(shí)驗(yàn)結(jié)果設(shè)定,不是本文的重點(diǎn),不再贅述。各優(yōu)化算法對(duì)每個(gè)函數(shù)的測(cè)試均運(yùn)行100次,測(cè)試結(jié)果取100個(gè)平均值的對(duì)數(shù)。具體測(cè)試結(jié)果見(jiàn)表2,測(cè)試指標(biāo)包括平均最優(yōu)值的對(duì)數(shù)和最優(yōu)值的方差。由表2的測(cè)試結(jié)果可知,MSM-PSO算法較LDI-PSO算法和TS-PSO算法有更好的收斂性能,最優(yōu)解的質(zhì)量有較好的改善,特別是對(duì)Ackley函數(shù),MSM-PSO算法得到的適應(yīng)值均值較LDI-PSO算法改善了近15倍。同時(shí),MSM-PSO算法所得方差更小,尋優(yōu)結(jié)果更穩(wěn)定。圖3、圖4給出了Sphere函數(shù)和Rastrigin函數(shù)這2個(gè)具有典型性的測(cè)試函數(shù)進(jìn)化曲線(xiàn)。由圖3可見(jiàn),對(duì)Sphere函數(shù),MSM-PSO算法與LDI-PSO算法、TS-PSO算法搜索走勢(shì)相似,但是MSM-PSO算法明顯有更快的收斂速度和更優(yōu)的尋優(yōu)精度,而LDI-PSO算法在750代左右的時(shí)候陷入局部極值而無(wú)法再改善。由圖4可見(jiàn),對(duì)Rastrigin函數(shù),MSM-PSO算法表現(xiàn)出明顯的快速收斂?jī)?yōu)勢(shì),且收斂結(jié)果也有較大改善。這歸功于MSM-PSO算法的慣性權(quán)重自適應(yīng)機(jī)制和多種群協(xié)同進(jìn)化機(jī)制,保持了種群的多樣性,使其不易于陷入局部極值,更易從極值點(diǎn)逃離,并繼續(xù)搜索尋優(yōu),以獲得更好的結(jié)果。針對(duì)其余測(cè)