微粒群算法速度與位置更新的穩定性分析

張成興

【摘要】微粒群算法已經成為一種高效容易實現的方法.微粒群算法根據鳥群捕食行為抽象而來，但是目前很少有文獻分析該算法在循環中改變速度和位置的穩定性.本文以基本微粒群算法為例，利用差分方程，常微分方程和線性系統控制理論對算法的更新公式進行了分析，給出了算法穩定的條件.

1.引 言

微粒群算法（Particle Swarm Optimization），利用當前個體適應度最優值和全局個體適應度最優值對更新過程施加影響，利用兩個加速因子調節種群中社會性和自身性的比例，和兩個隨機因子增大個體的多樣性.

自從1995年基本的微粒群算法提出以來，經過近20多年的發展，衍生出了很多微粒群算法的改進算法，比較著名的有帶有壓縮因子的微粒群算法（Constrict Factor Particle Swarm Optimization CFPSO），模擬退火的微粒群算法 （Simulating Annealing Particle Swarm Optimization SAPSO），混沌微粒群算法（Chaos Particle Swarm Optimization CPSO），全信息的微粒群算法 （Fully Informed Particle Swarm Optimization FIPS），綜合學習的微粒群算法 （Comprehensive Learning Particle Swarm Optimization CLSPO），自適應微粒群算法（Adaptive Particle Swarm Optimization APSO），基于文化基因進化的微粒群算法（ Particle Swarm Optimization based on Memetic Algorithm POMA）和自我學習的微粒群算法 （SelfLearning Particle Swarm Optimization SLPSO）.CFPSO利用壓縮因子代替基本PSO中的慣性權重，在Benchmark測試函數中取得了較好的精度；CPSO，SAPSO和POMA利用PSO結合其他具有一定局部搜索能力的算法來求解最優值.CLPSO采用綜合學習的機制，能夠維持種群的多樣性，使得算法不會發生早熟.APSO是典型的自適應算法，根據種群當前情況，調節慣性權重和加速因子，加快了收斂速度.SLPSO可以根據當前個體的搜索區域狀態，自主選擇適合的進化方式.

但是PSO的核心速度位置更新公式沒有發生較大的變化，所以本文通過分析PSO位置和速度的更新方式來討論算法穩定的條件.

2.穩定性分析

PSO的速度更新公式如下：

Vi（t+1）=ωVi（t）+λ1[P-Xi（t）]+λ2[G-Xi（t）].（1）

（1）為中P為當前最優個體位置，G為種群最優位置，ω是慣性權重.

Xi（t+1）=Xi（t）+Vi（t+1）.（2）

根據（1）和（2）可得：

-（λ1+λ2）Xi（t）=Vi（t+1）-ωVi（t）-λ1P-λ2G.（3）

Vi（t+2）+（λ1+λ2-ω-1）Vi（t+1）+ωVi（t）=0.（4）

根據（3）和（4）可以得到個體位置變化的方程：

Xi（t+2）=（1+ω-λ1-λ2）Xi（t+1）-ωXi（t）+λ1P+λ2G.（5）

（5）是一個典型的二階差分方程.

假設個體變化過程連續，根據（4）可以得到速度的二階常微分方程：

d2Vdt2+ln（αβ）dvdt+ln（α）ln（β）V=0.（6）

根據二階常微分方程的理論，可知α和β是φ2+（λ1+λ2+ω-1）φ+ω的兩個根.所以（5）的解的一般形式如下：

V（t）=eαt（C1sinβt+C2cosβt）.（7）

從（7）中分析可知，個體時刻的速度存在震蕩，而且α>0的情況下不收斂，需要具體分析速度更新公式中的參數.

對（4）進行Z變換，得到：

Vi（Z）=z2Vi（0）+zVi（1）+Z～（λ1+λ2-ω-1）Vi（0）z2+z（λ1+λ2-ω-1）+ω.（8）

因為λ1和λ2是常數，利用控制系統理論，得知（8）是一個線性系統，所以特征方程為（8）的分母.

利用雙線性變換，令z=μ+1μ-1，帶入（8）得到：

（λ1+λ2）μ2+（2-2ω）μ+（2ω+2-λ1-λ2）=0.（9）

利用控制理論中的Routh判據，可知系統穩定的充要條件是系數大于0.

（λ1+λ2）μ2+（2-2ω）μ+（2ω+2-λ1-λ2）=0.（9）

λ1+λ2>0

2ω+2-λ1-λ2>0

1-ω>0（10）

3.結 論

通過對PSO算法更新公式的分析，利用常微分方程和控制理論，得出算法中個體速度收斂的約束條件，得到了基本的結論.

【參考文獻】

[1]J.Kennedy and R.C.Eberhart，“Particle Swarm Optimization”，Proc.IEEE Int.Conf.Neural Netw.，Perth Austrilia，1995，vol.4pp.1942-1948.

[2]R.Mendes，J.Kennedy and J.Neves，“The Fully Informed Particle Swarm： Simpler，Maybe Better”，IEEE Trans.Evol.Comput.，vol.8，no.3，pp.204-211，2004.

[3]王俊年，申群太，沈洪遠，等.一種基于聚類的小生境微粒群算法.信息與控制，2005，34，（6）680-684.

[4]王俊年，申群太，周少武，等.基于種群小生境微粒群算法的前向神經網絡設計.控制與決策，2005，20，（9），981-985.

[5]姚 旭，王曉丹，張玉璽，權 文 基于微粒群優化算法的最大相關最小冗余混合式特征選擇方法.控制與決策，2013，28（3）：413-423.

[6]鄭永前，喻賽君 基于可重生PSO的雙層產品組合決策問題.計算機集成制造系統，2013，19（4）：783-789.

[7]丁大志，沈 鵬，陳如山，尚 社，范曉彥 降雨微粒群散射特性的高效分析.電波科學學報 2012，27（1）：30-36.

[8]陳如清，俞金壽.混沌微粒群混合優化算法的研究與應用.系統仿真學報.2008，20，（3）：685-688.