微粒群算法速度與位置更新的穩(wěn)定性分析

張成興

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

1.引 言

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

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

但是PSO的核心速度位置更新公式?jīng)]有發(fā)生較大的變化，所以本文通過分析PSO位置和速度的更新方式來討論算法穩(wěn)定的條件.

2.穩(wěn)定性分析

PSO的速度更新公式如下：

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

（1）為中P為當(dāng)前最優(yōu)個體位置，G為種群最優(yōu)位置，ω是慣性權(quán)重.

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

根據(jù)（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）

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

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

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

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

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

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

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

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

對（4）進(jìn)行Z變換，得到：

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

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

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

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

利用控制理論中的Routh判據(jù)，可知系統(tǒng)穩(wěn)定的充要條件是系數(shù)大于0.

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

λ1+λ2>0

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

1-ω>0（10）

3.結(jié) 論

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

【參考文獻(xiàn)】

[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]王俊年，申群太，沈洪遠(yuǎn)，等.一種基于聚類的小生境微粒群算法.信息與控制，2005，34，（6）680-684.

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

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

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

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

[8]陳如清，俞金壽.混沌微粒群混合優(yōu)化算法的研究與應(yīng)用.系統(tǒng)仿真學(xué)報.2008，20，（3）：685-688.