遗传算法岭师吴旭明

机器学习第9章遗传算法2003.12.181概述•遗传算法是一种大致基于模拟进化的学习方法•假设通常被描述为二进制位串，也可以是符号表达式或计算机程序•搜索合适的假设从若干初始假设的群体或集合开始•当前群体的成员通过模拟生物进化的方式来产生下一代群体，比如随机变异和交叉•每一步，根据给定的适应度评估当前群体中的假设，而后使用概率方法选出适应度最高的假设作为产生下一代的种子•遗传算法已被成功用于多种学习任务和最优化问题中，比如学习机器人控制的规则集和优化人工神经网络的拓扑结构和学习参数•本章主要介绍了基于位串描述假设的遗传算法和基于计算机程序描述假设的遗传编程2003.12.18机器学习-遗传算法作者：Mitchell译者：曾华军等讲者：陶晓鹏2动机•遗传算法（GA）是一种受生物进化启发的学习方法，它不再是从一般到特殊或从简单到复杂地搜索假设，而是通过变异和重组当前已知的最好假设来生成后续的假设•每一步，更新被称为当前群体的一组假设，方法是使用当前适应度最高的假设的后代替代群体的某个部分•这个过程形成了假设的生成测试的柱状搜索，其中若干个最佳当前假设的变体最有可能在下一步被考虑2003.12.18机器学习-遗传算法作者：Mitchell译者：曾华军等讲者：陶晓鹏3动机（2）•遗传算法的普及和发展得益于下面的因素–在生物系统中，进化被认为是一种成功的自适应方法，具有很好的健壮性–遗传算法搜索的假设空间中，假设的各个部分相互作用，每一部分对总的假设适应度的影响难以建模–遗传算法易于并行化•本章内容安排–描述了遗传算法，举例演示了它的用法，分析了它搜索的空间的特性–描述了遗传算法的一个变体：遗传编程，这个方法中，整个计算机程序向着某个适应度准则进化–介绍了一些有关生物进化的课题（遗传算法和遗传编程是进化计算领域中的两种普遍方法），比如鲍德温效应，它描述了个体的学习能力与整个群体进化速度之间的相互作用2003.12.18机器学习-遗传算法作者：Mitchell译者：曾华军等讲者：陶晓鹏4遗传算法•遗传算法研究的问题是搜索候选假设空间并确定最佳假设•最佳假设被定义为使适应度最优的假设–适应度是为当前问题预先定义的数字度量，比如：•如果学习任务是在给定一个未知函数的输入输出训练样例后逼近这个函数，适应度可被定义为假设在训练数据上的精度•如果是学习下国际象棋的策略，适应度可被定义为该个体在当前群体中与其他个体对弈的获胜率2003.12.18机器学习-遗传算法作者：Mitchell译者：曾华军等讲者：陶晓鹏5遗传算法（2）•遗传算法具有以下的共同结构：–算法迭代更新一个假设池，这个假设池称为群体–在每一次迭代中，根据适应度评估群体中的所有成员，然后用概率方法选取适应度最高的个体产生新一代群体–在被选中的个体中，一部分保持原样地进入下一代群体，其他被用作产生后代个体的基础，其中应用交叉和变异这样的遗传方法2003.12.18机器学习-遗传算法作者：Mitchell译者：曾华军等讲者：陶晓鹏6表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中返回适应度最高的假设pjjiihFitnesshFitnessh1)()()Pr()(maxhFitnessh2003.12.18机器学习-遗传算法作者：Mitchell译者：曾华军等讲者：陶晓鹏7遗传算法（3）•算法的每一次迭代以3种方式产生新一代群体–直接从当前群体中选择–在选中的个体中进行交叉操作–在新群体上进行变异操作•遗传算法执行一种随机的、并行柱状的搜索，根据适应度函数发现好的假设2003.12.18机器学习-遗传算法作者：Mitchell译者：曾华军等讲者：陶晓鹏8表示假设•遗传算法中的假设常常被表示成二进制位串，这便于用变异和交叉遗传算子来操作•把if-then规则编码成位串–首先使用位串描述单个属性的值约束•比如考虑属性Outlook，它的值可以取以下3个中的任一个：Sunny、Overcast、Rain，因此一个明显的方法是使用一个长度为3的位串，每位对应一个可能值，若某位为1，表示这个属性可以取对应的值–多个属性约束的合取可以很容易地表示为对应位串的连接–整个规则表示可以通过把描述规则前件和后件的位串连接起来2003.12.18机器学习-遗传算法作者：Mitchell译者：曾华军等讲者：陶晓鹏9表示假设（2）•位串的特点–表示规则的位串对假设空间中的每个属性有一个子串，即使该属性不被规则的前件约束。–得到一个固定长度的规则位串表示，其中特定位置的子串描述对应特定属性的约束•规则集的表示：单个规则的位串表示连接起来•有必要让每个句法合法的位串表示一个有意义的假设•假设也可以用符号描述来表示，而不是位串，比如计算机程序2003.12.18机器学习-遗传算法作者：Mitchell译者：曾华军等讲者：陶晓鹏10遗传算子•遗传算法使用一系列算子来决定后代，算子对当前群体中选定的成员进行重组•表9-1列出了用来操作位串的典型遗传算法算子，它们是生物进化中的遗传过程的理想化形式•最常见的算子是交叉和变异•交叉：–从两个双亲串中通过复制选定位产生两个新的后代，每个后代的第i位是从它的某个双亲的第i位复制来的–双亲中的哪一个在第i位起作用，由另一个称为交叉掩码的位串决定：•单点交叉：前n位来自第一个双亲，余下的位来自第二个双亲•两点交叉：用一个双亲的中间片断替换第二个双亲的中间片断•均匀交叉：合并了从两个双亲以均匀概率抽取的位2003.12.18机器学习-遗传算法作者：Mitchell译者：曾华军等讲者：陶晓鹏11遗传算子（2）•变异：–从单一双亲产生后代，对位串产生随机的小变化，方法是选取一个位，然后取反–变异经常是在应用交叉之后•其他算子–使规则特化的算子–直接泛化2003.12.18机器学习-遗传算法作者：Mitchell译者：曾华军等讲者：陶晓鹏12适应度函数和假设选择•适应度函数定义了候选假设的排序准则–如果学习任务是分类的规则，那么适应度函数中会有一项用来评价每个规则对训练样例集合的分类精度，也可包含其他的准则，比如规则的复杂度和一般性•选择假设的概率计算方法–适应度比例选择（或称轮盘赌选择），选择某假设的概率是通过这个假设的适应度与当前群体中其他成员的适应度的比值得到的–锦标赛选择，先从当前群体中随机选取两个假设，再按照事先定义的概率p选择适应度较高的假设，按照概率1-p选择适应度较低的假设–排序选择，当前群体中的假设按适应度排序，某假设的概率与它在排序列表中的位置成比例，而不是与适应度成比例2003.12.18机器学习-遗传算法作者：Mitchell译者：曾华军等讲者：陶晓鹏13举例•遗传算法可以被看作是通用的最优化方法，它搜索一个巨大的候选假设空间，根据适应度函数查找表现最好的假设•遗传算法尽管不能保证发现最优的假设，但一般能够发现具有较高适应度的假设•遗传算法的广泛应用–电路布线–任务调度–函数逼近–选取人工神经网络的拓扑结构2003.12.18机器学习-遗传算法作者：Mitchell译者：曾华军等讲者：陶晓鹏14Gabil系统•Dejongetal.1993的Gabil系统：遗传算法在概念学习方面的应用•学习以命题规则的析取集合表示的布尔概念•在对几个概念学习问题的实验中发现，在泛化精度方面Gabil与其他学习算法大体相当•Gabil使用的算法就是表9-1描述的典型算法2003.12.18机器学习-遗传算法作者：Mitchell译者：曾华军等讲者：陶晓鹏15Gabil系统（2）•Gabil的具体实现–表示：每个假设对应一个命题规则的析取集，按照9.2.1节描述的方法编码–遗传算子：•变异：使用表9-2中的标准变异算子•交叉：表9-2中的两点交叉算子的一个扩展，这种方法保证了产生的位串表示的规则集是良定义的–适应度函数：每个规则集的适应度是根据它在训练数据上的分类精度计算的，Fitness(h)=(correct(h))22003.12.18机器学习-遗传算法作者：Mitchell译者：曾华军等讲者：陶晓鹏16Gabil系统的扩展•增加两个新算子–AddAlternative，它泛化对某个特定属性的约束，方法是把这个属性对应的子串中的一个0改为1，使用概率为0.01–DropCondition，把一个特定属性的所有位都替换为1，使用概率为0.60•两种使用新算子的方法–对每一代群体中的每个假设以同样的概率应用–对假设的位串进行扩展，使其包含另外两位以决定是否可以对该假设应用这两个新算子2003.12.18机器学习-遗传算法作者：Mitchell译者：曾华军等讲者：陶晓鹏17假设空间搜索•遗传算法采用一种随机化的柱状搜索来寻找最大适应度的假设，与前面章节的搜索算法有很大不同–梯度下降搜索从一个假设平滑移动到另一个非常相似的假设–遗传算法的移动可能非常突然，使用和双亲根本不同的后代替换双亲假设–遗传算法的搜索不太可能像梯度下降方法那样陷入局部最小值的问题•遗传算法应用中的一个难题：拥挤问题–拥挤：群体中某个体适应度大大高于其他个体，因此它迅速繁殖，以至于此个体和与它相似的个体占据了群体的绝大部分–拥挤降低了群体的多样性，从而减慢了进化的进程2003.12.18机器学习-遗传算法作者：Mitchell译者：曾华军等讲者：陶晓鹏18假设空间搜索（2）•降低拥挤的策略–使用锦标赛选择或排序选择，而不用适应度比例轮盘赌选择–适应度共享，根据群体中与某个体相似的个体数量，减小该个体的适应度–对可重组生成后代的个体种类进行限制，比如受到生物进化的启示•通过只允许最相似的个体重组，可以在群体中促成相似的个体聚类，形成亚种•按空间分布个体，只允许相邻的个体重组2003.12.18机器学习-遗传算法作者：Mitchell译者：曾华军等讲者：陶晓鹏19群体进化和模式理论•模式理论（Holland1975）提供了一种用数学方法刻画遗传算法中群体进化的过程•模式是由若干0、1和*组成的任意串，*表示任意符号•模式理论根据每个模式的实例数量来刻画遗传算法中群体的进化–令m(s,t)表示群体中的模式s在时间t的实例数量–模式理论根据m(s,t)和模式、群体及其他属性来描述m(s,t+1)的期望值2003.12.18机器学习-遗传算法作者：Mitchell译者：曾华军等讲者：陶晓鹏20群体进化和模式理论（2）•遗传算法中群体的进化依赖于几个步骤，即选择、重组和变异。–符号表示：•f(h)表示位串个体h的适应度•n为群体中个体的总数量•表示在时间t群体中所有个体的平均适应度•表示在时间t群体中模式s的实例的平均适应度•表示个体h既是模式s的一个代表，又是时间t群体的一个成员)(tf),(ˆtsutpsh2003.12.18机器学习-遗传算法作者：Mitchell译者：曾华军等讲者：陶晓鹏21群体进化和模式理论（3）–E(m(s,t+1))的推导，仅考虑选择的情况–式子9.3表明，在t+1代中，模式s的实例期望数量与这个模式的实例在时间t内的平均适应度成正比，与群体的所有成员的平均适应度成反比，适应度高的模式的影响力会随着时间增加niihfhfh1)()()Pr(),()(),(ˆtsmhftsutpsh)(),(),(ˆ)()()Pr(