一种改进的粒子群优化算法

袁 琳，苑薇薇

(沈阳理工大学信息科学与工程学院，辽宁沈阳 110159)

粒子群优化算法是一种基于种群搜索的群智能进化计算技术［1－2］，在标准 PSO(Particle Swarm Optimization，粒子群优化)算法中，惯性权重是非常重要的参数。文献［3－4］对固定权重的选取做了深入讨论，但对于解决复杂优化问题时，找到合适的固定权重是很困难的。本文关注时变权重的选取，同时根据种群多样性自适应调整惯性权重，平衡局部搜索能力和全局搜索能力，使之能改善标准PSO算法易陷入局部收敛的缺点，并在解决复杂优化问题中达到更好的效果。

1 粒子群优化算法的基本原理

PSO算法的数学描述为:假设在一个N维搜索空间中，有m个粒子组成一个粒子种群，其中第i个粒子在搜索空间中的位置是xi，表示为向量xi，飞行速度表示为向量 vi=，第 i个粒子的个体极值记 pin=，全局极值记为了改善算法收敛性能，在速度和位置更新公式中引入惯性权重的概念［5］。

在每次迭代中，粒子根据下式更新速度和位置:

式中:i=1，2，…，m;n=1，2，…，N;k为当前进化代数;c1和c2为加速常数;r1和r2为均匀分布于(0，1)之间的随机数;w为惯性权重，其大小决定了对粒子当前速度继承的多少，适当选取可以使粒子具有均衡的探索和开发能力，可见原始PSO算法是惯性权重w=1的特殊情况。

粒子群优化算法具有并行处理特性，鲁棒性好，粒子只通过内部速度进行更新，因此原理更简单、参数更少、实现更容易［6］。但是，在算法运行过程中，粒子易陷入局部最优，会出现早熟收敛现象。针对其缺点，本文引入群体适应度方差和群体位置方差，目的是保持种群多样性，并对惯性权重进行自适应调整，使其快速收敛到最优解。

2 改进的粒子群优化算法

2.1 PSO算法种群多样性

(1)群体适应度方差

式中:m为粒子群粒子数;fi为第i个粒子的适应度;favg为粒子群当前的平均适应度;f为归一化因子。越小，则粒子群越收敛。

(2)群体位置方差

2.2 惯性权重调整策略

本文考虑种群多样性的信息，惯性权重调整如下式所示。

惯性权重曲线见图1。在寻优初期，当δ2p较大时，w保持在最大值附近，可提高算法的全局搜索能力;在寻优后期，随着δ2p由大到小的线性过渡，w随种群多样性的减少而递减，可提高算法的局部搜索能力。

图1 惯性权重曲线

2.3 惯性权重的多样性调整

为了克服PSO算法的早熟收敛，当群体满足收敛条件即群体适应度方差或群体位置方差时，利用各粒子的表现程度不同，将群体分成3个子群。适应度较好粒子组成X子群;适应度一般的粒子组成Y子群;其余适应度较差的粒子组成Z子群。

2.3.1 X子群的惯性权重调整

X子群中的粒子适应度较好，已经比较接近全局最优，惯性权重应逐渐减小，提高局部搜索能力。惯性权重调整如下式:

2.3.2 Y子群的惯性权重调整

Y子群中的粒子适应度一般，具有全局寻优能力和局部寻优能力，惯性权重调整如下式:

2.3.3 Z子群的惯性权重调整

Z子群中的粒子适应度较差，惯性权重应逐渐增大，提高全局寻优能力。惯性权重调整如下式:

2.4 改进粒子群算法流程

改进粒子群算法步骤如下:

(1)随机初始化一群粒子及其速度和位置，对每个粒子计算其适应度;

(3)根据每个粒子的适应度，如果好于该粒子当前的个体极值，则将其作为当前粒子的个体最优值;如果所有粒子中最好的个体极值优于当前的全局极值，则将其作为群体最优值;

(4)判断是否达到算法终止条件，若满足，则结束;否则，转至步骤(5);

(6)按式(1)和式(2)更新粒子的速度和位置后转至步骤(2)。

3 实验及结果分析

本文通过4个典型基准函数(见表1)的优化问题测试改进后算法的性能，同时与GA算法与PSO算法进行比较。实验参数设置如下:GA算法、PSO算法和改进算法各运行100次，粒子群的种群规模均为40，迭代次数均为5000次，在改进的算法中。为比较优化结果，选择观察其达优率及其取得平均最优值的迭代次数。

表1 用于测试的基准函数及其参数

测试结果与统计数据见表2～表5。

表2 Sphere的优化结果

表3 Rosenbrock的优化结果

表4 Rastrigrin的优化结果

表5 Griewank的优化结果

实验表明:对于Sphere和Rosenbrock单峰函数，改进后的优化效果要优于GA算法，和PSO算法的优化结果近似。对于Rastrigrin多峰函数，GA算法优化效果较差，在迭代1500次还未收敛到全局最优点，而改进算法和PSO算法都可以在迭代1000次以内找到最优解，且改进算法的达优率要比PSO算法高，能较快地到达全局最优值附近，其效果明显优于PSO算法和GA算法。对于Griewank函数，当空间维数超过20后，其特性趋向于单峰，改进算法的优越性并不明显，可见，改进算法更适于解决多峰函数优化问题。

4 结论

通过对基准函数的测试，验证了改进算法的收敛精度较高，收敛速度(这里是指算法迭代的次数)比GA算法和PSO算法要快。这要归结于在算法中引入群体适应度方差和群体位置方差协调种群多样性。根据种群多样性，对惯性权重自适应调整，保持了惯性权重的多样性，从而提高了优化性能。当优化问题是高维、多峰等复杂问题时，改进算法的优越性更加明显。

［1］ Kennedy J，Karnhart R C.Swarm Intelligence［M］.San Francisco，CA:Morgan Kaufmann Publishers Inc，2001.

［2］ Karnhart R C，Kennedy J.A new optimizer using particle swarm theory［C］.Proc of the 6th international symposium On Micro Machine and Human Science，Nagoya，Japan:IEEE Service Center，1995:39 －43.

［3］柯晶，钱积新，乔谊正.一种改进粒子群优化算法［J］.电路与系统学报，2003，8(5):87 －91.

［4］唐剑东，熊信艮，吴耀武，等.基于改进PSO算法的电力系统无功优化［J］.电力自动化设备，2004，24(7):81－84.

［5］周晖，周任军，谈顺涛，等.用于无功电压综合控制的改进粒子群优化算法［J］.电网技术，2004，28(13):45－49.

［6］闻朝中，李智.粒子群算法在配电网络无功补偿优化中的应用［J］.武汉工业学院学报，2004，23(1):18－21.