1、陕西理工学院毕业论文陕西理工学院毕业论文题目： 差分进化算法种群多样性分析姓名： 汪兵兵 学号： 0909014094所在院系： 数学与计算机科学学院专业：数学与应用数学 班级：数学 093 班指导教师： 雍 龙 泉陕西理工学院毕业论文差分进化算法种群多样性分析摘要： 提出了一种新的种群多样性（PD）度量方法， 给出了一组 PD 度量标准及计算方法，并运用 这种度量标准证明出了PD 与差分进化算法中三个算子的函数关系式；以此在选取参数值时给出了参考关系式 =0；本文还通过mpF22仿真实验来确定算子的取值范围，在 DE 算法进化过程中有效的保持种群的多样性是避免“早熟”现象生的一种行之有效的方
2、法。关键词 ： 种群多样性 差分进化算法 算子1.引言近年来尽管差分进化算法(简称 DE)得到了广大研究者的关注和研究,但它仍存在许多突出的问题需要解决，其中最广泛关注的问题之一就是 DE 的过早敛问题。最近的研究发现:过早收敛总是与种群中个体趋同、种群多样性的迅速下降有密切关系；算法的性能很大程度上和参数的选取有关。然而对 DE 算法参数分析的专门性文章却很少，种群多样性(Population Diversity,下简称 PD)应怎样定义和度量?在 DE 优化过程中 PD 是如何变化的并与 DE 中三个算子的关系是怎样的的?如何产生和利用/有用的种群多样性来提高 DE 的性能?这些问题对进一
3、步理解 DE 的进化动态、提高 DE 的搜索性能是很重要的,也是本文要解决的问题。2基本差分进化算法介绍差分进化算法是R.Stom和K.Price于1995年提出的，并在96 年首届IEEE 进化算法大赛中被证明为最快的进化算法。而且DE算法在收敛速度和稳定性方面都超过了其它几种知名的随机算法，对于大多数的数Benchmark问题， DE算法优于 P算法。此外，由于DE算法容易理解、易于实现等优点，所以一经提出就倍受关注并得到了广泛的应用。（1）种群初始化在问题的解空间内随机产生初始种群 ，0012NPX(),x，其中， 用于表征第i个个体解。个体的各个分量可按下式产生：00,1,2,.iii
4、Dx)xj,jrand(j, minm其中， 和 分别为解空间第 j维的上下界。,i（2）变异操作对于父代种群中任意的一个目标向量 按下面公式生成变异向量 ： i vi， )xr(Fxrvi 3211,2NP其中， 是父代种群中随机选择的三个不同个体，并且 ，可见，种群规模应23,r 123r满足NP 4；放缩因子F 是一个介于0,2 间的实型常量因子，用于控制差分向量（ ）的影响。 xr32陕西理工学院毕业论文（3）交叉操作差分进化算法交叉操作的目的是通过变异向量 和目标向量 各维分量的随机重组以提高种群个vixi体的多样性。算法通过下面公式生成新的交叉向量 = , ,., :u12uD,=
5、 i=1,.,NP,j=1,.,NP uji,randjjCRrandb,xjivrandb是 0,1间的随机数；CR是0,1间的常数，CR取值越大，发生交叉的可能就越大； 是在randj1，D随机选择的整数，它保证 至从少要 中获得一个元素，以确保有新的个体生成，从而避免群体uivi的进化停滞。（4）选择操作差分进化算法的选择操作是一种“贪婪”选择模式，当且仅当新的向量个体 的适应度值比目标向量iu个体 的适应度值更好时， 才会被种群接受。否则， 仍将保留在下一代的种群中，并在下一次迭代ixiuix计算中继续作为目标向量执行变异及交叉操作。设优化问题为minf(x),则选择操作可由下式描述：
6、 els,xti)tif()f(ti1差分进化算法的选择操作是由父代个体与新产生的候选个体之间一对一地进行竞争，优胜劣汰，使得子代个体总是优于或等于父代个体，从而使种群始终向最优解的方向进化。（5）终止判断记（4）产生的新种群X(t+1) 中的最优个体为 (t+1)。若满足要求或者达到其他的终止条件，则Xestb终止并输出 (t+1)作为最优解； 否则， 令t=t+1 ， 转（2） 。Xbest初始化 P(0)= ，g=01(0),.(0)NPx循环：变异：， ,()()()l123iiiggyxxFllNPl1ni交叉：公式编辑器中的文字的字体字号的大小,)(ilzl1ni选择：如果 那么
7、(g)xlf)z1(zlg)(l否则 (1xg=g+1直到一个停滞准则被满足。概率为 p NPl,1概率为 1-p陕西理工学院毕业论文图 1：DE 算法结构3.种群多样性的表示一般可从宏观和微观两个角度来考虑种群的多样性.从宏观上,考虑种群中个体间的差异程度,这是最直观意义上的多样性,另一方面,种群内个体多样性的增加或降低是由个体串基因位的变化引起的,因此还应考虑以基因为单位的种群多样性; 本文在上述思想基础上 ,提出一种新的种群多样性度量方法,较全面地刻画了种群的进化动态。以二进制编码的种群为例，设种群 P 由 N 个个体 p1,pN 组成,每个个体均是定义在0,1上的编码串,长度为 l 将
8、种群 P 表示为 N*l 的矩阵,其每一行表示为一个个体串,每一列表示各个体串在特定基因的值,pji 表示第 i 个个体的第 j 位基因值 1 有以下定义定义 1：种群的平均： （1）Nljiijp定义 2：种群的整体多样性： （2）2i1ljpijDP定义 3：基因内部多样性： （3）iNljjgwijg基因外部多样性： （4）21lbj式中 为基因 在群种中的平均。1Njjiigpj种群的基因多样性 （5）gwgbD定义 4：个体内部多样性 （6）2i1Nlji iijpP个体外部多样性 （7）iibi式中， 为个体的平均。1ljiijpP种群的个体多样性 （8）iiwibD实际上一共定义
9、了 5 种多样性,下面进一步分析各种多样性之间的关系，先分析种群基因多样性与种群整体多样性的关系。=gwgbD22i11Nl ljj jij jPpg陕西理工学院毕业论文22i1122i+Nl Nljj jij ijljjij Ppg） （ ）（ 2i1111()2()()12()()0Nljjjjgp iijl jjjiijlNjjijiljj jjjDPjiPPNpg） （ ）（因此 gpD同理可得 i所以 igp由以上结果可以看出,种群的整体多样性可以不同的方式进行分解得到不同意义和作用的多样性；由定义 3 和定义 4,式(3) (8)分别从基因和个体两个角度定义了种群多样性；它们对种群
10、多样性的分析方式不同,一个以基因为单位,一个以个体为单位,分别得到不同意义和作用的多样性度量标准，以个体的平均为中介,可将种群的个体多样性分为两部分:一是反映每个个体内部各基因相对于个体平均的差异,体现iP了一个个体内部构成的多样性; 另一个是反映所有个体的平均相对于种群平均的差异,即不同个体间的多样性,反映了不同个体间的差异程度；通常我们感兴趣的是后者,即个体外部多样性 ,它代表种群中的个体ibD在整个搜索空间中的聚集程度,反映了种群中各个体的分布情况,是衡量种群中所有个体对整个搜索空间覆盖范围的重要标志；同样,以基因 在种群的平均 为中介,也将种群基因多样性分成两部分:一是反映种jgjg群
11、中所有个体在特定的基因位取值的差异,它表明了种群在该基因位的收敛程度;另一个是反映各基因位的平均值与种群平均的差异,亦即基因平均间的差异，在 EA 的种群多样性和其收敛性研究中,我们关注前者,即基因的内部多样性 它代表遗传漂移的程度,是衡量 EA 进化能力强弱的重要尺度。gwD从以上的分析能够很明显看出 , 在研究 EA 过早收敛现象中的含义和作用,而其它几种多样性gwib指标的作用并不十分明显；从我们引入 PD 的目的来看,除了研究它们与过早收敛的关系以找到防止 EA 早熟的措施外,另一个重要目的就是中出 EA 中的三个算子之间的对 PD 的影响及其关系。在这里我们以个体外部多样性 为讨论对
12、象， 有一样的性质；令种群的方差 Var（x）= ；ibgwDibD为种群所有个体方差的数学期望用于表述种群的多样性。我们给出以下定义：()EVarx定义 5 若第 t 代种群中的个体 由 L 个基因构成,即it,定义第 t 代种群的平均个体 ,如下:1212i(i(m),Nxttt， ， ， ， ， ， it即每个元素 都有方差 整个种群的方差的数学期望值为：mllitit1)( it 2)(Variiix)(*xE1NiixVarVar陕西理工学院毕业论文在以下的定理中将 PD 解释为种群方差的数学期望 。)x(EVar4.定理的提出以及证明理论： 设但前值为 ，在变异后的中间种群为 ，在
13、以上过程基础上交1,mx Ym.1叉后得到的种群为 。就常数 和以上给出的 支持一下陈叙：Z.FlFl（a）在变异后种群方差的数学期望： )(2()(ExVarFYVar（b）在编译和交叉后种群方差的数学期望：)(12()( rmpZr证明：（a）由于 Y 中的每个元素 满足 ，其中 ， 和l )()(*)(321 ggxFxiiilil lll l1l2是从 中随机选取的三个不相同的数，对于种群 Y 的每个元素 ，这种类型的采样，确l31,2ml保选择的系数是不同的，由于抽样的性质不取决于系数 l，所以为了简化公式，我们删除系数 l。系数 ，1和 可以被视为值在 中的随机变量；并且他们有这样
14、的性质：对于任一个231,2都有 因此 也是一个随机变量并且有,.ikP(k)1imxi。应为 ， 和 是相互独立的，所以有xxiiE2)()(23。在另一方面对于所有的 l 都有)1()(),(1,P 2ji Eji 2)0)(FVarFlll 现在我们运算： ml xlxllxlEllY1 2)3(F)32(1F2)( )(1)( = xmllE 21F12 为了得到第二个等式我们用到了性质：当 时有Fl )3(E)2(x为了求得 我们还需求的 ，即：)(YVar)(2Y陕西理工学院毕业论文+221)3(Fl()(Eml xlxY ml xlxlE1)32(F( 2 lk kkl )32(
15、F1212 由于对于 Y 中的每个元素，系数 ， 和 经过新的一轮抽样而得到且相互独立，因此对 都23 lk有 和 是相互独立的。因此有)31xl*(Flx )(*xklk 213212 x)kE()xl(FllE 于是我们得到2)(1)(xmY因此 )(12()()E2 xVarmFYEVar （b） 种群 Z 的每一个元素有以下结构的随机变量：,(g)xilyz l1ni为了求得 ，我们必须计算出 和 ；EVar)Z(E2)(2 ml llmll YpExpZYx1 22122 )()()(另一方面：(9) lklklklmllmll ZEmZ)(1)()()2()()( 21212又由于
16、 和 是相互独立的，最后一个等式的第二个式子可以扩充为：k lk lkllkl pExYpExZE )Y()()()( l但是 lxYl 1)32F1 因此 ml xpmxpmxplpxlxpmmlllllkZE1 2)1(222)1(2)(2)1( )()()(代入上式（9）中得到： 22222 )1()( xpmxpZE因此：概率为 p概率为 1-p陕西理工学院毕业论文)(1p2F( )1()21()2)E 2222xVarm xmpxpxmFpZVar 定理得以证明。5.结论和仿真实验从以上证明结果可以看出：其中)(,()(ExVarmpFcZVar 122),( mpFmpc如果 1,
17、这些变量算子会是种群多样性增大；如果 1,在变异和交叉后种群多样性下,pc ),(降，算法可能早熟和局部收敛。由于大量的实验数据告诉我们选择通常降低种群的多样性；为了阻止种群的过快下降，我们可以根据以上定理选择合适的参数以确保 大于 1 因此，等式c=0 是至关重要的。mF22我们选择 Rastrigin 函数作为这次仿真实验的测试数据；并且初始化： 0,(,0),(nfxx (Rastrigin)函数 2f1*cos()10,5.2,1nxiii(1) 分析缩放因子 F 对 PD 的影响，固定 NP=10，CR=0.5（p）0 10 20 30 40 50 60 70 80 90 10000
18、.10.20.30.40.50.60.70.80.9GVar(x(G)F=0.9F=0.6F=0.3F=0.1图 1：放缩因子 F 对 PD 的影响（2）分析变异概率 CR（p）对 PD 的影响，固定 NP=10，F=0.3；陕西理工学院毕业论文0 10 20 30 40 50 60 70 80 90 1000.10.20.30.40.50.60.70.80.91GVar(x(G)CR=0.9CR=0.6CR=0.3CR=0.1图 2：变异概率 CR 对 PD 的影响（3）分析种群规模 NP 对 PD 的影响，固定 CR=0.5，F=0.3；0 10 20 30 40 50 60 70 80
19、90 1000.10.20.30.40.50.60.70.80.911.1GVar(x(G)NP=100NP=80NP=50NP=30图 3：种群规模 NP 对 PD 的影响陕西理工学院毕业论文我们知道变异，交叉操作会提高种群的多样性，而选择会减少 PD，从以上三个图可以得出结论：（1）对于固定的种群规模 NP，变异概率 CR（p） ；缩放因子 F 越小此函数收敛越快，一般取值在 0.1 到0.3 之间。（2）固定变异概率,种群规模；放缩因子在 0.3 与 0.6 之间收敛的更快；（3）固定变异概率,变异概率; 种群规模随着代数的增加而趋同，对 PD 影响不大；6.结束语经过多轮迭代过程之后，
20、种群中个体逐渐向最佳个体靠拢，种群多样性必然降低。个体差异变得越来越小，最终导致差异向量趋于零，方差也趋于零。对于单峰函数来讲，这种机制一般情况下会求出最佳解，但是对于多锋函数，最佳解仅仅只是一个局部最优点，那么变异操作和交叉操作将失去进化作用，导致算法出现如局部最优而出现早熟收敛现象。要克服上述基本算法中贪婪选择的缺陷，必须减缓种群多样性的下降速度，适当保持个体讲的差异，同时保证一定的收敛速度。为此，以上定理给出了三个算子与 PD 的关系；我们只需选择合适的参数值满足 =0 即可，同时仿真实验表明本文引mpF22入的几种多样性指标全面反映了 EA 的动态过程,完整描述了种群多样性各个侧面的含
21、义, 三个参数的选取时可以根据以上的仿真实验提出的选取范围，克服了以前选取算子的盲目性；将其用于 EA 的运行控制,可有效预测和预防 EA 的过早收敛 ,大大提高了 EA 的全局收敛性能。参考文献1 Storn R,Price K.Differential evolution for multi-objective optimizationJ.Evolutionary Computation,2003,42 杨启文 蔡亮 薛云灿.差分进化算法综述.模式识别与人工智能 .2008.43 Daniela Zaharie.CRITICAL VALUES FOR THE CONTROL PARAMET
22、ERS OF DIFFERENTION EVOLUTION ALGORITHMS.IEEE Press.20024 Daniela Zaharie.Statical Properties of DE and Related Random Search Algorithms.Computer Press.20085 段滨海 张祥银 徐春芳.仿生智能算法(Bio-inspired Computing).科学出版社.1010.116 张晓溃 戴冠中 徐乃平.遗传算法种群多样性的分析研究 .控制理论与应用.1998.17 刘波,王凌，金以慧差分进化算法研究进展J控制与决策,2007，22(7).Ana
23、lysis of the Population Diversity of the Differential Evolutionary AlgorithmGong Quan-Yong（Grade09,Class03,Major Mathematics and Applied Mathematics，Mathematics Dept.，ShaanxiUniversity of Technology, Hanzhong 723000,Shannxi） Tutor: Yong Long-quanAbstract：Propose a new diversity measure method (PD),
24、given a set of PD metrics and calculation methods, and the application of this metric shows the function of PD and the difference of three operator in evolutionary algorithms; this reference relationships of =0 given in this paper also selects the parameter value; through the simulation experiment to determine the mpF22range operator in EA algorithm, the evolutionary process effectively maintain population diversity is to avoid a kind of effective method for “premature“ phenomenon.Key words：differential evolution algorithm；Population Diversity；operator
