基于动态因子和共享适应度的改进粒子群算法

2016-12-15谭熠峰孙婷婷徐新民

浙江大学学报(理学版) 2016年6期

关键词：适应度全局粒子

谭熠峰, 孙婷婷, 徐新民

(浙江大学信息与电子工程学院，浙江杭州 310027)

表1 测试函数及其特点

表2 粒子数较多时算法的迭代对比

表3 粒子数较少时算法的迭代对比

基于动态因子和共享适应度的改进粒子群算法

谭熠峰, 孙婷婷, 徐新民*

(浙江大学信息与电子工程学院，浙江杭州 310027)

为提高粒子群算法的收敛速度和优化性能，避免陷入局部最优，提出了一种基于动态学习因子和共享适应度函数的改进粒子群算法.在惯性权重w随着迭代次数非线性减少而动态调整学习因子的基础上，引入共享适应度函数.当算法未达到终止条件而收敛时，利用粒子和最优解间距离挑选一批粒子重新初始化形成新群体，并用共享适应度函数对新群体进行评价，新旧2个群体分别追随自己的局部最优解直至迭代结束.对4个典型多峰复杂函数的测试结果表明，该改进算法不仅加快了寻得最优解的速度，而且提高了粒子群算法全局收敛的性能.

动态；学习因子；共享适应度；粒子群算法

0 引言

粒子群算法(Particle Swarm Optimization, PSO)的基本概念源于对鸟群觅食行为的研究，最早用于模拟简单的社会系统.与遗传算法、蚁群算法等进化计算方法相比，PSO算法具有收敛速度快、设置参数少、程序实现简洁方便等特点，可以解决大量非线性、不可微、连续多峰的优化问题，已广泛应用于神经网络训练、函数优化和模糊系统控制等领域[1-4].但是，由于PSO算法在优化过程中追随最优解，所有粒子趋向同一化，如果该最优解所在位置为一局部最优点，粒子群就难以跳出局部最优，出现早熟收敛现象.

为了克服标准PSO算法早熟收敛的缺点，GANDOMI等[5]提出了混沌增强型PSO算法，WANG等[6]提出通过增加变异算子改进PSO算法，张健等[7]提出了动态约束因子法(Dynamic Constrain Factor PSO, DCF-PSO).这些改进算法明显提高了收敛的速度，但在局部收敛方面收效甚微.本文在改进动态调整学习因子的基础上，引入遗传算法中的共享适应度函数，每当算法陷入局部最优时，根据海明距离对部分粒子重新初始化，并用共享适应度函数来评价新粒子群，对旧粒子群则通过调整学习因子方法达到快速精确搜索.通过经典测试函数结果表明，该改进在加快算法收敛速度的同时，大大提高了全局收敛的成功概率.

1 标准粒子群和动态约束因子算法

1.1 标准粒子群算法

(1)

(2)

1.2 动态约束因子算法

为了改进标准粒子群算法，避免粒子群算法过早收敛，根据进化算法在运行初期需加强全局搜索解空间能力，后期需要细化解空间开拓能力的特点，文献[7]提出了一种根据惯性权重值w的非线性递减动态调整学习因子c1和c2的DCF-PSO.该算法中w和c1、c2分别按式(3)与(4)更新：

(3)

c1=c2=0.5w2+w+0.5，

(4)

其中，wfinal和winitial分别为w的最大值和最小值，LoopIter表示最大迭代次数，CurIter表示当前迭代次数，n是幂级数.

实验结果表明，该改进有效提高了粒子群算法的收敛速度，但其全局收敛性能未能明显提高.

2 改进的PSO算法

2.1 共享函数

GOLDBERG等[9]在遗传算法中提出用共享函数度量2个个体的相邻关系和程度.给定个体g，其共享函数由其与种群中其他个体的关系决定，每个个体有一个共享函数值Si，i=1,2,…,P，则个体的原适应度函数f(i)可调整为新的适应度函数f(i)new：

(5)

