基于高斯扰动的粒子群优化算法算法

字数统计: 1.2k字  | 阅读时长:约 5 分钟
总阅读量次


在碎片时间被智能手机APP大肆压榨的时代，我们只能从增强自我管理开始。以上是自己最近的一些思考。欢迎一起来讨论（👉👇）。下面开始本篇主题

算法介绍

基于高斯扰动的粒子群算法(Particle Swarm Optimization based on Ganssian Disturbance, GDPSO)^1 ^，其很巧妙的在标准粒子群算法速度迭代公式基础上增加一个高斯扰动，使得算法收敛速度加快，且既能帮助算法有效跳出局部最优值，又能扩大粒子搜索范围。
具体GDPSO速度迭代公式如下：

$$v_{id}^{(t+1)} = \omega v_{id}^{(t)} + c_{1}r_{1}(p_{id}^{(t)} + r_{2}gauss_{id}^{(t)}-x_{id}^{(t)})\
+c_{2}r_{3}(p_{gd}^{(t)}-x_{id}^{(t)})$$$$x_{id}^{(t+1)} = x_{id}^{(t)} + v_{id}^{(t+1)}$$$$gauss_{id}^{(t)} = r_4gaussian(\mu, \sigma ^{2})$$

其中$\mu = 0，\sigma ^{2} = |p_{id}|$，其它参数与标准粒子群算法一致。
据算法分析，令$c_1 = c_2 = \lambda $，当算法参数满足：

$$\left{ {| \omega | < 1}\atop
{0 < \lambda < 2 + 2\omega}\right.$$

且个体极值、高斯扰动值和全局极值保持不变时，算法在$E[x]^{*}$处渐进稳定

算法进化模式分析

令$c_1 = c_2$， $r_1 = r_2 = r_3 = r$，那么种群所有粒子可分以下情况：

  1. 粒子$i$当前位置为其历史最优位置，但不是全局最优位置，即$x_{id} = p_{id}, x_{id} \not= p_{gd}$。
    则算法进化模式为 ： $$v_{id}^{(t+1)} = \omega v_{id}^{(t)} + c_{1}r(p_{id}^{(t)} + rgauss_{id}^{(t)}-x_{id}^{(t)})\
    +c_{2}r(p_{gd}^{(t)}-x_{id}^{(t)})\
    = \omega v_{id}^{(t)} + c_1r^2gauss_{id}^{(t)} + c_{2}r(p_{gd}^{(t)}-x_{id}^{(t)})$$

此时GDPSO速度增量比PSO更大，其全局搜索能力更强，收敛速度更快，且高斯扰动选项能帮助算法逃离局部最优。

  1. 粒子$i$当前位置为其历史最优位置，同时又是全局最优位置，即$x_{id} = p_{id} = p_{gd}$。
    则算法进化模式为：

$$v_{id}^{(t+1)} = \omega v_{id}^{(t)} + c_{1}r(p_{id}^{(t)} + rgauss_{id}^{(t)}-x_{id}^{(t)})\
+c_{2}r(p_{gd}^{(t)}-x_{id}^{(t)})\
= \omega v_{id}^{(t)} + c_1r^2gauss_{id}^{(t)}$$

此时GDPSO速度项比标准PSO增加了一个高斯扰动值，有助于算法跳出当前局部最优解。

  1. 粒子$i$当前位置不是其历史最优位置，同时又不是全局最优位置，但是粒子$i$的历史最优位置恰好是全局最优位置，即$x_{id} \not= p_{id}，x_{id} \not= p_{gd}, 且p_{id} = p_{gd}$。
    此时算法的进化模式为：$$v_{id}^{(t+1)} = \omega v_{id}^{(t)} + c_{1}r(p_{id}^{(t)} + rgauss_{id}^{(t)}-x_{id}^{(t)})\
    +c_{2}r(p_{gd}^{(t)}-x_{id}^{(t)})\
    =\omega v_{id}^{(t)} + 2c_1r(p_{gd}^{(t)} - x_{id}^{(t)} + \frac{1}{2}rgauss_{id}^{(t)})$$

此时，对于PSO，种群中粒子完全向当前全局最优值移动，很容易陷入局部最优值。而GDPSO一方面保证其收敛速度比PSO更快，另一方面由于增加了高斯扰动项，很好的避免了算法陷入局部最优值。

  1. 粒子 $i$当前位置不是其历史最优位置，同时又不是全局最优位置，且粒子$i$的历史最优位置不是当前种群全局最优位置，即
    $x_{id} \not= p_{id}，x_{id} \not= p_{gd}，且 p_{id} \not= p_{gd}$ 。算法的进化模式为：

$$v_{id}^{(t+1)} = \omega v_{id}^{(t)} + c_{1}r(p_{id}^{(t)} + rgauss_{id}^{(t)}-x_{id}^{(t)})\
+c_{2}r(p_{gd}^{(t)}-x_{id}^{(t)})\
= \omega v_{id}^{(t)} + c_{1}r(p_{id}^{(t)}-x_{id}^{(t)})+c_{2}r(p_{gd}^{(t)}-x_{id}^{(t)})\
+c_1r^2gauss_{id}^{(t)}$$

此时相比于PSO的速度项，GDPSO增加了一个高斯扰动项，其可以帮助粒子扩大搜索范围，增强全局寻优能力，且提高了算法收敛速度。

算法实现

  1. 选择测试函数
    $Griewank$函数(取值范围为$[一600，600]$，理论最优值为0)：$$f(x) = \frac{1}{4000}\sum_{i=1}^{D}x_i^2 - \prod_{i=1}^{D}cos(\frac{x_i}{\sqrt{i}}) + 1$$
  2. 环境
    JetBrains PyCharm + Python3.7
  3. 参数设置
W = 0.6  # 惯性权重，根据论文会随着迭代次数改变
C1 = 2.0  # 认知
C2 = 2.0  # 社会
P = []  # 第i个粒子搜索到的历史最优位值
Pifitness = []  # 记录第i个粒子搜索到的历史最优值
Pg = []  # 整个粒子群搜索到的最优位值
Pgfitness = float('inf')  # 记录整个粒子群搜索到的最优值
PgfitnessRecord = []
intervalMin = -600  # 种群搜索区间下限
intervalMax = 600  # 种群搜索区间上限
Vmin = -120  # 粒子的速度下限
Vmax = 120  # 粒子的速度上限
N = 10  # 粒子个数
T = 2000  # 迭代次数
D = 30  # 粒子的维度
  1. 实验结果

GDPSO_2000

GDPSO算法迭代2000次

GDPSO_20000

GDPSO算法迭代20000次

完整实验代码见我的Github

^1^. 通讯作者：孙辉，邮箱: sunhui@nit.edu.cn ↩