第9章遗传算法

1、第9章 遗传算法动机 算法 实现wGenetic Algorithm （GA）w受生物进化启发的学习算法w搜索特点： 不是从简单到复杂的搜索 不是从一般到特殊的搜索 是从当前最佳假设经过变异和重组来寻求更好假设w当前群体(Population)：当前使用的一组假设w使用目前适应度最高的假设的后代替换群体的某个部分9.1 动机GA算法的合理性w在生物系统中，进化被认为是一种成功的自适应方法，且具有很好的健壮性wGA搜索的假设空间中，假设的各个部分相互作用，每一部分对总的假设适应度难以建模wGA算法易于并行化，费用低廉w进化计算(Evolutionary Computation)： 遗传算法 遗传

2、编程 鲍德温效应遗传算法w算法目标：搜索候选假设空间并确定最佳假设w什么是最佳假设？ 使适应度(fitness)最优的假设w什么是适应度？ 为需解决的问题预先定义的数字度量遗传算法w算法实现的细节各有不同w都具有共同的结构：算法迭代更新一个假设池w假设池称为群体w通过适应度函数的评估，从当前群体中用概率的方法选取合适的个体w一部分保持原样进入下一代群体，另一部分使用交叉和变异的方法产生新个体遗传算法原型GA群体PFitnessThresh假设数量p交叉率r变异率mP中适应度最高的假设Random维持一个有p个假设组成的群体后继群体Ps通过根据假设的适应度用概率的方法选择个体和加入新的假设形成新

3、假设得到的两种途径：对最高适应度假设用交叉算子；通过创建部分假设的单点变异遗传算法w竞争：一个假设被选入下一个群体的概率与它自己的适应度成正比w繁殖：交叉操作产生新个体w变异：随机选位取反9.2.1 表示假设w规则的前件和后件 IF 前件 THEN 后件w规则的编码：位串w避免无意义的位串： 采用合适的编码方式来避免 赋予极低的适应度函数值9.2.2 遗传算子w算子(Operator)：用来对群体中的成员进行重组和变异，以决定后代w交叉算子(Crossover Operator)：从双亲中复制选定位产生两个新的后代w变异算子(Mutation Operator)：随机选位取反w人类的遗传是如何

4、进行交叉和变异的？9.2.3 适应度函数和假设选择w适应度函数(Fitness)：以概率方法选择下一代群体的准则w选择方案： 轮盘赌选择：适应度大小 锦标赛选择：适应度高则按照概率p被选 排序选择：按照适应度排序，每个排序位置有确定的被选概率p9.3 举例/xJava/GA/遗传与进化模拟草原与吃货w环境：空地、草块、墙w吃货（eater）：吃最多的草具有内部状态每次做一个移动的决定：w向前1格、向后1格w左转1格、右转1格草原与吃货w环境：空地、草块、墙w吃货（eater）：吃最多的草具有内部状态每次做一个移动的决定w规则（基因、染色体）：状态改变、转向 映射 原状态、视野共有64条规则适者生存w每年底算账，计算下年吃货名额w本年吃的越多，则获得后代的几率和数量越多w本年吃的太少，则基本不可能有后代w得到后代的操作：遗传（copy）变异（mutation）交叉（crossover）9.5 遗传编程程序表示举例9.6 进化和学习模型w生物个体的适应能力改善与物种进化的关系w拉马克进化 个别生物的生存经验直接影响其后代的遗传结构 有利于提高计算机遗传算法的效率w鲍德温效应 如果一个物种在一个变化的环境中进化，那么进化的压力会选择有学习能力