likes
comments
collection
share

【智能优化算法】PSO-粒子群优化算法原理

作者站长头像
站长
· 阅读数 36

算法背景

Particle Swarm Optimization：粒子群优化算法，也被称为鸟群觅食算法，属于进化计算技术(evolutionary computation)，1995年由Kennedy博士和Eberhart博士提出，源于对鸟群捕食的行为研究。

PSO算法原论文：J. Kennedy and R. Eberhart. Particle swarm optimization. In Proceedings of the IEEE International Conference on Neural Networks, pages 1942–1948, Piscataway, NJ, USA, 1995.

该算法最初是受到飞鸟集群活动的规律性启发，进而利用群体智能建立的一个简化模型；即在对动物集群活动行为观察的基础上，利用群体中的个体对信息的共享使得整个群体的运动在问题求解空间中产生从无序到有序的演化过程，从而获得最优解。

基本思想和原理

基本思想

【智能优化算法】PSO-粒子群优化算法原理

鸟群觅食行为：假设在一片森林中的多处存在食物，但每处地点食物的多少不同，整个鸟群为了发现这片森林中食物最多的地方，每只鸟都在森林中到处飞行寻找，对于每只鸟来说，每发现一处存在食物的地方都会默默记下来该处食物的多少，因此存在当前已发现的包含最多食物的地方；对于整个鸟群来说，整个鸟群中的鸟类会共享已寻找到的信息，互相交流，综合鸟群中所有鸟的发现地点，共享所有鸟发现地点中包含最多食物的地方。

此外，对于鸟群中的每只鸟而言，其还包括个体行为和社会行为：

  • 个体行为：单只鸟会根据自身搜索情况，向自身已知食物最多的地方移动
  • 社会行为：单只鸟会收到当前群体已知最好地点的影响，向目前群体已知食物最多的地方移动

鸟群觅食行为的抽象化：为了将鸟群觅食行为转化为算法，需要将其中的各个部分进行抽象化

① 求解空间抽象化：不难发现，鸟群所探索的森林就是求解空间，而食物多少则是待优化的目标函数对应的值

  • 整片森林：求解空间
  • 每处地点食物的多少：目标函数值
  • 包含食物最多的地点：全局最优解

② 鸟群信息抽象化：将鸟群抽象为粒子群，将鸟群的各个行为信息也进行抽象化处理

  • 整个鸟群：粒子群
  • 鸟群中的每只鸟：单个粒子
  • 某只鸟所处的位置：某单个粒子的位置，也就是空间中的一个解
  • 整个鸟群中所有鸟共享当前发现的最好地点：全局最优位置
  • 单只鸟自己发现的最好地点：个体最优位置

③ 鸟群移动抽象化：每个粒子的移动受以下三个因素的影响

  • 方向1：单个粒子具备对未知区域的探索能力，倾向于保持上一移动方向进行移动(惯性)
  • 方向2：单个粒子会收到个体行为影响，倾向于向个体最优位置移动
  • 方向3：单个粒子会收到社会行为影响，倾向于向全局最优位置移动

抽象化后，就得到了粒子群优化算法中各个部分的相关信息，而具体的算法实现则是基于上方抽象后得到的信息对鸟群觅食过程的模拟。

重要概念解释

在具体介绍PSO具体逻辑之前，先对该算法中涉及的一些重要参数或概念进行介绍以便于后续原理的讲解。

设在 ddd 维求解空间中存在 nnn 个粒子，则有：

  • 第 iii 个粒子的位置：Xi=(xi1,xi2,⋯ ,xid)X_{i} = (x_{i1}, x_{i2}, \cdots, x_{id})Xi​=(xi1​,xi2​,⋯,xid​)
  • 第 iii 个粒子的速度(包括粒子移动的距离和方向)：Vi=(vi1,vi2,⋯ ,vid)V_{i} = (v_{i1}, v_{i2}, \cdots, v_{id})Vi​=(vi1​,vi2​,⋯,vid​)
  • 第 iii 个粒子的个体最优位置：Pi,pbest=(pi1,pi2,⋯ ,pid)P_{i, pbest} = (p_{i1}, p_{i2}, \cdots, p_{id})Pi,pbest​=(pi1​,pi2​,⋯,pid​)
  • 粒子群搜索的全局最优位置：Pgbest=(p1,p2,⋯ ,pd)P_{gbest} = (p_{1}, p_{2}, \cdots, p_{d})Pgbest​=(p1​,p2​,⋯,pd​)
  • 第 iii 个粒子搜索到的历史最优位置(个体最优位置)的适应值：fpif_{pi}fpi​
  • 群体搜索到的最优位置(全局最优位置)对应的适应值：fgf_gfg​

