微粒群算法的分析与展望

摘要：围绕微粒群（PSO）算法的原理、特点、改进、应用等方面进行全面综述，并对其在理论研究和技术应用两方面的研究现状和未来的发展方向进行综述。

关键字：微粒群算法；进化计算；离散优化；多目标优化

中图分类号：TP18文献标识码：A文章编号：1009-3044(2008)33-1378-03

Particle Swarm Optimization Algorithm Analysis and Forecast

ZHANG Jie

(Jiangsu food science college ,Huai'an 223003, China)

Abstract: Encompassment Particle Swarm Optimization (PSO) aspects and so on algorithm principle, characteristic, improvement, application carry on the comprehensive summary, and will apply two aspects to it in the fundamental research and the technology the research present situations and the future development direction carries on the summary.

Key words: particle swarm optimization algorithm; evolution computation; separate optimization; multi-objective optimization

1 引言

微粒群算法（PSO）是J.Kennedy和R.C.Eberhart[1]于1995年提出的一种新的进化算法，借鉴了鸟群或鱼群捕食过程的社会行为，将群体中的成员描述为空间内一个没有质量、没有体积的“微粒”，所有微粒通过一个适应函数来确定其在空间中的适应度。进化初期，每个微粒的位置和速度都被随机初始化，微粒在飞行过程中相互合作，根据自身和同伴的运动状态及时调整自己的速度和位置，以便在适应值较好的位置降落。微粒群算法概念简明，参数设置少，并能根据当前的搜索情况动态调整搜索策略，对解决复杂环境中的优化问题非常有效。目前已成功的运用到电力、通讯、生物信息、医学等各个领域。

2 标准微粒群算法

2.1 微粒群算法基本原理

微粒群算法将每一个可能产生的解表述为群中的一个微粒，每个微粒都有自己的速度和位置向量，以及一个由目标函数决定的适应值，所有微粒在搜索空间中以一定速度飞行，通过追随当前搜索到的最优适应值来寻找全局最优。

在N维空间中有 M个微粒，每个微粒的位置表示一个潜在的解。设[2]

Xi=(xi1,xi2,..,xin)为微粒i的当前位置；

Vi=(vi1,vi2,..,vin)为微粒i的当前速度；

Pi=(pi1,pi2,..,pin)为微粒i所经历的最好位置，即为 Pbest；

Pg为群体中所有微粒所经过的最好位置，也称为 gbest。

则对于每一代，微粒i的第j维的进化方程为：

vij(t+1)=ωvij(t)+c1rand()(pij(t)-xij(t))+c2Rand()(pg(t)-xij (t))(1)

xij(t+1)=xij(t)+vij(t+1) (2)

其中：ω为惯性权重 (inertia weight)，c1和c2为加速常数 (accelerationconstants)，rand()和Rand()为两个在 0,1范围内变化的随机函数。在 (1)式中第一部分为微粒先前的速度；第二部分为 “认知 (cognition)”部分，表示微粒本身的思考，通过自己的经验来判断当前的飞行；第三部分为 “社会 (social)”部分，表示微粒间的信息共享与相互合作，借鉴其他微粒的飞行经验来调整当前的飞行。

2.2 算法基本流程

标准微粒群算法的流程如下：

1）随机初始化微粒的位置和速度。

2）计算每个微粒的适应值。

3）对于每个微粒，将其适应值与所经历过的最好位置 Pi的适应值进行比较，若较好，则将其作为当前的最好位置。

4）对每个微粒，将其适应值与全局所经历的最好位置 Pg的适应值进行比较，若较好，则将其作为当前的全局最好位置。

5）根据方程 (1)、(2)对微粒的速度和位置进行进化。

6）如未达到结束条件 (通常为足够好的适应值或达到一个预设的最大代数)，则返回步骤 2）。

3 微粒群算法的改进策略

微粒群算法作为一种新的进化算法，经过十多年的发展已获得了很大的进展。不同领域的专业人员都结合本专业的知识从不同侧面对基本微粒群算法进行改进，并通过仿真实验进行验证，取得不错的效果，为微粒群算法的理论提供了佐证，很大程度上推动了微粒群算法的发展。

3.1 算法参数和结构优化

1）调整惯性权重ω

Shi，Eberhart[3-4]研究了惯性因子ω对优化性能的影响：发现较大的ω值有利于跳出局部极小点，较小的ω值有利于算法的收敛，并先后提两种调整方法。自适应算法通过线性地减小ω值动态的调整参数ω，这使得算法在迭代初期探索能力较强，可以不断搜索新的区域，之后开发能力逐渐增强，使算法在可能解周围进行细致搜索。模糊算法则是利用模糊规则动态调整参数ω的值，通过对当前最好性能评价 (CBPE)和当前惯性权重制定相应的隶属函数和模糊推理规则确定惯性权重ω的增量，结果显示该方法能获得与惯性权重递减的算法类似甚至更好的结果。

2）增加收缩因子λ

Clerc首次提出了带有收缩因子的微粒群算法，其数学表达式为：

vij(t+1)=λ[ωvij(t)+c1rand()(pij(t)-xij(t))+c2Rand()(pg(t) -xij(t))](3)

式中：λ=■为收缩因子，ω=c1+c2，ω>4

Eberhar和Shi分别利用Vmax和收缩因子来控制微粒的速度，并对两种方法进行比较，结果后者比前者通常能够取得更好的收敛率。由于微粒可能偏离所期望的搜索空间导致在指定代数内无法达到全局极值点，因此应该预先设置搜索空间的大小或者设置参数 Vmax=Xmax，以便对算法进行限定，从而保证无论在收敛率还是搜索性能方面都有所改进。

此外，研究者就其他参数对算法性能的影响也进行了研究。P.N.Suganthan用实验表明 c1和c2的值为常数时可以获得较好的解，但不一定为 2。群体的初始化也对算法性能有所影响，但不十分明显。

3）与其他算法结合

与遗传算法的结合，Lovbjerg [5]提出了杂交算法.微粒被赋予一个杂交概率，再每次迭代中，依据杂交概率选定微粒然后微粒再两两杂交，微粒数目不会变化，用子代微粒代替父代微粒。

child1(Xi)=p *parent1(Xi)+(1-p)*parent2(Xi)

child2(Xi)=p *parent2(Xi)+(1-p)*parent1(Xi)(4)

其中，p是均匀分布在 0-1之间的随机数，后代的速度向量由父母向量之和归一化后得到：

Child1(Vi)=|parent1(Vi)|

Child2(Vi)=|parent2(Vi)| (5)

实验证明，杂交微粒群算法收敛速度较快，搜索精度也较高.但调整参数较多，增加了算法的复杂性。

国内学者，高鹰，谢胜利[6]将模拟退火思想引人到微粒群算法中，避免了微粒陷人局部最优，提高了收敛性能。

Angeline[7]把进化规划中使用的竞争选择方法引人微粒群算法，采用进化计算中的锦标赛选择方法：将每个个体的适应度基于当前的位置与其他K个个体进行比较，记下最差的一个得分，并根据比较结果进行排序，用微粒群中最好一半的当前位置和速度替换较差一半的位置和速度，同时保留每个个体所记忆的最好位置。实验证明该方法是一种更具开发能力的算法机制，但易陷入局部最优。

3.2 离散优化

由于许多实际工程的优化问题并非连续空间，微粒群算法必定要进行离散空间扩展。为了保持与连续空间的一致性，离散二进制的威力速度和位置公式如下:

Vid (t+1)=wVid (t)+c1rand ()[Pid (t)-Xid (t)]+c2Rand[Pgd (t)-Xid (t)]

If (rand()S(Vid(t+1))) then Xid (t) =1

Else Xid(t)=0 (6)

式中，S(Vid(t + 1 ))= 1/[1+exp(-Vid)]为Sigmoid函数，速度分量Vid决定了位置分量取1和0的概率。同时，离散二进制算法中，保留了V max，它起限制Xid取1和0的最终概率作用。

3.3 多目标优化

在社会生产及工程实践中很多优化问题都是多目标优化问题。传统的多目标优化方法是将多目标转化为单目标。而PSO在求解多目标问题上有很大的优势，可以并行搜索空间多个解。文献[8]首先将PSO运用到寻求多目标最优问题上。文献[9]针对直接使用PSO算法处理多目标优化问题很容易出现非劣最优域的局部收敛提出了最优解评估选取的PSO算法。

4 分析与展望

微粒群算法作为一种新兴的进化算法，相对于其它比较成熟的智能算法来说，微粒群算法的研究还处于起步阶段，还存在很多问题有待深人研究和解决可以归纳为以下几点:

1）PSO 的理论研究。应该注重算法收敛性、收敛速度、参数选取、参数鲁棒性等方面的理论探讨，包括多目标、约束、离散和动态环境下PSO 算法的相关理论研究。

2）PSO 的算法研究。应该注重高效PSO 的开发，提出合理的核心更新公式以及有效的均衡全局搜索和局部改进的策略。考虑到No Free Lunch 定理以及特定问题的特殊性，应该注重高效混合PSO方法的设计，包括PSO 与问题信息或规则、PSO 与神经网络、模糊逻辑、进化算法、模拟退火、禁忌搜索、生物智能以及混沌等方法或策略的结合。另外，鉴于PSO 对算法参数的依赖性，提出合理选取参数的指导性方法或结论同样值得重视。

3）PSO 的应用研究。目前，PSO 的应用大量局限于连续、单目标、无约束的确定性优化问题。因此，应该注重PSO 在离散、多目标、约束、不确定、动态等优化问题上的探讨和应用。同时，PSO 的应用领域也有待进一步拓宽。就化工及自动化领域而言，问题的多极小性、多约束性、离散连续变量共存、非线性、多目标性、不确定性等复杂性普遍存在，因此PSO 在该领域的研究与应用是一个很有前景的课题。

参考文献：

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

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

[3] Shi Y,Eberhart R C. A modified particle swarm optimizer[C]. Piscataway, NJ, IEEE Press. Proceedings of the IEEE International Conference on Evolutionary Computation,1998:69～73.

[4] Shi Y,Eberhart R C.Empirical study of particle swarmoptimization[C]. Piscataway, NJ, IEEEService Center. Proceedings of the 1999 Congress on Evolutionary Computation,1999:1945-1950.

[5] Lovbjerg MR . Ussen T K,Hybrid K T. Particle Swarm optimization With Breeding and Subpopulatious[C]. Prec Of Genetie and Evolutionary Computation Conference,2001.

[6] 高鹰,谢胜利.基于模拟退火的粒子群优化算法[J].一计算机工程与应用,2004(1): 47-50.

[7] Angeline P J.Using selection to improve particle swarm optimization[C]. Proceedings of the 1998 International Conference on Evolutionary Computation, NewYork,NY,USA:IEEE,1998:84-89.

[8] Schaffer J D.Multiple objective optimization with vector evaluated genetic algorithms[C]. The First Int'1 Conf on Genetic Algorith ms,Lawrence Erlba UITI,1985.

[9] 张利彪,周春光,马铭.基于粒子群算法求解多目标优化问题[J].计算机研究与发展, 2004,41(7):1286-1291.

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