粒子群优化算法

粒子群优化算法(PSO)最初是由Kennedy和Eberhart博士于1995年受人工生命研究的结果启发，在模拟鸟群觅食过程中的迁徙和群集行为时提出的一种基于群体智能的演化计算技术。该算法具有并行处理、鲁棒性好等特点，能以较大概率找到问题的全局最优解，且计算效率比传统随机方法高。其最大的优势在于编程简单，易实现、收敛速度快，而且有深刻的智能背景，既适合科学研究，又适合工程应用。因此，PSO一经提出，立刻引起了演化计算领域研究者的广泛关注，并在短短几年时间里涌现出大量的研究成果，该算法目前已被“国际演化计算会议”列为讨论专题之一。 PSO是受到鸟群或者鱼群社会行为的启发而形成的一种基于种群的随机优化技术。它是一类随机全局优化技术，通过粒子间的相互作用发现复杂搜索空间中的最优区域。该算法是一种基于群体智能的新型演化计算技术，具有简单易实现、设置参数少、全局优化能力强等优点。粒子群优化算法已在函数优化、神经网络设计、分类、模式识别、信号处理、机器人技术等许多领域取得了成功的应用。

产生背景

设想这样一个场景：一群鸟随机的分布在一个区域中，在这个区域里只有一块食物。所有的鸟都不知道食物在哪里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的方法就是追寻自己视野中目前离食物最近的鸟。如果把食物当作最优点，而把鸟离食物的距离当作函数的适应度，那么鸟寻觅食物的过程就可以当作一个函数寻优的过程。由此受到启发，经过简化提出了粒子群优化算法。

PSO算法的基本思想

每个优化问题的潜在解都是搜索空间中的一只鸟，称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值（fitness value），每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。PSO初始化为一群随机粒子（随机解）。然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解。这个解称为个体极值。另一个极值是整个种群目前找到的最优解。这个极值是全局极值。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。

基本模型

设群体规模为 $\mathrm{N}$, 在一个D维的目标搜索空间中, 群 体中的第 $\mathrm{i}(\mathrm{i}=1,2, \ldots \mathrm{N})$ 个粒子位置可以表示为一 个D维矢量 $X_{i}=\left(x_{i 1}, x_{i 2}, \cdots, x_{i D}\right)^{T}$, 同时用 $V_{i}=\left(v_{i 1}, v_{i 2}, \cdots, v_{i D}\right)^{T}, i=1,2, \cdots, N$ 表示第 $\mathrm{i}$ 个粒子的飞翔速度。用 $P_{i}=\left(p_{i 1}, p_{i 2}, \cdots, p_{i D}\right)^{T}$ 表示第 $\mathrm{i}$ 个粒子自身搜索到 的最好点。而在这个种群中, 至少有一个粒子是最 好的, 将其编号记为 $\mathrm{g}$, 则 $P_{g}=\left(p_{g 1}, p_{g 2}, \cdots, p_{82}\right)^{T}$ 就是当 前种群所搜索到的最好点, 即种群的全局历史最优位置。

粒子根据以下公式来更新其速度和位置: $$ \begin{gathered} v_{i j}^{k+1}=v_{i j}^{k}+c_{1} r_{1 j}\left(p_{i j}^{k}-x_{i j}^{k}\right)+c_{2} r_{2 j}\left(p_{g j}^{k}-x_{i j}^{k}\right) \\ x_{i j}^{k+1}=x_{i j}^{k}+v_{i j}^{k+1} \end{gathered} $$ 其中 $\mathrm{i}=1,2, \ldots, \mathrm{N}, \mathrm{j}$ 表示粒子的第 $\mathrm{j}$ 维, $\mathrm{k}$ 表示迭代次数 $, c_{1}, c_{2}$ 为加速常数，一般在 $0 \sim 2$ 之间取值。 $c_{1}$ 主要是为了 调节粒子自身的最好位置飞行的步长， $c_{2}$ 是为了调节粒子向全局最好位置飞行的步长。 $r_{1} \sim u(0,1), r_{2} \sim u(0,1)$ 为两个相互 独立的随机函数。为了减少在进化过程中, 粒子离开搜索 空间的可能性, $v_{i j}$ 通常限定于一定范围内, 即 $v_{j j} \in\left[V_{\text {min }}, V_{\max }\right]$

