粒子群算法研究综述

控制理论与控制工程 09104046 吕坤

一、粒子群算法的研究背景

人工智能经过半个世纪的发展，经历了由传统人工智能、分布式人工智能到现场人工智能等阶段的发展。到二十世纪九十年代，一些学者开始从各种活动和现象的交互入手，综合地由个体的行为模型开始分析社会结构和群体规律，于是90年代开始, 就产生了模拟自然生物群体(swarm)行为的优化技术。Dorigo等从生物进化的机理中受到启发, 通过模拟蚂蚁的寻径行为, 提出了蚁群优化方法；Eberhart和Kennedy 于1995年提出的粒子群优化算法是基于对鸟群、鱼群的模拟。这些研究可以称为群体智能(swarm-intelligence)。通常单个自然生物并不是智能的,但是整个生物群体却表现出处理复杂问题的能力,群体智能就是这些团体行为在人工智能问题中的应用。粒子群优化(Particle Swarm Optimization ,PSO)最初是处理连续优化问题的, 目前其应用已扩展到组合优化问题。由于其简单、有效的特点, PSO已经得到了众多学者的重视和研究。

二、粒子群算法的研究现状及研究方向

粒子群算法(PSO)自提出以来，已经历了许多变形和改进，包括数学家、工程师、物理学家、生物学家以及心理学家在内的各类研究者对它进行了分析和实验，大量研究成果和经验为粒子群算法的发展提供了各许多合理的假设和可靠的基础，并为实际的工业应用指引了新的方向。目前，PSO的研究也得到了国内研究者的重视，并已取得一定成果。

十多年来，PSO的研究方向得到发散和扩展，已不局限于优化方面研究。PSO算法按其研究方向分为四部分：算法的机制分析研究、算法性能改进研究、算法的应用研究及离散性PSO算法研究。算法的机制分析主要是研究PSO算法的收敛性、复杂性及参数设置。算法性能改进研究主要是对原始PSO算法的缺陷和不足进行改进，以提高原始PSO算法或标准PSO算法的一些方面的性能。目前技术与方法的改进主要是增加算法的多样性、加强局部搜索性及融合其它智能优化算法的技术；PSO算法的应用研究主要是关于如何利用PSO算法对工程技术、经济及社会等需要优化的问题求解，其中包括多目标问题、约束问题、动态问题和大量实际应用问题；离散PSO研究主要针对离散性的优化问题，PSO算法如何进行优化求解，原始PSO算法主要是解决连续性的优化问题，而离散性问题存在特殊性，因此离散性问题的求解，PSO算法需要一些特殊技术进行处理，其研究问题主要包括离散二进制问题和一般组合优化问题。

同时粒子群算法还存在很多的不足需要进一步研究，主要的研究及改进方向集中为以下几方面： (1)粒子群算法的改进

与许多仿生算法一样，粒子群算法现在还只是刚刚起步，本身有很多的不足之处需要改进，尤其它作为一种仿生算法，是对生物群体行为的模拟而产生的，

那么如何对生物群体行为进行进一步研究，改善粒子群算法的性能，将是我们努力的一个方向。’

(2)PSO算法的理论基础的研究

虽然PSO算法已经在很多方面得到应用，但对其理论上的分析还非常薄弱，例如人们一直都没给出很完善的收敛性、收敛速度估计等方面的数学证明。如何利用有效数学工具对PSO算法的收敛性、计算复杂性以及对算法中的参数设置进行分析也是目前的研究热点之一。

(3)PSO算法与其他进化算法的比较和融合

粒子群算法作为一种新兴的算法，虽然在应用方面展现很好的发展前景，但与其它早期提出的算法，如遗传算法、蚁群算法相比，在各个方面都不太成熟，如何引进这些相对成熟的进化算法的优点来弥补粒子群算法目前的不足将是我们今后研究的一个方向。 (4)粒子群算法的应用

