差分进化算法.ppt

差分进化算法


举例和应用
DE的来源

单击增加标题内容
GA
遗传算法(ic Algorithm),是一种通过模拟自然进化过程搜索最优解的方法。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境,末代种群中的最优个体经过解码(decoding),可以作为问题近似最优解。
单击增加标题内容
演化算法共有的对象元素
种群
编码
适应度
遗传操作
3
决定的参加交叉的染色体数,配对进行交叉操作,并用产生的新染色体代替原染色体
4
进行变异操作
1
初始化种群;
评价种群适应度
2
选择优秀个体,复制成为新的群体
5
得到新的子种群
遗传算法
遗传算法应用举例
例: 利用遗传算法求解区间[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中各染色体的适应度、选择概率、。
第一代种群S1中各染色体的情况
选择-复制设从区间[0, 1]中产生4个随机数如下:
r1=, r2=, r3=, r4=
按赌轮选择法,染色体s1, s2, s3, s4的被选中次数依次为:1, 2, 0, 1。于是,经复制得群体:
s1’=11000(24), s2’=01101(13), s3’=11000(24), s4’=10011(19)
可以看出,在第一轮选择中适应度最高的染色体s2被选中两次,因而被复制两次;而适应度最低的染色体s3一次也没有选中而遭淘汰。