一种动态分组的粒子群优化算法

王燕燕,葛洪伟,王娟娟,杨金龙

(1.江南大学物联网工程学院,江苏无锡214122;2.国网潍坊供电公司,山东潍坊261021)

一种动态分组的粒子群优化算法

王燕燕1,葛洪伟1,王娟娟2,杨金龙1

(1.江南大学物联网工程学院,江苏无锡214122;2.国网潍坊供电公司,山东潍坊261021)

针对粒子群优化算法易陷入局部最优的问题,提出一种动态分组的粒子群优化算法。通过对鸟群习性的研究,给出交互粒子的概念,并在粒子群优化过程中引入动态分组机制,将种群动态划分成多个子种群,且每次划分的子种群数目是从特定集合中随机选取,从而增加交互粒子划分到同一子种群的概率。每个子种群在收敛进化的同时,利用环拓扑结构提高种群多样性及算法搜索全局最优解的能力。实验结果表明,与其他粒子群优化算法相比,该算法具有更好的稳定性、寻优性能以及更高的收敛精度。

粒子群优化;局部最优;全局最优;交互粒子;动态分组;环拓扑结构

1 概述

粒子群优化(Particle Swarm Optimization,PSO)算法[1]是由Kennedy等人在1995年提出的一种基于种群的智能优化算法,该算法具有可变参数少、简单易于实现的特点,得到广泛关注。为了避免粒子陷入局部最优,提高粒子的全局搜索能力,增加算法的应用领域,研究者对其进行了大量研究,以期达到更好的优化能力。在算法参数的改进方面,文献[2]将惯性权重引入到速度更新公式中,提高了算法的收敛速度;文献[3-6]研究了惯性权重、参数的设置对算法优化性能的影响。在种群划分的改进方面,文献[7]将合作框架引入到PSO算法中,将种群划分成多个子种群,通过子种群协同合作,提高种群优化性能;文献[8]将主从模式引入到PSO算法中,将种群划分成多个子种群:由一个主群和几个奴仆群组成,提高了种群的多样性和收敛速度;文献[9]采用控制理论的分层思想,提出多种群分层PSO算法,有效提高了算法收敛速度;文献[10]提出一个基于动态邻居的多子种群PSO算法,避免算法陷入局部最优;文献[11]在文献[10]的基础上,提出一种基于动态邻居和变异因子思想的粒子群优化算法(DNMSPSO),提升了粒子跳出局部最优的能力。在其他改进方面,文献[12]提出基于学习策略的综合学习粒子群优化(CLPSO)算法,提高了算法解决多峰问题的性能;文献[13]使用Monte Carlo随机投点的方法确定粒子的具体位置进行协同进化更新,提高了算法优化性能。

上述研究对提升算法的收敛速度和运行效率有一定成效,但在种群多样性、跳出局部最优及收敛精度上仍存在不足。粒子群优化算法是从鸟群寻找食物的生物现象中得到启发,鸟群在寻找食物的过程中可能存在结伴现象,且不知道哪几只鸟结伴和结伴鸟的个数。在粒子群优化算法中,由于粒子之间的“结伴现象”(简称交互粒子)事先不知道,交互粒子的个数也不确定,因此交互粒子的出现可能导致种群陷入局部最优。为保证种群的多样性,避免种群陷入局部最优,提高种群的全局收敛性,提升算法的寻优能力,本文结合鸟群结伴行为的特性,提出一种动态分组的粒子群优化(DGPSO)算法,将种群动态地划分成多个子种群,每次划分的子种群数目从特定集合中随机取得,且子种群的数目不定,从而增加交互粒子划分到同一子种群的概率,而且在不同子种群中寻找全局最优,能增加种群的多样性,避免算法易陷入局部最优。

2 标准粒子群

PSO算法是基于社会群体中个体行为的一种群体智能优化算法,它通过共享群体的信息和个体本身经验的总结来引导个体的行动方向,最终找到问题的最优解。

