PSO粒子群算法

算法简介：

粒子群算法（Particle Swarm Optimization，简称PSO），或称粒子群优化，是属于人工智能算法，公元1995年由肯尼迪（Kennedy）与埃伯哈特（Eberhart）（1995）两位学者所提出，这两位学者借由观察鸟类族群觅食的讯息传递所得到的一个启发，粒子群算法的理论基础是以单一粒子来做为鸟类族群之中的单一个体，于算法中赋予该粒子（个体）拥有记忆性，并能够透过与粒子群体中的其他粒子之间的互动而寻求到最适解。因此在粒子群算法的基础理论可以理解，任一个体（粒子）皆可用有自身移动过程中所产生的记忆与经验，当个体移动的同时，能依造自身的经验与记忆来学习调整自身的移动方向，由于在粒子群算法中，多个粒子是同时移动的，且同时以自身经验与其他粒子所提供的经验进行比对找寻最适当的解，并使自己处于最适解中，该粒子群算法的特性使得粒子不单单受自身演化的影响，同时会对群体间的演化拥有学习性、记忆性，并使粒子本身达到最佳调整。

基本思想：

粒子群算法通过设计一种无质量的粒子来模拟鸟群中的鸟，粒子仅具有两个属性：速度和位置，速度代表移动的快慢，位置代表移动的方向。每个粒子在搜索空间中单独的搜寻最优解，并将其记为当前个体极值，并将个体极值与整个粒子群里的其他粒子共享，找到最优的那个个体极值作为整个粒子群的当前全局最优解，粒子群中的所有粒子根据自己找到的当前个体极值和整个粒子群共享的当前全局最优解来调整自己的速度和位置。

算法的实现：

假设目标函数有n个输入参数：f(x1, x2, …, xn)。

对于每个粒子，它包含的元素：

(1) 当前时刻位置：(x1, x2, …, xn)

(2) 当前时刻的目标函数值（也称为适应度）：f(x1, x2, …, xn)

(3) 该粒子的历史最优位置：(x1_pbest, x2_pbest, …, xn_pbest)

(4) 该粒子的历史最优目标函数值：f_pbest = f(x1_pbest, x2_pbest, …, xn_pbest)

对于全部粒子，它们共有的元素：

(1) 粒子总数：num

(2) 迭代总次数：cnt。粒子群算法也是一个迭代的过程，需要多次迭代才能获取到理想的最优解。

(3) 全局最优位置：(x1_gbest, x2_gbest, …, xn_gbest)

(4) 全局最优目标函数值：f_gbest = f(x1_gbest, x2_gbest, …, xn_gbest)

(5) 位置随机化的上下限：xmin，xmax。迭代开始的时候以及迭代的过程中，均需要对粒子的位置进行随机分布，需要设置随机分布的上下限，不然随机分布偏离得太远，会严重影响优化结果。

(6) 速度的上下限：Vmin，Vmax。迭代过程中，速度也具有一定的随机性，需要限制速度的大小在一定范围内，不然如果速度值太大也会严重影响优化结果。

(7) 速度计算参数：c1、c2。通常取1.0~1.8的值。

粒子位置的更新公式：

参考上述提到的博客，对于每一个粒子的每一个位置参数xi，其位置更新公式如下，其中randf为0~1的随机数，c1与c2通常取1.0~1.8之间的固定值。

为了加快收敛速度，根据速度具有惯性的原理，后来人们提出了在速度计算中增加惯性，也即加上上一轮迭代时该位置参数的速度。如下式，其中w为0~1的参数，通常随着迭代次数的增加，逐渐减小w，因为越到后面可能解就越接近真实解，迭代收敛就越慢，所以需要减小w来放慢速度，否则容易错过最优解。 

 算法流程图如下：

来源：多读点书!