angeline

微粒群优化算法

王元元;薛继华

【摘要】微粒群算法是继蚁群算法之后提出的又一种新型的进化计算技术,具有典

型的群体智能的特性.介绍了微粒群算法的基本原理及其改进算法,从群体组织与进

化以及混合微粒群算法等方面对国内外微粒群算法的研究进展进行综述.

【期刊名称】《南通纺织职业技术学院学报》

【年(卷),期】2009(009)001

【总页数】4页(P21-24)

【关键词】进化计算;微粒群算法;群体智能

【作者】王元元;薛继华

【作者单位】南通职业大学,南通,226007;南通职业大学,南通,226007

【正文语种】中文

【中图分类】TP301.6

20世纪90年代，就产生了模拟自然生物群体（swarm）行为的优化技术.Dorigo

等从生物进化的机理中受到启发，通过模拟蚂蚁的寻径行为，提出了蚁群优化方法；

Kennedy和Eberhart[1]等于1995年提出的微粒群算法（PSO）是对鸟群、鱼群

的模拟.这些研究可以称为群体智能（swarmintelligence）.通常单个自然生物并

不是智能的，但是整个生物群体却表现出处理复杂问题的能力，群体智能就是这些

团体行为在人工智能问题中的应用.微粒群算法（PSO）的基本思想来源于对鸟群

简化社会模型的研究及行为模拟.群体中的鸟被抽象为没有质量和体积的“微粒”，

通过这些“微粒”的相互协作和信息共享，其运动速度受到自身和群体的历史运动

状态信息的影响，以自身和群体的历史最优位置来对微粒当前的运动方向和运动速

度加以影响，能较好地协调微粒本身和群体运动之间的关系，在复杂的解空间寻找

最优解.由于该算法概念简单，易于实现，因而在短期内得到很大发展，迅速得到

国际演化计算研究领域的认可，并在很多领域得到应用，如电力系统优化、交通事

故探测、水库优化调度、自动频率规划等.

1.1基本原理

微粒群算法与其他进化算法相似，也是根据对环境的适应度将群体中的个体移动到

好的区域，不同之处在于它不像其他演化算法那样对个体使用演化算子，而是将每

个个体看作寻优空间中的一个没有质量没有体积的微粒，在搜索空间中以一定的速

度飞行，通过对环境的学习与适应，根据个体与群体的飞行经验的综合分析结果来

动态调整飞行速度.

微粒群算法将每一个可能产生的解表述为群中的一个微粒，每个微粒都有自己的速

度和位置向量，以及一个由目标函数决定的适应值，所有微粒在搜索空间中以一定

速度飞行，通过追随当前搜索到的最优适应值来寻找全局最优.

在n维空间中有M个微粒，每个微粒的位置表示一个潜在的解.设Xi＝（xi1，

xi2，…，xin）为微粒i的当前位置，Vi＝（vi1，vi2，…，vin）为微粒i的当前

速度，Pi＝（pi1，pi2，…，pin）为微粒i所经历的最好位置，即Pbest．Pg为

群体中所有微粒所经过的最好位置，也称为gbest．则对于每一代，微粒i的第j

维的进化方程为：

其中：ω为惯性权重（inertiaweight），c1和c2为加速常数（acceleration

constants），rand（）和Rand（）为两个在0，1范围内变化的随机函数[2].

从社会学的角度来看式（1），其中的第1部分为微粒先前的速度乘一个权值进行

加速，表示微粒对当前自身运动状态的信任，依据自身的速度进行惯性运动，因此

称这个权值为“惯性权重”；第2部分（微粒当前位置与自身最优位置之间的距

离）为“认知（cognition）”部分，表示微粒本身的思考，即微粒的运动来源于

自己经验的部分；第3部分（微粒当前位置与群体最优位置之间的距离）为“社

会（social）”部分，表示微粒间的信息共享与相互合作，即微粒的运动来源于群

体中其他微粒经验的部分，通过认知模仿较好同伴的运动[3].

1.2基本微粒群算法流程

微粒群算法的流程如下：第1步：初始化所有微粒（群体规模为M）.在允许范围

内随机设置微粒的初始位置和速度，并将各微粒的pbest设为初始位置，取

gbest为pbest中的最优值.第2步：评价每个微粒的适应值，即分别对每个微粒

计算目标函数值.第3步：对每个微粒，将其适应值与其历史最优位置pbest进行

比较，如果优于pbest，则将其作为当前最优位置pbest.第4步：对每个微粒，

将当前最优位置pbest与群体历史最优位置gbest进行比较，如果优于gbest，

则将其作为群体最优位置gbest，并重新设置gbest的索引号.第5步：根据微粒

群速度和位置更新方程来调整微粒的速度和位置.第6步：检查终止条件（通常为

达到最大迭代次数或者足够好的适应值）或者最优解停滞不再变化.若上述条件满