PSO算法对种群的位置xi=[x1,x2,…,xd]和速度vi=[v1,v2,…,vd],i=1,2,…,N进行随机初始化,并将通过迭代更新后的xi代入目标函数中,根据适应度值的大小判断找到粒子群的全局最优解。在迭代过程中,粒子通过2个极值更新其位置和速度。一个极值是粒子本身所遍历得到的最优解,称为个体最优解;另一个极值是整个种群到当前时刻所得到的最优解,这个极值称为全局最优解。此外,还有一个局部最优解,是指从种群中选取一部分作为当前粒子的邻居,取所有邻居中适应度值最好的值为当前粒子的局部最优解。PSO算法的速度和位置的更新公式为:

置的d维;w是惯性权重;c1和c2为加速因子,r1和r2是[0,1]内的随机数。

3 动态分组的粒子群优化算法

3.1 算法原理

优化算法在求解优化问题时,为了简化问题会在种群的进化开始前就确定好子种群的个数及其各子种群负责搜索的优化范围[7-11]。然而在优化过程中,给定的子种群粒子之间的关联不确定,所以这样一个静态的分组方法很有可能将交互粒子划分到不同的子种群中,从而降低粒子的收敛速度,增加粒子陷入局部最优的概率。种群中的交互粒子的数目不确定,可能2个或者更多的粒子是有关联的,为了便于理解,在此假设种群有2个交互粒子(A和B),且分别被划分到2个子种群中,迭代过程如图1所示。

图1 交互粒子的迭代过程

图1给出交互粒子的迭代过程,在种群被划分成2个子种群的情况下进行迭代。其中,黑箭头表示粒子运动方向;白箭头表示种群迭代进化的过程;1和2分别表示子种群1和子种群2;A和B分别表示第一次迭代下粒子A和粒子B所处的位置;C表示第n+1次迭代下粒子A和粒子B所处的位置。假设粒子A和粒子B是各自子种群的最优位置。随着种群的迭代进行,粒子A和粒子B的位置可能更新到同一个位置,那么2个子种群的局部最优解一致,此时,种群极有可能陷入局部最优。

本文在PSO算法思想的基础上,给出一种具有全局收敛性的改进算法DGPSO。DGPSO算法不指定固定的子种群数目,而是每次迭代时,从集合中随机选取子种群数目的一种动态的分组方法。这里的集合中包含了几个可能的从小到大的子种群的数目s,例如,S={2,3,5,6,10}。若适应度得到了改善,则继续使用原来的s值;否则需要重新选取一个不同的值。尽管仍然需要设置S集,但是参数s不再是必需的。动态随机分组无需知道待优化问题的任何先验知识。

3.2 算法进化机制

各子种群分别进行一次优化搜索后,粒子各维的位置改变一次,粒子各维的速度更新公式为:

位置更新公式为:

其中,i是第m个子种群内的粒子;m是从集合S=[s1,s2,…,st]中随机取得的分群数目;v′p是粒子i的认知部分;v′g是粒子i的社会部分;是第k次迭代中粒子i的局部最优解;是当前粒子i对应的全局最优解;和是第k次迭代中粒子i对应的速度和位置;w是惯性权重;c1和c2为加速因子;r1和r2是[0,1]内的随机数。

在DGPSO算法中,采用环拓扑结构策略求解局部最优解,求解过程如图2所示。以图2中粒子A为例,当前的粒子是A时,邻域为粒子B、粒子H,取3个粒子的适应度最小值作为粒子A的局部最优解;当前的粒子是B时,邻域为粒子A、粒子C,取3个粒子的适应度最小值作为粒子B的局部最优解;以此向后进行类推;当前的粒子是H时,整个粒子群的环拓扑循环结束。A=min(A,B,H)表示当前的粒子A与邻域粒子B、粒子H的适应度进行比较,找出适应度值最小值对应的粒子作为该粒子A的局部最优解。

图2 环拓扑结构

