一种混合聚类的粒子群差分进化算法*

刘　阳,高兴宝,刘　睿

(陕西师范大学 数学与信息科学学院,西安 710119)



一种混合聚类的粒子群差分进化算法*

刘阳,高兴宝,刘睿

(陕西师范大学 数学与信息科学学院,西安 710119)

摘要：针对差分进化算法在运行后期收敛速度慢和容易陷入局部最优的不足,提出一种混合聚类的粒子群差分进化算法.利用一步K-均值聚类算法改进粒子群优化算法的速度更新,使用线性递减的选择概率将改进后的粒子群算法与差分进化算法相融合,并在一定条件下对种群中部分较差个体进行重置.对9个典型测试函数的数值试验和与其他三种进化算法的比较结果表明：所提算法收敛速度快,寻优能力强并且鲁棒性好.

关键词：K-均值聚类;混合算法;差分进化;粒子群优化;种群重置

进化算法(Evolutionary Algorithms,EA)起源于达尔文生物进化理论,通常指模拟自然界生物进化的全局优化方法[1].由于解决数值优化问题时,进化算法仅需要目标函数值,而不要求其解析性质,因此被广泛应用于科学和工程各种领域[2].

差分进化算法[3](Differential Evolution,DE)和粒子群优化算法[4](Particle Swarm Optimization,PSO)是进化算法的主要分支,在不同的优化问题中表现出很好的性能,且在许多领域均有广泛应用[5-6].作为一种简单而有效的随机搜索算法,DE算法结构简单,探索能力强,但由于其基向量选取的随机性,使算法收敛较慢.而作为模仿鸟类觅食行为的群体智能算法,PSO算法具有易于应用,控制参数少和收敛速度快的优点,但在算法后期容易陷入局部最优.

为解决DE算法收敛速度慢以及PSO算法容易陷入局部最优的问题,研究者对DE算法和PSO算法分别进行了改进[7-8],但单一算法不能有效克服算法自身的缺陷,文献[9]提出了一种新型混合算法,算法采用双种群进化,对两个子种群分别执行DE算法和PSO算法,并在子种群之间引入信息交流机制,但该机制只针对子种群中的少数个体进行,不利于种群进化.文献[10]通过建立粒子早熟判断机制,在PSO算法中引入差分进化操作.文献[11]将差分进化算法的变异,杂交和选择操作引入到粒子群算法中,使算法性能有所提高.但是利用差分进化算子对粒子群优化算法的改进,不能充分发挥两种算法各自优势.

为充分发挥DE算法和PSO算法各自优势,本文设计了一种混合聚类的粒子群差分进化算法.算法运用一步K-均值聚类改进了粒子群优化算法的速度公式,对DE算法参数进行适应性选取;基于优势互补原则,利用线性递减的选择概率将DE算法和改进后的PSO算法相融合;在种群多样性较差时重置种群中部分较差个体.与其它三个进化算法相比,用9个典型测试函数的数值结果充分说明了本文算法的有效性.

1标准差分进化算法和粒子群算法

1.1标准差分进化算法

标准差分进化算法[12]以种群为基础,首先对种群中的每个个体(目标向量)加入差分项实现个体变异产生变异向量,该操作利用种群其它个体信息对当前个体进行扰动,使当前个体朝着好的方向前进;其次对变异向量的每个分量执行交叉操作生成试验向量,以保证产生的试验向量继承目标向量和变异向量的优良信息;最后,在目标个体和对应的试验向量之间选出适应度更好的一个进入下一代,保证种群中的个体总是朝着好的方向发展.标准差分进化算法的步骤如下:

① 初始化操作

设N为种群规模,G=0为当前种群代数,D为种群维数,初始化种群为Pop=(X1,G,X2,G,…,XN,G),Xi,G=(Xi,1,G,Xi,2,G,…,Xi,D,G)(i=1,2,…,N)表示种群中第i个个体,其分量按下式产生:

Xi,j,G=rand(Xi,j,max-Xi,j,min)+Xi,j,min

(1)

其中Xi,j,max和Xi,j,min分别为种群第i个个体第j个分量的最大值和最小值;