不难理解，在ddd维空间中，每个粒子都有 位置 和 速度，其中速度包括粒子移动的距离和方向，用于更新下轮迭代中某粒子的位置；而 适应值(fitness value) 则为目标函数值，用于评价当前位置的好坏程度，我们通常认为适应值越小越好，也就是目标函数的值越小越好，若目标函数为越大越好(如上方举例的食物量)，则通常取其负数。

算法原理与流程

算法逻辑

粒子群优化算法的总体逻辑：

  • 在求解空间内随机初始化各个粒子的位置XiX_iXi​、个体最优位置Pi,pbestP_{i, pbest}Pi,pbest​、全局最优位置PgbestP_{gbest}Pgbest​
  • 对于每次迭代：
    • 计算每个粒子的适应度：若某粒子当前的适应度小于 pi,pbestp_{i, pbest}pi,pbest​ 对应的适应度fpif_{pi}fpi​，则将当前位置赋值给 pi,pbestp_{i, pbest}pi,pbest​，将当前位置的适应度赋值给 fpif_{pi}fpi​
    • 比较每个粒子的 pi,pbestp_{i, pbest}pi,pbest​ 对应的适应度：将对应适应度最好的位置赋值给 pgbestp_{gbest}pgbest​，将该位置对应的适应度赋值给 fgf_gfg​
    • 计算每个粒子的速度 ViV_iVi​，并更新其在求解空间中的位置
  • 直到算法收敛或达到某种条件，停止迭代

速度更新原理

速度更新公式：PSO的核心在于如何更新每次迭代中各个粒子的位置，也就是如何对每个粒子的速度向量进行更新

① 什么是速度向量：设在3维求解空间中，第1次迭代时粒子的位置为Xi=(1,2,3)X_i=(1, 2, 3)Xi​=(1,2,3)，第2次迭代时该粒子的位置为 Xi+1=(5,8,4)X_{i+1} = (5,8,4)Xi+1​=(5,8,4)，则对应的速度向量为：

Vi=Xi+1−Xi=(5,8,4)−(1,2,3)=(4,6,1)V_i = X_{i+1} - X_i = (5, 8, 4) - (1, 2, 3) = (4, 6, 1)Vi​=Xi+1​−Xi​=(5,8,4)−(1,2,3)=(4,6,1)

不难想到，若已知某粒子当前迭代的位置和速度，可以计算粒子下次迭代更新的位置，如：

Xi+1=Xi+Vi=(1,2,3)+(4,6,1)=(5,8,4)X_{i+1} = X_i + V_i = (1, 2, 3) + (4, 6, 1) = (5, 8, 4)Xi+1​=Xi​+Vi​=(1,2,3)+(4,6,1)=(5,8,4)

② 速度向量如何计算：如上方鸟群移动抽象化所提及的一样，粒子的移动方向会收到三个因素影响，分别为 倾向于保持上次迭代的移动方向(惯性)、倾向于向个体最优位置移动、倾向于向全局最优位置移动，在下图中即分别对应速度向量 v2,v1,v3v_2, v_1, v_3v2​,v1​,v3​

【智能优化算法】PSO-粒子群优化算法原理

如图所示，不难得到各个速度向量的表达式分别为：

