并行分布式进化计算最新章节_陈伟能著

1.2.1 粒子群优化算法

1.算法基本思想

粒子群优化（Particle Swarm Optimization，PSO）算法是Eberhart和Kennedy于1995年提出的一种全局搜索算法。粒子群优化算法借鉴了自然界中鸟群、鱼群觅食等群体智慧涌现现象中的思想，融入了社会心理学中的个体认知（self-cognition）和社会影响（social-influence）的理论。

在自然界的鸟群觅食过程中，小鸟是结合各自的探索和群体的合作最终发现食物的位置的。一开始鸟群随机地飞行觅食，它们都不知道食物具体的位置，但是能通过气味浓度等方式间接了解自身和食物之间的距离，随着不断飞行，小鸟能不断记录、更新自身曾经到达的距离食物最近的位置，并且通过交流知道整个群体目前已找到的最优的位置，进而指导飞行方向，调整自身飞行速度和所在位置，最终使群体聚集到食物位置附近。

在粒子群优化算法中，鸟群中的每只小鸟被称为一个“粒子”，即搜索空间中的一个有效解。每个粒子具有各自的位置向量和速度向量，食物的位置即全局最优解的位置。通过随机生成一定规模的粒子作为一组初始有效解，结合每个粒子自身历史最优位置和全局历史最优位置迭代地更新各自的速度向量和位置向量，在搜索空间中探索和开发，最终找到全局最优解。

粒子群优化算法的拓扑结构又称为社会结构，指的是算法中的个体进行相互协同的拓扑结构。根据拓扑结构的不同，粒子群优化算法有不同的版本，其拓扑结构包括静态拓扑结构和动态拓扑结构。静态结构的粒子群优化算法主要有全局版本PSO（Global Version PSO，GPSO）和局部版本PSO（Local Version PSO，LPSO），两种版本的区别主要在于社会结构的定义不同。在GPSO中，整个种群构成一个星形的“社会”，即粒子在进行速度和位置更新时，将会使用自身的历史最好位置 p _Best 和种群中最好位置 g _Best 作为向导。而在LPSO中，整个种群的拓扑结构有环形结构、齿形结构、冯·诺依曼结构等，每个粒子所处的“社会”仅仅是一个小的邻域，即粒子在进行速度和位置更新时，将会使用自身的历史最好位置 p _Best 和邻域中的最好位置 l _Best 作为向导。如此，LPSO能用于作为更新向导的位置比GPSO多，因此LPSO的多样性更好，在处理复杂问题时的表现往往比GPSO更好，更不容易陷入局部最优。但LPSO并不能完全解决粒子群优化算法落入局部最优的问题，因此动态拓扑结构的粒子群优化算法尝试在不同阶段采用不同的拓扑结构，动态地调整算法的探索能力和开发能力，在保持种群多样性和算法收敛性上取得平衡，动态拓扑结构的粒子群优化算法的代表性工作包括逐步增长法、最小距离法、重新组合法、随机选择法。本节以静态拓扑结构中的GPSO为代表介绍粒子群优化算法的流程。

2.算法流程

对于一个维数为 D 的问题，每个粒子 i 具有两个在迭代过程中更新的向量，即速度向量和位置向量，其中速度向量决定粒子运动的方向和速率，位置向量则代表搜索空间的位置，用于评估解的适应值。每个粒子维护一个自身历史最优位置向量 p _Best ，在迭代过程中，每个个体到达了一个适应值更好的位置则更新自身的 p _Best 。种群维护一个全局最优向量 g _Best ，代表所有个体中最优的 p _Best ，能指导种群向全局最优区域收敛。

相比遗传算法等进化算法，粒子群优化算法只需要迭代地执行速度更新和位置更新的过程，而无须进行选择、交叉、变异等操作，实现更简单，效率更高，并行性能更好。

粒子群优化算法的流程图和伪代码如图1-15所示，具体步骤如下。

图1-15 粒子群优化算法的流程图和伪代码

1）初始化 ：随机初始化每个粒子个体的速度和位置，将个体的当前位置作为自身历史最优 p _Best ，而种群中最优的 p _Best 作为 g _Best 。

2）适应值评估 ：在每一代进化中计算各粒子的适应值函数值。

3）个体历史最优更新 ：如果当前粒子 i 适应值比其历史最优值要好，则更新 p _Best 为当前位置向量 x _i 。

4）全局历史最优更新 ：如果该粒子 i 的适应值比全局历史最优值要好，则更新 g _Best 为粒子 i 的位置向量 x _i 。

5）速度和位置更新 ：对每个粒子 i 的第 d 维的速度和位置分别按照式（1-5）和式（1-6）更新。这两个公式在二维空间中的关系如图1-16所示。

图1-16 粒子群优化算法中粒子的速度与位置在二维空间中的关系和更新示意图

式（1-5）中 ω 是惯性权重（inertia weight），表示保持粒子原来速度的趋势大小，文献[67]的实验表明， ω 取值在[0.9，1.2]之间时，算法收敛到全局最优的成功率较高，文献[68]建议将 ω 初始化为0.9，然后随进化过程线性初始化为0.4， c ₁ 和 c ₂ 是加速系数（acceleration coefficients），也称学习因子，一般取固定值2.0[67，68]，和是两个[0，1]区间上的随机数。需要注意的是，在更新过程中，速度更新需要按照用户设定的最大速度参数 v _max 来限制速度的范围。另外，式（1-6）中的位置更新也必须是合法的，在每次更新后需要检查是否在问题空间中，否则需要进行重新随机设定或限定在问题空间边界的修正。

6）结束条件判断 ：如果还未达到结束条件，则转回步骤2，否则输出 g _Best 并结束。