文献[10-11]提出了基于共享函数改进型粒子群优化算法(Fitness Sharing Particle Optimizer, FSPSO).该算法初期同标准PSO，当粒子群陷入局部最优或暂时停滞状态时，随机选择部分粒子重新初始化为一个新群体，同时保留部分作为旧群体用于继续搜索局部最优.2个群体在各自最优个体gbest下更新和搜索.新群体利用给定共享半径dshare得到的共享适应度函数阻止新群体立刻回到局部最优.该算法能达到跳出局部最优的目的，但速度比标准算法低.

2.2 改进的粒子群算法

为同时提高标准全局版PSO的收敛速度和全局收敛性，保证群体多样性的存在，防止算法过早成熟，结合文献[7]中的DFC-PSO和文献[10]中的FSPSO，提出了带有动态学习因子和共享适应度函数的粒子群算法.

在算法迭代早期，利用式(1)与(2)动态调整w和c1、c2，更新粒子的速度和位置.

当粒子群陷入局部最优时，对部分粒子重新初始化形成新群体.由于旧群体用于在早熟区继续寻找最优，因此越接近最优位置越好，本文将与早熟区最优解之间距离较近的粒子作为旧群体，分布较为分散的部分粒子则进行变异，再次初始化.给定个体xi，其与种群已找到的最优位置xg间的距离shi由海明距离决定：

(6)

假定有一个8个粒子的群体在某一时刻局部收敛到位置xg，如图1左图所示，且sh8>sh6>sh7>sh1>sh4>sh5>sh3>sh2，按海明距离值的大小顺序，取出占粒子总数前75%(即6个)的粒子作为新群体变异.保留位置较为集中的2个，构成一个独立的旧群体，继续搜索早熟区的最优解gbest.

图1 粒子群分布图Fig.1 Distribution of a particle swarm

为更好地搜索到最优解，本文按粒子类别分类调整学习因子.由于新群体被初始化，按式(3)与(4)计算w更新粒子，其中式(3)中分母上的迭代总数LoopIter变为LoopIternew，LoopIternew为剩下还未发生的迭代总次数，以保证w重新从wfinal递减至winitial.而旧群体用于追随最优解，因此早熟区粒子的惯性权重w和认知学习因子c1继续减小，而用于追随最优解的社会学习因子c2：

c2=4-c1.

(7)

则按式(7)调整，以便增大粒子的社会学习信息，寻得早熟区最优解.

然而，新群体中的粒子也可能再次进入早熟区，如图1右图中的粒子x6.为阻止粒子在迭代过程中再次陷入同一最优点，参照文献[10]利用共享距离dshare对新个体的适应度进行调整.本文根据粒子群的分布关系采用动态计算方法改变dshare.在初始化之前，根据shi的大小，以dshare=shm作为早熟区的判断条件，其中shm为占粒子总数百分比为m的粒子的距离.在图1中当m=25%时，dshare为粒子x3到最优解的距离.重新初始化后，计算新群体中粒子到早熟区最优解的距离d_deci，若d_deci

(8)

其中M为增强适应度的一个常数，取值1 000.

可见若新粒子进入早熟区，越靠近收敛中心其

对于粒子群是否陷入局部最优，可借鉴文献[12]中使用的判断方法，当gbest和每个粒子的pbest均值分别连续，T1和T2迭代最优值没有得到提升，则选择部分粒子重新初始化.

算法具体步骤如下：

1)对粒子的位置和速度进行随机初始化；

2)分别计算粒子的适应度，判断迭代次数是否超过最大值，若是则跳至步骤6，否则继续；

3)判断粒子群是否收敛，若是则跳至步骤5，否则继续；

4)按算法动态更新约束因子，更新每个粒子的位置与速度，跳至步骤2；

5)计算海明距离值shi及共享距离dshare，选出部分粒子重新初始化，跳至步骤2；

他们的通话内容如下：“老公，是不是我想要什么你都会给我啊？”“那当然。”“我要星星。”“你养仙人球都死，还养猩猩？一头猩猩多少钱？”“不是，我要天上的星星！”“这个啊……晚上回家带你看。”

6)迭代停止，得到最优解.

2.3 改进实验结果

