一种多样性反馈高斯粒子群算法

黄明，张春蕾,武耀旭,郝倩

(大连交通大学 软件学院，辽宁 大连 116028)

一种多样性反馈高斯粒子群算法

黄明，张春蕾,武耀旭,郝倩

(大连交通大学 软件学院，辽宁 大连 116028)

针对粒子群算法在算法迭代后期因多样性减少而容易陷入局部最优的缺陷,引入种群多样性反馈(群活性反馈)和高斯正态惯性权重变异算子对粒子群算法进行改进，当粒子群的多样性减少时，通过改变粒子的惯性权重调节粒子速度和位置，从而跳出局部最优解.与标准粒子群算法对比仿真结果表明：多样性反馈高斯粒子群算法在全局搜索能力和寻优性能上有很大提高,多样性提高近一倍，迭代时间缩短近3/4.

粒子群算法；惯性权重；多样性反馈；高斯算子

0 引言

近年来，群体智能优化算法在现代工业中的应用越来越广泛，为了进一步提高智能算法的性能，人们对其进行了大量的研究，群体智能优化算法也由最原始的遗传算法、蚁群算法和粒子群算法等发展为现在模拟退火遗传算法、改进蚁群算法和改进粒子群算法等.同其他智能优化算法相比，粒子群算法因参数少、步骤简单易实现等优点使其在工业问题应用更广泛，当然，粒子群算法迭代后期种群的群活性减少而使其容易陷入局部最优解.

针对粒子群算法的缺陷，许多国内外学者对其进行了改进，主要可以分为两类：一种是针对粒子群算法的迭代后期缺陷和迭代过程中种群多样性减少采用的惯性权重w改进[1- 8]；另一种则是混合算法[9- 10].但是大多数的改进仍然存在问题：①不能够很好的对粒子群多样性进行检测控制，而直接使用惯性权重算子改进惯性权重，有一些惯性权重算法的计算公式复杂难理解；②粒子群混合算法由于混合多个算法的优点，弥补了各个算法的不足,故在问题的解决上优于单纯的惯性权重改进.然而，混合算法的复杂度和计算量大大提高，在应用中难实现，并不能满足现在工业中对效率的需求.

因此，本文提出了基于多样性反馈(群活性反馈)的高斯粒子群算法(SAF-GPSO)，该算法不仅继承了粒子群算法的优点，而且改进算子简单易实现，与原始粒子群算法相比性能大大的提高.

1 标准粒子群算法

粒子群优化算法(particleswarmoptimization，简称PSO)是一种进化计算技术，源于对鸟群觅食行为的研究，由Eberhart博士和Kennedy博士在1995年提出的[11].粒子的各个属性都是由各个维数的分量进行表示，每个粒子的位置按如下公式进行变化：

为了提高基本粒子群算法的收敛性和全局搜索能力(避免陷入局部最优解)，Y.Shi和R.C.Eberhan提出了惯性权重的概念[1],将粒子群算法的速度迭代式(1)进行改进，加入固定惯性权重w(一般取0.3～0.8)，改进后的公式如下：

(3)

式中：i表示第粒子；d表示维数；P表示粒子个体极值；g表示粒子全局极值；t表示粒子的迭代次数.

2 改进粒子群算法

2.1 改进粒子群算法步骤

本文将种群的多样性作为群活性[8]，多样性反馈又称为群活性反馈(swarmactivityfeedback-SAF)是指通过种群多样性算子对群活性进行量化分析，当群活性减少时，采用高斯惯性权重改进操作产生新的惯性权重.算法步骤描述如下：

步骤1：初始化粒子群.粒子群的大小N，搜索空间维数D，最大迭代次数t，寻优目标函数，惯性权重w，社会参数，c1,c1及r1，r2；

步骤2：计算当前代粒子位置的适应度函数值，比较更新局部最优和全局最优；

步骤3：判断当前迭代次数是否达到最大或者适应度函数为0，若满足则直接跳到步骤7，否则执行步骤4；

步骤4：将当前粒子的位置和速度带入式(2)、(3)计算下一代粒子的速度和位置，并将迭代次数加1；

步骤5：计算当前粒子的平均粒子距(种群多样性计算)；

步骤6：判断群活性是否降低，若降低则进行高斯惯性权重改进操作产生新的惯性权重，然后使用新得到的惯性权重，若没有降低则执行步骤2；