{v1=Vikv2=Pi,pbestk−Xikv3=Pgbestk−Xik,\begin{cases} v_1 = V_i^k \\ v_2 = P^k_{i, pbest} - X_i^k \\ v_3 = P^k_{gbest} - X_i^k \end{cases} , \quad⎩⎨⎧​v1​=Vik​v2​=Pi,pbestk​−Xik​v3​=Pgbestk​−Xik​​,

将各个方向的向量合成后得到融合三个方向速度的新的速度向量 v5v_5v5​：

{v4=v1+v2v5=v3+v4⟶v5=v1+v2+v3\begin{cases} v_4 = v_1 + v_2 \\ v_5 = v_3 + v_4 \\ \end{cases} \quad \longrightarrow \quad v_5 = v_1 + v_2 + v_3{v4​=v1​+v2​v5​=v3​+v4​​⟶v5​=v1​+v2​+v3​

分配权重：为了更好地控制这三个方向的速度向量进行合成，给向量 v1,v2,v3v_1, v_2, v_3v1​,v2​,v3​ 分别加上对应权重 w,c1,c2w, c_1, c_2w,c1​,c2​，这三个权重也被分别称为 惯性权重，个体学习因子，群体学习因子，就得到了：

v5=wv1+c1v2+c2v3v_5 = w v_1 + c_1 v_2 + c_2 v_3v5​=wv1​+c1​v2​+c2​v3​

为什么被称为"学习因子": 某粒子需要向全局最优位置和个体最优位置"学习"，为了控制粒子向这两个位置的学习程度，因此这两个权重被称为"学习因子"

增加随机性：为了进一步增加粒子搜索的随机性，对全局最优位置和个体最优位置方向的向量 v2,v3v_2, v_3v2​,v3​ 分别乘以 [0,1][0, 1][0,1] 的随机数 r1,r2r_1, r_2r1​,r2​，得到以下改进的速度计算表达式：

v5=wv1+c1r1v2+c2r2v3v_5 = w v_1 + c_1 r_1 v_2 + c_2 r_2 v_3v5​=wv1​+c1​r1​v2​+c2​r2​v3​

将 v1,v2,v3v_1, v_2, v_3v1​,v2​,v3​ 代入到式子中得到迭代次数为 k+1k+1k+1 的速度向量的计算公式：

Vik+1=wVik+c1r1(Pi,pbestk−Xik)+c2r2(Pgbestk−Xik)V_{i}^{k+1} = w V_i^k + c_1r_1(P^k_{i, pbest} - X^k_i) + c_2r_2(P^k_{gbest} - X^k_i) Vik+1​=wVik​+c1​r1​(Pi,pbestk​−Xik​)+c2​r2​(Pgbestk​−Xik​)
  • www：惯性权重
  • c1c_1c1​：个体学习因子
  • c2c_2c2​：群体学习因子
  • Pi,pbestkP_{i, pbest}^kPi,pbestk​：迭代次数为k时的第i个粒子的个体最优位置
  • PgbestkP^k_{gbest}Pgbestk​：迭代次数为k时的全局最优位置
  • XikX_i^kXik​：迭代次数为k时的第i个粒子的位置
  • VikV_i^kVik​：迭代次数为k时的第i个粒子的速度向量
  • Vik+1V_i^{k+1}Vik+1​：迭代次数为k+1时的第i个粒子的速度向量

这里是将三个速度向量按一定权重进行合成，得到下轮迭代时粒子的速度

相关技巧和优化思路

速度限制：为了平衡算法的探索能力与开发能力，需要设定一个合理的速度大小范围，以限制粒子的最大速度 VmaxV_{max}Vmax​，一般将各个维度的速度变化量控制在该变量取值范围的 10% - 20%，若超出该范围，则直接将其设置在边界即可。

  • 探索能力：VmaxV_{max}Vmax​较大时，粒子飞行速度快，探索能力强，但粒子容易飞过最优解
  • 开发能力：VmaxV_{max}Vmax​较小时，飞行速度慢，开发能力强，但收敛速度慢，容易陷入局部最优解

位置限制：将所有粒子的位置限制在目标搜索区域中，若某一维度的位置超出范围，则和速度限制类似，通常采用边界处理，将其设置在边界即可。

优化停止准则：一般使用事先设置的最大迭代步数；或上一次迭代后全局最优位置的适应值与本次迭代后最优解的适应值之差小于某个阈值后停止优化。

自适应权重：基本粒子群算法的惯性权重是恒定不变的，但这并不是一个好的方法，在探索初期，粒子的探索能力应该较大，开发能力应该较小；而在后期，整个求解空间区域已经被探索了很大一部分区域了，这时粒子的探索能力应该较弱，而开发能力应该较强；粒子的惯性权重的大小反映了其探索能力，因此应该设置一个动态的自适应权重，基本方法为：

w=wmax−(wmax−wmin)n_itern_itermaxw = w_{max} - (w_{max} - w_{min})\frac{n\_iter}{n\_iter_{max}}w=wmax​−(wmax​−wmin​)n_itermax​n_iter​
  • wmaxw_{max}wmax​：设置的最大惯性权重
  • wminw_{min}wmin​：设置的最小惯性权重
  • n_itern\_itern_iter：当前的迭代次数
  • n_itermaxn\_iter_{max}n_itermax​：设置的最大迭代次数

上方的更新公式也就是使得惯性权重 www 随着迭代次数的增加而逐渐减小，从而使得粒子群算法在初期具有较强的全局收敛能力，在后期具有较强的局部收敛能力.

总结

PSO逻辑简单但功能强大; 其核心原理在于速度向量的更新, 总体逻辑较为简单; 算法仍有存在陷入局部最优解的可能, 且对种群的初始化较为敏感; 此外, 随着算法的发展, PSO也衍生出各种变体和改进方案, 在很多领域都着有相对不错的表现

基于Python实现PSO(GitHub)：Algorithm/IOA/PSO at main · Rink1t/Algorithm (github.com)

Reference

转载自:https://juejin.cn/post/7303465518157217833
评论
请登录