第9章遗传算法.ppt

第9章 遗传算法 动机 算法 实现 Genetic Algorithm （GA） 受生物进化启发的学习算法 有哪些信誉好的足球投注网站特点： 不是从简单到复杂的有哪些信誉好的足球投注网站 不是从一般到特殊的有哪些信誉好的足球投注网站 是从当前最佳假设经过变异和重组来寻求更好假设 当前群体(Population)：当前使用的一组假设 使用目前适应度最高的假设的后代替换群体的某个部分 9.1 动机 GA算法的合理性 在生物系统中，进化被认为是一种成功的自适应方法，且具有很好的健壮性 GA有哪些信誉好的足球投注网站的假设空间中，假设的各个部分相互作用，每一部分对总的假设适应度难以建模 GA算法易于并行化，费用低廉 进化计算(Evolutionary Computation)： 遗传算法 遗传编程 鲍德温效应 遗传算法 算法目标：有哪些信誉好的足球投注网站候选假设空间并确定最佳假设 什么是最佳假设？ 使适应度(fitness)最优的假设 什么是适应度？ 为需解决的问题预先定义的数字度量 遗传算法 算法实现的细节各有不同 都具有共同的结构：算法迭代更新一个假设池 假设池称为群体 通过适应度函数的评估，从当前群体中用概率的方法选取合适的个体 一部分保持原样进入下一代群体，另一部分使用交叉和变异的方法产生新个体 遗传算法原型 GA 群体P Fitness Thresh 假设数量p 交叉率r 变异率m P中适应度最高的假设 Random 维持一个有p个假设组成的群体 后继群体Ps通过根据假设的适应度用概率的方法选择个体和加入新的假设形成 新假设得到的两种途径：对最高适应度假设用交叉算子；通过创建部分假设的单点变异 遗传算法 竞争：一个假设被选入下一个群体的概率与它自己的适应度成正比 繁殖：交叉操作产生新个体 变异：随机选位取反 9.2.1 表示假设 规则的前件和后件 IF 前件 THEN 后件 规则的编码：位串 避免无意义的位串： 采用合适的编码方式来避免 赋予极低的适应度函数值 9.2.2 遗传算子 算子(Operator)：用来对群体中的成员进行重组和变异，以决定后代 交叉算子(Crossover Operator)：从双亲中复制选定位产生两个新的后代 变异算子(Mutation Operator)：随机选位取反 人类的遗传是如何进行交叉和变异的？ 9.2.3 适应度函数和假设选择 适应度函数(Fitness)：以概率方法选择下一代群体的准则 选择方案： 轮盘赌选择：适应度大小 锦标赛选择：适应度高则按照概率p被选 排序选择：按照适应度排序，每个排序位置有确定的被选概率p 9.3 举例 /xJava/GA/ 遗传与进化模拟 草原与吃货 环境： 空地、草块、墙 吃货（eater）： 吃最多的草 具有内部状态 每次做一个移动的决定： 向前1格、向后1格 左转1格、右转1格 草原与吃货 环境： 空地、草块、墙 吃货（eater）： 吃最多的草 具有内部状态 每次做一个移动的决定 规则（基因、染色体）： 状态改变、转向 映射 原状态、视野 共有64条规则 适者生存 每年底算账，计算下年吃货名额 本年吃的越多，则获得后代的几率和数量越多 本年吃的太少，则基本不可能有后代 得到后代的操作： 遗传（copy） 变异（mutation） 交叉（crossover） 9.5 遗传编程 程序表示 举例 9.6 进化和学习模型 生物个体的适应能力改善与物种进化的关系 拉马克进化 个别生物的生存经验直接影响其后代的遗传结构 有利于提高计算机遗传算法的效率 鲍德温效应 如果一个物种在一个变化的环境中进化，那么进化的压力会选择有学习能力的个体 不学习的个体完全取决于其遗传结构，处于劣势 个体的学习能力具有间接加速整个群体进化适应的作用 9.7 并行遗传算法 粗粒度并行方法 细粒度并行方法