算法研究的目的是应用，而PSO算法已经在较广阔的领域崭露头角，并且由于其简单、易操作的特点，PSO算法在收敛速度和精度方面都有了很好的效果，但其中相当一部分仍处于仿真和试验阶段，离实际的问题还有很远的距离，需要作进一步的努力。同时考虑到PSO算法和遗传算法、蚁群算法等有很多相似地方，所以可以将PSO算法用到原来遗传和蚁群应用的工程问题中。如何将PSO算法用到更广阔的领域中去，同时研究应用中存在的问题都是值得关注的热点。

二、粒子群算法(PSO)的基本原理

粒子群优化算法是基于群体的演化算法,其思想来源于人工生命和演化计算理论。Reynolds 对鸟群飞行的研究发现,鸟仅仅是追踪它有限数量的邻居,但最终的整体结果是整个鸟群好像在一个中心的控制之下,即复杂的全局行为是由简单规则的相互作用引起的。PSO即源于对鸟群捕食行为的研究,一群鸟在随机搜寻食物,如果这个区域里只有一块食物,那么找到食物的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域。PSO算法就是从这种模型中得到启示而产生的,并用于解决优化问题。另外,人们通常是以他们自己及他人的经验来作为决策的依据,这就构成了PSO的一个基本概念。

PSO求解优化问题时,问题的解对应于搜索空间中一只鸟的位置,称这些鸟为“粒子”(particle) 或“主体”(agent)。每个粒子都有自己的位置和速度(决定飞行的方向和距离),还有一个由被优化函数决定的适应值。各个粒子记忆、追随当前的最优粒子,在解空间中搜索。每次迭代的过程不是完全随机的,如果找到较好解,将会以此为依据来寻找下一个解。

令PSO初始化为一群随机粒子(随机解),在每一次迭代中,粒子通过跟踪两个“极值”来更新自己:第一个就是粒子本身所找到的最好解, 叫做个体极值点(用pbest表示其位置), 全局版PSO中的另一个极值点是整个种群目前找到的最好解, 称为全局极值点(用gbest表示其位置),而局部版PSO不用整个种群而是用其中一部分作为粒子的邻居,所有邻居中的最好解就是局部极值点(用lbest表示其位置)。在找到这两个最好解后,粒子根据如下的式(1)和式(2)来更新自己的速

度和位置。粒子i的信息可以用D维向量表示，位置表示为Xi(xi1,xi2,...,xiD)T，速度为Vi(vi1,vi2,...,viD)T，其他向量类似。则速度和位置更新方程为

k1kkkkkkVidVidc1rand1k(pbestidxid)c2rand2(gbestdxid) (1) k1kk1xidxidvid (2) k1vid是粒子i在第k次迭代中第d维的速度；c1,c2是加速度系数(或称学习因

子)，分别调节向全局最好粒子和个体最好粒子方向飞行的最大步长, 若太小, 则粒子可能远离目标区域, 若太大则会导致突然向目标区域飞去, 或飞过目标区域。合适的c1,c2可加快收敛且不易陷入局部最优, 通常令c1c20；rand1,2k是[0,1]之间的随机数；xid是粒子i在第k次迭代中第d维的当前位置；pbestid是

粒子i在第d维的个体极值点的位置(即坐标)；gbestid是整个群在第d维的全局极值点的位置。为防止粒子远离搜索空间, 粒子的每一维速度vd都会被钳位在

[vdmax,vdmax]之间，vdmax太大粒子将飞离最好解,太小将会陷入局部最优。假

设将搜索空间的第d维定义为区间[xdmax,xdmax]，则通常vdmaxkxdmax,0.1k1.0，每一维都用相同的设置方法。

四、粒子群算法的基本流程

1、PSO的具体实现步骤如下： Stepl：参数初始化。

