前言

  自然界中的一些生物行为特征呈现群体特征,而人工生命的主要研究领域之一是通过一些简单的规则给个体的行为建模,从而在计算机上构建其群体模型。生物学家Craig Reynolds在1987年提出了一个非常有影响的鸟群聚集模型,Boid模型。在这个模型中,Reynolds使用了以下三个简单的行为准则,利用这三个简单的规则,就可以非常接近的模拟出鸟群飞行的现象

  1. 冲突避免(collision avoidance):群体在一定空间内移动,个体有自己的移动意志,但不能影响其他个体的移动,避免碰撞和冲突
  2. 速度匹配(velocity matching):个体必须配合中心移动速度,在方向、距离和速率上都必须相互配合
  3. 群体中心(flock centering):个体将会向群体中心移动,配合群体中心向前移动

  依托这个模型,Kennedy和Eberhart通过模拟鸟群觅食过程中的迁徙和群聚行为提出了一个基于群体智能的全局随机搜索算法——粒子群优化(Particle Swarm Optimization, PSO)算法。


群鸟觅食模型

  为了理解PSO算法的过程,我们需要先理解群鸟觅食模型中鸟群觅食的过程。可以知道,鸟群在一定范围内搜索食物是一个最佳决策的过程。与人类的决策过程相似,鸟群觅食的过程综合了两个重要的信息:

  1. 个体经验:根据自身以往的经验和尝试,得出哪个选择更好的结论
  2. 群体经验:从其他个体的经验中得出哪个选择更好的结论

  在群鸟觅食的过程中,每只鸟的初始状态都处于随机位置,且飞翔的方向也是随机的。每只鸟都不知道食物在哪里,但是每只鸟能够估计目前所处位置对于找到食物有多大价值,即有多大的适应度(食物所在位置适应度最大)。此外,每只鸟能记住自己找过的最好位置(局部最优)以及鸟群中所有个体已经找到的最好位置(全局最优)。随着时间的推移(也就是不断地迭代),这些初始处于随机位置的鸟通过个体不断积累寻觅食物的经验、共享个体信息和群内互相学习(也就是不断综合局部最优和全局最优信息),逐渐朝群体共同的方向,也就是食物的位置前进,使得整个鸟群的觅食中心都趋向于全局最优移动。


基本理论

  PSO从这种模型中得到启示并用于解决优化问题。在PSO中,搜索空间中的一只鸟,称之为粒子(particle),整个鸟群被称为粒子群(particle swarm)。每个粒子所处的位置为优化问题的潜在解,每个位置找到食物的概率称为由目标函数决定的适应度值(fitness value)。此外,每个粒子还有一个速度决定它们飞翔的方向和距离来模拟随机觅食的过程。
  现在我们不妨假设在一个$D$维的搜索空间(优化问题有$D$个自变量)中,有$m$个粒子组成一个群体,其中第$i$个粒子在$D$维搜索空间中的位置表示为$X_i=(x_i^1,x_i^2,…x_i^D)$。将$X_i$代入目标函数我们可以得到该粒子在$X_i$处的适应度值,并根据得到的适应度值来衡量其优劣。粒子个体找过的最优位置记为$P_i=(p_i^1,p_i^2,…,p_i^D)$,粒子群中所有粒子找过的最佳位置记为$P_g=(p_g^1,p_g^2,…,p_g^D)$。粒子$i$的速度记为$V_i=(v_i^1,v_i^2,…,v_i^D)$。
  为了模拟个体随机觅食的过程,PSO采用下列公式不断迭代更新粒子所在的位置:
$$v_i^d = w v_i^d + c_1r_1(p_i^d - x_i^d) + c_2r_2(p_g^d - x_i^d)$$
$$x_i^d = x_i^d + \alpha v_i^d$$
其中,$i=1,2,…,m$,$d=1,2,…,D$。&w&是非负数,称为惯性因子加速常数$c_1$和$c_2$是非负常数,$r_1$和$r_2$是$[0, 1]$范围内变化的随机数,$\alpha$称为约束因子,目的是控制速度的权重。此外,$v_i^d \in [-v_{max}^d, v_{max}^d]$,即粒子的速度$V_i^d$被一个最大速度$V_{max}=(v_{max}^1,v_{max}^2,…,v_{max}^D)$所限制,从而保证保证粒子在任何一维上的速度不会超出这个限制。