步骤7：输出显示寻到的最优位置(也可以输出迭代次数等)；

粒子群算法在一定的范围区间内寻找函数的最优(最大值或最小值等)，若想找到全局最优，则希望所有粒子分布在这个搜索区间.由于锁定惯性权重时，粒子后期迭代速度主要由粒子的历史和全局最优位置引导，不能有效的跳出局部范围.如当迭代到t次时，粒子群算法中的每个粒子由原来在每个粒子位置为中心10为半径的邻域，缩减到了2为半径的邻域，而不能跳出10以外的邻域，这样种群群活性减少而陷入局部最优.通过高斯变异调节到适当的惯性权重，可以使粒子跳出局部，有效的分布到整个区间.实验分析，本文的惯性算子比于其他的改进惯性算子简单且产生的惯性权重分布[0.2,0.8]内，能够很好的涵盖整个区间.

2.2 多样性反馈机制

本文采用所有粒子的平均粒子距变化直接反应粒子的群活性，根据二维空间距离的求解推广到D维，得到第t+1次迭代后，粒子的平均粒子距公式为：

(4)

所有粒子的平均变化率公式为：

(5)

由式(2)、(5)化简后得到所有粒子的平均变化率公式为：

(6)

由式(6)可以看出，使用迭代粒子的平均粒子距表示粒子群活性可以通过调节粒子的速度来实现，对于粒子群速度的调节方法有很多，有些直接对速度初始化，有些则通过惯性权重对速度进行改进，由于通过对速度初始化操作的效果不够好，本文采用惯性权重调节的方式对速度进行改进，在2.3节会介绍.

2.3 改进惯性权重算子

通过学者们对于固定惯性权重w的取值(一般在[0,1.0])和非固定取值进行了大量的研究总结出：采用固定取值时，w的值在[0.3,0.7]之间时，算法的收敛速度较快，当w时，算法容易陷入局部最优[12].w采用非固定值时，通过递减或自适应调节算法进行计算，使其在0～1.0之间变换，粒子群算法在收敛速度和全局搜索能力上取得不错的结果.本算法采用高斯分布算子，相对于其他惯性权重算子，本算子优点如下：①算子更为简单，直接使w服从正态分布模型，一定有效范围内变化，便于算法收敛;②实验表明本算子对惯性权重的调节正好处于[0.3,0.7]最优范围内.数学期望为μ、方差为σ，则w的计算公式为：

(7)

式中:ε是在迭代过程中产生的随机数.在迭代搜索过程中，当粒子群算法的群活性变化不大时，选取0.3～0.7之间的数并采用固定惯性权重求解策略；当粒子群算法的群活性降低时，采用调整策略计算新的w对位置、速度进行更新.

3 仿真实验

在实验时，粒子群算法的参数设置为：c1=c2=2，原始ω=0.8,最大迭代次数为400，每个粒子维数为10，种群大小为50，精度为10-6，高斯变异算子参数为：μ=0,σ=0.5.首先对改进算子进行实验，群活性算子和高斯变异惯性权重进行Matlab仿真实验.群活性测量采用经典函数进行，对群活性值进行了一定的缩放，这种缩放不会影响群活性的变化曲线，形成的曲线如图1所示.

图1 粒子群活性变化图

从粒子群活性图中可以看出，SAF-GPSO算法相对于最基本的粒子群算法(PSO算法)在群活性变化上存在起伏波动，SAF-GPSO算法在迭代到100次群活性降到最低，而PSO算法迭代到50次就降到最低，延长了近一倍的迭代时间. 对于寻优性能比较，使用经典的测试函数Sphere函数和Rastrigrin函数，公式如下:

-5.12≤xi≤5.12

算法的性能随粒子维数变化使用遗传算法(GA)，PSO和SAF-GPSO算法比较如表1所示.

表1 算法的平均适应度值

由表1可以看出本文改进算法在函数求解精度上随着维数的增加优于PSO和GA算法，在函数上随着维数的增加，优于PSO算法，但当维数增加一定程度就没有遗传算法(GA)的求解精度好.对于求解效率，优于PSO收敛快，故使用SAF-GPSO算法和PSO算法进行比较.经过400次迭代后取的Sphere函数最优位置各维分量和适应度函数值变化分布如图2所示.

(a)Sphere函数分析图

(b)Sphere函数适应度函数值比较图

