李奕銘 張紅飛 程 琳 王 劼
(安徽電氣工程職業(yè)技術(shù)學(xué)院 合肥 230022)
粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法[1~2]是由Kennedy和 Eberhart模擬鳥群、魚群等聚集生物的捕食行為而提出的一種群體智能優(yōu)化算法。該算法原理簡單、參數(shù)少、收斂速度快等優(yōu)點,一經(jīng)提出就得到大地測量[3]、函數(shù)優(yōu)化[4]、模式識別[5]等眾多領(lǐng)域的廣泛應(yīng)用。
自傳統(tǒng)PSO算法提出至今,研究者為了不斷地提高傳統(tǒng)PSO算法的性能,進行了大量的改進。Liang等通過改變傳統(tǒng)PSO算法的拓撲結(jié)構(gòu),采用動態(tài)的鄰域拓撲結(jié)構(gòu),提出了綜合學(xué)習(xí)粒子群優(yōu)化算法(Comprehensive learning particle swarm optimizer for global optimization of multi-modal function,CLPSO)[6];Zhan等將種群的進化過程劃分為勘探、開采、收斂和跳出四個步驟,在算法進化過程中自適應(yīng)調(diào)整慣性權(quán)重等相關(guān)參數(shù),并對算法采用精英高斯學(xué)習(xí)策略,在此基礎(chǔ)上提出了自適應(yīng)子空間高斯學(xué)習(xí)的粒子群優(yōu)化算法(Particle swarm optimization based on adaptive subspace Gaussian learning,APSO)[7]。文獻[8]結(jié)合PSO算法和人工蜂群算法(Artificial Bee Colony,ABC)算法,種群分為PSO子群和ABC子群,且全局最優(yōu)粒子作為二個子群的引導(dǎo)粒子之一。伍大清等對種群不同的進化狀態(tài)采用不同的變異策略,算法能夠針對不同的復(fù)雜問題自適應(yīng)地采用相應(yīng)的學(xué)習(xí)策略,在此基礎(chǔ)上提出基于混合策略自適應(yīng)學(xué)習(xí)的粒子群優(yōu)化算法(Improved Parallel Particle Swarm Optimization algorithm with Hybrid strategy and self-adaptive Learning,HLPSO)[10]。朱德剛等通過對粒子個體最優(yōu)位置進行高斯擾動,提高算法的收斂速度和精度,提出一種基于高斯擾動的粒子群優(yōu)化算法(Particle swarm optimization algorithm based on Gaussian disturbance,GDPSO)[11]。
上述算法針對PSO的進化狀態(tài)、變異策略、算法融合等方面進行改進,本文提出一種基于多種群子空間學(xué)習(xí)的粒子群優(yōu)化算法(MSPSO)。通過對粒子進行分群,增加子群最優(yōu)粒子和混合粒子,增強種群多樣性。當(dāng)粒子進化后期進入同質(zhì)化,整個種群連續(xù)未更新的代數(shù)達到算法設(shè)置的閾值,對所有子群隨機選擇相應(yīng)的維度進行高斯擾動,增強了子群最優(yōu)粒子逃離局部最優(yōu)的能力。
MSPSO算法將種群分為M個種群,每個種群有N個粒子,粒子i(i=1,2,…,i,…N)在標(biāo)準(zhǔn)粒子群進化公式基礎(chǔ)上,在“自我認知”部分新增混合粒子 pm,d和子群最優(yōu)粒子 pg,d作為引導(dǎo)粒子,混合粒子 pm,d的每一個維度是隨機取自本種群的某個粒子的當(dāng)前歷史最優(yōu)位置的對應(yīng)維度,具體的進化模式如下所示:
其中k=rand(1,2,…,i,…N),t=(1,2,…,i,…D),混合粒子 pm,d的生成原理如圖(1)所示:
圖1 混合粒子 pm,d產(chǎn)生原理
隨著種群進化到后期,種群中的所有粒子的同質(zhì)化比較嚴(yán)重,種群易陷入到局部最優(yōu)。為了解決同質(zhì)化問題,MSPSO算法在種群進化過程中,判斷種群全局最優(yōu)位置是否連續(xù)H代沒有更新,自適應(yīng)對種群采取子空間學(xué)習(xí)策略。
定義1:子空間學(xué)習(xí)策略(Subspace Learning Strategy,SLS)[12]。假設(shè)在 D 維問題空間,粒子 i的位置為yij,…,yib),其中 1≤j≤D ,1≤b≤D ,且 yij∈Xi,則稱Yi是粒子 Xi的b維子空間。
MSPSO算法的子空間學(xué)習(xí)策略是針對分群的子群最優(yōu)粒子 pg,d進行子空間學(xué)習(xí),該策略在粒子 pg,d大多數(shù)維度保持不變的情況下,在D維問題空間中隨機選擇Q(Q≤D)個維度,并在該Q個維度上加上一個高斯隨機數(shù),得到一個全新的粒子P,再比較粒子P和 pg,d的適應(yīng)度,保留最優(yōu)適應(yīng)度粒子作為當(dāng)前子群最優(yōu)粒子。設(shè)P=pgd,D為問題的維度,第 j(j∈D)維空間搜索范圍為則子群最優(yōu)粒子P第 j維上的子空間學(xué)習(xí)策略可定義為
其中,μ是高斯隨機數(shù)的均值,σ2是高斯隨機數(shù)的方差,r為(0,1)區(qū)間服從均勻分布的隨機數(shù),j是在D維空間中隨機選取的一個維度。
算法的具體步驟:Step 1初始化所有的粒子,設(shè)置相關(guān)的參數(shù)。Step 2評價和計算每個粒子的適應(yīng)度函數(shù)值。Step 3計算當(dāng)前子群的粒子的當(dāng)前最優(yōu)位置 pid、混合粒子 pmd位置、子群最優(yōu)位置pgd和全局最優(yōu)位置 pGd。Step 4將粒子按照式(1)、(2)和(3)進行更新速度和位置。Step 5 進化過程中計算種群全局最優(yōu)位置 pGd連續(xù)未更新的迭代數(shù)ε,若ε>H,則對子群最優(yōu)粒子 pgd進行SLS學(xué)習(xí)策略。Step 6檢驗是否滿足終止條件,若滿足,則停止迭代,輸出全局最優(yōu)粒子位置 pGd及其對應(yīng)的適應(yīng)度值,并轉(zhuǎn)到Step 3,否則轉(zhuǎn)到Step 2。
為了驗證MSPSO算法的性能,本文選取了FIPS[13]、HPSO-TVAC[14]、DMS-PSO[15]、CLPSO[6]和APSO[7]五種經(jīng)典的改進粒子群算法進行對比實驗,對比了幾種算法在8個經(jīng)典的測試函數(shù)上的性能。
表1 8個Benchmark函數(shù)
子群個數(shù)M=4,每個子群的規(guī)模N=5,評估次數(shù)T_Fes=200000,學(xué)習(xí)因子c3=1.2 ,c4=0.8 ,慣性權(quán)重表示當(dāng)前的迭代次數(shù),iterNum表示總的迭代次數(shù),均值 μ=0,方差,j表示當(dāng)前子群最優(yōu)粒子的第 j維。
表2中的Mean、Std.Dev表示在30次獨立運行和20萬次評估次數(shù)下算法的平均最優(yōu)適應(yīng)值及標(biāo)準(zhǔn)差,標(biāo)準(zhǔn)差反映了算法的穩(wěn)定性。
觀察表2可知,MSPSO算法相比較其他5種知名算法,本文算法在單峰函數(shù)和多峰函數(shù)上均表現(xiàn)良好,特別在單峰函數(shù) f1和多峰函數(shù) f5、f6和 f8上優(yōu)勢明顯,達到最優(yōu)值0。
為了驗證MSPSO算法的優(yōu)越性,選擇PSO算法和CLPSO算法進行對比測試。粒子個數(shù)為20,評估次數(shù)為D*5000次,D為函數(shù)維數(shù)。表3表示算法30次獨立運行后的平均值。
表2 幾種優(yōu)化算法30維實驗對比結(jié)果
表3 改進算法的測試結(jié)果
由表3可知,通過對比MSPSO算法在100維和200維數(shù)上的收斂結(jié)果,隨著測試函數(shù)的維度的增加,問題優(yōu)化難度的額增加,MSPSO算法的性能依然表現(xiàn)優(yōu)勢明顯,算法穩(wěn)定性很好。如在Rosenbrock函數(shù)問題上,100維本文算法收斂精度稍遜于CLPSO算法,但隨著維度增長到200維,MSPSO算法在此函數(shù)上的表現(xiàn)優(yōu)于CLPSO算法。
本文為了提高標(biāo)準(zhǔn)PSO算法的性能,提出一種基于多種群子空間學(xué)習(xí)的粒子群優(yōu)化算法(MSPSO)。通過將種群劃分為若干個子群,并引入分群最優(yōu)粒子和混合粒子,自適應(yīng)對子群最優(yōu)粒子進行子空間學(xué)習(xí),幫助算法逃離局部最優(yōu)位置。仿真實驗表明,通過對30維、100維、200維測試函的測試,MSPSO算法在相同的評估次數(shù)的情況下相比較其它幾種算法,收斂速度更快,精度更高。