11.1　粒子群算法的基本原理

粒子群算法具有进化计算和群体智能的特点。与其他进化算法类似，粒子群算法也是通过个体间的协作和竞争，实现复杂空间中最优解的搜索。

在粒子群算法中，每一个优化问题的解被看作是搜索空间的一只鸟，即“粒子”。算法开始时，首先生成初始解，即在可行解空间中随机初始化m粒子组成的种群Z＝｛Z₁，Z₂，…，Z_m｝，其中每个粒子所处的位置Z_i＝｛z_i1，z_i2，…，z_in｝都表示问题的一个解，并且根据目标函数计算每个粒子的适应度值。然后每个粒子都将在解空间中迭代搜索，通过不断调整自己的位置来搜索新解。在每一次迭代中，粒子将跟踪两个“极值”来更新自己，一个是粒子本身搜索到的最好解p_id，另一个是整个种群目前搜索到的最优解p_gd，这个极值即全局极值。此外，每个粒子都有一个速度V_i＝｛v_i1，v_i2，…，v_in｝，当两个最优解都找到后，每个粒子根据下式来更新自己的速度：

v_id＝wv_id（t）＋η₁rand（）［p_id－z_id（t）］＋η₂rand（）［p_gd－z_id（t）］

z_id（t＋1）＝z_id（t）＋v_id（t＋1）

其中，v_id（t＋1）表示第i个粒子在t＋1次迭代中第d维上的速度；w为惯性权重，η₁、η₂为加速常数，rand()为0～1之间的随机数。此外，为使粒子速度不致过大，可设置速度上限，即当v_id（t＋1）＞v_max时，v_id（t＋1）＝v_max；v_id（t＋1）＜-v_max时，v_id（t＋1）＝-v_max。

从粒子的更新公式可看出，粒子的移动方向由三部分决定：自己原有的速度v_id；与自己最佳经历的距离p_id－z_id（t）；与群体最佳经历的距离p_gd－z_id（t），并分别由权重系数w、η₁和η₂决定其相对重要性。

当达到算法的结束条件，即找到足够好的最优解或达到最大迭代次数时，算法结束。

粒子群算法的基本流程如图11.1所示。

图11.1　粒子群算法流程

参数选择对算法的性能和效率有较大的影响。在粒子群算法中有3个重要参数即惯性权重w、速度调节参数η₁和η₂。惯性权重w使粒子保持运动惯性；速度调节参数η₁和η₂表示粒子向p_id和p_gd位置的加速项权重。如果w＝0，则粒子速率没有记忆性，粒子群将收缩到当前的全局最优位置，失去搜索更优解的能力。如果η₁＝0，则粒子失去“认知”能力，只具有“社会”性，粒子群收敛速度会更快，但是容易陷入局部极值。如果η₂＝0，则粒子只具有“认知”能力，而不具有“社会”性，等价于多个粒子独立搜索，因此很难得到最优解。

实践证明没有绝对最优的参数，针对不同的问题选取合适的参数才能获得更好的收敛速度和鲁棒性，一般情况下w取0～1之间的随机数，η₁和η₂分别选取2。