遗传算法.ppt

文档介绍：机器学****Tom  第9章遗传算法
1
遗传算法是一种大致基于模拟进化的学****方法,假设通常被描述为二进制位串,符号表达式或计算机程序
当前群体的成员通过模拟生物进化的方式来产生下一代群体,比如随机变异和交叉
遗传算法已被成功用于多种学****任务和最优化问题中,比如学****机器人控制的规则集和优化人工神经网络的拓扑结构和学****参数
本章主要介绍了基于位串描述假设的遗传算法(GA)和基于计算机程序描述假设的遗传编程(GP)
概述
2
动机
遗传算法(GA)是一种受生物进化启发的学****方法,它不再是从一般到特殊或从简单到复杂地搜索假设,而是通过变异和重组当前已知的最好假设来生成后续的假设
每一步,更新被称为当前群体的一组假设,方法是使用当前适应度最高的假设的后代替代群体的某个部分
遗传算法的普及和发展
在生物系统中,进化被认为是一种成功的自适应方法,具有很好的健壮性
遗传算法搜索的假设空间中,假设的各个部分相互作用,每一部分对总的假设适应度的影响难以建模
遗传算法易于并行化
3
本章内容安排
动机
遗传算法(表示假设、遗传算子、适应度函数和假设选择)
假设空间搜索
遗传编程(程序表示、遗传编程举例说明)
进化和学****模型(拉马克进化、鲍德温效应)
并行遗传算法
4
遗传算法
遗传算法研究的问题是搜索候选假设空间并确定最佳假设(使适应度最优的假设)
遗传算法具有以下的共同结构:
算法迭代更新一个假设池(群体)
在每一次迭代中,根据适应度评估群体中的所有成员,根据概率方法选取适应度最高的个体产生新一代群体
在被选中的个体中,一部分保持原样地进入下一代群体,其他被用作产生后代个体的基础
遗传算法执行一种随机的、并行柱状的搜索,根据适应度函数发现好的假设
5
表9-1 遗传算法原型
GA(Fitness, Fitness_threshold, p, r, m)
Fitness:适应度评分函数
Fitness_threshold:指定终止判据的阈值
p:群体中包含的假设数量
r:每一步中通过交叉取代群体成员的比例
m:变异率
初始化群体:P随机产生的p个假设
评估:对于P中每个假设h,计算Fitness(h)
当<Fitness_threshold,产生新一代PS,做:
选择:用概率方法选择P的(1-r)p个成员加入PS,概率公式是
交叉:按概率从P中选择rp/2对假设,对于每对假设<h1,h2>,应用交叉算子产生两个后代,把所有的后代加入PS
变异:使用均匀的概率从PS中选择m%的成员,应用变异算子
更新:PPS
评估:对于P中每个h计算Fitness(h)
从P中返回适应度最高的假设
6
表示假设
遗传算法中的假设常常被表示成二进制位串,这便于用变异和交叉遗传算子来操作
把if-then规则编码成位串
首先使用位串描述单个属性的值约束
多个属性约束的合取可以很容易地表示为对应位串的连接
整个规则表示可以通过把描述规则前件和后件的位串连接起来
位串的特点
表示规则的位串对假设空间中的每个属性有一个子串,即使该属性不被规则的前件约束。
得到一个固定长度的规则位串表示,其中特定位置的子串描述对应特定属性的约束
7
表示假设
单个属性约束
串010 Outlook=Overcast
串011 Outlook=OvercastRain
串111 我们不关心这个属性取哪个值
多个属性约束的合取
串 011 10 Outlook Wind (Outlook=OvercastRain)(Wind=Strong)
规则的后件
串111 10 10 Outlook Wind PlayTennis
Wind=Strong THEN PlayTennis=yes
8
遗传算子
交叉:
从两个双亲串中通过复制选定位产生两个新的后代,每个后代的第i位是从它的某个双亲的第i位复制来的
双亲中的哪一个在第i位起作用,由另一个称为交叉掩码的位串决定:
单点交叉:前n位来自第一个双亲,余下的位来自第二个双亲
两点交叉:用一个双亲的中间片断替换第二个双亲的中间片断
均匀交叉:合并了从两个双亲以均匀概率抽取的位
变异:
从单一双亲产生后代,对位串产生随机的小变化,方法是选取一个位,然后取反
变异经常是在应用交叉之后
其他算子
使规则特化的算子
直接泛化
9
10