算法步骤

  1. 初始化粒子群的数量$m$,确定每个粒子的速度$V$和位置$X$,确定惯性因子$w$、加速常数$c_1$和$c_2$、最大迭代次数和算法终止的最小允许误差

    • 粒子数$m$一般取$20~40$,$m$越大,越容易找到全局最优解,运行的时间越长。对于大多数问题,粒子数为$30$足够用了。
    • 惯性因子$w$影响算法的收敛性。$w$越大,粒子飞翔的幅度越大,跳出局部范围的能力越强,粒子在较大程度上能跳离原先的寻优轨道,有可能增大搜索空间,发现新的解域,进而增加全局搜索能力,但降低局部寻优能力;$w$太小,则跳出局部范围的能力较弱,粒子在较大程度上会按照原先的寻优轨道继续搜索,进而增强了局部寻优能力,但全局搜索效果差。若$w$是变量,那么可以在迭代初期将$w$设置得很大,在迭代过程中逐渐减小$w$的值;若$w$是定值,那么$w$一般取$[0.6, 0.75]$内的值
    • 加速常数$c_1$和$c_2$用于调整自身经验群体经验在其运动过程中所起的作用的权重。当$c_1 = 0$的时候,粒子没有自身经验,运动只受全局最优解的影响;当$c_2 = 0$的时候,粒子没有全局经验,运动只受局部最优解的影响;当$c_1 = c_2 = 0$的时候,粒子既没有个体经验,也没有群体经验,将杂乱地在边界寻找,很难找到最优解。对于一般的问题,一般取$c_1 = c_2 = 2.0$
  2. 评价每个粒子的初始适应度值

  3. 将初始适应度值作为每个粒子的局部最优值,并将初始位置作为每个粒子的局部最优解;将当前群体中,最大的个体初始适应度作为群体的全局最优值,并将其对应的位置作为全局最优解
  4. 根据公式$v_i^d = w v_i^d + c_1r_1(p_i^d - x_i^d) + c_2r_2(p_g^d - x_i^d)$更新每个粒子的飞行速度
  5. 确定粒子的最大速度$V_{max}$,对每个粒子的飞行速度进行限速处理,使之保持在预设的范围$[-V_{max}, V_{max}]$内

    PSO是通过调整每一次迭代时每一个粒子在每一维上移动的距离(也就是粒子的速度)来实现的。粒子速度的改变是随机的,为了避免搜索空间无意义地发散,我们需要使用$V_{max}$对粒子的速度进行限制。此外,$V_{max}$还限制了粒子每次移动的最大步长,一般来说,我们希望在粒子的步长在搜索初期足够大,以让粒子能跳出局部最优;又希望粒子的步长在接近全局最优解时足够小,以精确地搜索全局最优解。如果$V_{max}$的取值是固定不变的,通常设置$V_{max}$为每维变化范围的$10\%$ ~ $20\%$

  6. 比较当前每个粒子所处位置的适应度是否高于粒子的局部最优值,如果是,则更新粒子的局部最优值局部最优解

  7. 更新粒子群的全局最优值全局最优解
  8. 重复步骤$4~7$,知道满足预先设定的终止条件

    PSO的终止条件根据具体问题而定,一般达到预定最大迭代次数或者粒子群目前位置搜索的最优位置满足目标函数的最小容许误差。

  9. 输出粒子群的全局最优值全局最优解


算法流程图

粒子群算法流程图
粒子群算法流程图

后言

  通过前面的介绍我们可以知道,粒子群算法是一种随机算法,它通过不断随机改变粒子的位置来实现全局随机搜索的目的。和粒子群算法相似的是,遗传算法是通过随机改变个体的编码来实现全局随机搜索的目的,不同的是遗传算法的个体编码受父代个体的影响,而粒子群算法的粒子位置不受其他粒子的影响。此外,粒子群算法不涉及到复杂的编解码,实现起来也比遗传算法简单。