粒子群综述

粒子群优化算法综述

第一章 概述

粒子群优化算法(PSO)是近年来被广为关注和研究的一种智能优化算法，源于对鸟群捕食系统的模拟。它收敛速度快、易实现并且仅有少量参数需要调整，因而一经提出就成为智能优化与进化计算领域的一个新的研究热点，目前己经被广泛应用于目标函数优化、动态环境优化、神经网络训练、模糊控制系统等许多领域[1]。其中最具应用前景的领域包括多目标问题的优化、系统设计、分类、模式识别、生物系统建模、规划、信号处理、决策和模拟等。粒子群优化算法的理论背景是“人工生命”。人工生命(artificial life)是用来研究具有某些生命基本特征的人工系统，其中一个重要部分是利用生物技术来研究计算问题。粒子群优化算法的诞生来源于一种生物一社会系统，该生物一社会系统的研究集中于简单个体组成的群落与环境之间的关系，以及个体之间的互动行为。群居个体以集体的力量进行觅食、御敌，单个个体只能完成简单的任务，而由单个个体组成的群体却能完成复杂的任务，这种群体所表现出来的“智能”，就称之为群体智能(Swarm Intelligence，SI)[2]。而从群居昆虫互相合作进行工作中得到启迪，研究其中的原理，并以此原理来设计新的求解问题的算法被称为群智算法。在计算智能领域主要有两种基于群智能的算法，一种是蚁群算法(Ant Colony Optimization，ACO)，它是对蚂蚁群落食物采集过程的模拟，己经成功运用在很多离散优化问题上[3]；另一种是粒子群优化算法，最初由Jim Kennedy于1995年提出并成功的用于函数优化，后来又进行了有效的拓展[4]。但是，PSO的发展历史尚短，在理论基础与应用推广上都还存在一些问题有待解决。当PSO应用于高维复杂问题优化时，往往会早熟收敛(premature)，也就是种群在还没有找到全局最优点时已经聚集到一点停滞不动。这些早熟收敛点，有可能是局部极小点，也有可能是局部极小点邻域中的一个点。换句话说，早熟收敛并不能保证算法收敛到局部极小点。因而，对算法早熟收敛行为的研究可为算法的进一步改进奠定基础。此外，PSO在接近或进入最优点区域时的收敛速度也比较缓慢。实际上对PSO的研究发现，PSO早期收敛速度较快，但到寻优的后期，其结果改进则不甚理想。

第二章 粒子群优化算法

起初Kennedy和Eberhart[4]只是设想模拟鸟群觅食的过程，但后来发现PSO是一种很好的优化工具。与其他进化算法相类似，PSO算法也是通过个体间的协作与竞争，实现复杂空间中最优解的搜索。PSO第一步生成初始种群，即在可行解空间中随机初始化一群粒子，每个粒子都为优化问题的一个可行解，并由目标函数为之确定一个适应值。每个粒子将在解空间中运动，并由一个速度决定其方向和距离。通常粒子将追随当前的最优粒子，并经逐代搜索最后得到最优解。在每一代中，粒子将跟踪两个极值，一个是粒子本身迄今找到的最优解pbest，另一个是整个种群迄今找到的最优解gbest。

2．1 PSO算法基本原理

自然界中一些生物的行为特征呈现群体特征，可以用简单的几条规则将这种群体行为(Swarm Behavior)在计算机中建模，实际上就是在计算机中用简单的几条规则来建立个体的运动模型，但这个群体的行为可能很复杂。例如，Reynolds使用了下列三个规则作为简单的行为规则[5]：

1) 向背离最近的同伴的方向运动； 2) 向目的运动： 3) 向群体的中心运动。

这即是著名的Bold(Bird—oid)模型。在这个群体中每个个体的运动都遵循这三条规则，通过这个模型来模拟整个群体的运动。PSO算法的基本概念也是如此每个粒子(Particle)的运动可用几条规则来描述，因此PSO算法简单，容易实现，越来越多地引起人们的注意。设想这样一个场景：一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有的鸟都不知道食物在哪里，但是它们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢?最简单有效的就是搜寻目前离食物最近的鸟的周围区域。PSO算法就从这种生物种群行为特性中得到启发并用于求解优化问题。在PSO中，每个优化问题的潜在解都可以想象成d维搜索空间上的一个点，我们称之为“粒子”(Particle)。粒子在搜索空间中以一定的速度飞行，这个速度根据

它本身的飞行经验和同伴的飞行经验来动态调整。所有的粒子都有一个被目标函数决定的适应值(fitness value)，并且知道自己到目前为止发现的最好位置(particle best，记为pbest)和当前的位置。这个可以看作是粒子自己的飞行经验。除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置(global best，记为gbest)(gbest是在pbest中的最好值)，这个可以看作是粒子的同伴的经验。每个粒使用下列信息改变自己的当前位置：1)当前位置；2)当前速度；3)当前位置与自己最好位置之间的距离；4)当前位置与群体最好位置之间的距离。优化搜索正是在由这样一群随机初始化形成的粒子而组成的一个种群中，以迭代的方式进行。

