粒子群算法

粒子群算法（ Particle Swarm Optimization, PSO）最早是由Eberhart和Kennedy于1995年提出，它的基本概念源于对鸟群觅食行为的研究，它具有很强的全局搜索能力。

PSO算法就是模拟一群鸟寻找食物的过程，每个鸟都是PSO中的一个粒子，也就是我们需要求解问题的可能解，这些鸟在寻找食物的过程中不断的改变自己的位置与速度。然后记录每个粒子（鸟）的最合适位置，并且从中得到全局的最优位置。通过不断的循环，最后得到的全局位置可能就是食物的位置。

PSO算法步骤如下：

Step1: 初始化粒子群，即随机给定m个粒子的初始位置与初始速度。（通常，粒子群的数目是根据具体问题而定的，一般设置在10到50之间。其实对于大部分的问题10到20个粒子就可以取得很好的效果。）

Step2: 给定适应度函数，计算每个粒子的适应值。（适应度函数就是如何计算当前鸟与食物的距离。用来判断是否是最佳位置。假设求y=1-cos(3*x)*exp(-x)在[0,4]中的最大值，那么y的值就是适应值，而这个函数就是适应度函数。）

Step3: 计算惯性权值w（w较大促进全局搜索，w较低促进精细的局部搜索。因此动态递减的降低w是比较合适的,来自刘衍民的《粒子群算法的研究及应用》的论文中有如下一个公式:w=w_max-(w_max-w_min)*t/T_max，其中，w_max表示最大惯性权重；w_min表示最小惯性权重；t表示当前迭代次数；T_max表示最大迭代次数，在大多数应用中w_max=0.9,w_min=0.4）

Step4: 对每个粒子，比较它的当前的适应值和它之前经历过的最好位置Pi的适应值。如果更好，则更新Pi。

Step5: 对每个粒子，比较它当前的适应值和种群中最好的位置Pg的适应值。如果更好，则更新Pg。（Pg只有一个值。）

Step6: 对粒子进行位置与速度的更新。(速度的更新公式:vi=wvi c1r1­(pi-xi) c2r2(pg-xi)，其中等式右边的vi表示上一次粒子i的速度，c1为认知常数一般取2，r1是0到1之间的随机数，c2是社会知识常数一般取2，r2是0到1之间的随机数，pi是个体i的最优解，pg是群体的最优解，w是惯性权重，xi是i当前位置。位置更新公式:xi=xi vi，其中等式右边的xi是i上一次的位置，vi是i这次的速度。)

Step7: 是否满足停止条件（足够好的位置或最大的迭代次数），若满足停止条件则输出Pg，否则转到Step2继续进行直到满足条件。