② 变异操作

标准差分进化算法有多种变异操作,本文采用应用最多的DE/rand/1策略,该策略对种群中的每个个体进行变异生成变异向量Vi,G=(Vi,1,G,Vi,2,G,…,Vi,D,G) (i=1,2,…,N),变异方式如下:

Vi,G=Xr1,G+F(Xr2,G-Xr3,G)

(2)

其中r1,r2,r3为在区间[1,N]上随机产生的互不相同且不等于i的整数,对每个个体均随机产生一次,F为权衡不同向量的缩放因子,一般情况下F∈[0,1];

③ 交叉操作

对变异向量Vi,G和目标向量Xi,G的每个分量实施交叉操作生成试验向量Ui,G=(Ui,1,G,Ui,2,G,…,Ui,D,G) (i=1,2,…,N),常用的交叉操作有:二项式交叉和指数交叉,本文采用如下的二项式交叉:

(3)

其中jrand是区间[1,D]上的随机整数,它使得试验向量至少继承了变异向量的一个分量,交叉概率CR是由用户指定的区间[0,1)上的常数;

④ 选择操作

若Ui,G(i=1,2,…,N)的某个分量超出预设界限,则按如下规则产生新的对应分量:

(4)

然后依照下面的贪婪法则选择进入下一代的个体:

(5)

即在Xi,G和Ui,G之间选择目标函数值更小的进入下一代;

⑤ 若满足终止条件则停止,否则返回步②.标准差分进化算法具有强大的全局探索能力,能使种群中的个体探索到搜索空间的各个领域,并能有效维护种群多样性.但由于其基向量选取的随机性,使其比粒子群优化算法而言收敛速度慢,不能充分开发优势个体.

1.2粒子群优化算法

在粒子群算法[13]中,一个群体包含D维搜索空间中飞行的N个粒子,第t代第i个粒子Xi,t=(Xi,1,t,Xi,2,t,…,Xi,D,t)(i=1,2,…,N)表示优化问题的一个候选解,其中Xi,j,t表示第t代群体中第i个个体的第j(j=1,2,…,D)维分量.在搜索过程中,粒子的位置由粒子自身达到的历史最优位置Pi,t=(Pi,1,t,Pi,2,t,…,Pi,D,t)以及截止到目前群体达到的历史最优位置Pg,t=(Pg,1,t,Pg,2,t,…,Pg,D,t)决定.vi,t=(vi,1,t,vi,2,t,…,vi,D,t) (i=1,2,…,N)表示示第t代群体中第i个个体的当前速度,下一代种群中第i个粒子的速度和位置更新公式为

vi,j,t+1=ω·vi,j,t+c1·r1·(Pi,j,t-Xi,j,t)+c2·r2·(Pg,j,t-Xi,j,t)

(6)

Xi,j,t+1=Xi,j,t+vi,j,t+1

(7)

式中：ω为惯性权重；c1和c2分别为认知学习参数和社会学习参数,通常情况下取c1=c2=2，r1和r2是(0,1)上均匀分布的随机数.由于大的ω值能促进算法的全局搜索,而小的ω使算法具有良好的局部搜索能力[13],所以一般使用如下的线性递减惯性权重

ω=ωmax-(ωmax-ωmin)·G/Gmax

(8)

其中ωmax和ωmin分别为惯性权重的最大值和最小值,通常取ωmax=0.9,ωmin=0.4,使PSO算法在运行初期具有优良的的全局搜索能力,在运行后期具有良好的局部搜索能力,Gmax为最大迭代次数.

由式(6)可以看出,粒子由个体历史最优和全局历史最优引导飞行,能快速收敛到最优点附近.但当种群中的全局历史最优是目标问题的局部最优时,种群中所有粒子都会飞行到当前全局历史最优位置的附近区域,算法陷入局部最优.

2混合聚类的粒子群差分进化算法

2.1一步K-均值聚类算法

聚类算法[14]能对种群中个体进行分类,使具有相似性质的个体处于一类中.由于聚类算法计算量大,所需计算时间较长,因此本文采用一步K均值聚类算法来获取种群的关键信息,其主要步骤为

