专题3遗传算法.ppt

专题3 关于遗传算法 步骤： 1.编码 2.计算适应度 3.复制 4.交换 5.突变 * * 设自变量 x 介于0～31，求其二次函数的最大值，即： max f(x) = x2, x∈ [0, 31] 命题： 极大值问题 500 1000 0 31 x f (x) 当然，利用简单的代数运算，很容易求出该问题的解。现在改用遗传算法求解，遗传算法通常包括下述内容： （1）编码 遗传算法首先要对实际问题进行编码，用字符串表达问题。这种字符串相当于遗传学中的染色体。每一代所产生的字符串个体总和称为群体。为了计算机实现的方便，通常字符串长度固定，字符选0或1。 本例中，利用5位二进制数表示x值，采用随机产生的方法，假设得出拥有四个个体的初始群体，即：01101，11000，01000，10011。x值相应为13，24，8，19。 4 1 2 0 4.00 1.00 1.97 0.22 1.00 0.25 0.49 0.06 1170 293 576 64 总计∑f(xi) 平均值f 最大值 最小值 1 2 0 1 0.58 1.97 0.22 1.23 0.14 0.49 0.06 0.31 169 576 64 361 13 24 8 19 01101 11000 01000 10011 1 2 3 4 7 6 5 4 3 2 1 Mp f(xi)/f f(xi)/∑f(xi) 适应度f(xi) xi 初始群体 个体编号 （2）计算适应度 衡量字符串（染色体）好坏的指标是适应度，它也就是遗传算法的目标函数。 本例中适应度比较简单，用x2计算。 表中还列出了当前适应度的总和∑f(xi)及平均值f，即： ∑f(xi) = f(x1) + f(x2) + f(x3) + f(x4) = 1170 f = ∑f(xi) /4 = 293 4 1 2 0 4.00 1.00 1.97 0.22 1.00 0.25 0.49 0.06 1170 293 576 64 总计∑f(xi) 平均值f 最大值 最小值 1 2 0 1 0.58 1.97 0.22 1.23 0.14 0.49 0.06 0.31 169 576 64 361 13 24 8 19 01101 11000 01000 10011 1 2 3 4 7 6 5 4 3 2 1 Mp f(xi)/f f(xi)/∑f(xi) 适应度f(xi) xi 初始群体 个体编号 （2）计算适应度 表中第6列的 f(xi)/f 表示每个个体的相对适应度，它反映了个体之间的相对优劣性。如2号个体的 f(xi)/f 值最高（1.97），为优良个体，3号个体最低（0.22），为不良个体。 4 1 2 0 4.00 1.00 1.97 0.22 1.00 0.25 0.49 0.06 1170 293 576 64 总计∑f(xi) 平均值f 最大值 最小值 1 2 0 1 0.58 1.97 0.22 1.23 0.14 0.49 0.06 0.31 169 576 64 361 13 24 8 19 01101 11000 01000 10011 1 2 3 4 7 6 5 4 3 2 1 Mp f(xi)/f f(xi)/∑f(xi) 适应度f(xi) xi 初始群体 个体编号 （3）复制 为了将已有的群体变为下一代群体，遗传算法仿效进化论中“自然选择、适者生存”的原则，从旧群体中选择优良个体进行复制。选择的依据是个体适应度的大小，适应度大的个体接受复制，使之繁殖；适应度小的个体则删除掉，使之死亡。 （3）复制 在本例中，根据相对适应度的大小对个体进行取舍，2号个体性能最优，予以复制繁殖。3号个体性能最差，将它删除，使之死亡，表中的M表示传递给下一代的个体数目，其中2号个体占2个，3号个体为0，1号、4号个体保持为1个。 这样，就产生了下一代群体。 4 1 2 0 4.00 1.00 1.97 0.22 1.00 0.25 0.49 0.06 1170 293 576 64 总计∑f(xi) 平均值f 最大值 最小值 1 2 0 1 0.58 1.97 0.22 1.23 0.14 0.49 0.06 0.31 169 576 64 361 13 24 8 19 01101 11000 01000 10011 1 2 3 4 7 6 5 4 3 2 1 Mp f(xi)/f f(xi)