足，终止迭代；否则返回第2步.微粒群算法流程如图1所示.

2.1调整惯性权重ω

ShiY，Eberhart[4][5]研究了惯性因子ω对优化性能的影响.惯性权重ω可以对算

法的全局搜索能力和局部搜索能力进行平衡调整，因此，该参数对算法的性能影响

很大.许多文献中对惯性权重ω的调整进行了大量的研究，其中比较典型的有：

(1)线性调整ω的策略.即随迭代进行，线性减少ω的值[6].这样可以使算法更好控

制探索与开发，在迭代初期探索能力较强，可以搜索较大的解空间，并不断搜索新

的区域，然后在后期逐渐收缩到较好的区域进行更精细的搜索以加快收敛速度.

(2)非线性调整ω的策略.由于微粒群的搜索过程是一个非线性的复杂过程，让ω

线性过渡的方法并不能正确反映真实的搜索过程.因而，ShiY等提出了一种用模糊

规则动态调整ω的方法[7]，通过对当前最好性能评价（CBPE）和当前惯性权重

制定相应的隶属度函数和模糊推理规则，确定惯性权重ω的增量.CBPE测量的是

算法找到的最好候选解的性能.由于不同的优化问题有不同的性能评价值范围，所

以为了让该模糊系统有广泛的适用性，采用了标准化的CBPE（NCBPE）.实验结

果表明，与ω线性减小策略相比，模糊自适应策略具有更好的性能.

(3)随机惯性权重ω策略[8].随机地选取ω值，使得微粒历史速度对当前速度的影

响为随机的.ω的数学期望值将随最优值的变化率自适应地调节，从而可以更灵活

地调节全局搜索与局部搜索能力.另外，ω的随机取值在一定程度上类似于遗传算

法的变异算子，有助于保持种群的多样性.

2.2带收敛因子的微粒群算法

Eberhart等描述了一种带收敛因子的微粒群算法[9]，其位置和速度更新等式如式

（3）所示.

式中，为收敛因子，Φ＝c1＋c2＞4，通常取Φ为4．1，则χ＝0．729.

实验结果表明，与使用惯性权重的微粒群算法相比，使用收敛因子的微粒群算法有

更快的收敛速度.其实只要恰当地选取ω、c1和c2的值，两种算法是一样的，因

此带收敛因子的微粒群算法[18]可被看作带惯性权重的算法的一个特例.同时这也

说明，恰当地选择算法的参数值可以改善算法的性能.

2.3增加多样性的改进

由于GBEST[2]模型存在多样性少、易早熟收敛的缺点，因此在此基础上提出了

LBEST[2]模型，以增加群体多样性，从而更好地实现全局搜索，防止陷入局部最

优.

P．N．Suganthan[10]提出一种具有可变邻域算子的微粒群算法，该算法在初始

阶段微粒的邻域为它自身，随着进化代数的增长，邻域逐渐扩大至整个群体.换句

话说，PSO算法中的全局极值gbest被局部邻域内逐渐增加的局部极值lbest所

代替，同时算法中随机漫步和惯性权值的大小也逐渐调整，以使得在优化的最后阶

段进行更好的开发搜索.J．Kennedy和R．Mendes[11]讨论了不同邻域拓扑结构

对局部最优模型（LBEST模型）中的效果，发现VonNeumann邻域结构能取得

更好的效果，并随后提出两种改进方法PSON和PSOWN[12]，其中PSON算法

在搜索过程中参考微粒所在邻域内所有微粒对它的影响，而不单单是最好微粒对它

的影响；而PSOWN则将邻域内各微粒对该微粒的影响进行权值排序，模仿现实

中各方面因素影响程度的不同.

J．J．Liang和P．N．Suganthan[13]提出了一种多群体微粒群算法，第一阶段

按照局部最优模型进行搜索.首先将整个微粒群随机分割成多个子群体，每经过若

干代后进行重新分组，以提高种群多样性.第二阶段群体按照全局最优模型进化，

以加快全局最优搜索的能力和速度.该方法能够使得“勘探”和“开采”达到很好

的平衡，该方法对复杂多峰函数优化能够取得很好的效果.文献［14］对多种群的

协同进化也进行了大量研究.采用了不同的更新策略，实验结果表明该算法提高了

算法的收敛性和最优性.

另外，微粒群算法与复杂网络模型的结合也是微粒群算法在动态构造邻域模型方面

一个新的值得探索的途径.

Angeline[15]将进化规划中使用的竞赛选择方法引入微粒群算法.该混合算法根据

个体当前位置的适应度，将每个个体与其他个体进行比较，然后依据比较结果对整

个群体进行排序，用微粒群中较好的一半替换群体中较差的一半，同时保留每个个

体所记忆的个体最优位置.选择方法的引入使得该混合算法具有更强的开发搜索能

力，加快了对当前较好区域的开发过程，使得收敛速度较快，但也增加了陷入局部

解的可能性.

