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

张俊溪， 张嘉桐，张玉梅

(1 西安航空学院 车辆工程系， 陕西 西安 710077；

2 西北大学 文化遗产学院， 陕西 西安 710069；

3 陕西师范大学 计算机科学学院， 陕西 西安 710119)



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

张俊溪1， 张嘉桐2，张玉梅3*

(1 西安航空学院 车辆工程系， 陕西 西安 710077；

2 西北大学 文化遗产学院， 陕西 西安 710069；

3 陕西师范大学 计算机科学学院， 陕西 西安 710119)

摘要：在粒子群优化算法的基础上，将粒子群优化算法的速度更新公式中种群最优位置用所有个体的平均值与最优粒子有限邻居个体的平均值加权求和代替；通过将种群平均适应度和整体最优位置适应度的比值作为适应度函数，并引入了加速系数；得到改进的粒子群优化聚类算法既能够充分参考当前粒子的最优信息，也参考了所有个体的最优信息和当前最优粒子有限邻居的最优信息，在进化过程中可以通过新的适应度函数自适应地调整全局搜索和局部搜索的比重对粒子的影响，对算法收敛速度影响较小的前提下较好地提高了收敛精度。最后，选取了4组具有不同分布特征的Benchmark函数作为验证函数，试验结果表明,新算法具有较好的收敛特性。

关键词:粒子群优化算法； 适应度； 更新； 收敛速度；收敛精度

MR subject classification: 68Q45

粒子群优化算法(particle swarm optimization, PSO) 由Kennedy 和 Eberhart[1-2]于1995年提出。该算法结构简单、运算过程中参数调整较少且实现较为简便，自诞生以来在学术界影响广泛，并取得了大量的研究成果[3-7]。经典的粒子群优化算法主要关注2个信息，即位置和速度信息。二者的调整依赖当前粒子的最优位置和种群的最优位置信息，对粒子群优化算法的改进基本上围绕这二者展开。Shi和Eberhart通过在基本PSO算法中引入“惯性”和“约束”两个因子获得带有惯性权重的PSO算法[1]。Clerc提出了收敛因子模型PSO算法的速度递推方程[2]。Lovbjerg等将进化算法中的交叉操作引入HPSO算法模型[3]。吴晓军等[4]通过定义PSO粒子搜索中心，并计算局部最优解和全局最优解的概率密度，使搜索中心在二者之间均匀分布，提出均匀搜索粒子群优化算法；胡旺等[5]通过简化公式消去速度信息，仅依赖位置信息控制进化过程，大大提高了收敛效率；文献[6]分析了粒子轨迹对算法收敛性的影响，文献[7]深入分析了惯性权重的更新和种群拓扑结构的改进。

粒子群算法在进化过程中既参考了种群整体的位置信息又参考了当前粒子的位置信息，如果种群信息采用全体粒子的位置平均值则称为全局版PSO(GPSO)；如果种群信息采用当前粒子的有限邻居的位置平均值则称为局部版PSO(LPSO)[4-5]。采用全局版PSO，则存在着初期收敛速度快但容易陷入局部最优的问题，而采用局部版PSO则存在收敛精度高但收敛速度变慢的问题。无论是从参数进行改进还是从位置信息和速度信息进行改进，都可以不同程度地提高其某些指标，达到改进算法的目的。本文试图通过将全局版PSO和局部版PSO相结合，使算法在进化的过程中同时参考种群最优信息和当前粒子信息，同时加入当前粒子的有限邻居信息，使算法在进化的过程中能够保证收敛速度不会大幅度降低的前提下，提高其搜索精度，避免过早陷入局部最优。

1基本粒子群优化算法及其

相关改进

1.1经典粒子群优化算法

PSO算法通过模拟鸟群和鱼群群体觅食的运动行为，将鸟或鱼定义为种群的粒子，每个粒子的基本信息用其几何位置和速度向量表示，粒子在觅食的过程中既参考自己的运动方向，同时也参考整个种群所经历的最优方向来调整自己的觅食行为。粒子的觅食行为可以用公式(1)、(2)来表示，其中pbest和gbest称为个体极值和全局极值，分别是第i个粒子曾经达到的最优位置和种群所经历过的最优位置。粒子通过这2个极值来更新自己。

