智能优化算法 4：粒子群算法

基本原理

粒子群算法（Particle Swarm Optimization, PSO）是一种基于群体智能的优化算法。它通过模拟鸟群或鱼群等社会动物的群体行为来寻找最优解。可以假设这样一个场景：在一个区域里只有一个食物源，有一群鸟在觅食。所有鸟都不知道食物在哪里，但是它们知道当前的位置离食物还有多远。那么找到食物的最佳策略是什么呢？最简单有效的方法是搜索目前离食物最近的鸟的周围区域并根据自身经验判断食物的位置。

鸟群在寻找食物的过程中，个体之间存在信息交流和共享，每个成员可以从其他成员的搜索经验中获益，并调整自身的搜索行为。当食物源不可预测其分布状态时，这种个体之间的协作所产生的优势是巨大的。

  • 在 PSO 中，把一个优化问题看作是在空中觅食的鸟群，那么“食物”就是优化问题的最优解，而在空中飞行的每一只觅食的“鸟”就是 PSO 算法中在解空间中进行搜索的一个“粒子”(Particle)。
  • 粒子在搜索空间中以一定的速度飞行，这个速度根据它本身的飞行经验和同伴的飞行经验来动态调整。所有的粒子都有一个被目标函数决定的适应值（fitness value），这个适应值用于评价粒子的“好坏”程度。
  • 每个粒子知道自己到目前为止发现的最好位置（particle best，记为 pbest）和当前的位置，pbest 就是粒子本身找到的最优解，这个可以看作是粒子自己的飞行经验。
  • 除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置 (global best，记为 gbest)，gbest 是在 pbest 中的最好值，即是全局最优解，这个可以看作是整个群体的经验。

数学模型

粒子群算法（Particle Swarm Optimization, PSO）是通过模拟群体行为来解决优化问题的算法。它的核心在于每个粒子在搜索空间中不断调整其位置和速度，以接近全局最优解。下面介绍粒子群算法的数学模型，包括位置和速度的更新公式及其相关参数。

初始化

首先，初始化粒子群，包括每个粒子的初始位置和速度。假设粒子群由 NN 个粒子组成，每个粒子在 DD 维空间中。

  • 粒子 ii 的位置： xi=(xi1,xi2,…,xiD)\mathbf{x}_i = (x_{i1}, x_{i2}, \ldots, x_{iD})
  • 粒子 ii 的速度： vi=(vi1,vi2,…,viD)\mathbf{v}_i = (v_{i1}, v_{i2}, \ldots, v_{iD})
  • 粒子 ii 的个体最优位置（个体最优解）：pbesti=(pi1,pi2,…,piD)\mathbf{pbest}_i = (p_{i1}, p_{i2}, \ldots, p_{iD})
  • 全局最优位置（全局最优解）：gbest=(g1,g2,…,gD)\mathbf{gbest} = (g_1, g_2, \ldots, g_D)

速度更新公式

粒子 ii 在第 t+1t+1 代的速度由以下公式更新：

vi(t+1)=w⋅vi(t)+c1⋅r1⋅(pi(t)−xi(t))+c2⋅r2⋅(g(t)−xi(t))\mathbf{v}_i(t+1) = w \cdot \mathbf{v}_i(t) + c_1 \cdot r_1 \cdot (\mathbf{p}_i(t) - \mathbf{x}_i(t)) + c_2 \cdot r_2 \cdot (\mathbf{g}(t) - \mathbf{x}_i(t))

其中：

  • ww 是惯性权重，控制粒子的惯性对速度的影响。
  • c1c_1 是个体学习因子，衡量粒子自身经验的重要性。
  • c2c_2 是社会学习因子，衡量粒子借鉴群体经验的重要性。
  • r1r_1 和 r2r_2 是两个独立的均匀分布的随机数，范围在 [0, 1] 之间，增加搜索的随机性。

式子的三个部分也可以看作：粒子先前的速度 + 自身认知项（认知组件） + 群体认知项（社交组件）

位置更新公式

粒子 ii 在第 t+1t+1 代的位置由以下公式更新：

xi(t+1)=xi(t)+vi(t+1)\mathbf{x}_i(t+1) = \mathbf{x}_i(t) + \mathbf{v}_i(t+1)

位置是一个空间坐标，所以位置更新要加上整个空间内的位移

适应度评估

每个粒子的适应度值 f(xi)f(\mathbf{x}_i) 是其位置 xi\mathbf{x}_i 对应的目标函数值。适应度评估用于更新个体最优位置和全局最优位置：

  • 如果 f(xi(t+1))f(\mathbf{x}_i(t+1)) 优于 f(pbesti(t))f(\mathbf{pbest}_i(t))，则更新个体最优位置：pbesti(t+1)=xi(t+1)\mathbf{pbest}_i(t+1) = \mathbf{x}_i(t+1)
  • 如果 f(pbesti(t+1))f(\mathbf{pbest}_i(t+1)) 优于 f(gbest(t))f(\mathbf{gbest}(t))，则更新全局最优位置： gbest(t+1)=pbesti(t+1)\mathbf{gbest}(t+1) = \mathbf{pbest}_i(t+1)

终止条件

算法反复进行速度和位置的更新，直到满足以下停止条件之一：

  • 达到预设的最大迭代次数。
  • 全局最优位置的适应度值在若干次迭代中没有显著改善。
  • 全局最优位置的适应度值达到了预设的阈值。

参数设置

粒子群算法的性能在很大程度上依赖于参数的设置：

  • 惯性权重 ( w )：一般在 [0.4, 0.9] 范围内选择，通常随时间递减。
  • 个体学习因子 ( c_1 ) 和社会学习因子 ( c_2 )：通常都设置为 2。
  • 速度限制 vmaxv_{\text{max}}：限制粒子的速度以防止其移动过快，一般取值为位置范围的 10% 到 20%。

粒子群算法解决函数优化问题

Rosenbrock 函数是一个经典的测试函数，用于验证优化算法的性能，其定义如下：

f(x,y)=(a−x)2+b⋅(y−x2)2f(x,y)=(a-x)^2+b \cdot (y-x^2)^2

该函数有一个全局最小值点，当 a=1,b=100a=1, b=100 时，全局最小值点位于 (x,y)=(1,1)(x,y)=(1,1)，此时函数值为 0。函数在该点附近呈现一个狭长的谷底，这使得优化问题具有挑战性。

代码实现