基于纠错机制的粒子群优化算法*

， ，

(1.太原理工大学 信息与工程学院，山西 太原 030024; 2.太原理工大学 电气与动力工程学院，山西 太原 030024)

0 引 言

粒子群优化(PSO)算法[1～3]是由美国社会心理学家Kennedy J和电气工程师 Eberhart R C于1995年共同提出的一种新的全局优化算法，起源于自然界鸟类和鱼群的社会性行为的模拟。由于概念简单、参数少、易于实现等优点，PSO算法一经提出便引起了广泛的关注，应用于许多科学和实际工程领域[4～9]。

研究表明，PSO算法的搜索过程中存在“走弯路”现象，因此，会导致收敛速度慢，甚至不收敛。针对该缺点，在前人研究的基础上，提出一种基于纠错机制的粒子群优化(MPSO)算法。该算法通过建立一种简单的纠错机制对粒子每一步的进化方向进行判断，如果出现倒退现象，则使粒子向完全相反的方向前进，这样不仅降低了粒子在进化过程中出错的概率，同时也保持了PSO算法的多样性，从而有效地提高了PSO算法的收敛速度和搜索能力。

1 标准PSO概述

PSO算法中，每个粒子都被理解为解空间的一个解，通过事先设定的一个适应度函数来确定粒子的好坏。每个粒子将由一个速度变量来决定其在相应解空间中的飞行方向和距离。根据粒子本身的最优位置和群体找到的最优位置来动态调整自身的飞行方向和速度，通过粒子间的相互作用使其飞向最优粒子。

标准PSO算法[10]先对一群随机粒子初始化，在n维搜索空间中，由m个粒子组成的一个种群表示为X=(x1,x2,…,xm)。其中,第i个粒子的位置为Xi=(xi1,xi2,…,xin)，速度为Vi=(vi1,vi2,…,vin)，自身最优位置为Pi=(pi1,pi2,…,pin)，全局最优位置表示为Pg=(pg1,pg2,…,pgn)。

粒子速度和位置更新策略为

V(t+1)=wVi(t)+c1r1(Pi-Xi(t))+c2r2(Pg-

Xi(t)),

(1)

Xi(t+1)=Xi(t)+Vi(t+1),

(2)

式中i=1，2，3，…，n；t表示当前进化代数；c1，c2为学习因子，且为常数，c1用来调节微粒飞向自身最好位置的步长，c2则用来调节微粒向全局最好位置方向飞行的步长，根据经验通常在0～2之间取值；w为惯性因子，使微粒保持运动惯性的同时具有探索新区域的能力；r1，r2分别为[0,1]之间的随机数；为了降低在进化过程中微粒飞离搜索空间的可能性，速度Vi一般需限定于一定的范围之内，即Vi在(Vmin，Vmax)之间取值，一般情况下取变量空间的20 %～40 %。

由式(1)可知，粒子速度的更新由以下三部分构成：第一部分为粒子当前速度对下一刻速度的影响，即基于自身速度进行的惯性运动；第二部分为“自我认知”部分，通过对自身经验的思考来实现下一步行为的决策；第三部分为“群体认知”部分，依据粒子之前迭代过程中得到的种群经验，实现微粒间的信息合作与共享。

2 MPSO算法

本文提出的MPSO算法的基本原理是：由于粒子群算法具有随机搜索的本质，故在粒子进化过程中速度对位移的修正可能使粒子向更靠近全局最优的方向前进，也可能使粒子向背离全局最优的方向前进，即出现倒退现象，这时如果没有及时纠正，就会出现“走弯路”现象，即粒子向错误的方向前进一段时间后再走回正确的方向。为此，在粒子进化过程的每一步均增加一个纠错机制，只要粒子出现倒退现象就及时纠正，避免了“走弯路”现象，使粒子以更快的速度向全局最优和局部最优靠近。算法设计如下：

在每一次迭代中，对每个粒子当前时刻的速度Vi取反，得到一个新的速度-Vi，分别求得速度Vi和-Vi对应的位置X1和X2，若X2对应的适应度值比X1对应的适应度值好，则用-Vi取代Vi作为该粒子的当前速度，并用X2取代X1作为该粒子的当前位置，且将X2的适应度值取代X1的适应度值；若X2对应的适应度值比X1对应的适应度值差，则该粒子维持原来的速度Vi、位置X1和对应的适应度值。

此方法的优点在于，通过引入一种简单的纠错机制提高了粒子群算法的收敛速度和收敛精度，降低早熟收敛的比率，提高了解的质量。在进一步强化算法的局部搜索能力的同时，算法的全局搜索能力也得到了一定的提高。

3 算法步骤

综上所述，MPSO算法流程描述如下：

