基于多種群子空間學習的粒子群優化算法?

李奕銘 張紅飛 程 琳 王 劼

（安徽電氣工程職業技術學院 合肥 230022）

1 引言

粒子群優化（Particle Swarm Optimization，PSO）算法［1～2］是由Kennedy和 Eberhart模擬鳥群、魚群等聚集生物的捕食行為而提出的一種群體智能優化算法。該算法原理簡單、參數少、收斂速度快等優點，一經提出就得到大地測量［3］、函數優化［4］、模式識別［5］等眾多領域的廣泛應用。

自傳統PSO算法提出至今，研究者為了不斷地提高傳統PSO算法的性能，進行了大量的改進。Liang等通過改變傳統PSO算法的拓撲結構，采用動態的鄰域拓撲結構，提出了綜合學習粒子群優化算法（Comprehensive learning particle swarm optimizer for global optimization of multi-modal function，CLPSO）［6］；Zhan等將種群的進化過程劃分為勘探、開采、收斂和跳出四個步驟，在算法進化過程中自適應調整慣性權重等相關參數，并對算法采用精英高斯學習策略，在此基礎上提出了自適應子空間高斯學習的粒子群優化算法（Particle swarm optimization based on adaptive subspace Gaussian learning，APSO）［7］。文獻［8］結合PSO算法和人工蜂群算法（Artificial Bee Colony，ABC）算法，種群分為PSO子群和ABC子群，且全局最優粒子作為二個子群的引導粒子之一。伍大清等對種群不同的進化狀態采用不同的變異策略，算法能夠針對不同的復雜問題自適應地采用相應的學習策略，在此基礎上提出基于混合策略自適應學習的粒子群優化算法（Improved Parallel Particle Swarm Optimization algorithm with Hybrid strategy and self-adaptive Learning，HLPSO）［10］。朱德剛等通過對粒子個體最優位置進行高斯擾動，提高算法的收斂速度和精度，提出一種基于高斯擾動的粒子群優化算法（Particle swarm optimization algorithm based on Gaussian disturbance，GDPSO）［11］。

上述算法針對PSO的進化狀態、變異策略、算法融合等方面進行改進，本文提出一種基于多種群子空間學習的粒子群優化算法（MSPSO）。通過對粒子進行分群，增加子群最優粒子和混合粒子，增強種群多樣性。當粒子進化后期進入同質化，整個種群連續未更新的代數達到算法設置的閾值，對所有子群隨機選擇相應的維度進行高斯擾動，增強了子群最優粒子逃離局部最優的能力。

2 MSPSO算法

MSPSO算法將種群分為M個種群，每個種群有N個粒子，粒子i(i=1，2，…，i，…N)在標準粒子群進化公式基礎上，在“自我認知”部分新增混合粒子 pm，d和子群最優粒子 pg，d作為引導粒子，混合粒子 pm，d的每一個維度是隨機取自本種群的某個粒子的當前歷史最優位置的對應維度，具體的進化模式如下所示：

其中k=rand(1，2，…，i，…N)，t=(1，2，…，i，…D)，混合粒子 pm，d的生成原理如圖（1）所示：

圖1 混合粒子 pm，d產生原理

隨著種群進化到后期，種群中的所有粒子的同質化比較嚴重，種群易陷入到局部最優。為了解決同質化問題，MSPSO算法在種群進化過程中，判斷種群全局最優位置是否連續H代沒有更新，自適應對種群采取子空間學習策略。

定義1：子空間學習策略（Subspace Learning Strategy，SLS）［12］。假設在 D 維問題空間，粒子 i的位置為yij，…，yib)，其中 1≤j≤D ，1≤b≤D ，且 yij∈Xi，則稱Yi是粒子 Xi的b維子空間。

MSPSO算法的子空間學習策略是針對分群的子群最優粒子 pg，d進行子空間學習，該策略在粒子 pg，d大多數維度保持不變的情況下，在D維問題空間中隨機選擇Q（Q≤D）個維度，并在該Q個維度上加上一個高斯隨機數，得到一個全新的粒子P，再比較粒子P和 pg，d的適應度，保留最優適應度粒子作為當前子群最優粒子。設P=pgd，D為問題的維度，第 j(j∈D)維空間搜索范圍為則子群最優粒子P第 j維上的子空間學習策略可定義為

其中，μ是高斯隨機數的均值，σ2是高斯隨機數的方差，r為（0，1）區間服從均勻分布的隨機數，j是在D維空間中隨機選取的一個維度。

算法的具體步驟：Step 1初始化所有的粒子，設置相關的參數。Step 2評價和計算每個粒子的適應度函數值。Step 3計算當前子群的粒子的當前最優位置 pid、混合粒子 pmd位置、子群最優位置pgd和全局最優位置 pGd。Step 4將粒子按照式（1）、（2）和（3）進行更新速度和位置。Step 5 進化過程中計算種群全局最優位置 pGd連續未更新的迭代數ε，若ε＞H，則對子群最優粒子 pgd進行SLS學習策略。Step 6檢驗是否滿足終止條件，若滿足，則停止迭代，輸出全局最優粒子位置 pGd及其對應的適應度值，并轉到Step 3，否則轉到Step 2。

3 仿真實驗

3.1 基準測試函數

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

表1 8個Benchmark函數

3.2 算法的參數設置

子群個數M=4，每個子群的規模N=5，評估次數T_Fes=200000，學習因子c3=1.2 ，c4=0.8 ，慣性權重表示當前的迭代次數，iterNum表示總的迭代次數，均值 μ=0，方差，j表示當前子群最優粒子的第 j維。

3.3 低維仿真實驗結果

表2中的Mean、Std.Dev表示在30次獨立運行和20萬次評估次數下算法的平均最優適應值及標準差，標準差反映了算法的穩定性。

觀察表2可知，MSPSO算法相比較其他5種知名算法，本文算法在單峰函數和多峰函數上均表現良好，特別在單峰函數 f1和多峰函數 f5、f6和 f8上優勢明顯，達到最優值0。

3.4 高維仿真實驗結果

為了驗證MSPSO算法的優越性，選擇PSO算法和CLPSO算法進行對比測試。粒子個數為20，評估次數為D*5000次，D為函數維數。表3表示算法30次獨立運行后的平均值。

表2 幾種優化算法30維實驗對比結果

表3 改進算法的測試結果

由表3可知，通過對比MSPSO算法在100維和200維數上的收斂結果，隨著測試函數的維度的增加，問題優化難度的額增加，MSPSO算法的性能依然表現優勢明顯，算法穩定性很好。如在Rosenbrock函數問題上，100維本文算法收斂精度稍遜于CLPSO算法，但隨著維度增長到200維，MSPSO算法在此函數上的表現優于CLPSO算法。

4 結語

本文為了提高標準PSO算法的性能，提出一種基于多種群子空間學習的粒子群優化算法（MSPSO）。通過將種群劃分為若干個子群，并引入分群最優粒子和混合粒子，自適應對子群最優粒子進行子空間學習，幫助算法逃離局部最優位置。仿真實驗表明，通過對30維、100維、200維測試函的測試，MSPSO算法在相同的評估次數的情況下相比較其它幾種算法，收斂速度更快，精度更高。