第3卷第6期 智能系统学报 Vol.3 No.6 2008年12月 CAAI Transactions on Intelligent Systems Dec.2008 混合差分变异策略 刘三阳2，张晓伟 (1.西安电子科技大学数学科学系，陕西西安710071；2.西安电子科技大学综合业务网国家重点实验室，陕西 西安710071) 摘要：为了改善差分进化算法的求解性能，提出一种新的混合差分变异策略.该策略将种群中的每一个个体视作 带电粒子，利用粒子所带的电荷量以及粒子之间的吸引排斥机制确定个体移动方向和位移大小.该策略会使个体在 其他3个个体施加于它的力的方向上自适应地移动，数值实验表明基于该策略的差分进化算法求解精度高、评估次 数少. 关键词：全局优化；粒子群优化；差分进化 中图分类号：TP18:0224文献标识码：A文章编号：1673-4785(2008)06048705 A hybrid strategy for differential variation LIU San-yang'2,ZHANG Xiao-wei' (1.Department of Mathematical Sciences,Xidian University,Xian 710071,China;2.State Key Lab.of ISN,Xidian University,Xian 710071,China) Abstract:A new hybrid strategy for differential variation was developed in order to improve the performance of dif- ferential evolution.The strategy regards each individual in the population as a charged particle,and uses the charge level of the particle and the attraction-repulsion mechanism among particles to determine the probable direction and magnitude of motion.This strategy can compel individuals to move adaptively in the direction of the forces ex- erted on them by three other individuals.Numerical experiments showed that differential evolution based on this strategy has high accuracy and requires fewer evaluations. Keywords:global optimization;particle swarm optimization;differential evolution 差分进化(differential evolution,DE)算法于而后人的修改大多数是基于DE/Rand/I框架上的 1995由Stom和Price提出)，该方法简单、高效、鲁 参数的调整，没有摆脱DE算法原始思想的局限.修 棒，已在工程优化、运筹管理、计算机科学等领域得 改后的DE性能往往在某些方面表现优越，而在其 到广泛的应用.为了改善差分进化算法的性能，人们 他一些方面则不然，为了提出更鲁棒、高效的DE,本 提出了各种修改策略.如，Sron2]最早提出的 文提出一种新的差分变异策略.该策略融合了粒子 DE/Rand/1,DE/Rand/2,DE/Best/2等策略；2005 群优化、差分进化以及类电磁机制算法的思想.基于 年Qin]等将比例因子K取作均值为0.5，标准方差 该策略的差分进化算法使种群中每一个个体会在一 为0.3的正态分布随机数；2007年Kim4则将比例 个随机选取个体、当前个体经历最优和种群全局最 因子修改为K=a+b·r(0,1),这里r(0,1)表示 优3个个体分别施加于其的电磁力合力的方向上自 [0,1]之间均匀分布的随机数，a,b是正数且 适应地移动，从而避免了差分进化算法中比例因子 a+b<1.在Sron提出的策略中，DE/Rand/1因 参数设置的困难.最后的数值实验表明提出的策略 其简单、有效而常被当作标准差分进化算法来使用. 优于已有相关策略， 收稿日期：2008-07-04. 基金项目：国家自然科学基金资助项目(60574075,60674108)；综合 1相关知识 业务网国家重点实验室基金资助项目(ISV200806). 通信作者：刘三阳.E-mail:liusanyang@126.com. 粒子群优化(particle swarm optimization,PSO)
·488· 智能系统学报 第3卷 算法由Eberhart和Kennedy于I995年提出).它是 F(X,X2),而粒子X3对粒子X有一个吸引力F 一种模拟鸟类觅食社会行为的进化算法.每一个个 (X1,X3).根据平行四边形法则，粒子X1所受的合 体（粒子）在搜索空间中以一定的速度飞行，它的飞 力F(X)=F(X1,X2)+F(X1,X3).见图1. 行速度受到个体认知以及社会认知的影响而不断调 整.令X,(t)表示第t代种群中的第i个个体，那么 下一代的个体X(t+1)由下面的式子产生： 2差分进化新策略 (t+1)=0·Xw(t)+ DE算法和其他进化类算法的主要差别在于差 c1·r(0,1)·(g()-X())+ 分变异的使用.针对种群中的每一个个体，首先利用 c2·r2(0,1)(G(t)-X(t)), 随机选取的其他个体间的差分信息得到实验个体， X,(t+1)=X(t)+:(t+1). 然后将实验个体与该个体的每一个分量以一定概率 这里：j=1,…,n,n表示问题的维数；y:表示第i个 进行离散交叉得到候选个体，再以贪婪选择机制决 个体的飞行速度；：和G分别表示个体经历最优和 定哪个个体进入下一代种群.算法简单、鲁棒、参数 种群全局最优个体；r1(0,1)和2(0,1)表示[0,1] 少，易于程序实现；但是一个合适的参数赋值会大大 之间均匀分布的随机数；C1和c2表示飞行加速系数 改善算法的求解性能.研究者已经在参数调整方面 或认识系数；和是惯性权重，反映的是个体对过去飞 做了很多工作.正如本文开始所述，这些修改大多数 行速度的依赖程度， 是基于DE/Rand/I框架上的参数的调整，并未摆脱 类电磁机制(electromagnetism--like mechanism, DE算法原始思想的局限性 EM)算法是由Birbil和Fang于20O3年提出的一种 1996年Stron和Price给出几种变异策略，如 模拟电磁场中的吸引和排斥机制的随机全局优化算 DE/Rand/1: 法6).该算法将种群中的每个个体比作带电粒子， V=X+K·(Xn-X3); 然后按一定的准则使得搜索粒子朝最优解移动.这 DE/Rand/2: 种思想来源于电磁理论中带电粒子间的吸引与排 V=X,+K·（X2-Xg+X4-X）; 斥，类电磁机制算法首先根据问题的目标函数值确 DE/Best/2: 定出种群中每个个体（带电粒子）所带的电荷量.电 V=Xbt+K·（X,-X2+Xg-X4） 荷量的大小决定了该粒子对其他粒子的吸引或者排 等等，最常使用的为DE/Rand/I.对于一般的 斥的强弱程度，即目标函数值越小，吸引力就越强， DE/a/b,其含义如下：a表示基向量选择方式；b表 反之，排斥力就越大.然后算法计算每一个粒子所受 示差分向量的个数.这里：1≠r2≠r3≠T4≠T5,均为 到其他粒子施加于它的电磁力的合力，以此来确定 [1,N]间的随机整数，N表示种群规模， 该粒子下一步移动的方向. 在上述策略中，针对不同的问题，DE一般需要 不同的K才能得到求解结果或达到最佳性能.但是 K如何给值是相当麻烦的，一般需要对求解问题进 行前期的反复实验.本文试图在不降低DE求解性 F(X) 能的前提下免除比例因子K 对种群中的每一个个体赋予电荷属性，其所带 F(XX) F(X X2) 的电荷量不像EM中由N-1个个体决定，而是由随 机选取的一个个体确定.这种方法出现在文献[8] X 中，作者用其求解了项目进度安排问题.这个做法保 图1粒子X受到的合力F(X) 留了EM算法的精髓，而且计算简单.种群中第i个 Fig.1 The resultant force F(X)exerted on X 个体的电荷量Q(X,X,)由随机选取的个体（比如 计算每一个粒子所受的合力的方法同电磁力的 X)给出： 一样，就是通过将受到的其他粒子的力进行矢量叠 f(x)-f(x.) 加.如：粒子X1优于粒子X2,而粒子X1劣于粒子 Q(X,X）=fX)-fX) X3;那么粒子X2将对粒子X,有一个排斥力 这里：i≠r1,2,且ie[1,N],Xt,Xa分别表示当
第6期 刘三阳，等：混合差分变异策略 ·489· 前种群中最差和最好个体.在计算种群中的所有个 8)如课iM或f(Xwt(t)-f(Xet(t))I< 8,则停止并输出最优解。 图2算法求解∫时最优值随进化代数变化情况 4)对X(t)∈U(t)按照下式计算实验个体V,(t): Fig.2 Variations of current optimal values with iterations V:(t)=X,(t)+F(X(t),X,(t))+ forf 10 F(x(t),8n(t))+F(X,(t),Gn(t)) 5)对X(t)和V,(t)以概率C,进行交叉，得到 109 个体Y(t): 10 r为1~N的随机整数； for j=1:n 100 -DE/Rand/I if (r(0,1)<=C,orj=r) 10 --DE/Rand/2 -DE/Best/2 Yij(t)=Vij(t) …NDE else Yij(t)=Xij (t)end 109 400 8001200 1600 2000 迭代次数 end 6)边界检查.如果Y,(t)小于下边界或大于上 图3算法求解方时最优值随进化代数变化情况 边界，则用下边界或上边界替换 Fig.3 Variations of current optimal values with iterations 7)选择.如果f(Y:(t)<f(X(t)),则X(t)= forf Y(t),i=i+1. f是有噪音的函数，有多个局部最优解，NDE
·490 智能系统学报 第3卷 最好，从实验看，DE/Rand/2求解结果最差，DE/ 方便得到NDE算法10次求解的最优值的平均值， Best/2好于DE/Rand/1. 通过重复记录NDE退出循环时所得到的最优值方 具有罚项的测试函数方有许多局部最优解，具 式，补全2000次迭代. 有新变异策略的NDE求解结果明显优于其他策略， 对f4,NDE的求解结果最好，而DE/Rand/I、 DE/Rand/1的求解结果稍差，DE/Best/2更差， DE/Rand/2和DE/Best/2的求解结果分别只达到 DE/Rand/2最差 165、238和183. 10 从图2~5可以看出，NDE能更快地找到问题 的全局最优或次优，求解精度高 10 DEPS0算法[9是将文献[10-11]中分别提出的 DE算法和PSO算法进行了融合，其以一定的随机 概率来确定种群中粒子速度是由何种方式产生.作 10 DE/Rand/1 -.-..DE/Rand/2 者指出DEPS0算法能够维持种群的多样性，搜索效 109 ---DE/Best/2 率高.为了进一步说明NDE算法的优越性，NDE和 100 DEPSO算法进行了比较 400 800120016002000 迭代次数 表1NDE和DEPSO数值结果比较 Table 1 Comparison of results obtained by NDE and DEP- 图4算法求解方时最优值随进化代数变化情况 so Fig.4 Variations of current optimal values with iterations forf3 DEPSO NDE 函数 10 平均值 方差 平均值 方差 f 2.36×10-42.1×10-4 7.99×10-5 0 10 6 3.265×10-35.77×10-3 1.23×10-322.43×10-4s DE/Rand/I --…DE/Rand/2 --DE/Best/2 6.2×10-164.1x×10-16 0 0 NDE 10 24.21676.417 5.30642.6267 表1中给出了两种算法的求解结果平均值和方 差.DEPS0的数值结果来自文献[9].除了种群规模 00 400 8001200 1600 2000 外，NDE参数的设置同上.为了公平起见，在NDE算 迭代次数 法中，种群大小设置和DEPS0相同，即N=40.对于 图5算法求解f时最优值随进化代数变化情况 f,最大迭代次数M=4000,其他的测试函数，M均为 Fig.5 Variations of current optimal values with iterations 12000.从表1可以看出，在同样的种群规模和停机条 for f 件下，NDE有较高的求解精度和较小的方差。 同样地，Griewank(f)函数有许多局部最小点， DE/Rand/1在l0次运行中均找到了全局最优解0， 4 结束语 而其他算法的求解结果较差：NDE,DE/Best/2和 本文提出了一种混合差分变异策略，该策略融 DE/Rand/2的求解精度分别只达到104、l0-3、 合了粒子群优化、类电磁算法以及差分进化算法的 10°.这里需要说明一点，因为f(X(t))- 基本思想，避免了比例因子的设置.数值实验表明具 f(X(t))I<e终止条件的使用，NDE在求解， 有该变异策略的差分进化算法更鲁棒、高效.进一步 f时，一般未达到2000代就终止了迭代.因此为了 改善提出的策略是有待研究的一个问题。 附录： 万e)=-20ew-0.2√日g深-eam(8o(2）+20+em(1)e【-32,321r=-0 ()=bsin2(3m)+g(-1)P[1+m(3m]+(,-1)r[1+sim2(2m)]+含a(5,100,4)）
第6期 刘三阳，等：混合差分变异策略 491· k(x;-a)m xi<a 少1+花+1 4,i=l,…,n,u(x,a,k,m)=0 -a<x:<a,x:∈[-50,50]f=0. k(-x:-a)" x:<-a 5(=含4高m音+1，e[-6060],r-0 f(x)=10n+2[x-10cos(2mx)],x,∈[-5.12,5.12]，f=0. 169(2):638-653. 参考文献： [9]HAO Zhifeng,GUO Guanghan,HUANG Han.A particle [1]STORN R,PRICE K.Differential evolution-a simple and swarm optimization algorithm with differential evolution efficient heuristic for global optimization over continuous [C]//Proceedings of the Sixth International Conference on spaces[J].Journal of Clobal Optimization,1997,11(4): Machine Learning and Cybernetics.Hong Kong,China, 341-359 2007(2):1031-1035. [2]FEOKTSTOV V.Differential evolution:in search of solu- [10]PRICE K.Differential evolution vs.the functions of the tions[M].Berlin:Springer,2006. 2nd ICEO[C]//Proceeding of the 1997 IEEE Interational [3]QIN A,SUGANTHAN P.Self-adaptive differential evolu- Conference on Evolutionary Computation.Indianapolis, tion algorithm for numerical optimization[C]//Proceedings USA,1997,153-157. of the 2005 IEEE Congress on Evolutionary Computation. [11]CLERC M,KENNEDY J.The particle swarm-explosion, Edinburgh,UK,2005(2):1785-1791. stability,and convergence in a multidimensional complex [4]KIM H,CHONG J,PARK K,et al.Differential evolution space[J].IEEE Transactions on Evolutionary Computa- strategy for constrained global optimization and application to tion,2002,6(1):58-73 practical engineering problems[J].IEEE Transactions on 作者简介： Magnetics,2007,43(4):1565-1568. 刘三阳，男，1959年生，博士，教授， [5]KENNEDY J,EBERHART R.Particle swarm optimization 博士生导师，国家教学名师.主要研究 [C]//Proceedings of the IEEE International Joint Confer- 方向为应用数学、最优化和运筹学.现 ence on Neural Networks.Perth,Australia.1995(4):1942- 任西安电子科技大学理学院院长、工业 1948. 与应用数学研究所所长.发表学术论文 [6]BIRBIL S,FANG S.An electromagnetism-like mechanism 300余篇，出版专著10部. for global optimization[J].Journal of Global Optimization, 2003,25(3):263-282 张晓伟，男，1979年出生，博士研究 [7]BIRBIL S,FANG S,SHEU R.On the convergence of a 生.主要研究方向为进化算法及最优化 population-based global optimization[J].Journal of Global 理论与方法.发表学术论文10余篇，其 0 ptimization,2004,30(3):301-318. 中被SCI,EI、ISTP检索7篇. [8]DEBELS D,REYCK B,LEUS R,et al.A hybrid scatter search/electromagnetism meta-heuristic for project schedu- ling[J].European Journal of Operational Research,2006