① 从当前种群中随机选取K个个体作为聚类中心:C1,C2,…,CK

② 当下式成立时:

‖Xi-Cj‖=min‖Xi-Cp‖ (j=1,2,…,K,p=1,2,…,K,p≠j)

将种群中的个体Xi(i=1,2,…,N)分配给聚类中心Cj(j=1,2,…,K),其中‖Xi-Cj‖是Xi和Cj之间的欧几里德距离;

③ 计算新的聚类中心:

(9)

2.2改进的粒子群算法

由1.2节知,PSO算法容易陷入局部最优.因此本节提出基于一步K-均值聚类的粒子群优化算法(Clustering-basedParticleSwarmOptimization,CPSO),该算法首先对当前种群采用一步K-均值聚类对种群中个体进行分类,并计算每一类的历史最优位置gk,t(k=1,2,…,K),然后对群体中第i(i=1,2,…,N)个粒子使用如下的速度更新公式

vi,j,t+1=ω·vi,j,t+c1·r1·(Pi,j,t-Xi,j,t)+c2·r2·(gk,j,t-Xi,j,t)

(10)

其中gk,j,t表示粒子所属聚类k的历史最优位置gk,t的第j个分量.

不像式(6),式(10)使用粒子飞行的历史最优和其所在聚类飞行过的最优位置引导粒子速度,能有效避免所有粒子均由全局历史最优引导而产生的早熟收敛,由于聚类算法根据粒子位置对粒子进行分类,使用K个不同区域的历史最优个体对种群中的粒子进行引导有助于粒子跳出局部最优所在区域,使粒子更快地收敛到全局最优.

又考虑到随着进化的进行,种群中个体趋于一致,此时若继续使用聚类算法对种群进行聚类操作会减缓算法收敛,因此当式(11)

fitmax-fitmin

(11)

成立时,采用式(6)更新粒子速度,加快算法的收敛速度.其中fitmax和fitmin分别表示当前种群最大和最小适应度值.

2.3部分种群重置策略

随着算法的进行,种群多样性会逐渐降低,种群容易陷入局部最优,此外种群中较差的个体对种群进化的贡献比较小,因此考虑对种群较差的部分个体执行重置操作,可以达到维持种群的多样性的目的,并引导种群走出局部最优.在满足不等式(11)的前提下,当种群每一代的最优值在连续 m代没有改进时,对种群中较差的λ%的个体,利用下面的算法对该部分个体进行重置,步骤如下:

① 依下式计算每一维度新解的可能范围:

rj=max(X(best,j)-Xi,j,min,Xi,j,max-

X(best,j))

(12)

式中：rj为新解在第j维元素搜索范围的半径；X(best,j)为当前种群中最优个体的第j维分量.

② 生成重置个体:

Xi,j=X(best,j)+rj·yj

(13)

其中Xi,j表示重置新解Xi的第j维分量,yi由以下的Logistic映射[15]得到

yj+1=4·yj·(1-yj)

(14)

③ 当Xi,j超出搜索范围时,使用下式保证新解在搜索范围内:

Xi,j=Xi,j,min+Xi,j,max-Xi,j

(15)

不同于文献[16],这里使用混沌映射来重置新个体的原因在于混沌映射具有随机性、遍历性和规律性的特点,使重置个体能够分散在搜索空间中,达到维持种群多样性的目的;同时,重置后的个体分散在搜索空间的其他区域,能帮助陷入局部最优的粒子逃离局部最优,从而快速收敛到全局最优.

2.4混合粒子群差分进化算法

鉴于DE算法具有良好的全局探索能力,而CPSO算法又有收敛速度快的特点,本文采用自适应选择概率融合DE算法和CPSO算法.

由于算法交替使用DE和CPSO算法,首先采用粒子群优化算法的初始化方式,即初始化Xi,G(个体当前位置)和Pi,G(个体历史最优),以及vi,G(个体当前速度)(i=1,2,…,N);其次使用如下的选择概率将DE算法和CPSO算法相融合:

p=1-0.5·FES/MaxFES

