遗传算法例题分析PPT课件.ppt

一个实例的遗传操作步骤分析 1 为了说明遗传算法的实质 本节以简单函数极值的求解过程为例 设自变量介于0 31 求其二次函数的最大值 即 1 1 当然 利用简单的代数运算 我们可以求出该问题的解为x 31 现在改用遗传算法求解 遗传算法通常包括下述工作 2 1 遗传算法首先要用字符串表达所研究的问题 这称作编码 表达问题的字符串相当于遗传学中的染色体 每个字符串称作个体 每一遗传代次中个体的组合称为群体 为了便于计算机操作 通常字符串长度固定 字符用二进制码或为0 或为1 本例中 用二进制数表示x值 由于x的最大值 31 只需5位二进制数 以利用5位二进制数组成个体 3 2 形成初始群体 遗传算法中 常用随机的方法产生初始群体 即随机生成一组任意排列的字符串 群体中个体的数目通常也是固定的 本例中 采用随机产生的方法 假设得出拥有4个个体的初始群体 即 01101 11000 01100 10011 它们的x值相应为 13 24 8 19 见表2 1 4 表2 1遗传算法的第0代 5 3 计算适应度 衡量字符串 染色体 好坏的指标是适应度 Fitness 它通常也就是遗传算法中的目标函数 适应度是今后优胜劣汰的主要判据 在本例中 适应度比较简单 用计算 当x值为13 24 6 19时的适应度分别为 169 576 64 361 表2 1的第4列 表1 1中还列举当前适应度的总和及平均值 即 6 表1 1中第6列的表示每个个体的相对适应度 它反映个体之间的相对优劣性 例如 2号个体的值最高 1 97 为优良个体 而3号个体最低 0 22 为不良个体 8 4 复制 Reproduction 为了将已有的群体变为下一代群体 遗传算法仿效进化论中 自然选择 适者生存 的原则 从旧群体中选择优良个体予以复制 直接进入下一代群体 选择的依据是个体适应度的大小 适应度大的个体接受复制 使之繁殖 适应度小的个体则予删除 使之死亡 本例中 根据相对适应度的大小对个体进行取舍 2号个体性能最优 予以复制繁殖 3号个体性能最差 将它删除 使之消亡 表2 1第7列表示传递给下一代的个体数目 其中2号个体占2个 3号个体为0个 1号及4号个体仍保持为1个 9 这样 就产生下一代新群体 如表1 2所示 新群体的4个个体分别是01101 11000 11000 10011 从表2 2第4列可以看出 复制后产生的新一代群体 其平均适应度明显增加 由原来的293 表2 1 增至421 表2 2 造成平均适应度增加的原因有二 一是淘汰原来最差的个体 使最小的适应度由原来的64 表2 1 增至169 表2 2 另一个原因是增加优良个体 2号 的个数 使适应度累计值增加 因此 复制体现优胜劣汰原则 使群体素质不断得到改善 10 表2 2遗传算法的复制与交叉 第1代 11 5 交叉 Crossover 通过复制产生新群体 其总体性能得到改善 然而却不能产生新的个体 为了产生新的个体 遗传算法仿照生物学中交叉的方法 对染色体 字符串 的某些部分进行交叉换位 被交换的母体都选自经过复制产生的新一代个体 优胜者 本例中 利用随机配对的方法 决定1号和2号个体 3号和4号个体分别交叉 如表1 2第5列所示 再利用随机定位的方法 确定这两对母体交叉换位的位置分别从字符串左数第三位字符及第二位字符之后 例如 3号及4号如下式左侧所示 交换始于字符串左数第2位之后 交叉开始的位置称为交叉点 用 标记 所得的新个体如下表所示 12 至于1号 2号个体交换结果如表2 2第7列所示 表2 2中最后一列表示交换后群体的适应度 从表中可以看出 交换后出现优异个体3号 其适应度高达729 大大高于交换前的最大值 576 与此同时 平均适应度也从原来的421提高到439 说明变换后的群体正朝优良方向发展 13 6 变异 Mutation 遗传算法模仿生物学中基因变异的方法 将个体字符串某位符号进行逆变 即由1变为0或由0变为1 例如 下式左侧的个体于第3位变异 得到新个体如右侧所示 遗传算法中 个体是否进行变异以及在哪个字符变异 都由事先给定的概率决定 通常 变异概率很小 约为0 01 本例的第一代中就没有发生变异 7 终止 反复执行上述 3 6 项工作 直至得出满意的最优解