在初始范围内，随机初始化一群粒子，即设置种群规模N、粒子的初始位置xid、初始速度vid (其中i1,2,...,N)，其中位置和速度通常是在允许的范围内随机产生的， 每个粒子的pbest坐标设置为其当前位置, 且计算出其相应的个体极值(即个体极值点的适应度值) ,而全局极值(即全局极值点的适应度值) 就是个体极值中最好的,记录该最好值的粒子序号, 并将gbest设置为该最好粒子的当前位置。

Step2：根据式(1)和式(2)对粒子的速度和位置进行更新； Step3：计算每个粒子的适应值。 Step4：判断每个粒子的个体最优值。

对每个粒子，将其当前的适应值和上一次的个体最优值pbest,进行比较，如果当前适应值优于pbest，则令pbest取当前适应值，否则，个体最优值

仍为原来的pbest。

Step5：判断整个粒子群的全局最优值。

比较当前每个粒子的个体最优值，找出当前迭代中的全局最优值，与历史 全局最优gbest比较，如果优于gbest，则令gbest取当前迭代中的全局最优值，否则，全局最优gbest还取原来的值。

Step6：判断是否满足终止条件。满足则转入Step7；否则，转Step2，继续迭代。 Step7：输出全局最优gbest，算法进行结束。 其算法流程图如下图所示：

开始初始化更新粒子的速度和位置计算每个粒子的适应值更新个体最优值判断粒子群的全局最优值满足终止条件？是否输出全局最优值结束图1 粒子群算法流程图

2、 粒子群算法的控制参数

(1) 惯性权重

粒子群算法分为三部分：vid,c1rand()(pidxid)和c2rand()(pgdxid)。没有第一部分vid，相当于是局部搜索算法(local search aglorthm)；没有第一部分，所有粒子群很容易趋向于同一样位置。只有当全局最优解刚好在初始的搜索空

间，会有更大的机会使PSO找到最终解。因此，最后的解严重依赖于初始种群，所以没有第一部分，算法很可能是展示局部搜索能力。另一方面，如果增强第一部分vid，则粒子就会扩展搜索空间的能力，也就是有能力扩展新的搜索区域。所以，如果增强第一部分vid，则算法的全局搜索能就增强。局部搜索能力和全局搜索能力都有利于解决一些种类的问题。因此，算法的全局搜索与局部搜索必须存在一个平衡。对不同问题存在不同的平衡力，而惯性权重的引入起到一个平衡局部搜索能力和全局搜索能力的作用。从试验的效果来说，当权重固定值的范围是[0.9,1.2]时，优化会得到一个好的结果，能更好地找到全局最优解。

从试验中可以看到，大的惯性权重对初始解有更少依赖性，PSO算法对探索新的区域有更强的能力。权重起到平衡全局搜索与局部搜索能力的功能。一个大的惯性权重有利于全局探测能力(搜索新的区域)，而一个小的惯性倾向于局部探索，精细搜索目前的小区域。对于任何优化搜索算法，一个好的思想早期具有更强的探测能力(全局搜能力)，能够发现好的解种。晚期需要更强的探索能力(局部搜索能力)去搜索局部好的解区域。因此，权重W是一个随时间递减函数而不是一个固定不变的值。开始赋给大值，而后线性减少到一定值，一个好的递减值范围是从1.4到O.4。Y.Shi和R.Eberhart所做的实验再次说明采用权重线性递的PSO算法，其性能得到很大的提高且能获得更好结果。

(2)群体规模m

显然m越大，相互协同搜索的粒子就越多，更能发挥PSO的搜索能力。然而群体过大，需要计算的时间大幅增加。有文献反应，群体增长到一定数量，再增加对搜索算法能力并没多大增加。如果m=l，PSO算法就是个体搜索技术，没有全局信息可用，显然很容易陷入局部最优。当m很大时，PSO算法全局优化能加强，不仅搜索时间增加长，而且收敛全局最优点的速度将非常慢。目前，在更多的文献中，这个参数取值为20。

(3) 学习因子：c1和c2