(16)

其中FES和MaxFES分别为适应度评估次数和最大适应度评估次数,对当前种群产生(0,1)区间上均匀分布的随机数r,如果r

由于DE算法每一代均在目标向量和试验向量之间进行贪婪选择,其当前种群相当于粒子群优化算法中的个体历史最优位置集合.使用DE算法时,首先对种群中的每个个体依照下式在给定范围内随机选取不同的缩放因子和交叉概率

Fi=Fmin+rand·(Fmax-Fmin)

(17)

CRi=CRmin+rand·(CRmax-CRmin)

(18)

文中算法参考文献[17]中的取值，即Fmin=0.5,Fmax=0.6,CRmin=0.1,CRmax=0.3,这样的取值方式有利于保持种群多样性,减小算法陷入局部最优的概率;其次对目标个体Pi,G执行变异和交叉操作生成试验向量Ui,G,则Xi,G=Ui,G,即采用DE算法时,不在Xi,G和其生成的Ui,G之间进行贪婪选择,而是用生成的Ui,G代替个体当前位置Xi,G,最后对当前个体速度采用下式更新:

vi,G+1=Xi,G+1-Xi,G

(19)

该速度更新公式是受粒子群算法速度更新公式(7)的启发得到,为方便下一次使用CPSO算法做准备.

文中算法步骤如下:

① 设置G=0,FES=0,初始化种群当前位置XG,历史最优位置PG,种群飞行速度vG及其他参数;

② 若满足部分种群重置的条件时,对较差的部分个体按照重置策略进行重置,并计算重置后个体的适应度值,种群中其他较好个体执行③,若不满足重置条件,则对种群中所有个体执行③;

③ 根据式(16)选择要使用的算法,若随机数r

④ 对种群当前个体Pi,G,使用DE算法产生新的个体Xi,G+1,并对每个个体的速度进行更新,转⑥;

⑤ 对种群当前个体Xi,G,根据CPSO算法产生vi,G+1和Xi,G+1;

⑥ 计算新生成个体Xi,G+1(i=1,2…,N)的适应度值f(Xi,G+1),若f(Xi,G+1)

⑦ 若适应度评估次数不超过预设值,转②,否则输出最优值,算法结束.

3数值分析

为测试文中算法的性能,本节对9个具有不同特点的标准测试函数进行数值试验,并与线性递减惯性权重的粒子群算法(ParticleSwarmOptimizationwithInertiaWeight,PSO-w)[13]、综合学习的粒子算法(ComprehensiveLearningParticleSwarmOptimization,CLPSO)[8]算法及复合差分进

化算法(CompositeDifferentialEvolution,CoDE)[18]算法进行比较,测试函数见表1.

在表1所列出的8个测试函数中,f1～f2为连续单峰函数,f3是仅有一个最小值的不连续阶梯函数,f4为嘈杂四次函数,f5～f7为多峰函数[19],其局部极小的个数随问题维数的增长呈指数增长,f8～f9为低维多峰函数,其维数见表1.

在所有试验中,参数设置如下:本文算法中种群规模N=30,粒子速度的最大值和最小值分别为搜索范围上下界的0.2倍,m=15,λ=33,对测试函数f1～f7,决策变量维数D=30,f8和f9的维数如表1数据所示.其他算法参数设置见对应参考文献,对于所有算法的终止条件均为适应度评估次数不超过 次,为公平起见,每个测试函数均独立运行25次.

表1　标准测试函数表

表2给出了对比算法和本文算法对标准测试函数的优化结果,其中Average表示运行结果的平均最优值,Median表示运行结果的中值,Std表示运行结果的标准差.

由表2可以看出,对测试函数f3和f8,所有测试函数在平均值,中值和标准差三方面均达到了最优值;对其他测试函数而言,文中算法的优化结果在平均值和中值两方面均优于或等同于其他算法,只有在解决低维多峰函数f9时标准差略差于CoDE算法;尤其是对多峰函数f6和f7,文中算法能够快速找到测试函数的全局最优解,同时标准差也为零,说明文中算法解决多峰问题具优良的寻优能力，并且稳定性更好.