为了说明改进的有效性，在Dell-T7500、操作系统为Windows8、所用仿真软件Matlab版本为R2013a的环境下，将标准PSO、n=1.2的DCF-PSO与FSPSO以及本文算法进行对比.其中wfinal=1.0，winitial=0.3，变异比例l=0.6，对固定系数的算法选择c1= c2=2，w=0.729.为更好地对上述算法进行评估，避免算法性能表现出偶然性，采用4个经典多峰函数Griewank、Rastrigin、Ackley及Schaffer为适应度评价函数，这些函数存在大量局部最优值，很难从中找到全局最优值，是评估算法性能的理想函数，各测试函数的特点如表1所示.

[8,11,13]，表2列出了当Griewank、Rastrigin、Ackley粒子数为53、Schaffer粒子数为8时，算法的迭代条件及运行结果.同时作为对比，表3列出了当粒子数减少，Griewank、Rastrigin、Ackley粒子数为30、Schaffer粒子数为5时算法的迭代条件及运行结果.其中Ps表示成功收敛到最优解的次数，Tave表示达到门限值时的平均迭代次数.

表1 测试函数及其特点

Table 1 Test functions and their characters

表2 粒子数较多时算法的迭代对比

Table 2 Performance comparison of algorithms with more particles

表3 粒子数较少时算法的迭代对比

Table 3 Performance comparison of algorithms with fewer particles

由表2可知，当粒子数较多时，DCF-PSO的收敛速度明显提高，但其全局收敛性与标准PSO无明显差异；FSPSO的全局收敛性更好，搜索到最优解的次数增加，但其收敛速度与标准PSO几乎一致.DCF-PSO动态调整学习因子使得算法在不同时期有不同的搜索能力和速度，提高收敛速度的同时不至于经常陷入局部最优；FSPSO始终保证粒子群体的多样性，能够及时从局部最优状态中跳出，从而提高了全局收敛性.

改进算法结合了DCF-PSO和FSPSO的优点，相对于前述3种算法，其全局收敛性明显增强，成功搜索到最优解的次数Ps大大增加，几乎每次都能收敛到最小值；同时与前3种算法相比，改进算法的平均收敛次数更少，收敛速度提高很多，且均优于单独改进的DCF-PSO或FSPSO.

由表3可知，当粒子数较少时，各算法成功收敛到最优解的次数都有明显降低，速度变慢.DCF-PSO和FSPSO与标准PSO相比，其性能与粒子数较多时一致，改进算法相较于前述3种算法，全局收敛性明显变好，优于单独改进的DCF-PSO或FSPSO，但其收敛速度与DCF-PSO比无显著变化，比标准PSO和FSPSO要快.

3 结论

PSO算法是一种实现容易、精度高、收敛快的进化优化算法.本文在惯性权重随着迭代次数减小、动态改进学习因子的基础上，引入遗传算法中的共享适应度函数.在运算过程中，随着算法收敛选择部分粒子的初始化，将粒子群变异为新旧2个群体后进一步搜索全局最优解，通过动态共享距离阻止新群体回到旧群体的局部最优值.该改进算法相对于标准PSO计算量并未显著增加，对经典多峰复杂函数的仿真实验表明：该算法在不同粒子数量下均表现出更好的性能，具有很强的适应性，不仅加快了其寻得最优解的速度以及收敛速度，而且增强了粒子群算法全局收敛的性能.

参考文献(References)：

[1] 龙泉,刘永前,杨勇平.基于粒子群优化BP神经网络的风电机组齿轮箱故障诊断方法[J].太阳能学报，2012,33(1):120-125. LONG Quan, LIU Yongqian, YANG Yongping. Fault diagnosis method of wind turbine gearbox based on BP neural network trained by particle swarm optimization algorithm[J].Acta Energiae Solaris Sinica,2012,33(1):120-125.

[3] 王登科，李忠.基于粒子群优化与蚁群优化的云计算任务调度算法[J].计算机应用与软件，2013,30(1):290-293. WANG Dengke, LI Zhong. A task scheduling algorithm based on PSO and ACO for cloud computing[J]. Computer Applications and Software,2013,30(1):290-293.