在PSO算法中，学习因子是控制粒子向自我历史经验和群体最优个体学习的因子，从而控制向群体内或邻域内最优点靠近。与权重作用类似，学习因子也能起到平衡局部搜索与全局探索能力，只不过学习因子值越大，越有利于算法收敛，增加局搜索能力，这与权重刚好相反。学习因子通常等于2，不过也有其他的取值。但是一般两者相等，并且范围在0和4之间。在PSO算法的理论分析中，对权重与学习因子取值作了比较深入研究，其取值大小与权重有关联。分析结果基本与相关文献采用的取值基本一致。Zhang L等利用试验也对权重与学习因子参数作了详细分析，得到结果与理论分析结果基本一致。

(4)最大速度Vmax

最大速度决定粒子在一次迭代中最大的移动距离。若其值较大，探索能力增强，但是粒子容易飞过最好解。较小时，开发能力增强，但是容易陷入局部最优。

(5)停止准则

一般使用最大迭代次数或可以接受的满意解作为停止准则。 (6)拓扑结构

对于拓扑结构，PSO算法创始者最早就对此进行了研究。提出几中不同结构模型：其全局模型、环形模型和局部模型。全局模型PSO将整个群体作为粒子的邻域，速度快，不过有时会陷入局部最优；局部模型PSO将索引号相近或者位置相近的个体作为粒子的邻域，收敛速度慢一点，不过很难陷入局部最优。在实际应用中，可以先用全局PSO找到大致的结果，再用局部PSO进行搜索。本文所采用模型是全局模型。

（7）粒子空间的初始化

与其化智能随机搜索算法一样，PSO较好地选择粒子的初始化空间，将大大缩短收敛时间。但真正要较好选择初始化却是问题依赖的，而真正随机搜索算法与问题无关。所以更为合理的初始化是使初始的结果完全随机性的。例如，对粒子的位置初始应该让每粒子在整个搜索空间按均匀分布取样，这才是较为合理。参数选择是算法一个很重的问题，参数选择是否恰当直接影响算法的性能。对参数选择其实是问题依赖性的，对参数分析也是PSO算法分析研究一个方向，不少文献对算法作过实验或理论分析。。

五、结论与展望

粒子群优化(PSO)是一种新兴的基于群体智能的启发式全局随机搜索算法，具有易理解、易实现、全局搜索能力强等特点，为各个领域的研究人员提供了一种有效的全局优化技术。

由于PSO毕竟是一种新兴的智能优化算法，其研究还处于起步阶段，还存在

许多问题，

虽然已经应用在多个领域，但缺乏有力的理论基础支持和严谨的数学证明过程，因此在如几个方面还有待进一步的研究和改进：在以下方面仍然值得进一步研究：

(1) 理论研究：虽然目前对PSO稳定性和收敛性的证明已取得了一些初步成

果，但自诞生以来其数学基础一直不完备，特别是收敛性一直没有得到彻底解决。因此，仍需要对PSO的收敛性等方面进行进一步的理论研究。 (2) 控制参数自适应：虽然对PSO参数的改进策略等方面已取得了一定进展，

但仍然有很大的研究空间；

(3) 混合PSO：混合进化算法是进化算法领域的趋势之一，与其它进化算法

或传统优化技术相结合，提出新的混合PSO算法，甚至提出基于PSO的超启发式搜索算法(hyper-heuristics)，使算法对不同种类的问题具有尽可能好的普适性，并能“更好、更快、更廉(good enough – soon enough – cheap enough)”地得到问题的解，也是一个很有价值的研究方向。 (4) 应用研究：算法的有效性和价值必须在实际应用中才能得到充分体现。

广大科学与工程领域的研究人员，在各自的专业背景下，利用PSO解决各种复杂系统的优化问题，进一步拓展其应用领域，是一项十分有意义的工作。此外，由于PSO本质上是一种随机搜索算法，现场工程技术人员对它的可靠性仍难免心存疑虑，将PSO(或与工业系统在役技术结合)进行实用化推广，仍是一项任重而道远的任务。