基于多種群子空間學(xué)習(xí)的粒子群優(yōu)化算法?

李奕銘 張紅飛 程 琳 王 劼

（安徽電氣工程職業(yè)技術(shù)學(xué)院 合肥 230022）

1 引言

粒子群優(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)的能力。

2 MSPSO算法

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。

3 仿真實驗

3.1 基準(zhǔn)測試函數(shù)

為了驗證MSPSO算法的性能，本文選取了FIPS［13］、HPSO-TVAC［14］、DMS-PSO［15］、CLPSO［6］和APSO［7］五種經(jīng)典的改進粒子群算法進行對比實驗，對比了幾種算法在8個經(jīng)典的測試函數(shù)上的性能。

表1 8個Benchmark函數(shù)

3.2 算法的參數(shù)設(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維。

3.3 低維仿真實驗結(jié)果

表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。

3.4 高維仿真實驗結(jié)果

為了驗證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算法。

4 結(jié)語

本文為了提高標(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ù)的情況下相比較其它幾種算法，收斂速度更快，精度更高。