2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 1
机器学习第 9章 遗传算法
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 2
概述
遗传算法是一种大致基于模拟进化的学习方法
假设通常被描述为二进制位串，也可以是符号表达式或计算机程序
搜索合适的假设从若干初始假设的群体或集合开始
当前群体的成员通过模拟生物进化的方式来产生下一代群体，比如随机变异和交叉
每一步，根据给定的适应度评估当前群体中的假设，而后使用概率方法选出适应度最高的假设作为产生下一代的种子
遗传算法已被成功用于多种学习任务和最优化问题中，比如学习机器人控制的规则集和优化人工神经网络的拓扑结构和学习参数
本章主要介绍了基于位串描述假设的遗传算法和基于计算机程序描述假设的遗传编程
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 3
动机
遗传算法（ GA）是一种受生物进化启发的学习方法，它不再是从一般到特殊或从简单到复杂地搜索假设，而是通过变异和重组当前已知的最好假设来生成后续的假设
每一步，更新被称为当前群体的一组假设，方法是使用当前适应度最高的假设的后代替代群体的某个部分
这个过程形成了假设的生成测试的柱状搜索，
其中若干个最佳当前假设的变体最有可能在下一步被考虑
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 4
动机（ 2）
遗传算法的普及和发展得益于下面的因素
– 在生物系统中，进化被认为是一种成功的自适应方法，具有很好的健壮性
– 遗传算法搜索的假设空间中，假设的各个部分相互作用，每一部分对总的假设适应度的影响难以建模
– 遗传算法易于并行化
本章内容安排
– 描述了遗传算法，举例演示了它的用法，分析了它搜索的空间的特性
– 描述了遗传算法的一个变体：遗传编程，这个方法中，整个计算机程序向着某个适应度准则进化
– 介绍了一些有关生物进化的课题（遗传算法和遗传编程是进化计算领域中的两种普遍方法），比如鲍德温效应，它描述了个体的学习能力与整个群体进化速度之间的相互作用
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 5
遗传算法
遗传算法研究的问题是搜索候选假设空间并确定最佳假设
最佳假设被定义为使适应度最优的假设
– 适应度是为当前问题预先定义的数字度量，比如：
如果学习任务是在给定一个未知函数的输入输出训练样例后逼近这个函数，适应度可被定义为假设在训练数据上的精度
如果是学习下国际象棋的策略，适应度可被定义为该个体在当前群体中与其他个体对弈的获胜率
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 6
遗传算法（ 2）
遗传算法具有以下的共同结构：
– 算法迭代更新一个假设池，这个假设池称为群体
– 在每一次迭代中，根据适应度评估群体中的所有成员，然后用概率方法选取适应度最高的个体产生新一代群体
– 在被选中的个体中，一部分保持原样地进入下一代群体，其他被用作产生后代个体的基础，其中应用交叉和变异这样的遗传方法
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 7
表 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中返回适应度最高的假设
pj j
ii
hF itne ss
hF itne ssh
1
)(
)()P r(
)(max hFitnessh
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 8
遗传算法（ 3）
算法的每一次迭代以 3种方式产生新一代群体
– 直接从当前群体中选择
– 在选中的个体中进行交叉操作
– 在新群体上进行变异操作
遗传算法执行一种随机的、并行柱状的搜索，根据适应度函数发现好的假设
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 9
表示假设
遗传算法中的假设常常被表示成二进制位串，这便于用变异和交叉遗传算子来操作
把 if-then规则编码成位串
– 首先使用位串描述单个属性的值约束
比如考虑属性 Outlook，它的值可以取以下 3个中的任一个：
Sunny,Overcast,Rain，因此一个明显的方法是使用一个长度为
3的位串，每位对应一个可能值，若某位为 1，表示这个属性可以取对应的值
– 多个属性约束的合取可以很容易地表示为对应位串的连接
– 整个规则表示可以通过把描述规则前件和后件的位串连接起来
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 10
表示假设（ 2）
位串的特点
– 表示规则的位串对假设空间中的每个属性有一个子串，即使该属性不被规则的前件约束。
– 得到一个固定长度的规则位串表示，其中特定位置的子串描述对应特定属性的约束
规则集的表示：单个规则的位串表示连接起来
有必要让每个句法合法的位串表示一个有意义的假设
假设也可以用符号描述来表示，而不是位串，
比如计算机程序
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 11
遗传算子
遗传算法使用一系列算子来决定后代，算子对当前群体中选定的成员进行重组
表 9-1列出了用来操作位串的典型遗传算法算子，它们是生物进化中的遗传过程的理想化形式
最常见的算子是交叉和变异
交叉：
– 从两个双亲串中通过复制选定位产生两个新的后代，每个后代的第 i位是从它的某个双亲的第 i位复制来的
– 双亲中的哪一个在第 i位起作用，由另一个称为交叉掩码的位串决定：
单点交叉：前 n位来自第一个双亲，余下的位来自第二个双亲
两点交叉：用一个双亲的中间片断替换第二个双亲的中间片断
均匀交叉：合并了从两个双亲以均匀概率抽取的位
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 12
遗传算子（ 2）
变异：
– 从单一双亲产生后代，对位串产生随机的小变化，方法是选取一个位，然后取反
– 变异经常是在应用交叉之后
其他算子
– 使规则特化的算子
– 直接泛化
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 13
适应度函数和假设选择
适应度函数定义了候选假设的排序准则
– 如果学习任务是分类的规则，那么适应度函数中会有一项用来评价每个规则对训练样例集合的分类精度，也可包含其他的准则，比如规则的复杂度和一般性
选择假设的概率计算方法
– 适应度比例选择（或称轮盘赌选择），选择某假设的概率是通过这个假设的适应度与当前群体中其他成员的适应度的比值得到的
– 锦标赛选择，先从当前群体中随机选取两个假设，再按照事先定义的概率 p选择适应度较高的假设，按照概率 1-p选择适应度较低的假设
– 排序选择，当前群体中的假设按适应度排序，某假设的概率与它在排序列表中的位置成比例，而不是与适应度成比例
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 14
举例
遗传算法可以被看作是通用的最优化方法，它搜索一个巨大的候选假设空间，根据适应度函数查找表现最好的假设
遗传算法尽管不能保证发现最优的假设，但一般能够发现具有较高适应度的假设
遗传算法的广泛应用
– 电路布线
– 任务调度
– 函数逼近
– 选取人工神经网络的拓扑结构
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 15
Gabil系统
Dejong et al.1993的 Gabil系统：遗传算法在概念学习方面的应用
学习以命题规则的析取集合表示的布尔概念
在对几个概念学习问题的实验中发现，在泛化精度方面 Gabil与其他学习算法大体相当
Gabil使用的算法就是表 9-1描述的典型算法
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 16
Gabil系统（ 2）
Gabil的具体实现
– 表示：每个假设对应一个命题规则的析取集，按照
9.2.1节描述的方法编码
– 遗传算子：
变异：使用表 9-2中的标准变异算子
交叉：表 9-2中的两点交叉算子的一个扩展，这种方法保证了产生的位串表示的规则集是良定义的
– 适应度函数：每个规则集的适应度是根据它在训练数据上的分类精度计算的,Fitness(h)=(correct(h))2
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 17
Gabil系统的扩展
增加两个新算子
– AddAlternative，它泛化对某个特定属性的约束，方法是把这个属性对应的子串中的一个 0改为 1，使用概率为 0.01
– DropCondition，把一个特定属性的所有位都替换为
1，使用概率为 0.60
两种使用新算子的方法
– 对每一代群体中的每个假设以同样的概率应用
– 对假设的位串进行扩展，使其包含另外两位以决定是否可以对该假设应用这两个新算子
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 18
假设空间搜索
遗传算法采用一种随机化的柱状搜索来寻找最大适应度的假设，与前面章节的搜索算法有很大不同
– 梯度下降搜索从一个假设平滑移动到另一个非常相似的假设
– 遗传算法的移动可能非常突然，使用和双亲根本不同的后代替换双亲假设
– 遗传算法的搜索不太可能像梯度下降方法那样陷入局部最小值的问题
遗传算法应用中的一个难题：拥挤问题
– 拥挤：群体中某个体适应度大大高于其他个体，因此它迅速繁殖，以至于此个体和与它相似的个体占据了群体的绝大部分
– 拥挤降低了群体的多样性，从而减慢了进化的进程
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 19
假设空间搜索（ 2）
降低拥挤的策略
– 使用锦标赛选择或排序选择，而不用适应度比例轮盘赌选择
– 适应度共享，根据群体中与某个体相似的个体数量，
减小该个体的适应度
– 对可重组生成后代的个体种类进行限制，比如受到生物进化的启示
通过只允许最相似的个体重组，可以在群体中促成相似的个体聚类，形成亚种
按空间分布个体，只允许相邻的个体重组
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 20
群体进化和模式理论
模式理论（ Holland1975）提供了一种用数学方法刻画遗传算法中群体进化的过程
模式是由若干 0,1和 *组成的任意串,*表示任意符号
模式理论根据每个模式的实例数量来刻画遗传算法中群体的进化
– 令 m(s,t)表示群体中的模式 s在时间 t的实例数量
– 模式理论根据 m(s,t)和模式、群体及其他属性来描述
m(s,t+1)的期望值
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 21
群体进化和模式理论（ 2）
遗传算法中群体的进化依赖于几个步骤，
即选择、重组和变异。
– 符号表示：
f(h)表示位串个体 h的适应度
n为群体中个体的总数量
表示在时间 t群体中所有个体的平均适应度
表示在时间 t群体中模式 s的实例的平均适应度
表示个体 h既是模式 s的一个代表，又是时间 t群体的一个成员
)(tf
),(? tsu
tpsh
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 22
群体进化和模式理论（ 3）
– E(m(s,t+1))的推导，仅考虑选择的情况
– 式子 9.3表明，在 t+1代中，模式 s的实例期望数量与这个模式的实例在时间 t内的平均适应度成正比，与群体的所有成员的平均适应度成反比，适应度高的模式的影响力会随着时间增加
ni ihf
hfh
1
)(
)()Pr(
),(
)(
),(? tsm
hf
tsu tpsh
)( ),(),(?)( )()P r ( tfn tsmtsutfn hfsh tpsh
)( ),(),(?)Pr ()]1,([ tf tsmtsushntsmE
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 23
群体进化和模式理论（ 4）
– 同时考虑交叉和变异，仅考虑单点交叉和可能造成的负面影响最左一项描述了选择步的影响，中间一项描述了单点交叉算子的影响，最后一项描述了代表模式 s的任意个体在应用了变异算子后还代表 s的概率
模式理论不完备的是：无法考虑交叉和变异的正面影响
其他一些新的理论分析：基于马尔可夫链模型和统计力学模型
)()1(1)(1),()( ),(?)]1,([ sopl sdptsmtf tsutsmE mc
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 24
遗传编程
遗传编程是进化计算的一种形式，其中进化群体中的个体是计算机程序而不是位串
遗传编程中的程序一般被表示为程序的解析树，每个函数调用被表示为树的一个节点，函数的参数通过它的子节点给出
遗传编程算法维护多个个体组成的群体，在每一步迭代中，它使用选择、交叉、变异产生新一代个体
群体中某个体程序的适应度一般通过在训练数据上执行这个程序来决定
交叉操作：在一个双亲程序中随机选择一个子树，然后用另一个双亲的子树替代这个子树
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 25
遗传编程举例
学习堆砌图 9-3所示的子块的算法（ Koza1992）
– 开发一个通用的算法来把字块堆叠成单个栈，拼出单词，无论这些字块初始的结构如何
– 可执行的动作是每次只允许移动一个字块，栈中最上面的字块可以被移到桌面上，或者桌面上的字块移到栈顶
原子函数包含 3个端点参数
– CS，当前栈，即栈顶字块的名字，栈空时为 F
– TB，最上面的正确字块，即该字块和它以下的字块均为正确顺序的字块
– NN，下一个所需字块，即为了拼成单词,universal”，栈内紧邻 TB之上的所需字块的名字，当不再需要时为 F
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 26
遗传编程举例（ 2）
原子函数
– MS x：移动到栈，如果字块 x在桌面上，把 x移动到栈顶，并且返回 T；否则什么也不做，返回 F
– MT x：移动到桌面，如果字块 x是在栈中某个位置，把栈顶的字块移动到桌面，并且返回 T；否则返回 F
– EQ x y：如果 x等于 y，返回 T；否则 F
– NOT x：如果 x=F，返回 T；否则 F
– DU x y：反复执行表达式 x直到表达式 y返回 T
Koza提供了 166个训练问题，表示不同的初始字块结构，
任意给定程序的适应度就是它解决的训练问题的数量
群体被初始化为 300个随机程序的集合，经过 10代后，
系统发现了下面的程序解决所有的 166个问题
(EQ (DU (MT CS) (NOT CS)) (DU (MS NN) (NOT NN)))
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 27
遗传编程说明
遗传编程把遗传算法扩展到对完整的计算机程序的进化
尽管遗传算法要搜索巨大的假设空间，但已经证实相当数量的应用中遗传编程产生了很好的结果
遗传编程在更复杂的任务中的应用
– 电子滤波电路的设计
– 蛋白质分子片断的分析
在大多数情况下，表示方法的选择和适应度函数的选择对遗传编程的性能是至关重要的，一个活跃的研究领域是自动发现和合并子程序，改善最初的原子函数集合，从而允许系统动态地改变用以构建个体的原子
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 28
进化和学习模型
有关进化系统的一个有趣问题：单一个体生命期间的学习与整个物种较长时期内由进化促成的学习，它们的关系是什么？
拉马克进化
– 拉马克在 19世纪末提出，多代的进化直接受到个别生物体在它们生命期间的经验的影响
– 目前的科学证据不支持拉马克模型
– 但近来的计算机研究表明，拉马克过程有时可以提高计算机遗传算法的效率
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 29
进化和学习模型（ 2）
鲍德温效应
– 通过个体学习改变进化进程的机制
– 基于以下现象
如果一个物种在一个变化的环境中进化，那么进化的压力会支持有学习能力的个体，这种学习能力可以使个体在其生命期间执行一种小的局部搜索，以最大化它的适应度，
相反，不学习的个体的适应度完全取决于它的遗传结构，
会处于相对劣势
具备学习能力的个体可以通过学习克服遗传代码中的“丢失的”或“并非最优的”特性，从而支持更加多样化的基因池，然后促进适应性更加快速地进化
– 提供了一种间接的机制，使个体的学习可以正面影响进化速度
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 30
进化和学习模型（ 3）
人们一直努力开发研究鲍德温效应的计算模型
– Hinton & Nowlan1987对一个简单神经网络的群体进行试验
– 在一个网络个体的“生命期”间，它的一些权值是固定的，而其他权是可被训练的
– 在群体进化初期的各代中，具有很多可训练权值的个体占据较大的比例
– 随着进化的进行，群体向着遗传给定权值和较少依赖个体学习权值的方向进化，正确的固定权值的数量趋于增长
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 31
并行遗传算法
遗传算法很自然地适合并行实现
粗粒度并行方法
– 把群体细分成相对独立的个体群，称为类属，然后为每个类属分配一个不同的计算节点，在每个节点进行标准的 GA搜索
– 类属之间的通信和交叉发生的频率与类属内相比较低，类属之间的交换通过迁移来进行，也就是某些个体从一个类属复制或交换到其他类属
– 这个过程模拟了以下的生物进化方式，即自然界中异体受精可能发生在分离的物种子群体之间
– 这种方法的一个好处是减少了非并行 GA经常碰到的拥挤问题
细粒度并行方法
– 给每个个体分配一个处理器，然后相邻的个体间发生重组
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 32
小结
遗传算法用一种随机化的并行爬山搜索来发现使预先定义的适应度函数最优的假设
遗传算法基于对生物进化的模拟，维护一个由竞争假设组成的多样化群体，在每一次迭代中，选出群体中适应度最高的成员来产生后代，替代群体中适应度最差的成员
遗传算法阐明了如何把学习过程看成最优化过程的一个特例，学习任务就是根据预先定义的适应度函数发现最优假设
遗传编程是遗传算法的变体，在遗传编程中，被操作的假设是计算机程序而不是位串
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 33
补充读物
在计算机科学发展的早期，人们就开始探索基于进化的计算方法（ Box1957,Bledsoe1964）
Rechenberg1965,1973,Schwefel1975,1977,1995开发的进化策略用来优化工程设计中的数字参数
Folgel & Owens & Walsh1966开发了进化编程，作为进化有限状态机的一种方法
Koza1992介绍了遗传编程，把遗传算法的搜索策略应用到由计算机程序组成的假设中
K,Dejong和他的学生开发了使用 GA学习规则集的方法，
每个规则集是竞争假设组成的群体的一个成员
Holland和他的学生设定每个规则是群体的一个成员，
群体本身是一个规则集
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 34
补充读物（ 2）
Mitchell1996和 Goldberg1986给出了有关遗传算法的两本教材
Koza1992关于遗传编程的专著是对遗传算法扩展到操作计算机程序的标准参考书
会议
– 遗传算法国际会议（主要会议）
– 自适应行为仿真会议
– 人工神经网络和遗传算法国际会议
– IEEE进化计算国际会议
杂志
– 进化计算杂志
– 机器学习
机器学习第 9章 遗传算法
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 2
概述
遗传算法是一种大致基于模拟进化的学习方法
假设通常被描述为二进制位串，也可以是符号表达式或计算机程序
搜索合适的假设从若干初始假设的群体或集合开始
当前群体的成员通过模拟生物进化的方式来产生下一代群体，比如随机变异和交叉
每一步，根据给定的适应度评估当前群体中的假设，而后使用概率方法选出适应度最高的假设作为产生下一代的种子
遗传算法已被成功用于多种学习任务和最优化问题中，比如学习机器人控制的规则集和优化人工神经网络的拓扑结构和学习参数
本章主要介绍了基于位串描述假设的遗传算法和基于计算机程序描述假设的遗传编程
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 3
动机
遗传算法（ GA）是一种受生物进化启发的学习方法，它不再是从一般到特殊或从简单到复杂地搜索假设，而是通过变异和重组当前已知的最好假设来生成后续的假设
每一步，更新被称为当前群体的一组假设，方法是使用当前适应度最高的假设的后代替代群体的某个部分
这个过程形成了假设的生成测试的柱状搜索，
其中若干个最佳当前假设的变体最有可能在下一步被考虑
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 4
动机（ 2）
遗传算法的普及和发展得益于下面的因素
– 在生物系统中，进化被认为是一种成功的自适应方法，具有很好的健壮性
– 遗传算法搜索的假设空间中，假设的各个部分相互作用，每一部分对总的假设适应度的影响难以建模
– 遗传算法易于并行化
本章内容安排
– 描述了遗传算法，举例演示了它的用法，分析了它搜索的空间的特性
– 描述了遗传算法的一个变体：遗传编程，这个方法中，整个计算机程序向着某个适应度准则进化
– 介绍了一些有关生物进化的课题（遗传算法和遗传编程是进化计算领域中的两种普遍方法），比如鲍德温效应，它描述了个体的学习能力与整个群体进化速度之间的相互作用
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 5
遗传算法
遗传算法研究的问题是搜索候选假设空间并确定最佳假设
最佳假设被定义为使适应度最优的假设
– 适应度是为当前问题预先定义的数字度量，比如：
如果学习任务是在给定一个未知函数的输入输出训练样例后逼近这个函数，适应度可被定义为假设在训练数据上的精度
如果是学习下国际象棋的策略，适应度可被定义为该个体在当前群体中与其他个体对弈的获胜率
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 6
遗传算法（ 2）
遗传算法具有以下的共同结构：
– 算法迭代更新一个假设池，这个假设池称为群体
– 在每一次迭代中，根据适应度评估群体中的所有成员，然后用概率方法选取适应度最高的个体产生新一代群体
– 在被选中的个体中，一部分保持原样地进入下一代群体，其他被用作产生后代个体的基础，其中应用交叉和变异这样的遗传方法
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 7
表 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中返回适应度最高的假设
pj j
ii
hF itne ss
hF itne ssh
1
)(
)()P r(
)(max hFitnessh
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 8
遗传算法（ 3）
算法的每一次迭代以 3种方式产生新一代群体
– 直接从当前群体中选择
– 在选中的个体中进行交叉操作
– 在新群体上进行变异操作
遗传算法执行一种随机的、并行柱状的搜索，根据适应度函数发现好的假设
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 9
表示假设
遗传算法中的假设常常被表示成二进制位串，这便于用变异和交叉遗传算子来操作
把 if-then规则编码成位串
– 首先使用位串描述单个属性的值约束
比如考虑属性 Outlook，它的值可以取以下 3个中的任一个：
Sunny,Overcast,Rain，因此一个明显的方法是使用一个长度为
3的位串，每位对应一个可能值，若某位为 1，表示这个属性可以取对应的值
– 多个属性约束的合取可以很容易地表示为对应位串的连接
– 整个规则表示可以通过把描述规则前件和后件的位串连接起来
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 10
表示假设（ 2）
位串的特点
– 表示规则的位串对假设空间中的每个属性有一个子串，即使该属性不被规则的前件约束。
– 得到一个固定长度的规则位串表示，其中特定位置的子串描述对应特定属性的约束
规则集的表示：单个规则的位串表示连接起来
有必要让每个句法合法的位串表示一个有意义的假设
假设也可以用符号描述来表示，而不是位串，
比如计算机程序
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 11
遗传算子
遗传算法使用一系列算子来决定后代，算子对当前群体中选定的成员进行重组
表 9-1列出了用来操作位串的典型遗传算法算子，它们是生物进化中的遗传过程的理想化形式
最常见的算子是交叉和变异
交叉：
– 从两个双亲串中通过复制选定位产生两个新的后代，每个后代的第 i位是从它的某个双亲的第 i位复制来的
– 双亲中的哪一个在第 i位起作用，由另一个称为交叉掩码的位串决定：
单点交叉：前 n位来自第一个双亲，余下的位来自第二个双亲
两点交叉：用一个双亲的中间片断替换第二个双亲的中间片断
均匀交叉：合并了从两个双亲以均匀概率抽取的位
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 12
遗传算子（ 2）
变异：
– 从单一双亲产生后代，对位串产生随机的小变化，方法是选取一个位，然后取反
– 变异经常是在应用交叉之后
其他算子
– 使规则特化的算子
– 直接泛化
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 13
适应度函数和假设选择
适应度函数定义了候选假设的排序准则
– 如果学习任务是分类的规则，那么适应度函数中会有一项用来评价每个规则对训练样例集合的分类精度，也可包含其他的准则，比如规则的复杂度和一般性
选择假设的概率计算方法
– 适应度比例选择（或称轮盘赌选择），选择某假设的概率是通过这个假设的适应度与当前群体中其他成员的适应度的比值得到的
– 锦标赛选择，先从当前群体中随机选取两个假设，再按照事先定义的概率 p选择适应度较高的假设，按照概率 1-p选择适应度较低的假设
– 排序选择，当前群体中的假设按适应度排序，某假设的概率与它在排序列表中的位置成比例，而不是与适应度成比例
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 14
举例
遗传算法可以被看作是通用的最优化方法，它搜索一个巨大的候选假设空间，根据适应度函数查找表现最好的假设
遗传算法尽管不能保证发现最优的假设，但一般能够发现具有较高适应度的假设
遗传算法的广泛应用
– 电路布线
– 任务调度
– 函数逼近
– 选取人工神经网络的拓扑结构
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 15
Gabil系统
Dejong et al.1993的 Gabil系统：遗传算法在概念学习方面的应用
学习以命题规则的析取集合表示的布尔概念
在对几个概念学习问题的实验中发现，在泛化精度方面 Gabil与其他学习算法大体相当
Gabil使用的算法就是表 9-1描述的典型算法
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 16
Gabil系统（ 2）
Gabil的具体实现
– 表示：每个假设对应一个命题规则的析取集，按照
9.2.1节描述的方法编码
– 遗传算子：
变异：使用表 9-2中的标准变异算子
交叉：表 9-2中的两点交叉算子的一个扩展，这种方法保证了产生的位串表示的规则集是良定义的
– 适应度函数：每个规则集的适应度是根据它在训练数据上的分类精度计算的,Fitness(h)=(correct(h))2
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 17
Gabil系统的扩展
增加两个新算子
– AddAlternative，它泛化对某个特定属性的约束，方法是把这个属性对应的子串中的一个 0改为 1，使用概率为 0.01
– DropCondition，把一个特定属性的所有位都替换为
1，使用概率为 0.60
两种使用新算子的方法
– 对每一代群体中的每个假设以同样的概率应用
– 对假设的位串进行扩展，使其包含另外两位以决定是否可以对该假设应用这两个新算子
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 18
假设空间搜索
遗传算法采用一种随机化的柱状搜索来寻找最大适应度的假设，与前面章节的搜索算法有很大不同
– 梯度下降搜索从一个假设平滑移动到另一个非常相似的假设
– 遗传算法的移动可能非常突然，使用和双亲根本不同的后代替换双亲假设
– 遗传算法的搜索不太可能像梯度下降方法那样陷入局部最小值的问题
遗传算法应用中的一个难题：拥挤问题
– 拥挤：群体中某个体适应度大大高于其他个体，因此它迅速繁殖，以至于此个体和与它相似的个体占据了群体的绝大部分
– 拥挤降低了群体的多样性，从而减慢了进化的进程
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 19
假设空间搜索（ 2）
降低拥挤的策略
– 使用锦标赛选择或排序选择，而不用适应度比例轮盘赌选择
– 适应度共享，根据群体中与某个体相似的个体数量，
减小该个体的适应度
– 对可重组生成后代的个体种类进行限制，比如受到生物进化的启示
通过只允许最相似的个体重组，可以在群体中促成相似的个体聚类，形成亚种
按空间分布个体，只允许相邻的个体重组
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 20
群体进化和模式理论
模式理论（ Holland1975）提供了一种用数学方法刻画遗传算法中群体进化的过程
模式是由若干 0,1和 *组成的任意串,*表示任意符号
模式理论根据每个模式的实例数量来刻画遗传算法中群体的进化
– 令 m(s,t)表示群体中的模式 s在时间 t的实例数量
– 模式理论根据 m(s,t)和模式、群体及其他属性来描述
m(s,t+1)的期望值
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 21
群体进化和模式理论（ 2）
遗传算法中群体的进化依赖于几个步骤，
即选择、重组和变异。
– 符号表示：
f(h)表示位串个体 h的适应度
n为群体中个体的总数量
表示在时间 t群体中所有个体的平均适应度
表示在时间 t群体中模式 s的实例的平均适应度
表示个体 h既是模式 s的一个代表，又是时间 t群体的一个成员
)(tf
),(? tsu
tpsh
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 22
群体进化和模式理论（ 3）
– E(m(s,t+1))的推导，仅考虑选择的情况
– 式子 9.3表明，在 t+1代中，模式 s的实例期望数量与这个模式的实例在时间 t内的平均适应度成正比，与群体的所有成员的平均适应度成反比，适应度高的模式的影响力会随着时间增加
ni ihf
hfh
1
)(
)()Pr(
),(
)(
),(? tsm
hf
tsu tpsh
)( ),(),(?)( )()P r ( tfn tsmtsutfn hfsh tpsh
)( ),(),(?)Pr ()]1,([ tf tsmtsushntsmE
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 23
群体进化和模式理论（ 4）
– 同时考虑交叉和变异，仅考虑单点交叉和可能造成的负面影响最左一项描述了选择步的影响，中间一项描述了单点交叉算子的影响，最后一项描述了代表模式 s的任意个体在应用了变异算子后还代表 s的概率
模式理论不完备的是：无法考虑交叉和变异的正面影响
其他一些新的理论分析：基于马尔可夫链模型和统计力学模型
)()1(1)(1),()( ),(?)]1,([ sopl sdptsmtf tsutsmE mc
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 24
遗传编程
遗传编程是进化计算的一种形式，其中进化群体中的个体是计算机程序而不是位串
遗传编程中的程序一般被表示为程序的解析树，每个函数调用被表示为树的一个节点，函数的参数通过它的子节点给出
遗传编程算法维护多个个体组成的群体，在每一步迭代中，它使用选择、交叉、变异产生新一代个体
群体中某个体程序的适应度一般通过在训练数据上执行这个程序来决定
交叉操作：在一个双亲程序中随机选择一个子树，然后用另一个双亲的子树替代这个子树
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 25
遗传编程举例
学习堆砌图 9-3所示的子块的算法（ Koza1992）
– 开发一个通用的算法来把字块堆叠成单个栈，拼出单词，无论这些字块初始的结构如何
– 可执行的动作是每次只允许移动一个字块，栈中最上面的字块可以被移到桌面上，或者桌面上的字块移到栈顶
原子函数包含 3个端点参数
– CS，当前栈，即栈顶字块的名字，栈空时为 F
– TB，最上面的正确字块，即该字块和它以下的字块均为正确顺序的字块
– NN，下一个所需字块，即为了拼成单词,universal”，栈内紧邻 TB之上的所需字块的名字，当不再需要时为 F
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 26
遗传编程举例（ 2）
原子函数
– MS x：移动到栈，如果字块 x在桌面上，把 x移动到栈顶，并且返回 T；否则什么也不做，返回 F
– MT x：移动到桌面，如果字块 x是在栈中某个位置，把栈顶的字块移动到桌面，并且返回 T；否则返回 F
– EQ x y：如果 x等于 y，返回 T；否则 F
– NOT x：如果 x=F，返回 T；否则 F
– DU x y：反复执行表达式 x直到表达式 y返回 T
Koza提供了 166个训练问题，表示不同的初始字块结构，
任意给定程序的适应度就是它解决的训练问题的数量
群体被初始化为 300个随机程序的集合，经过 10代后，
系统发现了下面的程序解决所有的 166个问题
(EQ (DU (MT CS) (NOT CS)) (DU (MS NN) (NOT NN)))
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 27
遗传编程说明
遗传编程把遗传算法扩展到对完整的计算机程序的进化
尽管遗传算法要搜索巨大的假设空间，但已经证实相当数量的应用中遗传编程产生了很好的结果
遗传编程在更复杂的任务中的应用
– 电子滤波电路的设计
– 蛋白质分子片断的分析
在大多数情况下，表示方法的选择和适应度函数的选择对遗传编程的性能是至关重要的，一个活跃的研究领域是自动发现和合并子程序，改善最初的原子函数集合，从而允许系统动态地改变用以构建个体的原子
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 28
进化和学习模型
有关进化系统的一个有趣问题：单一个体生命期间的学习与整个物种较长时期内由进化促成的学习，它们的关系是什么？
拉马克进化
– 拉马克在 19世纪末提出，多代的进化直接受到个别生物体在它们生命期间的经验的影响
– 目前的科学证据不支持拉马克模型
– 但近来的计算机研究表明，拉马克过程有时可以提高计算机遗传算法的效率
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 29
进化和学习模型（ 2）
鲍德温效应
– 通过个体学习改变进化进程的机制
– 基于以下现象
如果一个物种在一个变化的环境中进化，那么进化的压力会支持有学习能力的个体，这种学习能力可以使个体在其生命期间执行一种小的局部搜索，以最大化它的适应度，
相反，不学习的个体的适应度完全取决于它的遗传结构，
会处于相对劣势
具备学习能力的个体可以通过学习克服遗传代码中的“丢失的”或“并非最优的”特性，从而支持更加多样化的基因池，然后促进适应性更加快速地进化
– 提供了一种间接的机制，使个体的学习可以正面影响进化速度
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 30
进化和学习模型（ 3）
人们一直努力开发研究鲍德温效应的计算模型
– Hinton & Nowlan1987对一个简单神经网络的群体进行试验
– 在一个网络个体的“生命期”间，它的一些权值是固定的，而其他权是可被训练的
– 在群体进化初期的各代中，具有很多可训练权值的个体占据较大的比例
– 随着进化的进行，群体向着遗传给定权值和较少依赖个体学习权值的方向进化，正确的固定权值的数量趋于增长
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 31
并行遗传算法
遗传算法很自然地适合并行实现
粗粒度并行方法
– 把群体细分成相对独立的个体群，称为类属，然后为每个类属分配一个不同的计算节点，在每个节点进行标准的 GA搜索
– 类属之间的通信和交叉发生的频率与类属内相比较低，类属之间的交换通过迁移来进行，也就是某些个体从一个类属复制或交换到其他类属
– 这个过程模拟了以下的生物进化方式，即自然界中异体受精可能发生在分离的物种子群体之间
– 这种方法的一个好处是减少了非并行 GA经常碰到的拥挤问题
细粒度并行方法
– 给每个个体分配一个处理器，然后相邻的个体间发生重组
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 32
小结
遗传算法用一种随机化的并行爬山搜索来发现使预先定义的适应度函数最优的假设
遗传算法基于对生物进化的模拟，维护一个由竞争假设组成的多样化群体，在每一次迭代中，选出群体中适应度最高的成员来产生后代，替代群体中适应度最差的成员
遗传算法阐明了如何把学习过程看成最优化过程的一个特例，学习任务就是根据预先定义的适应度函数发现最优假设
遗传编程是遗传算法的变体，在遗传编程中，被操作的假设是计算机程序而不是位串
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 33
补充读物
在计算机科学发展的早期，人们就开始探索基于进化的计算方法（ Box1957,Bledsoe1964）
Rechenberg1965,1973,Schwefel1975,1977,1995开发的进化策略用来优化工程设计中的数字参数
Folgel & Owens & Walsh1966开发了进化编程，作为进化有限状态机的一种方法
Koza1992介绍了遗传编程，把遗传算法的搜索策略应用到由计算机程序组成的假设中
K,Dejong和他的学生开发了使用 GA学习规则集的方法，
每个规则集是竞争假设组成的群体的一个成员
Holland和他的学生设定每个规则是群体的一个成员，
群体本身是一个规则集
2003.12.18 机器学习 -遗传算法 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 34
补充读物（ 2）
Mitchell1996和 Goldberg1986给出了有关遗传算法的两本教材
Koza1992关于遗传编程的专著是对遗传算法扩展到操作计算机程序的标准参考书
会议
– 遗传算法国际会议（主要会议）
– 自适应行为仿真会议
– 人工神经网络和遗传算法国际会议
– IEEE进化计算国际会议
杂志
– 进化计算杂志
– 机器学习
