简述粒子群算法的原理及改进

摘要：本文主要介绍了粒子群（Praticle Swarm Optimizer, PSO）算法，它是一种新的基于群体智能的优化算法，是在鸟群觅食行为规律的基础上提出的。他其结构简单、参数调整简单易行，更适合计算机编程处理，但在该算法中，如果粒子速度始终保持较大，容易“飞越”解空间中的最优区域，造成发散现象，收敛不到最优解，如果从惯性权重的自适应方面来调整，就可以很好的解决该问题。

关键词：粒子群优化算法；惯性权重的自适应；收敛性

中图分类号：TP311文献标识码：A文章编号：1009-3044(2008)12-2pppp-0c

PSO Algorithm and the Principle of Improving

XU Xu,JIANG Fei

(Department of Computer Science and Technology Suzhou college,Suzhou 234000,China)

Abstract:This text mainly introduced a grain sons(the Optimizer of the Praticle Swarm, PSO) calculate way,it is a kind of new according to community intelligence of excellent turn calculate way,is the foundation which looks for food behavior regulation in the birds up put forward. He its structure is simple,the parameter adjust to go in brief and easily,the more in keeping with calculator weaves a distance a processing,but in that calculate way, if the grain sub- speed keeps always more and greatly,the superior district in the easy "fly more" solution space,result in to dissipate of phenomenon,could not refrain from rash action the superior solution,if heavy from the inertial power of adjust from the orientation aspect,it can be good to resolve that problem.

Key words:particle swarm optimization algorithm;the inertial power is heavy of from orientation;Astringency

1 引言

粒子群优化算法（Particle Swarm Optimization，简称PSO）是继遗传算法（Genetic Algorithms，简称GA）、蚁群算法(Ant Colony Optimization，简称ACO)之后提出的一种新型进化计算技术，基本思想来源于对鸟群简化社会模型的研究及对鸟群觅食过程中迁徙和聚集行为的模拟，该算法利用信息共享机制，使个体之间可以相互借鉴经验以促进整个群体的发展，具有典型的群体智能特性。PSO于1995年由Kennedy博士和Eberhart博士提出[1]，引起了学者们的广泛关注，成为了一个新的研究热点，已在化工系统、电力系统、机械设计、通讯、机器人、经济、图像处理、生物信息、医学、运筹学等多个领域中得到了应用[2]。

2 PSO的基本原理

PSO模拟鸟群的捕食行为。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。PSO从这种模型中得到启示并用于解决优化问题。PSO中每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化函数决定的适应值(fitness value)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。

PSO初始化为一群随机粒子P(随机解)。然后通过叠代找到最优解。在每一次叠代中，粒子P通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解。这个解叫做个体极值点pbest. 另一个极值是整个种群目前找到的最优解。这个极值是全局极值点gbest。在找到这两个最优解时, 粒子根据如下的公式来更新自己的速度和新的位置：

其中，下标i代表第i个粒子，下标j代表速度（或位置）的第j维，上标k代表迭代代数，如vijk和vijk分别是第i粒子（Pi）在第k次迭代中第j维的速度和位置，两者均被限制在一定的范围内；c1和c2是学习因子，通常c1、c2∈[0，4]；r1和 r2是介于[0,1]之间的随机数；pbest ijk是粒子Pi在第j维的个体极值的坐标；gbestj k是群体在第 j 维的全局极值的坐标。

3 标准PSO算法

粒子群优化算法(Particle Swarm Optimization，PSO )是群体智能算法的一种，它是由美国社会心理学家James Kennedy和电气工程师Russell Eberhart 在1995年提出的，其基本思想是对鸟群、鱼群的觅食过程中的迁徙和聚集行为的模拟，并利用了生物学家Frank Heppner的生物群体模型。

PSO算法不像遗传算法那样对个体进行选择、交叉和变异操作，而是将群体中的每个个体视为多维搜索空间中一个没有质量和体积的粒子，这些粒子在搜索空间中以一定的速度飞行，并根据粒子本身的飞行经验以及同伴的飞行经验对自己的飞行速度进行动态调整，即每个粒子通过统计迭代过程中自身的最优值和群体的最优值来不断地修正自己的前进方向和速度大小，从而形成群体寻优的正反馈机制。PSO算法就是这样依据每个粒子对环境的适应度将个体逐步移到较优的区域，并最终搜索、寻找到问题的最优解。

在PSO算法中，用粒子的位置表示待优化问题的解，每个粒子性能的优劣程度取决于待优化问题目标函数确定的适应值，每个粒子由一个速度矢量决定其飞行方向和速率大小。设在一个 维的目标搜索空间中，有 个粒子组成一个群体，其中，在第 次迭代时粒子 的位置表示为Xi(t)=(xi1(t), xi2 (t) …, xid(t))，相应的飞行速度表示为 。开始执行PSO算法时，首先随机初始化 个粒子的位置和速度，然后通过迭代寻找最优解，在每一次迭代中，粒子通过跟踪两个极值来更新自己的速度和位置：一个极值是粒子本身迄今搜索到的最优解，称为个体极值，表示为Pbest(t)=( P1best(t), P2best(t),…Pdbest(t))；另一个极值是整个粒子群到目前为止找到的最优解，称为全局极值，表示为Pbest(t)=( P1best(t), P2best(t),…Pdbest(t))。在第t+1次迭代计算时，粒子i根据下列规则来更新自己的速度和位置：

式中w-为惯性权重；C1，C2：为两个学习因子，一般取为2；rand1和rand2为两个均匀分布在（0，l）之间的随机数；i=1,2,…,m；k=1,2,…,d。另外，粒子在每一维的速度Vi都被一个最大速度Vmax所限制。如果当前粒子的加速度导致它在某一维的速度超过该维上的最大速度Vmax，则该维的速度被限制为最大速度。式（3）中第1部分可理解为粒子先前的速度或惯性；第2部份可理解为粒子的“认知”行为，表示粒子本身的思考能力；第3部分可理解为粒子的“社会”行为，表示粒子之间的信息共享与相互合作。

4 PSO算法的改进

在标准粒子群算法中，如果粒子速度始终保持较大，容易“飞越”解空间中的最优区域，造成发散现象，收敛不到最优解[3]。为了保证PSO算法的收敛性，惯性权重通常情况下是线性减小的。若 能随算法迭代的进行而线性减小，将显著改善算法的收敛性能。令w-max为最大加权系数，w-min为最小加权系数，iter为当前迭代次数，itermax为算法总迭代次数，则有：

一般w-max取值为0.9，W-min取值为0.4。更新过程中，粒子每一维的最大速率限制在Vmax粒子每一维的坐标也被限制在允许范围之内。同时，个体极值Pbest和群体极值gbest在迭代过程中不断更新，最后输出的gbest就是算法

寻到的最优解。

5 结论

本文主要讲述了粒子群算法的基本原理和标准算法，介绍了从惯性权重的自适应方面调整来优化PSO的算法，该算法可以保证PSO算法的收敛性，是一种比较比较理想的算法。

参考文献：

[1]Kennedy J,Eberhart R.Particle Swarm Optimization[C].Proceedings of IEEE International Conference on Neural Networks,Perth, Australia,1995:1942-1948.

[2]刘波,王凌,金以慧,等.微粒群优化算法研究进展[J].化工自动化及仪表,2005,32(3):1-6.

[3]陈曦,傅明.改进粒子群算法在动态交通分配问题中的应用[J].计算技术与自动化,2006,25(2)60-63.

收稿日期：2008-01-26

作者简介：徐旭（1981-）男，安徽宿州人，助教，硕士在读，研究方向：数据挖掘。

注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”