表2　四种算法寻优性能比较

为更直观反映算法的寻优性能,图1～图4分别给出四种算法对测试函数f2、f4、f5和f7的优化性能曲线.

图1　函数f2进化曲线图

从图1可以看出,在处理单峰函数问题时,本文算法具有较快收敛速度;图2说明本文算法在解决嘈杂问题时,也能以较快的速度收敛到全局最优值点附近,图3表明文中算法与CoDE算法具有同等寻优能力，但文中算法优于PSO-W和CLPSO，图4表明本文算法在解决多峰函数问题时,能有效跳出局部最优,快速收敛到全局最优,这是由于在算法初期使用不同区域的最优个体引导种群进化,后期又对种群中较差的个体实施重置操作,维持了种群的多样性,有效避免算法陷入局部最优,使算法更快地收敛到全局最优.

总之,从表1以及图1～4的仿真结果可以看出,与其他三种先进进化算法相比,本文算法能有效避免早熟收敛,快速收敛到问题的全局最优,并且鲁棒性更好.

图2　函数f4进化曲线图

图3　函数f5进化曲线图

图4　函数f7进化曲线图

4结 论

1) 为解决差分进化算法收敛速度慢和容易陷入局部最优的问题,设计了一种混合聚类的粒子群差分进化算法.运用一步K-均值聚类算法改进了粒子群优化算法的速度更新,将改进后的粒子群优化算法融合到差分进化算法中,在种群多样性较差时采用部分种群重置策略.

2) 改进后的算法有效发挥了差分进化算法和粒子群优化算法各自的优势,权衡了算法的全局探索能力和局部开发能力,赋予了种群中个体逃离局部最优的能力.

3) 在9个标准测试函数的数值仿真结果表明:改进后的算法在解决单峰函数、嘈杂函数以及多峰函数时均表现出良好的性能,算法的收敛速度也大大提高.

参 考 文 献：

[1]KANARACHOS A,KOULOCHERIS D,VRAZOPOULOS H.Evolutionary Algorithms with Deterministic Mutation Operators used for the Optimization of the Trajectory of a Four-bar Mechanism[J].Mathematics and Computers in Simulation,2003,63:483.

[2]FUJIWARA Y,SAWAI H.Evolutionary Computation Applied to Mesh Optimization of a 3-D Facial Image[J].IEEE Transactions on Evolutionary Computation,1999,3(2):113.

[3]STORN R,PRICE K.Differential Evolution-A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Space[R].International Computer Science Institute,Berkeley,1995.

[4]KENNEDY J,EBERHART R C.Particle Swarm Optimization[C]//Proceedings of IEEE International Conference on Neural Networks,Piscataway:IEEE Press,1995:1942.

[5]赵艳丽.差分进化算法在图像处理中的应用研究[D].东营:中国石油大学,2010.

ZHAO Yanli.Research on the Application of Differential Evolution in Image Processing[D].Dongying:College of Computer & Communication Engineering China University of Petroleum,2010.(in Chinese)

[6]PEDRO F,JOAO S,ZITA V,et al.Modified Particle Swarm Optimization Applied to Integrated Demand Response and DG Resources[J].IEEE Transaction on Smart Grid,2013,4(1):606.

[7]汤小为,唐俊,万爽,等.改进变异策略的自适应差分进化算法及其应用[J].宇航学报,2013,34(7):1001.

TANG Xiaowei,TANG Jun,WAN Shuang,et al.Adaptive Differential Evolution Algorithm with Modified Mutation Strategy and Its Application.[J].Journal of Astronautics,2013,34(7):1001.(in Chinese)

[8]LIANG J J,QIN A K,SUGANTHAN P N,et al.Comprehensive Learning Particle Swarm Optimizer for Global Optimization of Multimodal Function[J].IEEE Transaction on Evolutionary Computation,2006,10(3):281.

[9]栾丽君,谭立静,牛奔.一种基于粒子群优化算法和差分进化算法的新型混合全局优化算法[J].信息与控制,2007,36(6):708.

