机器学习-遗传算法.ppt

机器学习-遗传算法
概述
遗传算法是一种大致基于模拟进化的学习方法
假设通常被描述为二进制位串，也可以是符号表达式或计算机程序
搜索合适的假设从若干初始假设的群体或集合开始
当前群体的成员通过模拟生物进化的方式来产生下一代群体，比如ook，它的值可以取以下3个中的任一个：Sunny、Overcast、Rain，因此一个明显的方法是使用一个长度为3的位串，每位对应一个可能值，若某位为1，表示这个属性可以取对应的值
多个属性约束的合取可以很容易地表示为对应位串的连接
整个规则表示可以通过把描述规则前件和后件的位串连接起来

9
机器学习-遗传算法 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏
Gabil系统
Dejong et ：遗传算法在概念学习方面的应用
学习以命题规则的析取集合表示的布尔概念
在对几个概念学习问题的实验中发现，在泛化精度方面Gabil与其他学习算法大体相当
Gabil使用的算法就是表9-1描述的典型算法

15
机器学习-遗传算法 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏
Gabil系统（2）
Gabil的具体实现
表示：每个假设对应一个命题规则的析取集，
遗传算子：
变异：使用表9-2中的标准变异算子
交叉：表9-2中的两点交叉算子的一个扩展，这种方法保证了产生的位串表示的规则集是良定义的
适应度函数：每个规则集的适应度是根据它在训练数据上的分类精度计算的，Fitness(h)=(correct(h))2

16
机器学习-遗传算法 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏
Gabil系统的扩展
增加两个新算子
AddAlternative，它泛化对某个特定属性的约束，方法是把这个属性对应的子串中的一个0改为1，
DropCondition，把一个特定属性的所有位都替换为1，
两种使用新算子的方法
对每一代群体中的每个假设以同样的概率应用
对假设的位串进行扩展，使其包含另外两位以决定是否可以对该假设应用这两个新算子

17
机器学习-遗传算法 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏
假设空间搜索
遗传算法采用一种随机化的柱状搜索来寻找最大适应度的假设，与前面章节的搜索算法有很大不同
梯度下降搜索从一个假设平滑移动到另一个非常相似的假设
遗传算法的移动可能非常突然，使用和双亲根本不同的后代替换双亲假设
遗传算法的搜索不太可能像梯度下降方法那样陷入局部最小值的问题
遗传算法应用中的一个难题：拥挤问题
拥挤：群体中某个体适应度大大高于其他个体，因此它迅速繁殖，以至于此个体和与它相似的个体占据了群体的绝大部分
拥挤降低了群体的多样性，从而减慢了进化的进程

18
机器学习-遗传算法 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏
假设空间搜索（2）
降低拥挤的策略
使用锦标赛选择或排序选择，而不用适应度比例轮盘赌选择
适应度共享，根据群体中与某个体相似的个体数量，减小该个体的适应度
对可重组生成后代的个体种类进行限制，比如受到生物进化的启示
通过只允许最相似的个体重组，可以在群体中促成相似的个体聚类，形成亚种
按空间分布个体，只允许相邻的个体重组

19
机器学习-遗传算法 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏
群体进化和模式理论
模式理论（Holland1975）提供了一种用数学方法刻画遗传算法中群体进化的过程
模式是由若干0、1和*组成的任意串，*表示任意符号
模式理论根据每个模式的实例数量来刻画遗传算法中群体的进化
令m(s,t)表示群体中的模式s在时间t的实例数量
模式理论根据m(s,t)和模式、群体及其他属性来描述m(s,t+1)的期望值

20
机器学习-遗传算法 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏
群体进化和模式理论（2）
遗传算法中群体的进化依赖于几个步骤，即选择、重组和变异。
符号表示：
f(h)表示位串个体h的适应度
n为群体中个体的总数量
表示在时间t群体中所有个体的平均适应度
表示在时间t群体中模式s的实例的平均适应度
表示个体h既是模式s的一个代表，又是时间t群体的一个成员

21
机器学习-遗传算法 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏
群体进化和模式理论（3）
E(m(s,t+1))的推导，仅考虑选择的情