1)初始化种群，包括最大进化代数、种群规模大小、学习因子等参数的初始化，以及粒子的速度、位置，每个粒子的历史最优值和整个群体的历史最优值的初始化；

2)根据式(1)和式(2)对每个粒子的速度进行更新，并取反得到一个新的速度；

3)根据粒子的当前速度和取反后的速度，分别求取其对应的位置和适应值，通过对这2个适应值的比较，将适应值较好的一方赋给当前粒子；

4)根据粒子当前的适应值更新粒子的历史最优值和整个群体的历史最优值，即个体极值和全体极值；

5)判断是否能够达到最大进化代数，或能否满足精度要求，若是满足，则输出结果并终止算法；否则，返回步骤(2)重新循环。

4 实验结果分析

下面将通过3个标准测试函数来验证文中算法的性能：

1)Sphere函数

xi∈[-100,100].

(3)

2)Ratrigrin函数

xi∈[-5.12,5.12].

(4)

3)Rosenbrock函数

xi∈[-30,30].

(5)

其中，函数1：Sphere函数，为非线性且对称的单峰函数，其理论上最小值为0；函数2：Ratrigrin函数，为具有大量局部最优的复杂多峰函数，其理论上最小值为0；函数3：Rosenbrock函数，为很难极小化的典型的病态二次函数，理论上最小值为0。

算法参数如下初始化：学习因子取c1=c2=2。惯性权重w从0.9随进化而线性减少到0.4。为了研究算法的拓展性能，对于每个函数的不同维数(D=20，100)用不同的种群规模(N=30，50，100)来实验，为了能给出相关性能正确的适应值，把算法连续运行100次求平均值，最大进化代数为2 000次。统计对比数据见表1。

为了证明本文提出的算法的有效性，取3个函数在种群规模为50，维数为20的情况下的实验结果，如图1～图3所示。

图1 Sphere函数对比图

表1 Sphere，Ratrigrin，Rosenbrock函数最优值的均值

图2 Ratrigrin函数对比图

通过表1、图1～图3可以看出：在相同迭代次数下，对所测试的3个函数的MPSO算法总体上能获得比标准PSO算法更优的结果，而且MPSO算法对于多峰高维函数也具有较好的性能。通过观察粒子适应值对比图发现，标准PSO算法出现了早熟收敛情况，MPSO算法对早熟收敛情况有所改善，并且其全局收敛速度明显快于标准PSO算法。实验表明，MPSO算法不仅在收敛速度上有所提高，而且提高了粒子群的优化性能，因此证明了算法的性能。

图3 Rosenbrock对比图

5 结束语

本文针对标准PSO算法存在的收敛速度慢与早熟等现象，提出了一种MPSO算法。为了测试算法的性能，本文选取Sphere，Ratrigrin，Rosenbrock三个标准测试函数进行仿真计算，并将标准PSO,MPSO两种算法的优化结果进行比较，结果表明：MPSO算法相对于标准PSO算法的收敛性能有显著提高，且具有较快的收敛速度。

参考文献:

[1] Al-Awami Ali T，Zerguine Azzedine，Cled Lahouari．A new modified particle swarm optimization algorithm for adaptive equaliza-tion[J].Digital Signal Processing,2011,21(2):195-207.

[2] Kennedy J,Eberhart R C.Particle swarm optimization[C]∥Proceedings of IEEE International Conference on Neural Networks,Piscataway:IEEE,1995:1492-1498.

[3] 潘 勇，郭晓东.一种基于遗传算法改进的粒子群优化算法[J].计算机应用与软件，2011，28(9)：222-224.

[4] Baskar G,Mohan M R.Contingency constrained economic load dispatch using improved particle swarm optimization for security enhancement[J].Electric Power Systems Research,2009,79(4):615-621.

[5] Siahkali H,Vakilian M.Electricity generation scheduling with large-scale wind farms using particle swarm optimization[J].Electric Power Systems Research,2009,79(5):826-836.

[6] Peng Li，Wang Maohai，Du Jiaping，et al.Isolation niches particle swarm optimization applied to traffic lights controlling[C]∥Proceedings of the 48th IEEE Conference,CDC/CCC 2009,2009.

[7] Samanta B,Nataraj C.Use of particle swarm optimization for machinery fault detection[J].Engineering Applications of Artificial Intelligence,2009,22(2):308-316.

[8] 张 静，王万良，徐新黎，等.基于改进粒子群算法求解柔性作业车间批量调度问题[J].控制与决策，2012，27(4)：513-518.

[9] Xin Bin,Chen Jie,Peng Zhihong,et al.An adaptive hybrid optimizer based on particle swarm and differential evolution for global optimization[J].Science China Information Sciences,2010,53(5):1869-1919.

[10] 纪 震，廖惠连，吴青华.粒子群算法及应用[M].北京:科学出版社,2009:72-76.