2．2 PSO算法数学描述

数学描述[6]可以是：假设在一个d维的目标搜索空间中，有m个代表潜在问题解的粒子组成的一个种群将

，其中

m表示第i个粒子在d维解空问的一个矢量点。

m

代入一个与求解问题相关的目标函数可以计算出相应的适应值。用

记录第i个粒子自身搜索到的最好点(所谓最好，是指计算得到的适应值为最小，即pbest)。而在这个种群中，至少有一个粒子是最好的，将其编号记为g，则

就是种群搜索到的最好值(即

gbest)，其中g∈{1,2,…,m}。而每个粒子还有一个速度变量，可以用

m表示第f个粒子的速度。

PSO算法一般是采用下面的公式对粒子进行操作的。

(2．1a)

(2．2a)

其中粒子的标号i=1,2,…,m：k为迭代代数；学习因子c1、c2是两个正常数，一般取值为2；r1、r2是均匀分布于[0，1]之问的两个随机数。为了控制形

和

的值在合理的区域内，需要指定

来限制。

公式(2．1a)主要通过三部分来计算粒子i新的速度：粒子i前一时刻的速度，粒子i当前位置与自己最好置之间的距离，粒子i当前位置与群体最好位置之间的距离。粒子i通过公式(2．2a)计算新位置的坐标。通过式(2．1a)、(2．2a)粒子，决定下一步的运动位置。在图2．1中，以两维空间为例描述了粒子根据公式(2．1a)、(2．2a)从位置到移动的原理。

如果从社会学的角度来看，公式(2．1a)的第一部分称为记忆项，表示上次速度大小和方向的影响；公式的第二部分称为自身认知项，是从当前点指向此粒子自身最好点的一个矢量，表示粒子的动作来源于自己经验的部分；公式的第三部分称为群体认知项，是一个从当前点指向种群最好点的一个矢量，反映了粒子间的协同合作和知识的共享。粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动，这与人类的决策何其相似，人们通常也是通过综合自身己有的信息和从外界得到的信息来作出决策的。

图2.1 粒子移动原理图

2．3 基本PSO的算法步骤

从前述分析可见该PSO算法是一种全局优化算法，其计算步骤如下：

基本PSO算法具体实现[6] 选定PSO种群规模m： 设X[i]为种群中第i个粒子的位置； 设fitness[i]为第i个粒子的适应值；

设V[i]为第i个粒子的速度； 设gBest为种群最好粒子的标号；

设Pbest[i]为第i个粒子自身搜索到的最好点位置；

设Pbest_fitness[i]为第i个粒子自身搜索到的最好适应值，即Pbest[i]处的适应函数值；

Stepl：(初始化)对于每一个种群中的粒子i，i=1，2,?，m Stepl.1: 随机初始化X[i] Step1.2：随机初始化v[i]

Stepl.3：计算fitness[i]，并以此初始化Pbest_fitness[i] Stepl.4：以种群中最好适应值的粒子标号初始化gBest Stepl.5：以X[i]初始化Pbest[i]

Step2：循环迭代，直到满足PSO终止条件 Step2.1：选择算法控制参数w；

Step2.2：对每个粒子，计算其适应值fitness[i]。若fitness[i]< Pbest_fitness[i]，则

Pbest_fitness[i]=fitness[i]，且Pbest[i]=X[i]

Step2.3：搜索gBest值：若Pbest_fitness[i]< Pbest_fitness[gBest]，则gBest=i； Step2.4：对每个粒子，依据公式(2．1b)、(2．2b)更新V[i]和X[i]值

2．4 PSO算法的改进

2.4.1 加入惯性权重因子w的PSO算法[6]

正如先前所述，公式(2．1a)由三部分组成：第一部分是粒子先前的速度项，即分是导致粒子速度变化的两项，即

和

。

，第二部分和第三部

一方面，公式(2．1a)如果没有后两项，粒子将保持在相同的方向上以当前的速度“飞翔”至下一个点，直至达到边界值。这样的PSO将不能找到一个可接受的解，除非这样的飞行轨迹是一种合理的方案，而这在现实中是非常少见的。

另一方面，如果公式(2．1a)没有第一项，那么“飞翔”粒子的速度仅仅取决于粒子的当前位置和它们最好的历史位置。速度自身是没有记忆性的。假设在开始的时候，粒子i正好是整体最好所在的点，那么粒子i将以速度为0“飞翔”，这将保持粒子此次的位置不变，直到出现新的一个最好点替代粒子i。同时，每一个粒子将向自身最好点和整体最好点的质心方向“飞翔”。推荐c1和c2都取常数2，这正如文献[7]中提到的那样，这样使得“社会认知”和“个体经验”的权重为l。在这种状况下，各个粒子逐渐的向当前最好的位置处收缩，直到出现新的最好值，而那样粒子群体又向这个位置收缩。因此可以想象，在没有第一项情况下的PSO搜索过程，其搜索空间将在迭代中逐渐衰退，这类似与局部搜索算法。只有当全局最好点包含在