高尚等[16]结合遗传算法、蚁群算法和模拟退火算法的思想，提出用混合微粒群算

法来求解著名的离散优化问题——旅行商（TSP）问题，所提24种混合粒子群算

法的效果都比较好，其中交叉策略D和变异策略F的混合微粒群算法的效果最好，

而且简单有效.Lobjerg[17]等提出了基于繁殖和子群的杂交微粒群算法，他们在繁

殖过程中引入繁殖概率来代替适应度.每次迭代时，依据繁殖概率在微粒群中选取

一定数量的微粒放入一个池中随机两两进行算术“交叉”繁殖，产生数目相同的后

代，用后代微粒代替父母微粒，使种群数目保持不变.后代微粒的位置由父母位置

的交叉获得.

最近，Higashi和lba[17]提出了用进化计算中的高斯“变异”算子与微粒群算法

杂交的思想.该方法在传统的速度与位置更新规则中融入高斯“变异”，以避免陷

入局部最优.

微粒群算法是一种新型的群体智能算法，由于微粒群算法在求解复杂优化问题方面

的优势，在很多工程领域如工程设计与优化、电力系统领域[18]、机器人控制和工

业生产优化领域等取得了较为成功的应用.但微粒群算法的研究还处于起步阶段，

许多方法大多处于性能验证和实验阶段，缺乏强有力的理论支持.对微粒群算法

“早收敛”问题的实质，以及对于离散、多目标、约束及动态等优化问题无法达到

满意效果，仍然是今后值得研究的问题.

【相关文献】

[1]KennedyJ，EberhartRC．Particleswarmoptimization[A].ProcIEEEInternationalConf

onNeuralNetworks［C］//Perth：IEEEPiscataway，1995：1942－1948．

[2]曾建潮，介婧，崔志华．微粒群算法[M].北京：科学出版社，2004：5.

[3]KennedyJ．Particleswarm：socialadaptationofknowledge[A]．ProcIEEEIntConfon

EvolutionaryComputation[C]//Indianapolis：IEEEPiscataway，1997：303－308．

[4]ShiY，EberhartR．C．Amodifiedparticleswarmoptimizer[Z]．ProceedingsoftheIEEE

away，NJ，IEEEPress，1998：

69-73．

[5]ShiY，EberhartR．C．Empiricalstudyofparticleswarmoptimization[Z]．1945－

1950．1999．Piscataway，NJ，IEEEServiceCenter．Proceedingsofthe1999Congresson

EvolutionaryComputation．

[6]ShiY，EberhartRC．Amodifiedparticleswarmoptimizer[A]．IEEEWorldCongresson

ComputationalIntelligence［C］//．Anchorage：IEEE，1998：69273．

[7]ShiY，EberhartRC．Fuzzyadaptiveparticleswarmoptimization[A]．Proceedingsof

theIEEEConferenceonEvolutionaryComputation［C］．Soul：IEEE，2001：101－106．

[8]张丽平，俞欢军，陈德钊，等．粒子群优化算法的分析与改进[J]．信息与控制，2004，33

（5）：513-517．

[9]EberhartRC，ShiY．Comparinginertiaweightsandconstrictionfactorsinparticle

swarmoptimization[A]．ProceedingsoftheIEEEConferenceonEvolutionary

Computation［C］//．California：IEEEPiscataway，2000：84－88．

[10]P．N．Suganthan，ParticleSwarmOptimirwithNerighbourh－oodOperator，in

Proc．IEEEInt．Congr．EvolutionaryComputation，1999：1958-1962．

[11]J．Kennedy，R．tionstructureandparticle

swarmperformance[M].WorldCongressonComputationalIntelligence，Honolulu，HI，

USA，2002：1507-1512．

[12]R．Mendes，J．Kennedy，J．hyNeighborOrHowTheSwarmCan

LearnFromItsEnvironment[M].IEEEInt．Conf．onEvolutionaryComputationIndianapolis，

2003：88-94．

[13]J．J．Liang，P．N．cMulti－SwarmParticleSwarm

Optimizer[M].IEEEInternationalSwarmIntelligenceSymposium，2005：124-129．

[14]王元元，曾建潮．多种群协同进化的微粒群算法[J]．计算机工程与设计，2007，（11）：

3661.

[15]AngelinePJ．Usinglectiontoimproveparticleswarmoptimization[A].Proceedings

oftheIEEEConferenceonEvolutionaryComputation［C］//．Anchorage：IEEE

Piscataway，1998：84－89．

[16]高尚，韩斌，吴小俊，等．求解旅行商问题的混合粒子群优化算法[J]．控制与决策，2004，

19（11）：1286－1289．

[17]张露，焦长义．微粒群算法综述[J]．河南广播电视大学学报，2007，20（4）：108－109．

[18]康琦，张燕，汪镭，等．智能微粒群算法[J]．冶金自动化，2005，（4）：5－9．