粒子群优化算法的理论分析

2.2　粒子群优化算法的理论分析

粒子群优化算法已经得到了广泛的应用，很多学者也对其原理进行了理论分析，因为对其进行理论分析不仅有助于改进算法，完善此算法的体系，还可以扩大此算法的应用领域。粒子群算法的理论研究包括微观和宏观两个层面的分析^［64］。微观上是以单个粒子在解空间的飞行轨迹作为参考，单个粒子的行为过程在一定程度上反映了群体的变化趋势;宏观上则是对整个群体的行为做研究，分析群体一般性的搜索过程，建立合理的数学模型，讨论算法的收敛性。分析手段包括代数分析、解析分析、基于热力学的类比分析、差分方程分析、随机过程分析等。

1．单个粒子行为分析

Ozcan和Mohan在参考文献［65］中首次尝试对粒子群优化算法进行了理论方面的探讨，他们对粒子在一维空间中的轨迹进行了分析。Ozcan等为了理解复杂系统的行为，把搜索空间假设成只有一维，且令基本粒子群优化算法中的个体极值pbest和全局极值gbest相等，并且都用p表示，为了进一步简化粒子的两个更新公式，可以假设R₁c₁，R₂c₂和p都是常数，且初始条件为x(0)=x₀，x(1)=x₀(1－φ)+v₀+φp，把粒子的速度和位置更新公式相减可得到如下的递推公式:

其中，φ=R₁c₁+R₂c₂。解此非齐次线性递归方程，可得闭合形式解为

其中，δ=，β=(x₀－p)(δ+φ)/(2δ)－v₀/δ，α=x₀－p－β。公式(2.13)的重要性在于，在算法执行的任何阶段都可以根据此公式得到单个粒子的运行轨迹。

为了分析粒子在多维空间中的运行轨迹，Ozcan和Mohan采用类似的分析方法得到粒子在多维空间中的轨迹递归方程，本书不再赘述，具体可以参看参考文献［66］中的推导分析。

2．代数分析和解析分析

在粒子群优化算法理论研究方面，Clerc和Kennedy^［60］于2002年发表在IEEE Transactions on Evolutionary Computation上题为The Particle Swarm-explosion，Stability，and Convergence in A Multidimensional Complex Space的论文被认为是具有里程碑意义的巅峰之作，并获得Best Paper Award，作者较完整地给出了PSO算法的收敛性分析，从代数的观点分析了粒子在离散时间下的运动轨迹，接着从解析的角度分析了粒子在连续时间下的运动轨迹，并发现使用收缩因子可以保证算法收敛。

3．差分方程分析

很多研究是在连续时间上利用状态转移矩阵和微分方程进行分析的，因而大量分析和讨论工作是在复数域上进行的，因此李宁等^［67］认为其中许多讨论对实际的PSO算法是没有任何意义的。针对PSO算法本身是一个离散过程的特点，李宁等人通过差分方程以及Z变换对粒子的运动轨迹做描述，使分析过程变得非常简洁。在对粒子运动轨迹的收敛性分析的基础上，作者深入讨论了pbest，gbest和随机量对粒子运动轨迹的影响以及粒子运动轨迹收敛与算法收敛性之间的关系，给出了控制粒子运动轨迹振荡幅值的公式和条件。

4．基于热力学的类比分析

熊勇^［68］将粒子群优化算法和待优化函数作为一个系统来考虑，它对应的物理模型是一个处于外力场中的多粒子系统。其中外力场是由待优化函数决定的，是待优化函数产生的势场力，它作用在每一个粒子上;而粒子系统则由粒子的拓扑结构以及粒子的运动方程来决定，前者决定了每个粒子受哪些粒子的相互作用，后者决定了每个粒子在既定时刻运动的方向和幅度。作者采用非平衡热力学的工具:Langevin方程和Fokker-Planck方程。利用这两种方程之间的对应关系，并对系统加以合理的简化，可以将复杂的多变量常微分方程组转换为一个多变量的偏微分方程，从而把研究所有粒子的轨迹演化转化为研究整个粒子系统的联合分布的演化。作者之所以这样分析，目的有两个:第一个目的是理解这个系统演化的过程是怎样的以及系统的演化具有哪些特征;第二个目的是试图理解系统的演化稳定之后，最终停留在一个什么样的状态，这个状态具有什么样的物理含义。最后，根据以上的分析，结合退火规则设计了一类中间变量较少的类粒子群优化算法。

5．基于随机过程的收敛性分析

金欣磊等^［69］发现已有文献对系统稳定性的分析大多基于线性系统理论，在稳定性分析和证明过程中系统往往是一个带有随机因素的线性时变系统。作者从随机过程角度出发，把原有的带随机因素的线性时变系统在概率意义下转换成线性定常系统加以分析研究，很好地解决了已有文献中的不足，通过分析位置参数序列X₀，X₁，…，X_t，…的数学期望和方差给出系统依均方稳定的一个充分条件，最后作者认为基于随机过程理论的分析研究方法将会是对粒子群系统稳定性分析的重要方法之一。

此外，还有很多学者也在粒子群优化算法理论分析方面做了大量的研究工作，比如，Trelea^［70］在Ozcan工作的基础上，给出了模型的稳定区域和不稳定区域以及相应的运动轨迹分析;Bergh^［71］给出了基本PSO算法的全局收敛性和局部收敛性分析;Emara^［72］提出了一种基于连续系统的PSO模型，并利用李亚普诺夫方法证明了其稳定性;曾建潮等^［73］在Bergh工作的基础上给出了以概率1收敛于全局最优的PSO算法，并通过分析已有的PSO算法，提出了一种统一模型，通过线性系统理论分析了其收敛性。