(1)

xid=xid+vid,

(2)

其中：d为搜索空间的维度；r1和r2是服从U(0,1)分布的随机数；学习因子c1和c2为非负常数; vid∈[-vmax,vmax]，vmax是由用户设定的速度约束常数。如果取xgd为整个种群的最优位置，则上述算法被称为全局版PSO(GPSO)，如果令x0d为第i个粒子的有限邻居搜索到的最优位置，并取xgd=x0d，则算法被称为局部版PSO(LPSO)[5]。

1.2粒子群优化算法的相关改进

自PSO算法提出以来，在改善PSO性能方面展开了大量的研究工作[10-17]。基本PSO算法经过Shi[1，9]等人的改进，引入了惯性权重w，形成了目前应用最为广泛的一种形式：

vi(t+1)=wvi(t)+c1r1(t)[pi(t)-xi(t)]+c2r2(t)[pg(t)-xi(t)],

(3)

xi(t+1)=xi(t)+vi(t+1),

(4)

其中:w为惯性系数，典型取值为w=0.4或w=0.9,该算法侧重先全局后局部的搜索方式，很大程度上改善了算法的搜索能力和收敛精度;随机变量r1和r2以及学习因子c1和c2与经典粒子群算法中的取值相同;pi(t)为当前粒子的最优位置信息；pg(t)为整个种群的最优位置信息；vi∈[-vmax,vmax],vmax是由用户设定的约束速度的常数[10]。Clerc建议采用收缩因子来保证PSO算法收敛[6,11]：

(5)

其中，“收缩因子”的计算按照(6)式进行，即

(6)

使用Clerc的收缩因子方法时,通常取φ=4.1,从而使收缩因子χ=0.729。该算法不再需要限制最大速度vmax。

此外，对PSO的改进主要集中于与其他进化算法的结合，如遗传算法(GA)、遗传规划(GP)和免疫算法等，目标是提高算法收敛的速度以及收敛的精度。Angeline[1]将GA的选择算子引入PSO中，通过选择每一代中的较优粒子进行迭代，可以提高算法的优化性能；李宁[13]、吕振肃[14]等人提出带变异算子的PSO算法，通过变异算子处理部分极值点问题来增强全局搜索能力，同时又不降低收敛速度和收敛精度。高鹰等[15]则将免疫算法引入到PSO中，改善了算法的收敛速度。以上算法都有各自的优缺点，而且都通过引入其他算子来优化算法性能，且往往增加了算法的时间复杂度[12，16]。

2改进的粒子群优化算法

2.1粒子群的位置更新优化

从粒子群优化算法的标准公式(3)和(4)中可以看出，粒子根据pi(t)(i=1、2、…、N)和pg(t)来更新自己的速度和位置，在进化的过程中如果选择pg(t)为有限邻居的平均值，则算法搜索效率低；如果选择pg(t)为种群所有粒子的平均值，则算法容易陷入局部最优，因此应该充分利用当前最优粒子的邻居信息以及整个种群所有粒子的最优位置信息来更新算法，就可以兼顾搜索过程中对信息的充分利用。可以对(3)式作如下变化，如(7)式所示：

vi(t+1)=ωxi(t)+c1r1(pi(t)-xi(t))+

c2r2(α(p0(t)-xi(t))+

(1-α)(pg(t)-xi(t)))，

(7)

xi(t+1)=vi(t)+xi(t+1),

(8)

其中:随机变量r1和r2以及学习因子c1和c2与经典粒子群算法中的取值相同;pi(t)为当前粒子的最优位置信息；pg(t)为整个种群的最优位置信息；P0为粒子Pi的有限邻居位置信息，Pg为全局粒子的位置信息，基本粒子群算法中的Pg(t)分量被P0(t)和Pg(t)的加权平均取代。这样粒子的搜索中心从Pi和Pg之间变成Pi和P0与Pg之间的某个中心值之间，如图1所示，pi′为P0和Pg的加权平均位置信息。

