粒子群算法

粒子群算法，也称粒子群优化算法或鸟群觅食算法，来源于对一个简化社会模型的模拟。 PSO 算法属于进化算法的一种，和模拟退火算法相似，它也是从随机解出发，通过迭代寻找最优解，它也是通过适应度来评价解的品质，但它比遗传算法规则更为简单，它没有遗传算法的“交叉”（Crossover）和“变异”（Mutation）操作，它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。粒子群算法是一种并行算法。

算法原理

设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。

PSO 从这种模型中得到启示并用于解决优化问题。 PSO 中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值（fitness value），每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。

PSO 算法是基于群体的，根据对环境的适应度将群体中的个体移动到好的区域。然而它不对个体使用演化算子，而是将每个个体看作是$D$ 维搜索空间中的一个没有体积的微粒（点），在搜索空间中以一定的速度飞行，这个速度根据它本身的飞行经验和同伴的飞行经验来动态调整。第$i$ 个微粒表示为$X_i = (x_{i1}, x_{i2}, ..., x_{iD})$ ，它经历过的最好位置（有最好的适应值）记为$P_i = (p_{i1}, p_{i2}, ..., p_{iD})$ ，也称为$pBest$ 。在群体所有微粒经历过的最好位置的索引号用符号$g$ 表示，即$P_g$ ，也称为$gBest$ 。微粒$i$ 的速度用$V_i = (v_{i1}, v_{i2}, ..., v_{iD})$ 表示。对每一代，它的第$d$ 维$(1 ≤ d ≤ D)$ 根据如下方程进行变化：

$$ v_{id} = w \cdot v_{id} + c_1 \cdot rand() \cdot (p_{id} - x_{id}) + c_2 \cdot rand() \cdot (p_{gd} - x_{id}) x_{id} = x_{id} + v_{id} $$

其中$w$ 为惯性权重（Inertia Weight），$c_1$ 和$c_2$ 为加速常数（Acceleration Constants），rand() 为在[0,1]范围里变化的随机值。此外，微粒的速度$V_i$ 被一个最大速度$V_{max}$ 所限制。如果当前对微粒的加速导致它的在某维的速度$v_{id}$ 超过该维的最大速度$v_{max,d}$ ，则该维的速度被限制为该维最大速度$v_{max,d}$ 。

算法流程

初始化一群微粒（群体规模为$m$ ），包括随机的位置和速度；
评价每个微粒的适应度；
对每个微粒，将它的适应值和它经历过的最好位置$pBest$ 的作比较，如果较好，则将其作为当前的最好位置$pBest$ ；
对每个微粒，将它的适应值和全局所经历最好位置$gBest$ 的作比较，如果较好，则重新设置$gBest$ 的索引号；
根据上述方程变化微粒的速度和位置；
如未达到结束条件（通常为足够好的适应值或达到一个预设最大代数$G_{max}$ ），回到 2。

粒子群算法