为取得更好的收敛性能,随着迭代的进行,粒子群的搜索范围从全局逐步向局部进行搜索,w值也随之改变,w的更新公式如下[2]:

其中,wmax表示惯性权重的最大值;wmin表示惯性权重的最小值;u表示当前的迭代次数;maxiter表示粒子群优化的最大迭代次数。

3.3 算法步骤

算法步骤具体如下:

步骤1设置粒子群数目、最大迭代次数、惯性权重最大值及最小值、学习因子、状态值cc和子种群数目集合S。

步骤2随机初始化种群中粒子的初始位置和速度。

步骤3在约束条件下求出粒子的适应度值,并分别记录个体最优解和全局最优解。

步骤4判断状态值cc是否等于0,若等于0,则从集合S=[s1,s2,…,st]中随机选取子种群的数目,按照该子种群的数目重新划分子种群;若不等于0,则子种群保持当前划分。

步骤5分别求出各子种群的适应度值,记录个体最优解和各子种群的全局最优解,通过环拓扑结构策略,求出粒子的局部最优解。

步骤6利用式(3)、式(4)更新各子种群中粒子的速度和位置。

步骤7各子种群的全局最优解与粒子群的全局最优解比较,若粒子群的全局最优解并没有得到更新,则状态值cc不变;若得到更新,则状态值cc加1。

步骤8判断是否满足终止条件,即是否已经达到设置的最大迭代次数,若满足,则执行步骤9;否则返回执行步骤4。

步骤9终止优化运算,输出粒子的最优位置和全局最优解。

3.4 算法验证

在种群进化迭代中,给定的粒子群数目N随机分成m个子种群,每个子种群包含个粒子。随着迭代次数的增加,2个交互粒子被划分到相同子种群的概率变得更高(推理过程,见证明),概率公式如下:

其中,X是交互粒子划分到同一个子种群的次数;k是交互粒子划分到同一个子种群的迭代次数;r是当前的迭代次数;H是总的迭代次数;是的简写,是从H个次数中取出r(r≤H)次的组合数;m是子种群数目;v是交互粒子的总数;X取大于或等于k值;k值限制在一个小于H大于0的范围内。

证明:

(1)将种群划分成m个子种群;

(2)由概率公式可知,在种群中的粒子被划分到其中一个

(3)假设在种群中存在着v个交互粒子,那么这些交互粒子被划分到同一个子种群中的概率为:

(4)种群中共有m个不同的子种群,所以在种群中与步骤(3)一样的情况会有m种不同划分的可能,则总概率为:

(5)种群在经过r次迭代后,所有N个粒子随机划分到m个子种群中,由二项概率分布可知,计算种群中所有交互粒子到同一个子种群的概率公式如下:

由上述证明过程可知,在不同迭代次数下,交互粒子被划分到相同子种群的概率见式(6)。

实例当N=40,m=10,H=50,v=4时,交互粒子划分到同一个子种群的概率为:

其中,p(1)表示在50次迭代中2个粒子被放置到同一个子种群中的情况出现一次的概率;p(2)表示在50次迭代中2个粒子被放置到同一个子种群中的情况出现2次的概率;p(50)表示有50个这样的情况“成功”的概率。式(7)表明,随机分组策略将帮助解决交互粒子的问题,且概率会随着子种群的数目变化而发生相应改变。种群最优解的更新如图3所示。

图3 种群最优解更新

将每个子种群的全局最优解Pi_gbest,i=1, 2,…,m分别与种群的全局最优解gbest进行比较,用最小值取代gbest(gbest=min(gbest,P1_gbest,P2_gbest,…,Pk_gbest)),若gbest得到更新,那么仍继续使用现在的分组进行迭代;若gbest没有得到更新,则需要对种群进行重新分组。其中,k,k′表示粒子数;m表示子种群数目。

4 实验结果与分析

4.1 测试函数

为测试本文算法性能,采用了12个测试函数。