图1　改进后粒子的搜索路径与搜索中心

则(7)和(8)式就构成了新的自适应PSO算法模型，定义

其中:N为种群中个体的总数;m为当前粒子的有限个邻居粒子的个数。

2.2粒子搜索中心的概率密度分布

在粒子群优化算法中，加速系数c1和c2分别控制个体粒子的位置信息和种群的位置信息对粒子速度的影响。根据PSO算法的特点，进化初期个体粒子的更新应起主导作用，这样可以使搜索空间增加，不易陷入局部极值；而在进化后期，种群的位置信息应起主导作用，这样可以提高搜索的速度和精度。文献[17]对加速系数做了如下改进：

令

c1(t)=1-exp(-β|Fa(t)-Fg(t)|)，

(9)

c2(t)=1-c1(t)，

(10)

其中:Fa(t)为粒子群的平均适应度;Fg(t)为整体最优位置pg(t)的适应度。二者在进化初期有较大的差，而后期差别越来越小， 为控制系数。因此,该模型中，c1(t)非线性减小，c2(t)则非线性增大。

假定r1、r2为常数，则粒子搜索中心位于pi和pg之间[4]；假定r1和r2为随机数，则令c=c1/c2，pi=0，pg=1，X、Y代表随机变量r1和r2，则令

(11)

计算公式(11)的联合概率密度函数[4]，如公式(12)所示，从中可以看出，z′并不服从均匀分布，且在1/(1+c)处取得极大值，图2为c取不同值时的概率密度函数图形，其中h为c取不同值对应的概率密度，纵坐标为概率密度，横坐标为p0-pg的归一化参数。

(12)

图2　概率密度函数图形

(7)式可以扩展为

vi(t+1)=wxi(t)+c1(t)r1(pi(t)-xi(t))+

c2(t)v2(α(p0(t)-xi(t))+

(1-α)(pg(t)-xi(t)))。

(13)

(13)式和(8)式构成了新的自适应粒子群优化算法的模型(new adaptive PSO,NAPSO)。

根据文献[12]，分别对粒子群的位置信息进行分析，可以得到(14)式，该式中对于种群的最优位置信息pg只能取全体种群粒子的平均值或者当前粒子的有限邻居粒子的平均值，根据本文提出的新的自适应PSO算法(NAPSO)，可以扩展为式(15)，同时参考2个全局位置信息。

(14)

(15)

通过大量实验证明，当α=0.3,w=0.5,β=10时，算法具有较好的收敛性能。

从式(15)中可以得出：当p0=pg时，即种群的最优位置信息选择相同的种群粒子，则(13)式又还原为(7)式，同全局版或局部版PSO。

3实验结果与分析

通过选取4组Benchmark函数，测试新的自适应粒子群优化算法(NAPSO)的搜索性能。Benchmark函数可以有效考察新型算法对不同类型问题的优化性能，本文选取的4组基准测试函数涵盖单峰函数和多峰函数，可以考察算法的收敛速度和收敛精度。分别用全局版PSO(GPSO)、局部版PSO(LPSO)和NAPSO做验证试验，惯性因子w按照惯例取0.8，全局版PSO和局部版PSO的加速系数c1和c2都取1，进化次数设为2 000，运行50次所得函数最优值点的平均值和最优值的平均值作为算法的衡量指标。

所用的Benchmark函数及其参数选择如表1所示，由于维度增大，自变量取值范围增大会增加算法的复杂度，本文对部分函数的参数做了微调，便于简化运算过程。

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

