1 简介
粒子群优化算法(Particle Swarm optimization, PSO)，是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法。能够在系统中寻找最优解，方法的原理与概念简单、操作便捷、易于实现，具有良好的寻优能力。该算法主要用于产品的功能优化、神经网络训练集、多模式分类等。
假如一群鸟在随机搜索食物，在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是它们知道当前的位置离食物还有多远。此时想要搜寻到食物的话，自然是搜寻离食物最近的鸟的周围区域。整个鸟群通过互相传递各自的信息，让所有个体鸟之间都知道各自的位置，通过这样的协作，来判断自己找到的是不是最优解，同时也将最优解的信息传递给整个鸟群，最终，整个鸟群都能聚集在食物源周围，即找到了最优解。
PSO 中，每只鸟都包含一些特征信息，其所在位置就是该鸟特征信息所能得到的优化问题的解。这种在优化问题的搜索空间中不停寻找最优解（食物）的鸟，我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitness value)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。
2 粒子及群落所含信息
设粒子群优化算法的搜寻空间为 $D$ 维空间，群集由 $N$ 个粒子构成，每个粒子都有属于自己的位置和速度，分别记为 $X_i$ 和 $V_i$ 。
每一个粒子 $i$ 代表一个 $D$ 维的向量，即粒子本身代表位置：
$$
X_i = (X_{i1},X_{i2},\cdots,X_{iD}),i = 1,2,\cdots,N \tag1
$$
在探寻空间过程中，每一个粒子的速度均可构成一个 $D$ 维向量，记为：
$$
V_i = (V_{i1},V_{i2},\cdots,V_{iD}),i = 1,2,\cdots,N \tag2
$$
在每次迭代时，每个粒子都通过自身所在位置与种群的位置共享中挑选出个体最优解（$pbest$）和全局最优解（$gbest$），接着根据个体最优解来引导粒子向下一个更好的位置靠拢。这里个体最优解可以看作粒子自己的 “经验” ，全局最优解可以看作粒子同伴的 “经验”，粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动的。
由上，在迭代过程中，任何一个粒子到当前的最佳位置称为个体极值，记为：
$$
pbest = (p_{i1},p_{i2},\cdots,p_{iN}),i = 1,2,\cdots,N \tag3
$$
整个探寻最优解的过程中，群体到目前为止的最佳位置称为全局极值，记为：
$$
gbest = (g_1,g_2,\cdots,g_D) \tag4
$$
3 速度与位置的更新
PSO 群落中的所有粒子在初始状态下位置与速度均为随机生成的（随机解），然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪 $pbest$ 、$gbest$ 来更新自己。在找到这两个最优值后，每个粒子的速度和位置更新公式如下：
$$
v_i(t+1) = w\cdot v_i(t) + c_1r_1(x_{pbesti} - x_i(t)) + c_2r_2(x_{gbesti} - x_i(t)) \tag5
$$
$$
x_i(t+1) = x_i(t) + v_i(t+1) \tag6
$$
其中，$v_i(t)$、$x_i(t)$ 分别表示粒子 $i$ 在 $t$ 时刻的速度和位置；$v_i(t+1)$、$x_i(t+1)$ 分别表示粒子 $i$ 在 $t+1$ 时刻的速度和位置；$w$ 表示惯性权重；$c_1$ 表示个体最优加速因子；$c_2$ 表示全局最优加速因子；$r_1$、$r_2$ 表示在 $(0,1)$ 范围内正态分布产生的随机数；$x_{pbesti}$ 表示粒子 $i$ 的个体最优解； $x_{gbesti}$ 表示粒子 $i$ 的全局最优解。
由式$(5)$可以看出，粒子的速度更新具有三个组成成分：
- 继承部分：通过惯性权重权衡当代速度对下代速度的影响比例，起到控制粒子全局开发与局部探索的能力；
- 自我认知部分：通过自身最优位置引导粒子飞行，增添粒子的自身经验能提高种群多样性，避免盲目跟风而只能求得局部最优解；
- 群体经验部分：通过种群中所有粒子之间的位置信息共享和对比来寻求最优位置，增添此部分能大大提高粒子群算法的收敛速度。
4 $w$ 、$c_1$、$c_2$ 的设置
值得注意的是，$w$ 作为惯性权重，需自行设置，其大小决定了离子对当前速度继承的多少。
$w$ 应为非负，其值较大时，全局寻优能力强，局部寻优能力弱；其值较小时，全局寻优能力弱，局部寻优能力强。因此，动态 $w$ 能获得比固定值更好的寻优结果，而动态 $w$ 可在 PSO 搜索过程中线性变化，也可以根据 PSO 性能的某个测度函数动态改变。
目前采用较多的是线性递减权值（Linearly Decreasing Weight, LDW）策略：
$$
w^{(t)} = \frac{(w_{ini} - w_{end})(G_k - g)}{G_k} + w_{end} \tag7
$$
其中，$G_k$ 表示最大迭代次数；$w_{ini}$ 表示初始惯性权值；$w_{end}$ 表示迭代值最大进化代数是的惯性权值。一种经典权值设置为：$w_{ini} = 0.9, w_{end} = 0.4$
而 $c_1$、$c_2$ 亦需自行设置，分别代表更新速度时自我认知部分所占权重及群体经验部分所占权重。
- 当 $c_1=0$ 时 ，则粒子没有了认知能力，变为只有社会的模型（social-only），称为全局PSO算法。粒子有扩展搜索空间的能力，具有较快的收敛速度，但由于缺少局部搜索，对于复杂问题比标准PSO 更易陷入局部最优；
- 当 $c_2=0$ 时 ，则粒子间没有社会信息，变为只有认知的模型（cognition-only）称为局部PSO算法。由于个体之间没有信息的交流，整个群体相当于多个粒子进行盲目的随机搜索，收敛速度慢，因而得到最优解的可能性小。
通常情况下 $c_1 = c_2 = 2$，或者前期 $c_1$ 大，后期 $c_2$ 大，亦可自行动态调整。
以上三个自定义参数分别控制继承部分、自我认知部分、群体经验部分的权重占比，而这三部分相互协调决定了算法的整体性能。
5 算法流程
粒子群优化算法的流程图如下所示：
- 初始化群粒子(群体规模为N)，包括随机位置和速度；
- 计算粒子适应度。一般的，我们优化目标是找到目标函数的最小值。所以个体计算出的函数值越小，适应度越高。
- 对每个粒子，将其适应值与其经过的最好位置pbest作比较，如果较好，则将其作为当前的最好位置pbest；对每个粒子，将其适应值与其经过的最好位置gbest作比较，如果较好，则将其作为当前的最好位置gbest。
- 根据式$(5)$、式$(6)$ 调整粒子的速度和位置。
- 判断算法是否终止，迭代终止条件根据具体问题一般选为最大迭代次数 $G_k$ 或(和)粒子群迄今为止搜索到的最优位置满足预定最小适应阈值。
- 未达到结束条件则转第 2 步。否则输出 $gbest$ 及全局最优解对应的粒子的 $pbest$。
参考文献
[1] 崔慧珍. 基于粒子群算法的灰色-马尔科夫改进模型的土地利用变化模拟[D].黑龙江科技大学,2022.
[2] 王春博. 基于改进粒子群算法冷热电联供型的微网优化运行研究[D].中国矿业大学,2022.
[3] 李娜娜. 基于改进粒子群算法的多目标优化问题研究[D]. 贵州民族大学,2022.
[4] https://cloud.tencent.com/developer/article/1424756
[5] https://github.com/CHENHUI-X/My-lecture-slides-and-code/blob/main