差分进化算法课件.ppt

《差分进化算法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、差分进化算法1.1GA的基本概念1.2基本遗传算法1.3举例和应用2.1DE的来源2.2DE的标准算法单击增加标题内容GA遗传算法（GeneticAlgorithm）它是由美国的J.Holland教授1975年首先提出的模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。单击增加标题内容演化算法共有的对象元素种群编码适

2、应度遗传操作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

3、也就是衡量x能否为最佳解的一种测度。那么,用遗传算法的眼光来看,区间［0,31］就是一个(解)空间,x就是其中的个体对象,函数值f(x)恰好就可以作为x的适应度。这样,只要能给出个体x的适当染色体编码,该问题就可以用遗传算法来解决。解(1)定义适应度函数,编码染色体。由上面的分析,函数f(x)=x2就可作为空间U上的适应度函数。显然y=x2是一个单调增函数,其取最大值的点x=31是个整数。另一方面,5位二进制数也刚好能表示区间［0,31］中的全部整数。所以,我们就仅取［0,31］中的整数来作为参加进化的个体,并且

4、用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中各染色体的情况选择-复制设从区间［0,1］中产生4个随机数如下:r

5、1=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’

6、配对。分别交换后两位基因，得新染色体：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中各染色体的情况假设这一轮选择-复制操作中，种群S2中的4个染色

7、体都被选中（因为选择概率毕竟只是一种几率，所以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）

8、,s4=10011（19）表1.3.3第三代种群S4中各染色体的情况设这一轮的选择-复制结果为：s1’=11100（28）,s2’=11100（28）,s3’=11000（24）,s4’=10011（19）然后，做交叉运算，让s1’与s4’，s2’与s3’分别交换后两位基因，得s1’’=11111（31）,s2’’=11100（28）,s3’’=11000（