实验表明SAF-GPSO算法与PSO算法相比在单峰函数Sphere求解寻优性能和迭代次数上取得了很大的提高.对于多峰函数及分散性求解的SAF-GPSO寻优性能使用Rastrigrin函数，经过400次迭代后去的函数最优位置各维分量和适应度函数值变化分布如图3所示.

由3可知，迭代400次后，Rastrigrin函数最优位置各维分量和求解问题适应度函数优化效果没有第Sphere函数优化效果好，不过在整体的寻优能力和时间上都比原始的粒子群算法更好.由第二个小图的缩放图可以看出，本文算法在迭代到45次左右时，适应度函数就接近于0，而原始的粒子群算法则需要迭代到110次左右，故本文算法在Rastrigrin函数求解上也提高了近3/4的迭代次数.

(a)Rastrigrin函数分析图

(b)Rastrigrin函数适应度函数比较图

4 结论

本文提出了一种以种群多样性作为群活性反馈的高斯粒子群优化算法.通过算法改进分析和函数实验结果表明:多样性反馈能够很好的增加群活性，提高近一倍；改进惯性权重算子提高全局搜索，迭代时间缩短3/4；综上可知，改进算法能够有效地调节PSO的早熟现象，搜索性能更优化.

[1]EBERHART R C,SHI Y H.Comparing inertia weights and Constriction factors in particle swarm optimization[C].Proc of the 2000 Congress on Evolutionary Computation.San Diego: IEEE,2000:84- 88.

[2]JIAO B,LIAN Z G.A dynamic inertia weights particle swarm optimization algorithm[J].Chaos Solutions&Fractals,2008,37(3):698- 705.

[3]张顶学,廖锐全.一种基于种群速度的自适应粒子群算法[J].控制与决策,2009,24(8):1257- 1265.

[4]ZHAN Z,ZHANG J.Adaptive particle swarm optimization[J].IEEE Trans on Systems,Man and Cybernetics,Part B:Cybernetics,2009,39(6):1362- 1381.

[5]秦全德,李荣钧.基于生物计生行为的双种群粒子群算法[J].控制与决策,2011,26(4):548- 552.

[6]WANG Y,LI B,WEISE T,et al.Self-adaptive learning based particle swarm optimization [J].Applied Soft Computing,2011,11(1):574- 584.

[7]杨帆,胡春平,颜学峰.基于蚁群系统的参数自适应粒子群算法及其应用[J].控制理论与应用,2010,27(11):1479- 1488.

[8]左旭坤,苏守宝.一种群活性反馈粒子群优化算法[J].计算机工程,2012,38(13):183- 184.

[9]LI PENG,QUAN HUIYUN.Improved hybrid particle swarm optimization algorithm[J].Computer EngineeringandApplication,2010,46(11):29- 31.

[10]张浩,张铁男,沈继红，等.Tent混沌粒子群算法及其在结构优化决策中的应用[J].控制与决策,2008,23(8):857- 863.

[11]EBERNART R C,KENNEDY J.Particle swarm optimization [C]// IEEE International Conference on Neural Networks.Perth,Australia,1995:1942- 1948.

[12]田雨波,朱人杰,薛权祥.粒子群优化算法中惯性权重的研究进展[J].计算机工程与应用,2008，23:39- 41.

A Diversity of Feedback Gauss Particle Swarm Algorithm

HUANG Ming,ZHANG Chunlei,WU Yaoxu,HAO Qian

(Software Institute,Dalian Jiaotong University,Dalian 116028,China)

The diversity of the population feedback (swarm activity feedback) and Gauss normal inertia weight mutation operator is introduced to improve the particle swarm algorithm.When the particles swarm diversity is reduced,the inertia weight of particle is state calculation of regulation,and then adjust the particle velocity and position which could make the PSO jump out of local optimal solution. The standard function simulation results show that,compared with the standard particle swarm optimization algorithm,this algorithm is greatly improved in global search ability and search performance.

particle swarm optimization;inertia weight;diversity feedback;Gauss distribution

1673- 9590(2015)01- 0105- 04

2014- 02- 19

国家863计划课题资助项目(2012AA041402-4)；辽宁省高校优秀青年学者成长计划资助项目(LJQ2013048)

黄明(1961-),男,教授，博士，主要从事计算机管理信息系统的研究

E-mail:dlhm@263.net.

A