一種多階段多子群粒子群算法的改進(jìn)

一種多階段多子群粒子群算法的改進(jìn)

1pso相關(guān)研究干預(yù)粒子群優(yōu)化算法（pso）是一種先進(jìn)的算法。這是由美國的心理學(xué)家詹姆斯金乃（jameskney）和電氣工程設(shè)計師斯科特韋勒（scottweber）提出的。這源于鳥群捕獲行為。PSO同遺傳算法類似,是一種基于迭代的優(yōu)化工具。系統(tǒng)初始化為一組隨機解,通過迭代搜尋最優(yōu)值。目前已廣泛應(yīng)用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、數(shù)據(jù)挖掘、模糊系統(tǒng)控制以及其他應(yīng)用領(lǐng)域。在生產(chǎn)和生活實踐中通過建模等數(shù)學(xué)手段分析,可將大量的實際問題最終歸結(jié)到函數(shù)優(yōu)化問題,但通常這些函數(shù)表現(xiàn)出高維、大規(guī)模、非線性、不可微等特性,是典型的復(fù)雜函數(shù),求解實際問題的過程往往可轉(zhuǎn)化為求取這些復(fù)雜函數(shù)的優(yōu)化解,但由于這些函數(shù)通常存在大量的局部最優(yōu)點,導(dǎo)致了傳統(tǒng)的優(yōu)化算法雖具有收斂快、精度好等優(yōu)勢,卻容易陷入局部最優(yōu)點,無法得到最優(yōu)化結(jié)果。2標(biāo)準(zhǔn)子群算法的標(biāo)準(zhǔn)版本首先粒子群算法初始化為一群隨機粒子(隨機解),然后通過迭代找到最優(yōu)解。在每一次迭代中,粒子通過跟蹤兩個“極值”來更新自己。一個是粒子本身所找到的最優(yōu)解叫做個體極值pbest,另一個極值是整個種群目前找到的最優(yōu)解,這個極值是全局極值gbest。在找到這兩個最優(yōu)值時,起初的粒子群算法是不帶慣性權(quán)重的,人們將其稱為PSO算法的初始版本。目前,關(guān)于PSO算法的研究都是在YuhuiShi提出的帶慣性權(quán)重的粒子群算法的標(biāo)準(zhǔn)版本基礎(chǔ)上進(jìn)行的,所以直接給出標(biāo)準(zhǔn)粒子群算法公式,每個粒子根據(jù)如下的公式來更新自己的速度和新的位置:其中:vt是粒子的速度向量;xt是當(dāng)前粒子的位置;pbestt表示粒子本身所找到的最優(yōu)解的位置;gbestt表示整個種群目前找到的最優(yōu)解的位置;c0、c1、c2表示群體認(rèn)知系數(shù),c0一般取介于(0,1)之間的隨機數(shù),c1、c2取(0,2)之間的隨機數(shù);r1,r2∈為均勻分布的隨機數(shù);vt+1是vt、pbestt-xt和gbestt-xt矢量的和。每一維粒子的速度都會被限制在一個最大速度vmax(vmax>0)內(nèi),如果某一維更新后的速度超過用戶設(shè)定的vmax,那么這一維的速度就被限定為vmax,即若vt>vmax時,vt=vmax或vt<-vmax時,vt=-vmax。3把免疫克隆原理引入pso算法中為了改進(jìn)粒子群算法過早收斂的缺點,文獻(xiàn)通過采用梯形規(guī)律動態(tài)調(diào)整粒子群的規(guī)模,文獻(xiàn)提出了把免疫克隆原理引入PSO算法中。這些方法歸根到底均是提升整個粒子群尋優(yōu)過程中粒子間多樣性差異(diversity),該文算法則著眼于粒子群算法的記憶性,充分利用搜索過程中得到的信息,提高其搜索到全局最優(yōu)解的概率。3.1基本粒子群算法在基本粒子群算法中,根據(jù)直接相互作用的微粒群定義可構(gòu)造粒子群算法的兩種不同版本,也就是說,可以通過定義全局最好微粒(位置)或局部最好微粒(位置)構(gòu)造具有不同社會行為的粒子群算法。(1)全局最好模型基本粒子群算法就是該模型的具體實現(xiàn),在該模型中,整個算法以當(dāng)前的全局最好解為吸引子,將所有微粒拉向它,使所有微粒將最終收斂于該位置。這樣,如果在進(jìn)化過程中,該最好解得不到有效更新,則微粒群將出現(xiàn)類似于遺傳算法中的早熟現(xiàn)象。全局最好模型是以犧牲算法的魯棒性為代價提高算法的收斂速度。(2)局部最好模型為了防止全局最好模型可能出現(xiàn)的早熟現(xiàn)象,局部最好模型采用多吸引子代替全局最好模型中的單一吸引子。首先將整個微粒群分解為若干個子群,在每一子群中保留其局部最好微粒,稱之為局部最好位置或鄰域最好位置。子群中的微粒與其在搜索空間域內(nèi)所處的位置無關(guān),僅依賴微粒的索引數(shù)或微粒的編碼。這樣一方面避免了微粒間的聚類分析,節(jié)省了計算時間,另一方面能夠加快更好解信息在整個群體間的擴散。局部最好模型的收斂速度低于全局最好模型,但收斂的全局最優(yōu)性明顯改善。此外,Boyd和Richerson在研究人類的決策過程中提出了個體學(xué)習(xí)和文化傳遞的概念,他們認(rèn)為人們的學(xué)習(xí)過程就是利用自身經(jīng)驗和他人經(jīng)驗的過程,人們根據(jù)這兩種信息做出自己行動的決策,該思想成為粒子群算法的另一基本概念。粒子群算法搜索最優(yōu)解的過程實質(zhì)上是粒子之間相互學(xué)習(xí)共同尋優(yōu)的過程,基于這種思想,人們嘗試用不同方式將粒子分為多個子群,以便更加充分地利用粒子在探索過程中積累的信息?；谝陨蟽牲c理論,且考慮到人們在日常學(xué)習(xí)的過程中,經(jīng)常采用分組學(xué)習(xí)、階段性總結(jié)的學(xué)習(xí)模式,往往能取得較好的學(xué)習(xí)效果。在深入分析粒子群算法尋優(yōu)過程的基礎(chǔ)上該文對基本粒子群算法作如下改進(jìn),首先通過多子群之間階段性的重新分組強化不同群體之間的信息交流,其次通過分階段搜索模式的轉(zhuǎn)變將全局最好模型收斂的快速性和局部最好模型收斂的全局最優(yōu)性進(jìn)行折中,即算法開始階段粒子分為多個子群,每個子群互不干擾,獨立進(jìn)化,經(jīng)過固定代數(shù)T1后,所有子群進(jìn)行合并統(tǒng)一進(jìn)化固定代數(shù)T2,然后重新分組。循環(huán)上述分組、子群進(jìn)化、統(tǒng)一進(jìn)化的過程,直到滿足結(jié)束條件為止。顯然,多子群的進(jìn)化較單一的進(jìn)化有更強的全局搜索能力,子群之間階段性的重新分組增強了信息交流,提高算法搜索到全局最優(yōu)解的概率。同時,如果處于子群進(jìn)化階段的粒子陷入局部最優(yōu)解,全局優(yōu)化模式的轉(zhuǎn)入將對其進(jìn)行修正,跳出局部極值而繼續(xù)尋優(yōu)過程,所以搜索模式的轉(zhuǎn)換過程實際上也增加了粒子跳出局部極值的能力,而且在算法后期全局搜索模式可以防止由于子群劃分帶來的兵力不足問題,進(jìn)一步提高精細(xì)搜索的能力。算法還可以根據(jù)不同問題的復(fù)雜程度調(diào)整兩種模型的相對強度,增加了算法應(yīng)用上的靈活性。3.2子群算法的改進(jìn)算法的重點是分組策略和兩個進(jìn)化代數(shù)的確定,因為算法要進(jìn)行多次分組,采用合適的分組策略將有利于各子群個體信息的充分交流。為了平衡各子群之間的實力,首先將隨機產(chǎn)生的粒子按照適應(yīng)度大小進(jìn)行排序,將其序號劃分為n/m,按行排列,取其第一列為第一個子群,依此類推。n表示粒子數(shù),m表示子群數(shù)。例如粒子群規(guī)模n=8,m=4,分組過程如下所示:算法中使用了兩個進(jìn)化代數(shù)T1、T2,當(dāng)T1為0時,該算法就是基本粒子群算法,非常容易早熟,如果T2為0,該算法是多子群之間獨立搜索和定期重新分組的過程,具有較強的探索全局極值的能力,但是是以犧牲收斂速度為代價的。明確兩個參數(shù)帶給算法的影響,根據(jù)實際問題的復(fù)雜程度選用合適的T1、T2,將能以最小的時間代價取得較優(yōu)解。例如,如果所求解的問題是單峰的就可以令T1較小,如果存在多個局部極值就可以增大T1與T2的比值,如果將兩個參數(shù)的選擇也作為一個優(yōu)化過程,將能取得更好的效果。3.3算法流程如上所述,提出了一種改進(jìn)的多子群粒子群算法,它的基本步驟如下:4模擬與分析4.1影響適應(yīng)度進(jìn)化的算法為了對MMPSO算法的性能進(jìn)行測試,選用表1中的3個測試函數(shù)并與基本粒子群算法進(jìn)行對比研究,算法的參數(shù)設(shè)置為:,子群數(shù)p=4,T1=T2=50,算法獨立運行50次,取平均值作為最終的計算結(jié)果(表2~表4),并給出種群規(guī)模為80、變量維數(shù)為30時3個函數(shù)的平均適應(yīng)度進(jìn)化情況(圖1~圖3)。為了測試參數(shù)T1、T2對算法的影響,選用Rosenbrock函數(shù)進(jìn)行測試,分別就T1=0,T2=50;T1=50,T2=100;T1=100,T2=100;T1=50,T2=50;T1=50,T2=0共5種情況進(jìn)行仿真,得到圖4所示5條曲線。4.2結(jié)果分析5搜索全局最優(yōu)解通過分析粒子群優(yōu)化算法的算法原理,利用多子群之間的信息融合,改進(jìn)了粒子群算法容易陷入局部極值的問題,同時保留了粒子群算法高效優(yōu)化的特點,針對復(fù)雜高維函數(shù)優(yōu)化問題具有更強的適應(yīng)性、魯棒性,實驗表明算法改進(jìn)是可行和有效的。由表2~表4,圖1~圖3的仿真結(jié)果可以看出,所提出的多階段多子群算法與基本粒子群算法相比收斂速度有所下降,但具有更高的收斂精度。圖4中,T1=0,T2=50時,MMPSO相當(dāng)于基本粒子群算法,從其他4條曲線與它的比較可以看出,文中對粒子群算法的改進(jìn)均取得了優(yōu)于基本粒子群算法的平均最優(yōu)解,說明MMPSO方法在一定范圍內(nèi)具有更好的搜索全局最優(yōu)解的能力。對T1=50,T2=100;T1=50,T2=50;T1=50,T2=0曲線的比較可以看出,在T1相同的情況下,隨著T2的減小,因為全局搜索模式的減弱,局部搜索模式的相對增強,算法收斂精度有所提高,收斂速度有所降低。對T1=100,T2=100與T1=50,T2=100的比較可以看出,在T2相同的情況下,隨著T1的減小,因為局部搜索模式的減弱,全局搜索模式的相對增強,算法速度提高,精度有所下降。通過對T1=50,T2=50;T1=100,T2=10