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

张成兴

【摘要】微粒群算法已经成为一种高效容易实现的方法.微粒群算法根据鸟群捕食行为抽象而来，但是目前很少有文献分析该算法在循环中改变速度和位置的稳定性.本文以基本微粒群算法为例，利用差分方程，常微分方程和线性系统控制理论对算法的更新公式进行了分析，给出了算法稳定的条件.

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.