实验结果如图3所示，横坐标为迭代次数，纵坐标为适应度的对数值，标号Ⅰ、Ⅱ、Ⅲ分别表示LPSO、GPSO和NAPSO对表1中4个函数的优化曲线。本实验所选的4个函数最优值均为零，从图3a可以看出，对于Rastrigr函数的仿真结果中，NAPSO算法的收敛效率最高，在第800步就已经收敛到极小值，且最终收敛的结果更趋近于零值。而LPSO的收敛效率较差，在1 800步时收敛到极小值。图3b是对Griewank函数的仿真结果，该函数为多峰函数，且极值分布具有不均匀性，故3种算法对该函数的仿真结果均比第一个函数的仿真结果差，从收敛曲线可以看出，收敛的最终结果误差较大，且最终收敛的步数均在1 600步之后，整体上收敛的效率为NAPSO高于GPSO，GPSO高于LPSO。图3c为SchwefelProblem函数，该函数与Griewank函数相比，极值点分布更加不均匀，因此仿真的结果次于Rastrigr函数和SchwefelProblem函数。收敛的极值距零点差别较大，接近于1。图3d为Rosenrock函数的仿真结果，该函数为较为复杂的单峰函数，3种算法对该函数的仿真结果收敛效率差别较小，总体上NAPSO的收敛效率略高于LPSO，LPSO略高于GPSO。

从4个函数的仿真结果来看，NAPSO的收敛效率总体上高于经典PSO算法，且更适合于极值点均匀分布的函数。对于极值点非均匀分布的函数，由于粒子在搜索的过程中较多地参考了“社会”信息，而使得收敛速度相对下降，而导致部分粒子收敛于局部极值点。但总体上本文提出的NAPSO算法在综合考虑了当前最优粒子位置信息、种群最优位置信息以及当前粒子邻居位置信息的情况下，能够更好地全面利用进化过程中的位置信息，使算法尽量在“认知”和“社会”信息之前取得折中值。所得结果可以看出，NAPSO算法的稳定性是最优的。

图3GPSO、LPSO和NAPSO算法在4个函数下的收敛性分析

Fig.3Convergence analysis of GPSO、LPSO and NAPSO in the 4 function

4结论

本文在经典粒子群优化算法的基础上提出了一种新的自适应粒子群优化算法，通过将粒子群算法的速度更新公式进行改进，在种群最优位置信息的基础上增加了当前最优粒子的邻居位置信息，并将二者的加权平均值作为位置信息的进化依据；同时将种群平均适应度和整体最优位置适应度的比值作为适应度函数，引入加速系数，得到新的自适应粒子群算法模型。该模型在进化的过程中，可以自适应地调整“认知”部分和“社会”部分对粒子的影响，在进化前期以“认知”部分为主导，加快收敛速度，进化后期以“社会”部分为主导，提高收敛的精度。

4组标准Benchmark函数涵盖了不同分布特点的单峰和多峰函数，仿真结果表明本文提出的算法在收敛效率和收敛精度方面有一定的优势，尤其对于极值点均匀分布的函数具有较好的优越性。但是该算法增加了权重因子和控制系数，这两个参数需要通过多次试验获得，因此对于极值点分布特点差别较大的优化问题处理结果表现不一致。

参考文献：

[1] SHI Y H, EBERHART R C. A modified particle swarm optimizer[C]∥IEEE International Conference of Evolutionary Computation, Anchorage:IEEE, 1998: 69-73.

[2] CLERC M. The swarm and queen towards a deterministic and adaptive particle swarm optimization[C]∥Proceedings of Congress on Evolutionary Computation, Washinton D C:IEEE, 1999: 782-786.

[3] LOVBJERG M, RASMUSSEN T K, KRINK T. Hybrid particle swarm optimization with breeding and subpopulations[C]∥IEEE International Conference on Evolutionary Computation, San Diego:IEEE, 2000: 1217-1222.

[4] 吴晓军, 杨战中, 赵明. 均匀搜索粒子群算法[J]. 电子学报,2011,39(6)：1261-1266.

[5] 胡旺, 李志蜀. 一种更简化而高效的粒子群优化算法[J]. 软件学报,2007,18(4)：861-868.