其中,f1～f5函数是单峰函数;f6～f12函数是多峰函数。函数具体取值范围和最优解如表1所示。

表1 测试函数

4.2 结果分析

为测试DGPSO算法的有效性,本文将DGPSO算法与以下算法进行对比:

(1)基本粒子群优化算法PSO[2];

(2)基于动态邻居的DNMSPSO算法[11];

(3)基于综合学习的CLPSO算法[12];

(4)基于协同量子的CQPSO算法[13]。

本文实验采用Matlab7.8进行仿真,系统软硬件环境为:2.20 GHz,4.00 GB内存,Windows7操作系统。实验中,DGPSO算法与PSO算法[2]惯性权重最大值设为0.9,最小值设为0.4,学习因子c1=1.7,c2=2.05,DNMSPSO算法的参数设置与文献[11]中的一致,CLPSO算法的参数设置与文献[12]中的一致,CQPSO算法的参数设置与文献[13]中的一致。5个算法的最大迭代次数均设置为1 000次,粒子数目为30个,维数为30维,DGPSO算法的子种群数目集合为S=[2,3,5,6,10],测试函数如表1所示,取50次运行结果的平均值。

DGPSO算法的时间复杂度为O(N×D×maxiter),其中,N为粒子群数目;D为粒子维数;maxiter表示粒子群优化的最大迭代次数。

表2为5个算法在12个测试函数上的实验结果,其中,最差解和最好解分别表示在50次独立运行中,算法找到的最差的最优解和最好的最优解。均值表示在50次独立运行中,算法最优解的平均值。方差表示50次独立运行中,算法的稳定性。为了准确判定算法的优化能力,取上述测试指标中的均值和方差作为评价标准。

表2 4种算法在测试函数上的实验结果

由表2的均值和方差结果可以看出DGPSO算法的实验结果,除了在f1函数的优化性能比CQPSO算法[13]稍差,f2～f12测试函数的实验结果都明显优于其他算法,其收敛精度和稳定性较好。

图4～图9给出了5种算法在6个测试函数中的迭代进化曲线对比,为了便于观察,将各算法寻找到的最优解进行取对数操作。可以看出,本文提出的DGPSO算法在收敛速度上具有明显优势,可以有效跳出局部最优,且算法搜索到的解的精度高。由于篇幅有限,本文只列举了6个测试函数的对比图,在其他测试函数上算法也具有相似的性能。

图4 算法在f3函数上的迭代效果

图5 算法在f4函数上的迭代效果

图6 算法在f5函数上的迭代效果

图7 算法在f7函数上的迭代效果

图8 算法在f11函数上的迭代效果

图9 算法在f12函数上的迭代效果

5 结束语

本文提出一种采用动态随机划分子种群策略的粒子群优化算法。该算法能增加交互粒子划分到同一个子种群的概率,避免不同子种群搜索范围可能相同的情况,帮助种群跳出局部最优。理论分析和实验结果表明,DGPSO算法能有效利用粒子的共享信息、扩大种群的搜索范围、提高算法的寻优性能以及处理复杂多峰问题的能力。

[1] Kennedy J,Eberhartr C.Particle Swarm Optimization[C]// Proceedings of IEEE International Conference on Neural Networks.Perth,USA:IEEE Press,1995:1942-1948.

[2] Shi Yuhui,EberhartR.A Modified Particle Swarm Optimizer[C]//Proceedings of 1998 IEEE International Conference on World Congress on Computational Intelligence.Anchorage,USA:IEEE Press,1998:69-73.

[3] Eberhart R C,Shi Y.Comparing Inertia Weights and Constrict in Factors in Particle Swarm Optimization[C]// Proceedings of 2000 Congress on Evolutionary Computation.San Diego,USA:IEEE Press,2000:84-88.

[4] van den Bergh F,Engelbrecht A P.Effects of Swarm Size on Cooperative Particle Swarm Optimizers[C]//Proceedings of the 3rd Genetic and Evolutionary Computation Conference.San Francisco,USA:IEEE Press,2001.