[4] KHARE A, RANGNEKAR S. A review of particle swarm optimization and its applications in solar photovoltaic system[J]. Applied Soft Computing,2013,13(5):2997-3006.

[5] GANDOMI A H, YUN G J, YANG X S, et al. Chaos-enhanced accelerated particle swarm optimization[J]. Communications in Nonlinear Science and Numerical Simulation,2013,18(2):327-340.

[6] WANG G G, GANDOMI A H, YANG X S, et al. A novel improved accelerated particle swarm optimization algorithm for global numerical optimization[J]. Engineering Computations,2014,31(7):1198-1220.

[7] 张健，朱旭东，王真.一个新的动态约束因子PSO算法[J].河北工业大学学报，2010,39(003):51-55. ZHANG Jian, ZHU Xudong, WANG Zhen. A new dynamic constrain factor particle swarm optimization algorithm[J]. Journal of Heibei University of Technology,2010,39(3):51-55.

[8] KENNEDY J. Particle Swarm Optimization[M]// SAMMUT C, WEBB G I. Encyclopedia of Machine Learning. New York: Springer US,2010:760-766.

[9] GOLDBERG D E, RICHARDSON J. Genetic algorithms with sharing for multimodal function optimization[C]// Proceedings of the Second International Conference on Genetic Algorithms on Genetic Algorithms and Their Application. Hillsdale: L Erlbaum Associates Inc,1987:41-49.

[10] LI T, WEI C, PEI W. PSO with sharing for multimodal function optimization[C]//Proceedings of the 2003 International Conference on Neural Networks and Signal Processing, 2003. Nanjing: IEEE,2003(1):450-453.

[11] 白瑞林，王利峰.一种基于共享法的改进型粒子群优化算法[C]//2005中国控制与决策学术年会论文集(上).沈阳：东北大学出版社，2005：795-798. BAI Ruilin, WANG Lifeng. A modified particle swarm optimization algorithm based on sharing method[C]//Proceeding of 2005 Chinese Control and Decision Conference. Shenyang: Northeastern University Press,2005:795-798.

[12] 刘衍民，隋常玲，牛奔.解决约束优化问题的改进粒子群算法[J].计算机工程与应用，2011(12):23-26. LIU Yanmin, SUI Changling, NIU Ben. Improved particle swarm optimizer for constrained optimization problems[J]. Computer Engineering and Applications,2011(12):23-26.

[13] 邬啸.一种对粒子群算法惯性权重的改进[J].计算机时代，2010(10):25-27. WU Xiao. An improvement for inertia weight of particle swarm optimization[J]. Computer Era,2010(10):25-27.

[14] 周飞红,廖子贞.自适应惯性权重的分组并行粒子群优化算法[J].计算机工程与应用，2014,50(8)：40-44. ZHOU Feihong, LIAO Zizhen. Grouping parallel particle swarm optimization algorithm with adaptive inertia weight[J]. Computer Engineering and Applications,2014,50(8)：40-44.

TAN Yifeng, SUN Tingting, XU Xinming

(CollegeofInformationScience&ElectronicEngineering,ZhejiangUniversity,Hangzhou310027,China)

A modified particle swarm optimization algorithm based on dynamic learning factors and sharing method. Journal of Zhejiang University(Science Edition), 2016,43(6):696-700

To improve the global convergence ability and rate of particle swarm optimization, an improved particle swarm optimization algorithm based on dynamic learning factors and sharing method is proposed. The inertia weight factor of the algorithm decreases non-linearly, and the learning factor changes dynamically with the descending. A sharing fitness function is introduced on the basis of dynamic regulation. When the algorithm is stagnated without reaching termination, part of the particles will be selected according to the distance between particles and optimal solution. The chosen particles will be re-initialized as a new swarm and be evaluated by sharing fitness. The old and new swarms follow their own local solutions respectively until the end of the iteration. Simulation results of four typical multimodal functions show that the modified algorithm can greatly enhance the rate of the optimal solution searching and improve the global convergence performance of PSO.

dynamic; learning factor; sharing fitness; particle swarm optimization