LUAN Lijun,TAN Lijing,NIU Ben.A Novel Hybrid Global Optimization Algorithm Based on Particle Swarm Optimization and Differential Evolution[J].Information and Control,2007,36(6):708.

(in Chinese)

[10]刘建平.基于混沌和差分进化的混合粒子群优化算法[J].计算机仿真,2012,29(2):208.

LIU Jianping.Hybrid Particle Swarm Optimization Algorithm Based on Chaos and Differential Evolution[J].Computer Simulation,2012,29(2):208.

(in Chinese)

[11]段玉红,高岳林.基于差分演化的粒子群算法[J].计算机仿真,2009,26(6):212.

DUAN Yuhong,GAO Yuelin.A Particle Swarm Optimization Algorithm Based on Differential Evolution[J].Computer Simulation,2009,26(6):212.

(in Chinese)

[12]DAS S,ABRAHAM A,CHAKRABORTY U K,et al.Differential Evolution Using a Neighborhood-based Mutation Operator[J].IEEE Transation on Evolutionary Computation,2009,13(3):526.

[13]SHI Y,EBERHART R C.Parameter Selection in Particle Swarm Optimization[C]//International Conference on Evolutionary Programming VII,London:Springer-verlag,1998:591.

[14]CAI Zhihua,GONG Wenyin,LING C X,et al.A Clustering-based Differential Evolution for Global Optimization[J].Applied Soft Computing,2011,11:1363.

[15]匡芳君,张思扬,金钟,等.混沌差分进化粒子群协同优化算法[J].微电子学与计算机,2014,31(8):29.

KUANG Fangjun,ZHANG Siyang,JIN Zhong,et al.Chaotic Differential Evolution Particle Swarm Cooperative Optimization Algorithm[J].Microelectronics & Computer,2014,31(8):29.(in Chinese)

[16]DONG L,JIE C,BIN X.A Novel Differential Evolution Algorithm with Gaussian Mutation that Balances Exploration and Expoitation[C]//IEEE Symposium on Differential Evolution,Singapore:IEEE,2013:18.

[17]WANG Yong,CAI Zixing.Combining Multiobjective Optimization with Differential Evolution to Solve Constrained Optimization Problems[J].IEEE Transactions on Evolutionary Computation,2012,16(1):117.

[18]WANG Yong,CAI Zixing,ZHANG Qingfu.Differential Evolution with Composite Trial Vector Generation Strategies and Control Parameters[J].IEEE Transactions on Evolutionary Computation,2011,15(1):55.

[19]SHANG Yunwei,QIU Yuhuang.A Note on the Extended Rosenbrock Function[J].Evolutionary Computation,2006,14(1):119.

(责任编辑、校对张立新)

A Hybrid Clustering Particle Swarm and Differential Evolution Algorithm

LIU Yang,GAO Xingbao,LIU Rui

(School of Mathematics and Information Science,Shaanxi Normal University,Xi’an 710062,China)

Abstract:A hybrid differential evolution algorithm is introduced because the basic differential evolution algorithm has disadvantages of low convergence speed and local optimum.Firstly,K-means cluster algrithm was used to modify the velocity updating formula of the particle swarm optimization algorithm.Then the modified particle swarm optimization algorithm was combined with the differential evolution algorithm by means of a linear decreasing selective probability.Finally some individuals with poor performance were reset under certain conditions.Numerical experiments on nine typical benchmark functions illustrate that the proposed algorithm is fast in convergence speed,strong in search ability and good in robustness.

Key words:K-means clusters;hybrid algorithms;differential evolution;particle swarm optimization;population reset

DOI:10.16185/j.jxatu.edu.cn.2016.05.003

收稿日期：2015-10-14

基金资助：国家自然科学基金(61273311;61173094)

作者简介：刘阳(1990-),女,陕西师范大学硕士研究生. 通讯作者：高兴宝(1966-),男,陕西师范大学教授,主要研究方向为最优化理论与方法、智能计算、神经网络等.E-mail:xinbaog@snnu.edu.cn.

文献标志码:中图号：TP301.6A

文章编号：1673-9965(2016)05-0357-08