差分进化算法

差分进化算法1.1GA的基本概念1.2基本遗传算法1.3举例和应用2.1DE的来源2.2DE的标准算法单击增加标题内容GA遗传算法（GeneticAlgorithm）它是由美国的J.Holland教授1975年首先提出的模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。单击增加标题内容演化算法共有的对象元素种群编码适应度遗传操作3决定的参加交叉的染色体数，配对进行交叉操作，并用产生的新染色体代替原染色体4进行变异操作1初始化种群；评价种群适应度2选择优秀个体，复制成为新的群体5得到新的子种群遗传算法1.3遗传算法应用举例例:利用遗传算法求解区间［0,31］上的二次函数y=x2的最大值。分析可以看出,只要能在区间［0,31］中找到函数值最大的点a,则函数y=x2的最大值也就可以求得。于是,原问题转化为在区间［0,31］中寻找能使y取最大值的点a的问题。显然,对于这个问题,任一点x∈［0,31］都是可能解,而函数值f(x)=x2也就是衡量x能否为最佳解的一种测度。那么,用遗传算法的眼光来看,区间［0,31］就是一个(解)空间,x就是其中的个体对象,函数值f(x)恰好就可以作为x的适应度。这样,只要能给出个体x的适当染色体编码,该问题就可以用遗传算法来解决。解(1)定义适应度函数,编码染色体。由上面的分析,函数f(x)=x2就可作为空间U上的适应度函数。显然y=x2是一个单调增函数,其取最大值的点x=31是个整数。另一方面,5位二进制数也刚好能表示区间［0,31］中的全部整数。所以,我们就仅取［0,31］中的整数来作为参加进化的个体,并且用5位二进制数作为个体x的基因型编码,即染色体。(2)设定种群规模,产生初始种群。我们将种群规模设定为4,取染色体s1=01101(13),s2=11000(24),s3=01000(8),s4=10011(19)组成初始种群S1。(3)计算各代种群中的各染色体的适应度,并进行遗传操作,直到适应度最高的染色体(该问题中显然为“11111”=31)出现为止。计算S1中各染色体的适应度、选择概率、积累概率等并列于表4.1中。表1.3.1第一代种群S1中各染色体的情况染色体适应度选择概率积累概率估计被选中次数s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.001选择-复制设从区间［0,1］中产生4个随机数如下:r1=0.450126,r2=0.110347,r3=0.572496,r4=0.98503按赌轮选择法，染色体s1,s2,s3,s4的被选中次数依次为：1,2,0,1。于是，经复制得群体：s1’=11000（24）,s2’=01101（13）,s3’=11000（24）,s4’=10011（19）可以看出，在第一轮选择中适应度最高的染色体s2被选中两次，因而被复制两次；而适应度最低的染色体s3一次也没有选中而遭淘汰。交叉设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。设s1’与s2’配对，s2’与s4’配对。分别交换后两位基因，得新染色体：s1’’=11001（25）,s2’’=01100（12）,s3’’=11011（27）,s4’’=10000（16）变异设变异率pm=0.001。这样，群体S1中共有540.001=0.02位基因可以变异。0.02位显然不足1位，所以本轮遗传操作不做变异。现在，我们得到了第二代种群S2：s1=11001（25）,s2=01100（12）,s3=11011（27）,s4=10000（16）表1.3.2第二代种群S2中各染色体的情况染色体适应度选择概率积累概率估计被选中次数s1=110016250.360.361s2=011001440.080.440s3=110117290.410.852s4=100002560.151.001假设这一轮选择-复制操作中，种群S2中的4个染色体都被选中（因为选择概率毕竟只是一种几率，所以4个染色体恰好都被选中的情况是存在的），我们得到群体：s1’=11001（25）,s2’=01100（12）,s3’=11011（27）,s4’=10000（16）然后，做交叉运算，让s1’与s2’，s3’与s4’分别交换后三位基因，得s1’’=11100（28）,s2’’=01001（9）,s3’’=11000（24）,s4’’=10011（19）这一轮仍然不会发生变异。于是，得第三代种群S3：s1=11100（28）,s2=01001（9）,s3=11000（24）,s4=10011（19）表1.3.3第三代种群S4中各染色体的情况染色体适应度选择概率积累概率估计被选中次数s1=111007840.440.442s2=01001810.040.480s3=110005760.320.801s4=100113610.201.001设这一轮的选择-复制结果为：s1’=11100（28）,s2’=11100（28）,s3’=11000（24）,s4’=10011（19）然后，做交叉运算，让s1’与s4’，s2’与s3’分别交换后两位基因，得s1’’=11111（31）,s2’’=11100（28）,s3’’=11000（24）,s4’’=10000（16）这一轮仍然不会发生变异。于是，得第四代种群S4：s1=11111（31）,s2=11100（28）,s3=11000（24）,s4=10000（16）显然，在这一代种群中已经出现了适应度最高的染色体s1=11111。于是，遗传操作终止，将染色体“11111”作为最终结果输出。然后，将染色体“11111”解码为表现型，即得所求的最优解：31。将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。它是由Storn等人于1995年提出的，和其它演化算法一样，DE是一种模拟生物进化的随机模型，通过反复迭代，使得那些适应环境的个体被保存了下来。但相比于进化算法，DE保留了基于种群的全局搜索策略，采用实数编码、基于差分的简单变异操作和一对一的竞争生存策略，降低了遗传操作的复杂性。同时，DE特有的记忆能力使其可以动态跟踪当前的搜索情况，以调整其搜索策略，具有较强的全局收敛能力和鲁棒性，且不需要借助问题的特征信息，适于求解一些利用常规的数学规划方法所无法求解的复杂环境中的优化问题。2.1DifferentialEvolutionAlgorithms变异(Mutation)交叉(Crossover)选择(Selection)遗传操作算法的基本思想是从某一随机产生的初始群体开始，利用从种群中随机选取的两个个体的差向量作为第三个个体的随机变化源，将差向量加权后按照一定的规则与第三个个体求和而产生变异个体，该操作称为变异。然后，变异个体与某个预先决定的目标个体进行参数混合，生成试验个体，这一过程称之为交叉。如果试验个体的适应度值优于目标个体的适应度值，则在下一代中试验个体取代目标个体，否则目标个体仍保存下来，该操作称为选择DE是一种随机的并行直接搜索算法,它可对非线性不可微连续空间函数进行最小化,以其易用性、稳健性和强大的全局寻优能力在多个领域取得成功；在约束优化计算、聚类优化计算、非线性优化控制、神经网络优化、滤波器设计、阵列天线方向图综合及其它方面得到广泛应用。应用根据实际问题进行编码开始设置参数生成初始种群计算个体适应值是否满足进化终止条件算法结束，输出最优个体遗传操作，生成新种群否是一般演化算法的过程问题1、遗传操作象种群中所有个体种群中部分个体2、遗传操作顺序重叠非重叠3、新种群重组方式演化算法算法流程2.2标准DE流程图开开开开开开开开t=0开开开开开开开开POP(0)开开开开开开开开开开开开开开开开开开开开开开POP(t)for(inti=0;ipop_size;i++){开开i开开Xi开开开开开开开开开开开开开开开开开开Vi;开开开Xi开开开开开Vi开开开开开开,开开开开开开Ui;}开开开开开开开开开开开开开开POP(t+1)开开开开开开开开开开开开开开开开t=t+1开开开开开开开DE算法：基于实数编码；整体结构类似于遗传算法；变异操作是基于染色体的差异向量进行的；,1,2,max,,,1,2,,;1,2,.iiiinxtxtxtxtiMttixt1,2,LUijijijxxxjn求解非线性函数f(x1,x2,⋯,xn)的最小值问题,xi满足：令是第t代的第i个染色体,则其中,n是染色体的长度,即变量的个数,M为群体规模,是最大的进化代数。maxt基本算法实例(1)生成初始种群在n维空间里随机产生满足约束条件的M个染色体,实施措施如下：,00,1,1,2,,;1,2,LULijijijijijxxrandxxiMjn(2)变异操作从群体中随机选择3个染色体，，且(i≠p1≠p2≠p3),则1231ijpjpjpjvtxtxtxt3px2px为差异化向量,为缩放因子。23pjpjxtxt1px(3)交叉操作交叉操作是为了增加群体的多样性,具体操作如下:ijt11i1t1iijijijijvrandCRjrandutxrandCRjrand或且是在[0,1]之间的随机小数,CR为交叉概率,CR∈[0,1],rand(i)在[1,n]之间的随机整数,这种交叉策略可确保xi(t+1)至少有一分量由xi(t)的相应分量贡献。1ijrand(4)选择操作为了确定是否成为下一代的成员,比较向量和目标向量的评价函数:ixtixtu1it＋111,2,,iiiiiufutfxtxtiMxtotherwiset+1反复执行(2)至(4)操作,直至达到最大的进化代数tmax.DifferentialEvolution实验222221212(1)22351211211()3(1)(1)10()53xxxxxfxxexxxxee差分进化算法参数选取差异演化算法主要涉及群体规模M、缩放因子以及交叉概率CR三个参数的设定。•M：一般介于5×n与10×n之间,但不能少于4,否则无法进行变异操作;•：一般在[0,2]之间选择,通常取0.5;•CR：一般在[0,1]之间选择,比较好的选择应在0.3左右,CR大些收敛速度会加快,但易发生早熟现象。优点:差异演化在求解非凸、多峰、非线性函数优化问题表现极强的稳健性。在同样的精度要求下,差异演化算法收敛的速度快。差异演化算法尤其擅长求解多变量的函数优化问题。操作简单,易编程实现。缺点：由于差异演化的关键步骤变异操作是基于群体的差异向量信息来修正各个体的值,随着进化代数的增加,各个体之间的差异化信息在逐渐缩小,以至于后期收敛速度变慢,甚至有时会陷入局部最优点。优缺点差分进化算法DE的改进方法为了提高DE的寻优能力、加快收敛速度、克服启发式算法常见的早熟收敛现象，许多学者对DE算法进行改进:控制参数的改进。差分策略的改进。选择策略的改进。种群重构混合算法。DE的研究点DE还有很多方面有待完善，需要加强并进行深人研究：加强DE算法理论基础和系统分析方法的研究。加强DE各种改进方法的综合研究。加强DE与其他算法的结合。加强DE与应用的结合。谢谢侬编曲：吴瑞峰填词：吴瑞峰演唱：Eason