[6] CLERC M, KENNEDY J. The particle swarm explosion, stability and convergence in a multi-dimensional complex space[J].IEEE Transaction on Evolutionary Computation, 2002, 6(1): 58-73.

[7] MAHFOUF M, CHEN M Y, LINKENS D A. Adaptive weighted swarm optimization for multi-objective optimal design of alloy steels[C]∥Parallel Problem Solving from Nature. Berlin: Springer-Verlag, 2004: 762-771.

[8] KENNEDY J, EBERHART R C. Particle swarm optimization[C].∥Proceeding of the IEEE Conference on Neural Networks,New York:Institute of Electrical and Electronics Engineers,1995:1942-1948.

[9] SHI Y H, EBERHART, R.C. Empirical study of particle swarm optimization[C]∥Proceeding of the IEEE Congress on Evolutionary Computation,Washinton D C:IEEE,1999:1945-1950.

[10] SHI Y H, EBERHART R C. Parameter selection in particle swarm optimization[C]∥Proceeding of 7th Annual Conference on Evolutionary Programming.Washington D C:IEEE,1998:591 -600.

[11] CLERC M. The swarm and queen: towards a deterministic and adaptive particle swarm optimization[C]∥Proceedings of the IEEE Congress on Evolutionary Computation,Washinton D C:IEEE, 1999:1951-1957.

[12] HIGASHI N, IBA H. Particle Swarm Optimization with Gaussian Mutation[C]∥The 2003 Congress on Evolutionary Computation. Piscataway, New Jersey: IEEE, 2003: 72-79.

[13] 李宁，刘飞，孙德宝. 基于带变异算子粒子群优化算法的约束布局优化研究[J]. 计算机学报, 2004,27(7)：897-903.

[14] 吕振肃, 侯志荣.自适应变异的粒子群优化算法[J].电子学报,2004, 32(3):416-420.

[15] 高鹰, 谢胜利.免疫粒子群优化算法[J].计算机工程与应用,2004, 40(6):4-6.

[16] 邹彤, 李宁, 孙德宝, 等. 带阴性选择的粒子群优化算法[J]. 华中科技大学学报(自然科学版), 2006，34(2):87-90.

[17] 高鹰. 一种自适应扩展粒子群优化算法[J]. 计算机工程与应用, 2006(15)：12-15.

〔责任编辑宋轶文〕

An improved particle swarm optimization algorithm

ZHANG Junxi1, ZHANG Jiatong2， ZHANG Yumei3*

(1 Department of Vehicle Engineering, Xi′an Aeronautical University,Xi′an 710077, Shaanxi, China;2 College of Cultural Heritage, Northwest University, Xi′an 710069, Shaanxi, China;3 School of Computer Science, Shaanxi Normal University, Xi′an 710119, Shaanxi, China)

Abstract:Based on the basic particle swarm optimization algorithm, the average of best particles is replaced by the weighted sum of the average of best particles and the average of the neighbor particles in the speed update formula. Using the ratio of average fitness of the whole particles and the average fitness of best particle as the fitness function, and the acceleration factor is introduced, a new adaptive PSO algorithm is obtained. The new algorithm used both the information of present particle and the information of the whole particles and the neighbors of present particle. In the process of evolution, it can adjust the global search and the local search component by the new model adaptively. So the convergence speed and precision can be improved. Experiments on 4 benchmark functions demonstrate that the new algorithm is more efficient.

Keywords:particle swarm optimization algorithm; fitness; update; convergence speed; convergence precision

中图分类号：TP18

文献标志码：A

*通信作者：张玉梅，女，副教授，博士。E-mail:zym0910@tom.com

基金项目：陕西省重点科技创新团队项目(2014KTC-18)；陕西省自然科学基金重点项目(2014JZ021)；陕西省自然科学基金(2014JM8353)

收稿日期：2015-06-16

doi:10.15983/j.cnki.jsnu.2016.02.124

文章编号：1672-4291(2016)02-0015-07

第一作者： 张俊溪，女，讲师，主要研究方向为模式识别与智能系统。E-mail:zhang_junxi@126.com