智能计算之粒子群算法(PSO)介绍

1. 简介(思想)

2. 研究发展

3. 算法步骤

4. 应用举例

1. 简介(思想)

粒子群优化算法（Particle Swarm Optimization，PSO）是进化计算的一个分支，是一种模拟自然界的生物活动及群体智能的随机搜索算法。PSO模拟了自然界鸟群觅食和鱼群捕食等过程。通过群体中的协作寻找到问题的全局最优解。它是1995年由美国学者Eberhart和Kennedy提出的一种全局搜索算法，现在已经广泛应用于各种工程领域的优化问题之中。

2. 研究发展

其中，我们可以看一下鸟群觅食和粒子群优化算法的基本定义对照图如下：

而鸟群觅食到粒子群优化算法的关系示意图如下：

3. 算法步骤

PSO的算法步骤：
（1）初始化所有粒子，即给它们的速度和位置赋值，并将个体的历史最优pBest设为当前位置，群体中的最优个体作为当前的gBest。
（2）在每一代的进化中，计算各个粒子的适应度函数值。
（3）如果当前适应度函数值优于历史最优值，则更新pBest。
（4）如果当前适应度函数值优于全局历史最优值，则更新gBest。
（5）对每个粒子i的第d维的速度和位置分别按照公式6.1和公式6.2进行更新：

在这里插入图片描述

而这两个公式在二维空间中的关系如图所示：

（6）判断是否达到了结束条件（具体怎么定义后面会提），否的话就转到（2）继续执行，否则输出gBest并结束。

PS0算法流程图和伪代码如下：

在这里插入图片描述

4. 应用举例

我们接下来用一个实例实现一下PSO算法：

解题步骤如下：

5. 粒子群优化算法的改进研究

粒子群优化算法的研究内容和改进方向如下：

5.1 理论改进

5.2 拓扑结构改进

(1) 静态拓扑结构

全局版本（Global Version PSO, GPSO）和局部版本（Local Version PSO, LPSO）两个主要范式。

两者主要区别在于社会网络结构的定义不同。

从全局和局部其实也不难看出，粒子在更新速度和位置的时候，前者使用到的是自身的历史最好位置pBest和整个群体中最好的位置gBest，而后者的话，每个粒子所处的“社会”不是整体，而是一个小的邻域。更新速度和位置时用到的除了自身最好的历史位置pBest外，还用到邻域中的最好位置lBest作为更新的向导。

不难发现，后者的多样性更好，在处理复杂的问题的时候，LPSO比GPSO会表现出更好的性能。