差分进化算法种群多样性分析.doc

陕西理工学院毕业论文 陕西理工学院毕业论文题目： 差分进化算法种群多样性分析姓名： 汪兵兵 学号： 0909014094所在院系： 数学与计算机科学学院 专业：数学与应用数学 班级：数学093班指导教师： 雍 龙 泉差分进化算法种群多样性分析摘要： 提出了一种新的种群多样性（PD）度量方法，给出了一组PD度量标准及计算方法，并运用这种度量标准证明出了PD与差分进化算法中三个算子的函数关系式；以此在选取参数值时给出了参考关系式=0；本文还通过仿真实验来确定算子的取值范围，在DE算法进化过程中有效的保持种群的多样性是避免“早熟”现象生的一种行之有效的方法。关键词： 种群多样性 差分进化算法 算子1.引言近年来尽管差分进化算法(简称DE)得到了广大研究者的关注和研究,但它仍存在许多突出的问题需要解决，其中最广泛关注的问题之一就是DE的过早敛问题。最近的研究发现:过早收敛总是与种群中个体趋同、种群多样性的迅速下降有密切关系；算法的性能很大程度上和参数的选取有关。然而对DE算法参数分析的专门性文章却很少，种群多样性(Population Diversity,下简称PD)应怎样定义和度量?在DE优化过程中PD是如何变化的并与DE中三个算子的关系是怎样的的?如何产生和利用/有用的种群多样性来提高DE的性能?这些问题对进一步理解DE的进化动态、提高DE的搜索性能是很重要的,也是本文要解决的问题。2基本差分进化算法介绍差分进化算法是R.Stom和K.Price于1995年提出的，并在96年首届IEEE进化算法大赛中被证明为最快的进化算法。而且DE算法在收敛速度和稳定性方面都超过了其它几种知名的随机算法，对于大多数的数Benchmark问题，DE算法优于P算法。此外，由于DE算法容易理解、易于实现等优点，所以一经提出就倍受关注并得到了广泛的应用。（1）种群初始化在问题的解空间内随机产生初始种群，其中，用于表征第i个个体解。个体的各个分量可按下式产生： 其中，和分别为解空间第j维的上下界。（2）变异操作对于父代种群中任意的一个目标向量按下面公式生成变异向量： ， 其中，是父代种群中随机选择的三个不同个体，并且 ，可见，种群规模应满足NP4；放缩因子F是一个介于0,2间的实型常量因子，用于控制差分向量（）的影响。（3）交叉操作差分进化算法交叉操作的目的是通过变异向量和目标向量各维分量的随机重组以提高种群个体的多样性。算法通过下面公式生成新的交叉向量= , ,.,:= i=1,.,NP,j=1,.,NP randb是0,1间的随机数；CR是0,1间的常数，CR取值越大，发生交叉的可能就越大；是在1，D随机选择的整数，它保证至从少要中获得一个元素，以确保有新的个体生成，从而避免群体的进化停滞。（4）选择操作差分进化算法的选择操作是一种“贪婪”选择模式，当且仅当新的向量个体的适应度值比目标向量个体的适应度值更好时，才会被种群接受。否则，仍将保留在下一代的种群中，并在下一次迭代计算中继续作为目标向量执行变异及交叉操作。设优化问题为minf(x),则选择操作可由下式描述： 差分进化算法的选择操作是由父代个体与新产生的候选个体之间一对一地进行竞争，优胜劣汰，使得子代个体总是优于或等于父代个体，从而使种群始终向最优解的方向进化。（5）终止判断记（4）产生的新种群X(t+1)中的最优个体为(t+1)。若满足要求或者达到其他的终止条件，则终止并输出(t+1)作为最优解； 否则， 令t=t+1， 转（2） 。初始化 P(0)= ，g=0循环：变异： ，,交叉：公式编辑器中的文字的字体字号的大小概率为p概率为1-p ,选择： 如果 那么 否则 g=g+1直到一个停滞准则被满足。 图1：DE 算法结构3.种群多样性的表示一般可从宏观和微观两个角度来考虑种群的多样性.从宏观上,考虑种群中个体间的差异程度,这是最直观意义上的多样性,另一方面,种群内个体多样性的增加或降低是由个体串基因位的变化引起的,因此还应考虑以基因为单位的种群多样性;本文在上述思想基础上,提出一种新的种群多样性度量方法,较全面地刻画了种群的进化动态。以二进制编码的种群为例，设种群P由N个个体p1,pN组成,每个个体均是定义在0,1上的编码串,长度为l将种群P表示为N*l的矩阵,其每一行表示为一个个体串,每一列表示各个体串在特定基因的值,pji表示第i个个体的第j位基因值1有以下定义定义1：种群的平均： （1）定义2：种群的整体多样性： （2）定义3：基因内部多样性： （3） 基因外部多样性： （4）式中为基因在群种中的平均。种群的基因多样性 （5）定义4：个体内部多样性 （6）个体外部多样性 （7）式中， 为个体的平均。种群的个体多样性 （8）实际上一共定义了5种多样性,下面进一步分析各种多样性之间的关系，先分析种群基因多样性与种群整体多样性的关系。=因此同理可得 所以 由以上结果可以看出,种群的整体多样性可以不同的方式进行分解得到不同意义和作用的多样性；由定义3和定义4,式(3) (8)分别从基因和个体两个角度定义了种群多样性；它们对种群多样性的分析方式不同,一个以基因为单位,一个以个体为单位,分别得到不同意义和作用的多样性度量标准，以个体的平均为中介,可将种群的个体多样性分为两部分:一是反映每个个体内部各基因相对于个体平均的差异,体现了一个个体内部构成的多样性;另一个是反映所有个体的平均相对于种群平均的差异,即不同个体间的多样性,反映了不同个体间的差异程度；通常我们感兴趣的是后者,即个体外部多样性,它代表种群中的个体在整个搜索空间中的聚集程度,反映了种群中各个体的分布情况,是衡量种群中所有个体对整个搜索空间覆盖范围的重要标志；同样,以基因在种群的平均为中介,也将种群基因多样性分成两部分:一是反映种群中所有个体在特定的基因位取值的差异,它表明了种群在该基因位的收敛程度;另一个是反映各基因位的平均值与种群平均的差异,亦即基因平均间的差异，在EA的种群多样性和其收敛性研究中,我们关注前者,即基因的内部多样性它代表遗传漂移的程度,是衡量EA进化能力强弱的重要尺度。从以上的分析能够很明显看出,在研究EA过早收敛现象中的含义和作用,而其它几种多样性指标的作用并不十分明显；从我们引入PD的目的来看,除了研究它们与过早收敛的关系以找到防止EA早熟的措施外,另一个重要目的就是中出EA中的三个算子之间的对PD的影响及其关系。在这里我们以个体外部多样性为讨论对象，有一样的性质；令种群的方差Var（x）=；为种群所有个体方差的数学期望用于表述种群的多样性。我们给出以下定义：定义5 若第t代种群中的个体由L个基因构成,即,定义第t代种群的平均个体,如下: 即每个元素都有方差 整个种群的方差的数学期望值为：在以下的定理中将PD解释为种群方差的数学期望。4.定理的提出以及证明理论： 设但前值为，在变异后的中间种群为，在以上过程基础上交叉后得到的种群为。就常数和以上给出的支持一下陈叙：（a）在变异后种群方差的数学期望： （b）在编译和交叉后种群方差的数学期望： 证明： （a）由于Y中的每个元素满足，其中，和是从中随机选取的三个不相同的数，对于种群Y的每个元素，这种类型的采样，确保选择的系数是不同的，由于抽样的性质不取决于系数l，所以为了简化公式，我们删除系数l。系数，和可以被视为值在中的随机变量；并且他们有这样的性质：对于任一个都有因此也是一个随机变量并且有。应为，和是相互独立的，所以有。在另一方面对于所有的l都有现在我们运算：= 为了得到第二个等式我们用到了性质：当时有为了求得 我们还需求的，即：+由于对于Y中的每个元素，系数，和经过新的一轮抽样而得到且相互独立，因此对都有和是相互独立的。因此有于是我们得到 因此 （b） 种群Z的每一个元素有以下结构的随机变量：概率为1-p概率为p ,为了求得，我们必须计算出和；另一方面： (9)又由于和是相互独立的，最后一个等式的第二个式子可以扩充为：但是 因此代入上式（9）中得到：因此：定理得以证明。5.结论和仿真实验从以上证明结果可以看出： 其中如果1,这些变量算子会是种群多样性增大；如果1,在变异和交叉后种群多样性下降，算法可能早熟和局部收敛。由于大量的实验数据告诉我们选择通常降低种群的多样性；为了阻止种群的过快下降，我们可以根据以上定理选择合适的参数以确保大于1因此，等式=0是至关重要的。我们选择Rastrigin函数作为这次仿真实验的测试数据；并且初始化： (Rastrigin)函数 (1) 分析缩放因子F对PD的影响，固定NP=10，CR=0.5（p） 图1：放缩因子F对PD的影响（2）分析变异概率CR（p）对PD的影响，固定NP=10，F=0.3； 图2：变异概率CR对PD的影响（3）分析种群规模NP对PD的影响，固定CR=0.5，F=0.3； 图3：种群规模NP对PD的影响我们知道变异，交叉操作会提高种群的多样性，而选择会减少PD，从以上三个图可以得出结论：（1）对于固定的种群规模NP，变异概率CR（p）；缩放因子F越小此函数收敛越快，一般取值在0.1到0.3之间。（2）固定变异概率,种群规模；放缩因子在0.3与0.6之间收敛的更快；（3）固定变异概率,变异概率; 种群规模随着代数的增加而趋同，对PD影响不大；6.结束语经过多轮迭代过程之后，种群中个体逐渐向最佳个体靠拢，种群多样性必然降低。个体差异变得越来越小，最终导致差异向量趋于零，方差也趋于零。对于单峰函数来讲，这种机制一般情况下会求出最佳解，但是对于多锋函数，最佳解仅仅只是一个局部最优点，那么变异操作和交叉操作将失去进化作用，导致算法出现如局部最优而出现早熟收敛现象。要克服上述基本算法中贪婪选择的缺陷，必须减缓种群多样性的下降速度，适当保持个体讲的差异，同时保证一定的收敛速度。为此，以上定理给出了三个算子与PD的关系；我们只需选择合适的参数值满足=0即可，同时仿真实验表明本文引入的几种多样性指标全面反映了EA的动态过程,完整描述了种群多样性各个侧面的含义, 三个参数的选取时可以根据以上的仿真实验提出的选取范围，克服了以前选取算子的盲目性；将其用于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 PARAMETERS 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).Analysis 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), 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