粒子群优化算法简介

PSO算法受到鸟群觅食方式的启发。欧椋鸟（European starling）成群结队飞行时组成的鸟群，会让人怀疑每一只欧椋鸟并不是完全独立的个体，鸟群才是真正有智能的生命体。对鸟群的数学分析显示，不管群体有多庞大，抑或仅有几只小鸟，每只欧椋鸟的动作都为其他同伴所影响，仿佛每只小鸟都链接在一个无形的网络中（Cavagna et al.，2010）。

设想在一个布满食物的空间里，鸟群随机搜索食物。食物随机分布于空间的每一块区域，有些区域食物多，而有些区域食物较少。显然，必定存在某一块区域含有最多的食物。鸟群希望它们中至少有一只小鸟能够搜索到食物最多的那块区域；如果找不到，也希望退而求其次找到食物第二多的或第三多的区域。每一只小鸟各自按照简单策略来寻找食物：一方面，不断参考自己飞过的区域并记下食物最多的一块区域，在向领域搜索无果时返回记忆中食物最多的那块区域；另一方面，参考整个鸟群中已经找到的当前食物最多的区域，并向其靠近。前者是“自学习”机制，后者则是“相互学习”机制。在这两种机制的作用下，虽然作为个体的小鸟的决策机制非常简单，但整个鸟群则表现出智能性，可以有大概率搜索到食物最多的区域。

将上面布满食物的空间看成解空间，每个区域相当于一个解，区域中食物的多少就是解的质量，即适应值。设计类似于上述鸟群的搜索策略，并通过迭代改进来搜索问题的最优解，就是PSO算法的基本思路。

PSO的搜索策略采用位置-速度更新模型（Kennedy and Eberhart，1995）。在PSO中，待优化问题的解空间中的每个可行解被定义为一个粒子（particle）。粒子包含三种属性：位置（position）、速度（velocity）和适应值（fitness）。其中，适应值可以直接由位置通过一定的算法来计算。对于组合优化问题，位置其实就是问题解的编码；由位置计算适应值的过程便是解码。而粒子的速度决定了粒子飞行的方向和距离，从而决定了该粒子经过迭代后所在的新位置（新的解）。粒子的搜索策略就是通过向局部极值和全局极值学习，不断更新速度和位置。局部极值是粒子经过路径中的最好解，全局极值则是整个粒子群目前找到的最好解。

在一个n维搜索空间中，设第t次迭代后，粒子（ii=1，2，…，SwarmSize；SwarmSize为粒子群大小）的位置为Xi（t）=[xi1（t），xi2（t），…，xin（t）]，速度为Vi（t）=[vi1（t），vi2（t），…，vin（t）]，局部极值记为，全局极值记为。那么在第t+1次迭代中，粒子i速度和位置的更新方式如下（Kennedy and Eberhart，1995）：

其中，j=1，2，…，n，n为解空间的维数；t=1，2，…，T，T是最大的迭代次数。c1和c2是学习因子（learning factor），r1和r2是区间[0，1]内的随机数。(www.xing528.com)

从式（9.1）可以看出，速度的更新公式包含三部分，分别代表粒子自身已有速度、向局部极值学习的部分和向全局极值学习的部分。同时，为了避免搜索越界，粒子的速度被限制在一定的范围内，第j维分量的限制范围为[−vj max，vj max]。

为了改善算法收敛性能，Shi和Eberhar（t1998）在PSO算法中引入了惯性因子w，将速度和位置更新公式修改为：

上述公式中，速度和位置更新公式仍旧是代数意义上的，无法适应组合优化问题的需要。为此，Clerc（2004）将PSO算法的更新公式进行调整，并将其应用到离散问题中，修改后的更新公式表示为：

其中，⊕表示某种操作算子，以给予研究者充分的自由度，可以针对特定优化问题进行专门的设计。