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

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

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