文章目录
1. 提出论文
Kennedy J, Eberhart R. Particle swarm optimization[C]//Proceedings of ICNN’95-international conference on neural networks. IEEE, 1995, 4: 1942-1948.
2. 基本思想
粒子群算法的思想源于对鸟群觅食行为的研究，鸟群通过集体的信息共享使群体找到最优的目的地。如下图，设想这样一个场景：鸟群在森林中随机搜索食物，它们想要找到食物量最多的位置。但是所有的鸟都不知道食物具体在哪个位置，只能感受到食物大概在哪个方向。每只鸟沿着自己判定的方向进行搜索，并在搜索的过程中记录自己曾经找到过食物且量最多的位置，同时所有的鸟都共享自己每一次发现食物的位置以及食物的量，这样鸟群就知道当前在哪个位置食物的量最多。在搜索的过程中每只鸟都会根据自己记忆中食物量最多的位置和当前鸟群记录的食物量最多的位置调整自己接下来搜索的方向。鸟群经过一段时间的搜索后就可以找到森林中哪个位置的食物量最多（全局最优解）。
![[attachments/Particle swarm optimization/image-20230228175646425.png|450]]
3. 基本概念
- 粒子：优化问题的候选解个数 $n$
- 位置：候选解所在的位置 $x_i^d$
- 速度：候选解移动的速度 $v_i^d$
惯性权重 $w$ - 粒子的个体学习因子，也称为个体加速因子: $c_1$
- 粒子的社会学习因子，也称为社会加速因子: $c_2$
- 适应度：评价粒子优劣的值，一般设置为目标函数值 $f(x)$
- 个体最佳位置：单个粒子迄今为止找到的最佳位置 $pbest_i^d$
- 群体最佳位置：所有粒子迄今为止找到的最佳位置 $gbest_i^d$
4. 特点
粒子群算法具有收敛速度快、参数少、算法简单易实现的优点（对高维度优化问题，比遗传算法更快收敛于最优解），但是也会存在陷入局部最优解的问题。
5. 算法流程图
![[attachments/Particle swarm optimization/image-20230227201728513.png|450]]
6. 迭代公式
- 这只鸟第 $d$ 步的速度 = 上一步自身的速度惯性 + 自我认知部分 + 社会认知部分
$$
\begin{aligned}
& v(d)=wv(d-1)+c_1 r_1 *\left(\text { pbest(d)-x(d)) }+c_2 r_2(g b e s t(d)-x(d)) \quad\right. \
& \boldsymbol{v}i^d=w v_i^{d-1}+c_1 \boldsymbol{r}_1\left(p b e s t { i } ^ { d }-x_i^d\right)+c_2 r_2\left(\text { gbest }^d-x_i^d\right)
\end{aligned}
$$
其中 $r_1, r_2$ 是 $[0,1]$ 上的随机数
注意, 这里我们没有在变量说明的表格中放入 $r 1$ 和 2 这两个随机数, 是因为他们表示的含义不太重要, 我们只需要简单的交代一下就行。 - 这只鸟第 $\mathrm{d}+1$ 步所在的位置 = 第 $\mathrm{d}$ 步所在的位置 + 第 $\mathrm{d}$ 步的速度 $*$ 运动的时间 $x(d+1)=x(d)+v(d) * t \quad($ 每一步运动的时间 $t$ 一般取 1 $)$
$$
x_i^{d+1}=x_i^d+v_i^d
$$
7. 预设参数确定
学习因子 $c$
Kennedy J, Eberhart R. Particle swarm optimization[C]//Proceedings of ICNN’95-international conference on neural networks. IEEE, 1995, 4: 1942-1948.
在最初提出粒子群算法的论文中指出，个体学习因子和社会 (或群体) 学习因子取2比较合适。 （注意：最初提出粒子群算法的这篇论文没有惯性权重）
惯性权重 $w$
提出论文
SHI,Y. A Modified Particle Swarm Optimizer[C]// Proc. of IEEE ICEC conference, Anchorage. 1998.
论文中得到的结论：惯性权重取0.9‐1.2是比较合适的，一般取0.9就行。
惯性权重 w 体现的是粒子继承先前的速度的能力， Shi, Y 最先将惯性权重 w 引入到粒子群算法中，并分析指出==一个较大的惯性权值有利于全局搜索，而一个较小的权值则更利于局部搜索。==
粒子数量
增加粒子数量会增加我们找到更好结果的可能性，但会增加运算的时间。
迭代次数
迭代的次数 K 越大越好吗？不一定哦，如果现在已经找到最优解了，再增加迭代次数是没有意义的。
粒子速度
为了平衡算法的探索能力与开发能力，需要设定一个合理的速度范围，限制粒子的最大速度 $v_{max}$ ，即粒子下一步迭代可以移动的最大距离。
- $v_{max}$ 较大时，粒子飞行速度快，探索能力强，但粒子容易飞过最优解；
- $v_{max}$ 较小时，飞行速度慢，开发能力强，但是收敛速度慢，且容易陷入局部最优解；
- $v_{max}$ 一般设为粒子变化范围的10％~20％，可根据实际情况调试，但不能大于粒子 (解)的变化范围。
位置约束
限制粒子搜索的空间，即自变量的取值范围，对于无约束问题此处可以省略。
X 的下界和上界是保证粒子不会飞出定义域。
8. Python 实现
# 定义粒子群类
class PSO:
def __init__(self, func, n, dim, max_iter, lb, ub): # 初始化粒子群
self.func = func # 目标函数
self.n = n # 粒子数量
self.dim = dim # 维度
self.max_iter = max_iter # 迭代次数
self.lb = lb # 下界
self.ub = ub # 上界
self.w = 0.9 # 惯性权重
self.c1 = 2 # 学习因子
self.c2 = 2 # 学习因子
self.gbest_x = np.zeros(dim) # 全局最优解
self.gbest_y = float('inf') # 全局最优解的函数值
self.particles = [Particle(np.zeros(dim), np.zeros(dim), np.zeros(dim), float('inf')) for _ in range(n)] # 粒子群
def init_Population(self): # 初始化粒子群
for particle in self.particles:
# 'particle.x = self.lb + (self.ub - self.lb) * np.random.rand(self.dim) # 初始化粒子位置
# 初始化粒子位置
for i in range(self.dim):
particle.x[i] = np.random.uniform(self.lb[i], self.ub[i])
# 初始化粒子速度
particle.v = np.random.uniform(-1, 1, self.dim)
particle.fitness = self.func(particle.x) # 计算粒子适应度
particle.p = particle.x # 初始化粒子的最优位置
if particle.fitness < self.gbest_y: # 更新全局最优位置
self.gbest_x = particle.x
self.gbest_y = particle.fitness
def iterator(self): # 迭代
fitness = [] # 用于存储每次迭代的最优解
for iter in range(self.max_iter): # 迭代次数
for particle in self.particles: # 更新粒子
v = self.w * particle.v + self.c1 * random.random() * (
particle.p - particle.x) + self.c2 * random.random() * (self.gbest_x - particle.x) # 更新粒子速度
# 限制粒子速度
for i in range(self.dim):
if v[i] > (self.ub[i] - self.lb[i]) * 1.2:
v[i] = self.ub[i] - self.lb[i]
if v[i] < (self.lb[i] - self.ub[i]) * 1.2:
v[i] = self.lb[i] - self.ub[i]
x = particle.x + v # 更新粒子位置
# 限制粒子位置
for i in range(self.dim):
if x[i] > self.ub[i]:
x[i] = self.ub[i]
if x[i] < self.lb[i]:
x[i] = self.lb[i]
fit = self.func(x) # 计算粒子适应度
if fit < particle.fitness: # 更新粒子最优位置
particle.update(v, x, fit)
if fit < self.gbest_y: # 更新全局最优位置
self.gbest_x = x
self.gbest_y = fit
fitness.append(self.gbest_y) # 记录每次迭代的最优解
print('iter:', iter, 'gbest_x:', self.gbest_x, 'gbest_y:', self.gbest_y) # 打印每次迭代的最优解
return fitness
def run(self): # 运行
self.init_Population() # 初始化粒子群
fitness = self.iterator() # 迭代
return fitness # 返回每次迭代的最优解
9. 改进算法
对惯性权重的改进
线性递减惯性权重
为了更好地平衡算法的全局搜索以及局部搜索能力，==Shi, Y== 提出了线性递减惯性权重 LDIW (Linear Decreasing Inertia Weight), 公式如下：
$$
w^d=w_{\text {start }}-\left(w_{\text {start }}-w_{\text {end }}\right) \times \frac{d}{K}
$$
其中 $d$ 是当前迭代的次数, $K$ 是迭代总次数 $w_{\text {start }}$ 一般取 $0.9 ， w_{\text {end }}$ 一般取 $0.4$。
与原来相比，现在惯性权重和迭代次数有关。
![[attachments/Particle swarm optimization/image-20230228184509581.png]]
self.w = 0.9 - iter * (0.9 - 0.4) / self.max_iter
非线性递减惯性权重
$$
\begin{gathered}
W^d=w_{\text {start }}-\left (w_{\text {start }}-w_{\text {end }}\right) \times\left (\frac{d}{K}\right)^2 \
W^d=w_{\text {start }}-\left (w_{\text {start }}-w_{\text {end }}\right) \times\left[\frac{2 d}{K}-\left (\frac{d}{K}\right)^2\right]
\end{gathered}
$$
![[attachments/Particle swarm optimization/三种惯性权重对比.jpg]]
自适应惯性权重
$$
v_i^d=w v_i^{d-1}+c_1 r_1\left(\text { pbest }i^d-x_i^d\right)+c_2 r_2\left(\text { gbest }^d-x_i^d\right) $$ 假设现在求==最小值问题==，那么: $$ w_i^d=\left{\begin{array}{cc} w{\min }+\left(w_{\max }-w_{\min }\right) \frac{f\left(x_i^d\right)-f_{\min }^d}{f_{\text {average }}^d-f_{\min }^d}, & f\left(x_i^d\right) \leq f_{\text {average }}^d \
w_{\max }, & f\left(x_i^d\right)>f_{\text {average }}^d
\end{array}\right.
$$
其中:
- $w_{\min }$ 和 $w_{\max }$ 是我们预先给定的最小惯性系数和最大惯性系数, 一般取 $0.4$ 和 $0.9$
- $f_{\text {average }}^d=\sum_{i=1}^n f\left(x_i^d\right) / n$, 即第 $d$ 次迭代时所有粒子的平均适应度
- $f_{\min }^d=\min \left{f\left(x_1^d\right), f\left(x_2^d\right), \cdots, f\left(x_n^d\right)\right}$, 即第 $d$ 次迭代时所有粒子的最小适应度
与原来的相比，现在惯性权重和迭代次数以及每个粒子适应度有关
==适应度越小==，说明距离最优解越近，此时==更需要局部搜索==
适应度越大，说明距离最优解越远，此时更需要全局搜索
随机惯性权重
提出论文
Zhang L , Yu H , Hu S . A New Approach to Improve Particle Swarm Optimization[J]. lecture notes in computer science, 2003, 2723:134‐139.
==使用随机的惯性权重，可以避免在迭代前期局部搜索能力的不足；也可以避免在迭代后期全局搜索能力的不足。==
$$
v_{i d}=r_0 v_{i d}+c_1 r_1\left(p_{i d}-x_{i d}\right)+c_2 r_2\left(p_{g d}-x_{i d}\right)
$$
改进的权重公式
基于随机惯性权重的简化粒子群优化算法[J]. 计算机应用研究, 2014, 031 (002): 361-363,391.
$$
v_i^d=w v_i^{d-1}+c_1 r_1\left (\text { pbest }i^d-x_i^d\right)+c_2 r_2\left (\text { gbest }^d-x_i^d\right) $$ 基于以上分析，提出随机惯性权重。生成公式如下： $$ w = \mu{min} + (\mu_{max} – \mu_{min}) \times rand()+\sigma \times randn()
$$
其中：$\mu_{min}$ 是随机惯性权重的最小值; $\mu_{max}$ 是随机惯性权重的最大值; $rand (）$ 为 $[0,1 ]$ 均匀分布随机数; 第三项中 $randn ()$ 为正态分布的随机数; $\sigma$ (标准差)用来度量随机变量权重 $w$ 与其学期望 (即均值)之间的偏离程度，一般取 0.2-0.5 之间。该项是为了控制取值中权重误差，使权重 $w$ 有利于向期望权重方向进化，这样做的据是正常情况下实验误差服从正态分布。
对学习因子的改进
压缩因子法
提出论文
M. Clerc. The swarm and queen: towards a deterministic and adaptive particle swarm op‐timization. Proc. Congress on Evolutionary Computation, Washington, DC,. Piscataway, NJ: IEEE Service Center (1999) 1951–1957
$$
v_i^d=w v_i^{d-1}+c_1 r_1\left (\text { pbest }_i^d-x_i^d\right)+c_2 r_2\left (\text { gbest }^d-x_i^d\right)
$$
个体学习因子 $c 1$和社会 (群体)学习因子$c 2$ 决定了粒子本身经验信息和其他粒子的经验信息对粒子运行轨迹的影响，其反映了粒子群之间的信息交流。设置 $c 1$ 较大的值，会使粒子过多地在自身的局部范围内搜索，而较大的 $c 2$ 的值，则又会促使粒子过早收敛到局部最优值。
为了有效地控制粒子的飞行速度，使算法达到全局搜索与局部搜索两者间的有效平衡，Clerc 构造了引入收缩因子的 PSO 模型，采用了压缩因子，这种调整方法通过合适选取参数，可确保 PSO 算法的收敛性，并可取消对速度的边界限制。
改进的速度公式
压缩因子法中应用较多的个体学习因子 c1和社会学习因子 c2均取2.05，用我们自己的符号可以表示为：
$\boldsymbol{c1}=\boldsymbol{c2}=2.05, \boldsymbol{C}=\boldsymbol{c 1}+\boldsymbol{c 2}=4.1$, 收缩因子 $\boldsymbol{\Phi}=\frac{\mathbf{2}}{\left|\left(\mathbf{2}-\boldsymbol{C}-\sqrt{\boldsymbol{C}^2-4 \boldsymbol{C}}\right)\right|}$; 惯性权重 $\boldsymbol{w}=0.9$, 速度更新公式改为:
$$
\begin{aligned}
v_i^d &=\Phi \times [wv_i^ { d – 1 }+c_1 r_1(\text {pbest}_i^d-x_i^d)+c_2r_2(\text{gbest}^d-x_i^d)]\
&= 0.657v_i^{d-1}+1.496r_1(pbest_i^d-x_i^d)+1.496r_2(gbest_i^d -x_i^d)
\end{aligned}
$$
非对称学习因子
提出论文
毛开富, 包广清, 徐驰. 基于非对称学习因子调节的粒子群优化算法[J]. 计算机工程, 2010 (19):188‐190.
在经典 PSO 算法中，由于在寻优后期粒子缺乏多样性，易过早收敛于局部极值，因此通过调节学习因子，在搜索初期使粒子进行大范围搜索，以期获得具有更好多样性的高质量粒子，尽可能摆脱局部极值的千扰。
学习因子 $c 1$ 和 $c 2$ 决定粒子个体经验信息和其他粒子经验信息灯寻优轨迹的影响，反映了粒子之间的信息交换。设置较大的 $c1$ 值，会使粒子过多的在局部搜索；反之，较大的 $c2$ 值会使粒子过早收敛到局部最优值。因此，在算法搜索初期采用较大的 $c1$ 值和较小的 $c 2$ 值，使粒子尽量发散到搜索空间即强调“个体独立意识”，而较少受到种群内其他粒子即“社会意识部分”的影啊，以增加群内粒子的多样性。随着迭代次数的增加。使 $c 1$ 线性递减，$c 2$ 线性递增，从而加强了粒子向全局最优点的收敛能力。
改进的学习因子公式
$$
\begin{aligned}
& c 1=c_{1 i} + k \times\left(c_{1 f}-c_{1 i}\right) / k_{\max } \
& c 2=c_{2 i}+k \times\left(c_{2 f}-c_{2 i}\right) / k_{\max }
\end{aligned}
$$
其中, $k$ 为当前迭代次数; $k_{\text {max }}$ 是最大迭代数; $c_{1 i} 、 c_{2 i}$ 分别为 $c 1 、 c 2$ 的初始值; $c_{1 f} c_{2 f}$ 分别为 $c 1 、 c 2$ 的最终值。
$$
\begin{gathered}
c_1^{i n i}=2.5, c_1^{f i n}=0.5, c_2^{i n i}=1, c_2^{f i n}=2.25 \
c_1^d=c_1^{i n i}+\left(c_1^{f i n}-c_1^{i n i}\right) \times \frac{d}{K} ; c_2^d=c_2^{i n i}+\left(c_2^{f i n}-c_2^{i n i}\right) \times \frac{d}{K}
\end{gathered}
$$
其中 $d$ 是当前迭代的次数, $K$ 是迭代总次数
10. 优化问题的测试函数
张玮, 王华奎. 粒子群算法稳定性的参数选择策略分析[J]. 系统仿真学报, 2009, 21 (014):4339‐4344.
![[attachments/Particle swarm optimization/image-20230301160357343.png]]
- 维数：自变量 x 的个数, 也是上面表达式中 n 的大小
- 取值范围：每个 x 对应的变化范围
- 理论极值：这个函数理论上的最小值
- 误差目标：只要我们求出来的最小值小于这个目标值就能被接受
0