[5] Chatterjee A,Siarry P.Nonlinear Inertia Weight Variation for Dynamic Adaptation in Particle Swarm Optimization[J].Computers&Operations Research,2006,33(3): 859-871.

[6] Zhan Z H,Zhang J,Li Y,et al.Adaptive Particle Swarm Optimization[J].IEEE Transactions on Systems,Man,and Cybernetics,2009,39(6):1362-1381.

[7] van den Bergh F,Engelbrecht A P.A Cooperative Approach to Particle Swarm Optimization[J].IEEE Transactions on Evolutionary Computation,2004,8(3):225-239.

[8] Niu B,Zhu Y,He X.Multi-population Cooperative ParticleSwarm Optimization[C]//Proceedings of ECAL’05.Berlin,Germany:Springer,2005:874-883.

[9] 吕 林,罗 绮,刘俊勇,等.一种基于多种群分层的粒子群优化算法[J].四川大学学报:工程科学版, 2008,40(5):171-176.

[10] Liang J J,Suganthan P N.Dynamic Multi-swarm Particle Swarm Optimizer with Local Search for Large Scale Global Optimization[C]//Proceedings of IEEE World Congress on Computational Intelligence.Hong Kong,China:[s.n.], 2008:3845-3852.

[11] 刘衍民,赵庆祯,隋常玲,等.一种基于动态邻居和变异因子的粒子群算法[J].控制与决策,2010,25(7):968-974.

[12] Liang J J,Qin A K,Suganthan P N,et al.Comprehensive Learning Particle Swarm Optimizer for Global Optimization of MultimodalFunctions[J].IEEE Transactionson Evolutionary Computation,2006,10(3):281-295.

[13] Li Yangyang,Xiang Rongrong,Jiao Licheng,et al.An Improved Cooperative Quantum-behaved Particle Swarm Optimization[J].Soft Computing,2012,16(6):1061-1069.

编辑 陆燕菲

A Particle Swarm Optimization Algorithm of Dynamic Grouping

WANG Yanyan1,GE Hongwei1,WANG Juanjuan2,YANG Jinlong1
(1.College of Internet of Things Engineering,Jiangnan University,Wuxi 214122,China; 2.Weifang Power Supply Company,State Grid Corporation of China,Weifang 261021,China)

Aiming at Particle Swarm Optimization(PSO)algorithm is easy to fall into local optimal problems,this paper puts forward a PSO algorithm of dynamic group.Through the study of the flock behavior,the concept of interacting particles is presented.It introduces dynamic groupings into the PSO algorithm.Population is divided into multiple sub populations dynamically,and the number of each division of sub populations is randomly selected from a specific set.It increases the probability of interacting particles into the same sub population.During converging evolution,each sub population uses the ring topology structure to increase the diversity of population and the global search ability of the algorithm.Experimental results show that compared with other PSO algorithms,the algorithm has better optimal performance,stability,and higher convergence precision.

Particle Swarm Optimization(PSO);local optimum;global optimum;interacting particle;dynamic grouping;ring topology

1000-3428(2015)01-0180-06

A

TP18

10.3969/j.issn.1000-3428.2015.01.033

国家自然科学基金资助项目(61305017);江苏省自然科学基金资助项目(20130154);江苏高校优势学科建设工程基金资助项目。

王燕燕(1986-),女,硕士,主研方向:粒子群优化算法;葛洪伟,教授;王娟娟,工程师;杨金龙,副教授。

2014-01-21

2014-02-20 E-mail:wangyanyanever86@163.com

中文引用格式:王燕燕,葛洪伟,王娟娟,等.一种动态分组的粒子群优化算法[J].计算机工程,2015,41(1):180-185.

英文引用格式:Wang Yanyan,Ge Hongwei,Wang Juanjuan,et al.A Particle Swarm Optimization Algorithm of Dynamic Grouping[J].Computer Engineering,2015,41(1):180-185.