式中其第一部分 $v_{i j}^{k}$ 为粒子先前的速度 ; 其第二部分 $c_{1} r_{1 j}\left(p_{i j}^{k}-x_{i j}^{k}\right)$ 为 “认知”部分, 它仅考虑了粒子白身的经验, 表示粒子本身 的思考, 其第三部夯 $r_{2 j}\left(p_{g}^{k}-x_{i j}^{k}\right)$ 为 “社会” 部分， 表示粒子间的社会信息共享,

基本流程

$\square$ 基本粒子群算法的流程如下:

带惯性权重的粒子群算法

为了改变基本粒子群算法的收玫性能, Y.Shi与 R.C.Eberhart在1998年的IEEE国际进化计算学术会 议上发表了题为 “A Modified Particle Swarm Optimization"的论文。首先在速度进化方程中引入惯 性权重(inertia weight) $w$, 即 $v_{i j}^{k+1}=w v_{i j}^{k}+c_{1} r_{1 j}\left(p_{i j}^{k}-x_{i j}^{k}\right)+c_{2} r_{2 j}\left(p_{g j}^{k}-x_{i j}^{k}\right)$

基本粒子群算法是 $w=1$ 的特殊情况。把带惯性权重的微粒群算法 称之为标准粒子群算法。由基本粒子群算法模型中粒子位置的进化方程可以看出, 粒子在不同时刻的位置主要是由飞行速度决定的, 也就 是说粒子的飞行速度相当于搜索步长: $x_{i j}^{k+1}=x_{i j}^{k}+v_{i j}^{k+1}$ 飞行速度的大小直接影响着算法的全局收敛性。当粒子的飞行速度过 大时, 各粒子初始将会以较快的速度飞向全局最优解邻近的区域, 但 是当逼近最优解时, 由于粒子的飞行速度缺乏有效的控制与约束, 则 将很容易飞越最优解, 转而去搜索其它区域, 从而使算法很难收敛于 最优解, 陷入局部最优解; 当粒子的飞行速度过小时, 粒子在初期向 全局最优解邻近区域靠近的搜索时间就需要很长。收玫速度慢, 很难达到最优解。基于此现实情况,他们二人提出了标准的微粒群算法。

式中的 $w$ 为惯性权重, 它具有维护全局和局部搜索能力的平 衡作用, 可以使粒子保持惯性运动, 使其有扩展搜索空间的趋 势, 有能力探索新的区域。对全局搜索, 通常的好方法是在前 期有较高的搜索能力以得到合适的粒子, 而在后期有较高的开发能力以加快收敛速度。为此, 可将W设定为随着进化而线性 减少, 例如由 $0.9 \sim 1.2$ 等。有些学者在研究中曾论证出 $w$ 的最 佳值在 $0.8$ 附近, 这将为设计标准微粒粒子群算法参数时提供 了有利的参考。一般人们认为较大的 $\mathrm{w}$ 提高了寻优时粒子的全 局搜索能力, 有利于提高寻优的成功率; 较小的 $\mathrm{w}$ 则有利于粒 子群在迭代运算时的快速聚集, 有利于提高寻优的速度。

引入惯性权重 $\mathrm{w}$ 可消除基本粒子群算法对 $V_{\text {max }}$ 的需要。当 $V_{\text {max }}$ 增加时, 可通过减少 $w$ 来达到平衡搜索, 而 $w$ 的减少可使得所 需的迭代次数变小。所以, 可以将各维变量的 $V_{\text {max, } D}$ 固定，而 只对 $w$ 进行调节。 $w$ 越大, 粒子的飞行速度就越大, 它将以较 大的步长进行全局搜索; $\mathrm{W}$ 越小，粒子的速度步长越小, 粒子 趋向于进行精细的局部搜素。 $\mathrm{W}$ 的变化趋势正好相当于粒子速 度的变化趋势。所以带惯性权重的粒子群算法的改进之处就是 将二者结合起来以使粒子可以尽快的向最优解区域靠拢, 而又 不至孚在到达最优解区域附近时飞越最优解。 目前关于粒子群算法的研究,一般都是将带惯性权重的粒子群 算法作为最基本的PSO算法模型。