2009-8-20 史忠植 高级人工智能 1
第十一章 进化计算史忠植中科院计算所
2009-8-20 史忠植 高级人工智能 2
内容
11.1 概述
11.2 进化系统理论的形式模型
11.3 达尔文进化算法
11.4 分类器系统
11.5 桶链算法
11.6 遗传算法
11.7 并行遗传算法
11.8 分类器系统 Boole
11.9 规则发现系统
11.10 进化策略
11.11 进化程序设计
2009-8-20 史忠植 高级人工智能 3
11.1 概述遗传算法思想来源于生物进化过程,它是基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的搜索算法 (以字符串表示状态空间 )。遗传算法用概率搜索过程在该状态空间中搜索，产生新的样本。
2009-8-20 史忠植 高级人工智能 4
发展历史遗传算法的发展历史：
1965年,Holland首次提出了人工遗传操作的重要性，并把这些应用于自然系统和人工系统中。
1967年,Bagley在他的论文中首次提出了遗传算法这一术语，并讨论了遗传算法在自动博弈中的应用。
1970年,Cavicchio把遗传算法应用于模式识别中。第一个把遗传算法应用于函数优化的是 Hollstien。
2009-8-20 史忠植 高级人工智能 5
发展历史
1975年是遗传算法研究的历史上十分重要的一年。
这一年,Holland出版了他的著名专著《自然系统和人工系统的适应性,该书系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论（ schemata theory），
该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。
同年,DeJong完成了他的重要论文《遗传自适应系统的行为分析》。他在该论文中所做的研究工作可看作是遗传算法发展过程中的一个里程碑，这是因为他把 Holland的模式理论与他的计算使用结合起来。
2009-8-20 史忠植 高级人工智能 6
发展历史
1989 Goldberg对遗传算法从理论上，方法上和应用上作了系统的总结,
2009-8-20 史忠植 高级人工智能 7
特点特点：
通用
鲁棒
次优解、满意解遗传算法能解决的问题：
优化
NP完全
NP难
高度复杂的非线性问题
2009-8-20 史忠植 高级人工智能 8
遗传算法与自然进化的比较自然界染色体基因等位基因 (allele)
染色体位置 (locus)
基因型 (genotype)
表型 (phenotype)
遗传算法字符串字符，特征特征值字符串位置结构参数集，译码结构
2009-8-20 史忠植 高级人工智能 9
面向执行的学习系统任务子系统学习子系统任务检测器 …
1d
md
…
1e
me
任务效应器执行效应器执行检测器
2009-8-20 史忠植 高级人工智能 10
新达尔文进化理论的主要论点
1) 个体是基本的选择目标 ;
2) 随机过程在进化中起重大作用,遗传变异大部分是偶然现象 ;
3) 基因型变异大部分是重组的产物,特别是突变 ;
4) 逐渐进化可能与表型不连续有关 ;
5) 不是所有表型变化都是自然选择的必然结果 ;
6) 进化是在适应中变化的,形式多样,不仅是基因的变化 ;
7) 选择是概率型的,而不是决定型的。
2009-8-20 史忠植 高级人工智能 11
11.2 进化系统理论的形式模型进化在个体群体中起作用。瓦铤顿 (Waddington)指出基因型和表型之间关系的重要性 (Waddinton 1974)。
群体禁止异构环境。但是 ``后成环境,是多维空间。表型是基因型和环境的产物。然后表型通过异构 ``选择环境 "
发生作用。注意，这种多维选择环境与后成环境空间是不同的。现在，适应性是表型空间和选择环境空间的产物。它经常被取作一维，表示多少子孙对下一代作出贡献。
基于这种想法，莫楞贝 (Muhlenbein) 和肯德曼
(Kindermann)提出了一种称 为进化系统理论的形式模型
(Muhlenbein 1989)。
2009-8-20 史忠植 高级人工智能 12
进化系统理论的形式模型进化的主要过程后生环境遗传操作符 选择环境
g p
2009-8-20 史忠植 高级人工智能 13
进化系统理论的形式模型
}),,.,,,({ 1 iin AaaagGS基因型空间：
}),,.,,,({ 1 IRppppPS im表型空间：
其中,g 是基因型
p 是表型。
基因 gi的可能值称为等位基因。
在门德尔 (Mendel)遗传学中，假设每个基因有有限数的等位基因。
2009-8-20 史忠植 高级人工智能 14
进化系统理论的形式模型
},...,{ 1 kEPEPEP?后生环境：
),( EPgfp
PSEPGSf
：变换函数：
IRtESpq i ),,(质量函数：
这个变换函数给出了模型,说明表型的发展是通过基因与环境的交互作用 。
变换过程是高度非线性的。
2009-8-20 史忠植 高级人工智能 15
进化系统理论的形式模型
IRtESpq i ),,(质量函数：
质量函数 q给出了具体选择环境 ESi下表型的质量,
其定义如下：
质量定义适应度,用于达尔文选择 。 至今已有三种具体范例的通用模型,即门德尔遗传学遗传生态学进化配子
2009-8-20 史忠植 高级人工智能 16
门德尔遗传学在门德尔遗传学中,基因型被详细模型化,而表型和环境几乎被忽略 。 在遗传生态学 中恰好相反 。
进化配子论是从社会生物学导出的模型 。
首先让我们讨论门德尔遗传学的选择模型 。 为了简单起见,我们假设一个基因具有 n 等位基因 a1,…,an。 二倍基因型以元组 (ai,aj)为特征 。 我们定义 pi,j 为总群体中基因型 (ai,aj) 的频度 。 假设基因型与表型相等 。 质量函数给每个表 型赋值 。
q(ai,aj) = qi,j
qi,j 可以被解释为出生率减去死亡率
2009-8-20 史忠植 高级人工智能 17
门德尔遗传学假设 p’i,j是下一代表型 (ai,aj) 的频度 。 然后达尔文选择根据选择方程调整表型的分布,
Qqjiji jipp,,,'?Q
qpp ji
jiji
,
,,'?
ji
ji
ji pqQ,
,
,
Q-是群体的平均适应度。
2009-8-20 史忠植 高级人工智能 18
门德尔遗传学设 pi 是群体中等位基因的频率。如果
pi,j = pipj
那么,我们得到在 GS中的一个选择方程为
QQpp iii?'
j
j
jii pqQ,
2009-8-20 史忠植 高级人工智能 19
门德尔遗传学这个离散的选择方程可以用连续方程近似,
QQQpdtdp iii /)(
如果 qi,j = qj,i,那么这个离散的选择方程可以用连续方程近似,
)( QQpdtdp iii
2009-8-20 史忠植 高级人工智能 20
门德尔遗传学这个方程很容易被证明,
0)(2))((2 22 QV a rQQEdtQd
这个结果称作菲希尔 (Fisher)基本定理 。 它说明平均适应度随适应度的差别呈正比例增加 。 实际上,全部可能的基因型仅有一部分实现 。 这就是遗传操纵子探索基因型空间的任务,其个体数目相当小 。 这些操纵子是群体遗传变异性的来源 。 最重要的操纵子是突变和重组 。
2009-8-20 史忠植 高级人工智能 21
11.3 达尔文进化算法根据定量遗传学,达尔文进化算法采用简单的突变 /选择动力学 。
达尔文算法的一般形式可以描述如下：
)/(),/(
mu 是一代的双亲数目,
lambda 为子孙数目 。
整数 rho 称作 ``混杂,数 。
如果两个双亲混合他们的基因,则
rho = 2。 仅 mu 是最好的个体才允许产生子孙 。
逗号表示双亲们没有选择,加号表示双亲有选择 。
2009-8-20 史忠植 高级人工智能 22
11.3 达尔文进化算法
1) 建立原始种体。
2) 通过突变建立子孙。
3) 选择：
4) 返回到步骤 (1)。
11' sgs?
111 '' Zsxx …
sgs?'
Zsxx ''
)}'({m a x)( 1 xQxQ i
2009-8-20 史忠植 高级人工智能 23
11.4 分类器系统
Holland和他的同事提出了一种分类器系统的认知模型,
其中的规则不是规则集,而是遗传算法操纵的内部实体。
图 11.3给出了分类器系统的一般结构,从分类器系统看学习,它由三层动作构成,即执行子系统、信用赋值子系统和发现子系统。
2009-8-20 史忠植 高级人工智能 24
分类器系统执行子系统处在最低层,直接与环境进行交互。它与专家系统相同,由产生式规则构成。但是,它们是消息传送,
高度平行。这类规则称作分类器。
分类器系统中的学习,要求环境提供反馈,确认所希望的状态是否达到。系统将评价这些规则的有效性,这些活动常常称作信用赋值。有些特定算法专门用来实现信用赋值,
例如,桶链算法。
最后一层是发现子系统,该系统必须产生新的规则,取代当前用处不大的规则。通过系统累积的经验产生规则。系统根据适应值,使用遗传算法选择,重组和取代规则。
2009-8-20 史忠植 高级人工智能 25
分类器系统分类器系统的一般结构发现
[遗传算法 ]
信用赋值
[桶链 ]
执行
[分类器系统 ]
消息来自输入接口支付消息送出输出接口
（目标）
来自内部监控器的消息
2009-8-20 史忠植 高级人工智能 26
分类器系统分类器系统是平行执行、消息传递和基于规则的系统。
在简单的方案中,消息采用规定的字母,全部为固定长度。
全部规则采用条件 /动作形式。每个条件规定必须满足的信息,每个动作规定当条件满足时所发送的消息。
为了方便,假设消息采用长度为 l的二进制字符串记录,字符采用子集 {1,0,#}。
2009-8-20 史忠植 高级人工智能 27
规则与消息产生式规则,IF <条件 > THEN <动作 >
约定：条件的长度是固定的，用二进制数表示。
定义：
kimmmmm e s s a g e ik,.,,,1},1,0{,,.,,,,:,21
为通配符#,,...,1},#,1,0{,,...,,:,21 kissssc o n d i t i o n ik
m e s s a g ec o n d i t i o nc l a s s i f i e r /::
If sj = 1 or sj = 0,then mj = sj
If sj = #,then mj can be either 1 or 0,
2009-8-20 史忠植 高级人工智能 28
规则与消息满足要求的全部消息构成子集,即每个子集是在消息空间的一个超平面 。 分类器系统是由一组分类器
{C1,C2,…,CN},一个消息表,输入接口,输出接口构成 。 每部分的主要功能如下,
(1) 输入接口将当前环境状态翻译成标准消息 。
(2) 分类器根据规则,规定系统处理消息的过程 。
(3) 消息表包含当前全部消息 。
(4) 输出接口将结果消息翻译成效应器动作,修改环境状态 。
2009-8-20 史忠植 高级人工智能 29
分类器系统的基本结构分类器消息表
(a)全部消息进行条件测试条件 消息规约输出接口送到环境输入接口来自环境
(a)
(b)
(b)选中分类器产生新消息
2009-8-20 史忠植 高级人工智能 30
分类器基本算法
1) 将输入接口全部消息放入消息表。
2) 将消息表中的全部消息与全部分类器所有条件比较,记录所有匹配。
3) 满足分类器条件部分的每组匹配,将其动作部分所规定的消息送到新的消息表。
4) 用新的消息表取代消息表中的全部消息。
5) 将消息表中的消息翻译成输出接口的要求,
产生系统当前的输出。
6) 返回到步骤 (1)。
2009-8-20 史忠植 高级人工智能 31
简单的视觉分类器系统视觉向量 视野 运动向量对象检测器
1 1 1 10…
消息
1d
2d
3d
4d
2009-8-20 史忠植 高级人工智能 32
性质检测器规定的值
1d
1，如果移动对象
0，其它
),( 32 dd
(0,0)，如果对象在视野的中间
(1,0)，如果对象在中心的左边
(0,1)，如果对象在中心的右边
4d
1，如果系统是对象的近邻
0，其它
5d
1，如果对象很大
0，其它
6d
1，如果对象是狭长的
0，其它
2009-8-20 史忠植 高级人工智能 33
规则表示规则：
IF 如果有“捕食 (prey)”(small,moving,nonstriped object),
处于视野中间 (centered),非邻近 (nonadjacent),
THEN 迅速移向对象 (ALIGN),(FAST).
可以表示为：
00#########000001 / 0100000000000000,ALIGN,FAST.
2009-8-20 史忠植 高级人工智能 34
网络图
[MOVING]11?d [SMALL]05?d [NOT STRPED]06?d [NEAR]010?d [FAR]110?d
01001
[ALERT]
10001
[TARGET]
11001
[PORSUE]
11010
[APPROACH]
11011
[FLEE]
11100
[FREEZE]
10010
[DANGER]
2009-8-20 史忠植 高级人工智能 35
网络图的规则表示
MOVING和 ALERT之间的箭头：
00#############1/01001###########
SMALL,NOT STRIPED and ALERT到
TARGET的箭头：
00########00####,01001###########/
10001###########
2009-8-20 史忠植 高级人工智能 36
学习机制分类器系统使用两个学习机制，
桶链 (bucket brigade) 算法。基于对系统的贡献,对现有规则分配一个信用值。
规则发现算法。这包括遗传算法，该算法可产生新规则，用于改善系统的知识库。
2009-8-20 史忠植 高级人工智能 37
11.5 桶链算法桶链 (bucket brigade) 算法基于对系统的贡献,
对现有规则分配一个信用值。主要解决多条规则同时要求被激活时的竞争问题。
例如：下面的情况下应该选择哪条规则。
0111→01# #,0000 →# #00,0001→00# 0,1100
2009-8-20 史忠植 高级人工智能 38
主要问题引入信用值后的两个问题：
当多条规则同时要求被激活时，如何解决竞争问题
对一规则被激活产生过作用的那些规则如何分配信用
2009-8-20 史忠植 高级人工智能 39
桶链算法为解决上述两个问题，引入拍卖行和票据交易所：
当有多个分类器获得匹配时，每个分类器要出一个与其强度成正比的叫价 B
叫价高的分类器被激活并允许发送消息，同时通过票据交易所,将其叫价 B提供给激活的分类器。
如此继续下去，一条规则可通过消费者获利
（增加了强度），通过规则的不断激活形成一条消费者链，直至最终消费者（达到目标）直接从环境中得到补偿。
若链中一条规则导致错误结论，则序列上该规则的强度将减弱，并且沿着序列回溯，从而产生新的消费者链
2009-8-20 史忠植 高级人工智能 40
举例环境 0111，强度为 0，叫价系数为 0.1。
索引号 分类器 强度
1 01# #,0000 200
2 00# 0,1000 200
3 11# #,1000 200
4 # #00,0001 200
2009-8-20 史忠植 高级人工智能 41
第一步分类器 强度 消息 匹配 叫价
01# #,0000 200 E 20
00# 0,1000 200
11# #,1000 200
# #00,0001 200
2009-8-20 史忠植 高级人工智能 42
第二步分类器 强度 消息 匹配 叫价
01# #,0000 180 0000
00# 0,1000 200 1 20
11# #,1000 200
# #00,0001 200 1 20
两条规则同时激活
2009-8-20 史忠植 高级人工智能 43
第三步分类器 强度 消息 匹配 叫价
01# #,0000 220
00# 0,1000 180 1100
11# #,1000 200 2 20
# #00,0001 180 0001 2 18
2009-8-20 史忠植 高级人工智能 44
第四步分类器 强度 消息 匹配 叫价
01# #,0000 220
00# 0,1000 218
11# #,1000 180 1000
# #00,0001 162 3 16
2009-8-20 史忠植 高级人工智能 45
第五步分类器 强度 消息 匹配 叫价 强度
01# #,0000 220 220
00# 0,1000 218 218
11# #,1000 196 196
# #00,0001 146 0001 206
规则 4达到目标获得补偿 60。
2009-8-20 史忠植 高级人工智能 46
投标改变分类器的强度在时间 t满足 C
送去消息的分类器
),(),(),()1( 3211 tCBtCBtCBCV
1C
1C
1C
),( 1 tCB
),( 2 tCB
),( 3 tCB
对在 t-1作用的分类器投标在时间 t对分类器 C的支持
2009-8-20 史忠植 高级人工智能 47
分类器中的遗传算法遗传算法可产生新规则，用于改善系统的知识库。
可以在三种情况下应用 GA：
1) 引入一个参数 T（ 时间间隔），用于控制何时使用 GA。
2) 特殊情况时（如消息的条件都不能匹配）
使用 GA。
3) 系统的性能太差。
2009-8-20 史忠植 高级人工智能 48
算法步骤
1) t=0,随机生成集合 Bt,|Bt|=M（ 大小）；
2) 计算 Bt中全体分类器的平均强度 Vt,对每个分类器赋予一个标准强度 St(Cj)/Vt；
3) 给 Bt中的每个分类器 Cj赋予一个与其标准强度成正比的概率，并根据 Bt中的概率分布，从 Bt中选取 n个分类器,n<<M；
4) 对每个分类器应用交叉算子，生成 2n个分类器；
5) 将 Bt中的 2n个强度最低的分类器用新生成的 2n个取代；
6) t=t+1,转 (2)。
2009-8-20 史忠植 高级人工智能 49
算法说明
1) 算法中 S0(Cj)是预知的；
2) 实现时考虑结束条件；
3) 该算法是经典 GA的变种，其中没有变异算子；
4) 新分类器的强度是由旧分类器的强度决定的。
2009-8-20 史忠植 高级人工智能 50
11.6 遗传算法
遗传算法先将搜索结构编码为字符串形式,每个字符串结构被称为个体。
然后对一组字符串结构 (被称为一个群体 )进行循环操作。每次循环被称作一代,包括一个保存字符串中较优结构的过程和一个有结构的、随机的字符串间的信息交换过程。
类似于自然进化，遗传算法通过作用于染色体上的基因寻找好的染色体来求解问题。
2009-8-20 史忠植 高级人工智能 51
遗传算法
与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。
在遗传算法中，位字符串扮演染色体的作用，单个位扮演了基因的作用，随机产生一个体字符串的初始群体，每个个体给予一个数值评价，称为适应度，取消低适应度的个体，选择高适应度的个体参加操作。
常用的遗传算子有复制、杂交、变异和反转。
2009-8-20 史忠植 高级人工智能 52
遗传算法与传统优化算法的主要不同
1) 遗传算法不是直接作用在参变量集上,而是利用参变量集的某种编码 ;
2) 遗传算法不是从单个点,而是在群体中从一个点开始搜索 ;
3) 遗传算法利用适应值信息,无需导数或其它辅助信息 ;
4) 遗传算法利用概率转移规则,而非确定性规则。
2009-8-20 史忠植 高级人工智能 53
遗传算法的准备工作
1) 确定表示方案 ;
2) 确定适应值的度量 ;
3) 确定控制该算法的参数和变量 ;
4) 确定怎样指定结果及程序运行结束的标准。
2009-8-20 史忠植 高级人工智能 54
基本的遗传算法
1,随机产生一个由固定长度字符串组成的初始群体 ;
2,对于字符串群体，迭代地执行下述步骤，直到选种标准被满足为止：
1) 计算群体中的每个个体字符串的适应值 ;
2) 应用下述三种操作 (至少前两种 )来产生新的群体,
复制,把现有的个体字符串复制到新的群体中。
杂交,通过遗传重组随机选择两个现有的子字符串,
产生新的字符串。
变异,将现有字符串中某一位的字符随机变异。
3,把在后代中出现的最高适应值的个体字符串指定为遗传算法运行的结果。这一结果可以是问题的解 (或近似解 )。
2009-8-20 史忠植 高级人工智能 55
基本遗传算法的流程图
GEN=0
概率地选择遗传操作随机创建初始群体是否满足选中标准？
计算群体中每个个体的适应值
i:=0
i:=M
指定结果 结束
GEN:=GEN+1 是是否
（转下页）
2009-8-20 史忠植 高级人工智能 56
概率地选择遗传操作根据适应值选择一个个体完成杂交
i:=i+1
i:=i+1完成繁殖
p(r)繁殖
（接上页）
基于适应值选择两个个体把新的两个孩子加到群体中
p(c)杂交 变异 p(m)
把新的孩子加入到群体中完成变异根据适应值选择一个个体把变异后个体加入到群体中
2009-8-20 史忠植 高级人工智能 57
表示模式所谓模式就是一个相同的构形,它描述的是一个串的子集,这个集合中的串之间在某些位上相同。
模式的复制生长方程：
这表明,一个特定的模式按照其平均适应值与群体的平均适应值之间的比率生长。
f
HftHMtHM )(),()1,(
2009-8-20 史忠植 高级人工智能 58
杂交操作
杂交操作是个有结构、随机的字符串间信息交换过程。
简单的杂交操作分为三步
从当前群体 B(t)中选择两个结构：
随机选择一个整数
交换 a和 a‘中位置 x左边的元素,产生两个新的结构：
ll sssasssa '.,,'''.,,2121,
}1,.,,,2,1{ lx
lxxlxx ssssssss,,,'.,,''.,,'.,,1111,
2009-8-20 史忠植 高级人工智能 59
具有强度的遗传算法
1,在 t = 0时随机产生 M字符串的群体 B(t)。 计算群体 B(t)中字符串的平均强度 v(t),给群体 B(t)中的每个字符串赋以规范值 S(Cj,t)/v(t)。
2,对群体 B(t)中的每个字符串赋与一个概率值,其值与规范值成正比。然后,使用概率分布,从 B(t)中选择 n对字符串,
n<<M,并且将它们复制。
3,对每对复制字符串进行杂交操作,形成 2n个新的字符串。
4,用步骤 (3)中生成的 2n个新的字符串取代群体 B(t)中 2n个强度最低的字符串。
5,时间 t 变为 t + 1,返回步骤 (1)。
2009-8-20 史忠植 高级人工智能 60
杂交操作举例
),( tCv j
1
0
2
2
0
2
0
1
[No Offspring]
Pt,of interchange
[Crossover]jC[Parents] jC[Offspring]
1110###0#
1##0111##
0001##11#
010##1000
#00####11
0#01##10#
###100100
100##0111
6
17
1
1110##11#
0001###0#
0001##11#
#00####11
#00####11
0#01##10#
000##0111
1#01##10#
2009-8-20 史忠植 高级人工智能 61
变异操作简单的变异操作过程如下,
每个位置的字符变量都有一个变异概率,各位置互相独立。通过随机过程选择发生变异的位置：
产生一个新结构,其中 是从对应位置 的字符变量的值域中随机选择的一个取值。 可以同样得到。
lxxx,...,,21
txxxxxx ssssssssa,..'...'...' 11111 222111
1'xs
1x
kxx ss ',...,' 2
2009-8-20 史忠植 高级人工智能 62
反转操作简单反转操作的步骤如下,
1) 从当前群体中随机选择一个结构
2) 从中随机选择两个数 i’和 j’,并定义
i = min{i',j'},j=max{i',j'};
3) 颠倒 a中位置 i,j之间的部分,产生新的结构
lsssa,..21?
ljijji ssssssss,.......,12121
2009-8-20 史忠植 高级人工智能 63
遗传算法举例问题：求
（ 1） 编码：
此时取均长为 5，每个染色体
（ 2）初始群体生成：群体大小视情况而定，此处设置为 4，随机产生四个个体：
编码,01101,11000,01000,10011
解码,13 24 8 19
适应度,169 576 64 361
（ 3）适应度评价：
]31,0[,)( 2 xxxfM a x
11111~00000?x
5}1,0{
2)( xxfitn es s?
2009-8-20 史忠植 高级人工智能 64
（ 4）选择：选择概率个体,01101,11000,01000,10011
适应度,169 576 64 361
选择概率,0.14 0.49 0.06 0.31
选择结果,01101,11000,11000,10011
（ 5）交叉操作：发生交叉的概率较大哪两个个体配对交叉是随机的交叉点位置的选取是随机的（单点交叉）
0110 1 01100 11 000 11011
1100 0 11001 10 011 10000
ffP ii / 1170 f
...9.0,8.0?cP
2009-8-20 史忠植 高级人工智能 65
（ 6）变异：发生变异的概率很小
（ 7）新群体的产生：
保留上一代最优个体，一般为 10%左右，至少 1个用新个体取代旧个体，随机取代或择优取代。
11000,11011,11001,10011
（ 8）重复上述操作：
说明,GA的终止条件一般人为设置；
GA只能求次优解或满意解。
分析：按第二代新群体进行遗传操作，若无变异，永远也找不到最优解 —— 择优取代有问题。
若随机的将个体 01101选入新群体中，有可能找到最优解。
0 0 0 1.0?mP
2009-8-20 史忠植 高级人工智能 66
11.7 并行遗传算法基于离散门德尔模型的遗传算法由六部分组成：
1) 对给定问题求解的染色体表示；
2) 求解的原始物种；
3) 起环境作用的品质函数；
4) 可以生成子孙的个体的选择过程；
5) 一种遗传操纵子，如变异、重组；
6) 控制算法本身的参数。
2009-8-20 史忠植 高级人工智能 67
并行遗传算法并行遗传算法：
1) 给定具有不同开始表型的 N个个体；
2) 每个个体计算局部最大；
3) 选择 —— 在“近邻”中选择配对；
4) 用重组和突变创建子孙；
5) 返回步骤 2。
2009-8-20 史忠植 高级人工智能 68
11.8 分类器系统 Boole
Wilson 于 1987年开发了一个布尔问题的分类器系统 Boole(Wilson 1987)。 一个布尔函数变量 L 是从长度为 L的字符串到 {0,1}的映射。学习函数意味获得对任何输入字符串能给出正确输出 0 或 1的能力。
2009-8-20 史忠植 高级人工智能 69
分类器强度调整算法
1) 将与所选动作相同的分类器形成子集 [M],称作动作集 [A]。 将不在 [M]中的其它分类器放在集合
NOT[A]中。
2) 在 [A]中的全部分类器强度减少一个分数 e。
3) 如果系统决策正确，则将赢利量 R分配给 [A]的强度 ;
4) 如果系统决策错误，则将赢利量 R'(其中 0≤R'≤R)分配给 [A]的强度，从 [A]的强度减少一个分数 p。 至少 R'和 p中的一个为 0。
5) 从 NOT[A]中的强度减去一个分数 t。
2009-8-20 史忠植 高级人工智能 70
Boole的遗传算法
1) 根据 [P]中分类器的强度，通过概率选择第一个分类器 。
2) 根据概率,与步骤 (1)相同，选择分类器,并对 和进行杂交；从结果中选择一个作为子孙，另一个被抛弃。
3) 如果步骤 (2) 未完成，则复制 形成子孙。
4) 对子孙应用变异操作，以概率 改变每个分类的等位基因。
5) 如果通过杂交生成子孙，每个父母的强度减少三分之一，
子孙的初始强度等于父母减少的总和；否则减少 的一半，
而子孙的初始强度等于减少的量。
6) 将子孙加到 [P]中。
7) 根据 [P]中分类器强度的概率分布，删除最小的一个分类器。
1C
1C
2C 1C 2C
1C
2009-8-20 史忠植 高级人工智能 71
11.9 规则发现系统在规则发现系统中,学习经常是首先评价系统现有的规则质量,
然后进行修改。 Grefenstette 研制了一种规则发现系统 RUDI。
问题求解级由简化的分类器系统组成。学习级是对知识结构群体进行遗传算法操作,每一个表示为一组规则表。知识结构的整个行为控制这些结构的复制。
在 RUDI中,信用赋值方法赢利共享规划 (Profit-Sharing Plan,
简称 PSP) 和桶链算法 (BBA) 对每个规则提供互补的效用信息。
根据期望的外部奖励,PSP-强度对规则效用提供更精确的评估。
当问题求解时它被用作冲突消解。与此相反,BBA-强度表示规则之间的动态相关性,规则点火依次会聚到相似水平。这种测度可以用作一组协作规则的聚类。
2009-8-20 史忠植 高级人工智能 72
规则发现系统
Grefenstette 提出一种强度修改方案称作嬴利共享规划 PSP。
在这种方案中问题求解划分成情节,按所接受的外部奖励区分。
如果任何步情节在投标竞争中获胜,则认为该规则在该情节活动。
在情节 t,PSP 修改每个活动规则 Ri的强度 Si(t) 如下,
Si(t + 1) = Si(t) -bSi(t) + bp(t),
其中,p(t) 称作在情节结束时所获得的外部奖励,即当获得外部奖励,从每个活动规则搜集投标,每个活动规则给出一部分外部奖励。考虑 PSP 对给定规则 Ri 的影响,它按照方程 得到,
)1()()0()1()( 1 ipbibSbtS ittiiti
2009-8-20 史忠植 高级人工智能 73
规则发现系统其中,t 的范围是在该情节规则 Ri 是活动的,即 Si(t) 基本上外部奖励的权值平均 p(t),(1 - b) 作为指数衰减因子。如果
b 足够小,那么 S(t) 具有 p(t) 的平均值。如果外部奖励 p(t)
是常数,p*,那么 Si 收敛到一个平衡值 Si*:
)1()()0()1()(
1
ipbibSbtS
itt
i
i
t
i
**
1
* ])()0()1[(l i m ppbibSbS
itt
i
i
t
ti
2009-8-20 史忠植 高级人工智能 74
规则发现系统在常数赢利下,PSP 将以下列速率减少误差
Ei(t) = p* - Si(t)
)(
))((
)1()(
)()1(
*
tbE
tSpb
tStS
tEtEE
i
i
ii
iii
强度每次改变,以因子 b减少当前强度与平衡强度之差。
2009-8-20 史忠植 高级人工智能 75
规则发现系统我们看出,奖励相当是常数情况下,在 PSP下每个规则强度很快收敛到一个平衡强度,可以预测情节结束时将接收的奖励水平。
PSP的一种可能的限制是它取决于这种前提,成功外部奖励区分的情节所对应的合适区间,在这个区间里进行信用赋值。情节的选择非常重要。
2009-8-20 史忠植 高级人工智能 76
规则发现系统在桶链算法 BBA中,是基于规则之间单独处理的,可以避免有关情节的假设。假设规则 Ri 在 tau 步点火,规则 Rj 在 tau + 1
点火,那么 BBA 按照下面公式修改规则 Ri的强度 Si:
)()()()1( jiii bSbSSS
第一个改变意味 BBA 在给定的情节修改规则强度多于一次 。 第二个改变导致 PSP与 BBA基本的不同 。 PSP强度预测所期望的情节结束获得的外部奖励是在规则点火,BBA的强度预测所期望的内部奖励是在规则的下一步 。
2009-8-20 史忠植 高级人工智能 77
11.9 规则发现系统
RUDI的控制结构问题求解
BBA/PSP
遗传算法任务 执行强度新规则 信用 奖励
2009-8-20 史忠植 高级人工智能 78
PSP与 BBA比较
A
1R
C
3R
E
6R
H
B
2R
D
4R
F
6R
I
5R
G
7R
J
奖励,1000 0 300
初始状态结束状态
2009-8-20 史忠植 高级人工智能 79
不同的强度修改方案规则 PSP强度 BBA强度
1R
3R
6R
2R
4R
5R
7R
1000 648
299 567
1000 645
4 644
300 300
999 531
300 300
2009-8-20 史忠植 高级人工智能 80
11.10 进化策略进化策略模仿自然进化原理作为一种求解参数优化问题的方法。最简单的实现方法如下,
(1)定义的问题是寻找 n维的实数向量 x,它使函数
(2) 双亲向量的初始群体从每维可行范围内随机选择。
(3) 子孙向量的创建是从每个双亲向量加上零均方差高斯随机变量。
(4) 根据最小误差选择向量为下一代新的双亲。
(5) 向量的标准偏差保持不变,或者没有可用的计算方法,那么处理结束。
RRxF n?:)(
2009-8-20 史忠植 高级人工智能 81
11.11 进化程序设计进化程序设计 (evolutionary programming)的过程,可理解为从所有可能的计算机程序形成的空间中,搜索有高的适应值的计算机程序个体，在进化程序设计中，几百或几千个计算机程序参与遗传进化。
2009-8-20 史忠植 高级人工智能 82
进化程序设计步骤
1,产生出初始群体,它由关于问题 (计算机程序 )的函数随机组合而成。
2,迭代完成下述子步骤，直至满足选种标准为止,
1) 执行群体中的每个程序，根据它解决问题的能力，给它指定一个适应值
2) 应用变异等操作创造新的计算机程序群体。基于适应值根据概率从群体中选出一个计算机程序个体，然后用合适的操作作用于该计算机程序个体。 把现有的计算机程序复制到新的群体中。通过遗传随机重组两个现有的程序,创造出新的计算机程序个体。
3,在后代中适应值最高的计算机程序个体被指定为进化程序设计的结果。这一结果可能是问题的解或近似解。
第十一章 进化计算史忠植中科院计算所
2009-8-20 史忠植 高级人工智能 2
内容
11.1 概述
11.2 进化系统理论的形式模型
11.3 达尔文进化算法
11.4 分类器系统
11.5 桶链算法
11.6 遗传算法
11.7 并行遗传算法
11.8 分类器系统 Boole
11.9 规则发现系统
11.10 进化策略
11.11 进化程序设计
2009-8-20 史忠植 高级人工智能 3
11.1 概述遗传算法思想来源于生物进化过程,它是基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的搜索算法 (以字符串表示状态空间 )。遗传算法用概率搜索过程在该状态空间中搜索，产生新的样本。
2009-8-20 史忠植 高级人工智能 4
发展历史遗传算法的发展历史：
1965年,Holland首次提出了人工遗传操作的重要性，并把这些应用于自然系统和人工系统中。
1967年,Bagley在他的论文中首次提出了遗传算法这一术语，并讨论了遗传算法在自动博弈中的应用。
1970年,Cavicchio把遗传算法应用于模式识别中。第一个把遗传算法应用于函数优化的是 Hollstien。
2009-8-20 史忠植 高级人工智能 5
发展历史
1975年是遗传算法研究的历史上十分重要的一年。
这一年,Holland出版了他的著名专著《自然系统和人工系统的适应性,该书系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论（ schemata theory），
该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。
同年,DeJong完成了他的重要论文《遗传自适应系统的行为分析》。他在该论文中所做的研究工作可看作是遗传算法发展过程中的一个里程碑，这是因为他把 Holland的模式理论与他的计算使用结合起来。
2009-8-20 史忠植 高级人工智能 6
发展历史
1989 Goldberg对遗传算法从理论上，方法上和应用上作了系统的总结,
2009-8-20 史忠植 高级人工智能 7
特点特点：
通用
鲁棒
次优解、满意解遗传算法能解决的问题：
优化
NP完全
NP难
高度复杂的非线性问题
2009-8-20 史忠植 高级人工智能 8
遗传算法与自然进化的比较自然界染色体基因等位基因 (allele)
染色体位置 (locus)
基因型 (genotype)
表型 (phenotype)
遗传算法字符串字符，特征特征值字符串位置结构参数集，译码结构
2009-8-20 史忠植 高级人工智能 9
面向执行的学习系统任务子系统学习子系统任务检测器 …
1d
md
…
1e
me
任务效应器执行效应器执行检测器
2009-8-20 史忠植 高级人工智能 10
新达尔文进化理论的主要论点
1) 个体是基本的选择目标 ;
2) 随机过程在进化中起重大作用,遗传变异大部分是偶然现象 ;
3) 基因型变异大部分是重组的产物,特别是突变 ;
4) 逐渐进化可能与表型不连续有关 ;
5) 不是所有表型变化都是自然选择的必然结果 ;
6) 进化是在适应中变化的,形式多样,不仅是基因的变化 ;
7) 选择是概率型的,而不是决定型的。
2009-8-20 史忠植 高级人工智能 11
11.2 进化系统理论的形式模型进化在个体群体中起作用。瓦铤顿 (Waddington)指出基因型和表型之间关系的重要性 (Waddinton 1974)。
群体禁止异构环境。但是 ``后成环境,是多维空间。表型是基因型和环境的产物。然后表型通过异构 ``选择环境 "
发生作用。注意，这种多维选择环境与后成环境空间是不同的。现在，适应性是表型空间和选择环境空间的产物。它经常被取作一维，表示多少子孙对下一代作出贡献。
基于这种想法，莫楞贝 (Muhlenbein) 和肯德曼
(Kindermann)提出了一种称 为进化系统理论的形式模型
(Muhlenbein 1989)。
2009-8-20 史忠植 高级人工智能 12
进化系统理论的形式模型进化的主要过程后生环境遗传操作符 选择环境
g p
2009-8-20 史忠植 高级人工智能 13
进化系统理论的形式模型
}),,.,,,({ 1 iin AaaagGS基因型空间：
}),,.,,,({ 1 IRppppPS im表型空间：
其中,g 是基因型
p 是表型。
基因 gi的可能值称为等位基因。
在门德尔 (Mendel)遗传学中，假设每个基因有有限数的等位基因。
2009-8-20 史忠植 高级人工智能 14
进化系统理论的形式模型
},...,{ 1 kEPEPEP?后生环境：
),( EPgfp
PSEPGSf
：变换函数：
IRtESpq i ),,(质量函数：
这个变换函数给出了模型,说明表型的发展是通过基因与环境的交互作用 。
变换过程是高度非线性的。
2009-8-20 史忠植 高级人工智能 15
进化系统理论的形式模型
IRtESpq i ),,(质量函数：
质量函数 q给出了具体选择环境 ESi下表型的质量,
其定义如下：
质量定义适应度,用于达尔文选择 。 至今已有三种具体范例的通用模型,即门德尔遗传学遗传生态学进化配子
2009-8-20 史忠植 高级人工智能 16
门德尔遗传学在门德尔遗传学中,基因型被详细模型化,而表型和环境几乎被忽略 。 在遗传生态学 中恰好相反 。
进化配子论是从社会生物学导出的模型 。
首先让我们讨论门德尔遗传学的选择模型 。 为了简单起见,我们假设一个基因具有 n 等位基因 a1,…,an。 二倍基因型以元组 (ai,aj)为特征 。 我们定义 pi,j 为总群体中基因型 (ai,aj) 的频度 。 假设基因型与表型相等 。 质量函数给每个表 型赋值 。
q(ai,aj) = qi,j
qi,j 可以被解释为出生率减去死亡率
2009-8-20 史忠植 高级人工智能 17
门德尔遗传学假设 p’i,j是下一代表型 (ai,aj) 的频度 。 然后达尔文选择根据选择方程调整表型的分布,
Qqjiji jipp,,,'?Q
qpp ji
jiji
,
,,'?
ji
ji
ji pqQ,
,
,
Q-是群体的平均适应度。
2009-8-20 史忠植 高级人工智能 18
门德尔遗传学设 pi 是群体中等位基因的频率。如果
pi,j = pipj
那么,我们得到在 GS中的一个选择方程为
QQpp iii?'
j
j
jii pqQ,
2009-8-20 史忠植 高级人工智能 19
门德尔遗传学这个离散的选择方程可以用连续方程近似,
QQQpdtdp iii /)(
如果 qi,j = qj,i,那么这个离散的选择方程可以用连续方程近似,
)( QQpdtdp iii
2009-8-20 史忠植 高级人工智能 20
门德尔遗传学这个方程很容易被证明,
0)(2))((2 22 QV a rQQEdtQd
这个结果称作菲希尔 (Fisher)基本定理 。 它说明平均适应度随适应度的差别呈正比例增加 。 实际上,全部可能的基因型仅有一部分实现 。 这就是遗传操纵子探索基因型空间的任务,其个体数目相当小 。 这些操纵子是群体遗传变异性的来源 。 最重要的操纵子是突变和重组 。
2009-8-20 史忠植 高级人工智能 21
11.3 达尔文进化算法根据定量遗传学,达尔文进化算法采用简单的突变 /选择动力学 。
达尔文算法的一般形式可以描述如下：
)/(),/(
mu 是一代的双亲数目,
lambda 为子孙数目 。
整数 rho 称作 ``混杂,数 。
如果两个双亲混合他们的基因,则
rho = 2。 仅 mu 是最好的个体才允许产生子孙 。
逗号表示双亲们没有选择,加号表示双亲有选择 。
2009-8-20 史忠植 高级人工智能 22
11.3 达尔文进化算法
1) 建立原始种体。
2) 通过突变建立子孙。
3) 选择：
4) 返回到步骤 (1)。
11' sgs?
111 '' Zsxx …
sgs?'
Zsxx ''
)}'({m a x)( 1 xQxQ i
2009-8-20 史忠植 高级人工智能 23
11.4 分类器系统
Holland和他的同事提出了一种分类器系统的认知模型,
其中的规则不是规则集,而是遗传算法操纵的内部实体。
图 11.3给出了分类器系统的一般结构,从分类器系统看学习,它由三层动作构成,即执行子系统、信用赋值子系统和发现子系统。
2009-8-20 史忠植 高级人工智能 24
分类器系统执行子系统处在最低层,直接与环境进行交互。它与专家系统相同,由产生式规则构成。但是,它们是消息传送,
高度平行。这类规则称作分类器。
分类器系统中的学习,要求环境提供反馈,确认所希望的状态是否达到。系统将评价这些规则的有效性,这些活动常常称作信用赋值。有些特定算法专门用来实现信用赋值,
例如,桶链算法。
最后一层是发现子系统,该系统必须产生新的规则,取代当前用处不大的规则。通过系统累积的经验产生规则。系统根据适应值,使用遗传算法选择,重组和取代规则。
2009-8-20 史忠植 高级人工智能 25
分类器系统分类器系统的一般结构发现
[遗传算法 ]
信用赋值
[桶链 ]
执行
[分类器系统 ]
消息来自输入接口支付消息送出输出接口
（目标）
来自内部监控器的消息
2009-8-20 史忠植 高级人工智能 26
分类器系统分类器系统是平行执行、消息传递和基于规则的系统。
在简单的方案中,消息采用规定的字母,全部为固定长度。
全部规则采用条件 /动作形式。每个条件规定必须满足的信息,每个动作规定当条件满足时所发送的消息。
为了方便,假设消息采用长度为 l的二进制字符串记录,字符采用子集 {1,0,#}。
2009-8-20 史忠植 高级人工智能 27
规则与消息产生式规则,IF <条件 > THEN <动作 >
约定：条件的长度是固定的，用二进制数表示。
定义：
kimmmmm e s s a g e ik,.,,,1},1,0{,,.,,,,:,21
为通配符#,,...,1},#,1,0{,,...,,:,21 kissssc o n d i t i o n ik
m e s s a g ec o n d i t i o nc l a s s i f i e r /::
If sj = 1 or sj = 0,then mj = sj
If sj = #,then mj can be either 1 or 0,
2009-8-20 史忠植 高级人工智能 28
规则与消息满足要求的全部消息构成子集,即每个子集是在消息空间的一个超平面 。 分类器系统是由一组分类器
{C1,C2,…,CN},一个消息表,输入接口,输出接口构成 。 每部分的主要功能如下,
(1) 输入接口将当前环境状态翻译成标准消息 。
(2) 分类器根据规则,规定系统处理消息的过程 。
(3) 消息表包含当前全部消息 。
(4) 输出接口将结果消息翻译成效应器动作,修改环境状态 。
2009-8-20 史忠植 高级人工智能 29
分类器系统的基本结构分类器消息表
(a)全部消息进行条件测试条件 消息规约输出接口送到环境输入接口来自环境
(a)
(b)
(b)选中分类器产生新消息
2009-8-20 史忠植 高级人工智能 30
分类器基本算法
1) 将输入接口全部消息放入消息表。
2) 将消息表中的全部消息与全部分类器所有条件比较,记录所有匹配。
3) 满足分类器条件部分的每组匹配,将其动作部分所规定的消息送到新的消息表。
4) 用新的消息表取代消息表中的全部消息。
5) 将消息表中的消息翻译成输出接口的要求,
产生系统当前的输出。
6) 返回到步骤 (1)。
2009-8-20 史忠植 高级人工智能 31
简单的视觉分类器系统视觉向量 视野 运动向量对象检测器
1 1 1 10…
消息
1d
2d
3d
4d
2009-8-20 史忠植 高级人工智能 32
性质检测器规定的值
1d
1，如果移动对象
0，其它
),( 32 dd
(0,0)，如果对象在视野的中间
(1,0)，如果对象在中心的左边
(0,1)，如果对象在中心的右边
4d
1，如果系统是对象的近邻
0，其它
5d
1，如果对象很大
0，其它
6d
1，如果对象是狭长的
0，其它
2009-8-20 史忠植 高级人工智能 33
规则表示规则：
IF 如果有“捕食 (prey)”(small,moving,nonstriped object),
处于视野中间 (centered),非邻近 (nonadjacent),
THEN 迅速移向对象 (ALIGN),(FAST).
可以表示为：
00#########000001 / 0100000000000000,ALIGN,FAST.
2009-8-20 史忠植 高级人工智能 34
网络图
[MOVING]11?d [SMALL]05?d [NOT STRPED]06?d [NEAR]010?d [FAR]110?d
01001
[ALERT]
10001
[TARGET]
11001
[PORSUE]
11010
[APPROACH]
11011
[FLEE]
11100
[FREEZE]
10010
[DANGER]
2009-8-20 史忠植 高级人工智能 35
网络图的规则表示
MOVING和 ALERT之间的箭头：
00#############1/01001###########
SMALL,NOT STRIPED and ALERT到
TARGET的箭头：
00########00####,01001###########/
10001###########
2009-8-20 史忠植 高级人工智能 36
学习机制分类器系统使用两个学习机制，
桶链 (bucket brigade) 算法。基于对系统的贡献,对现有规则分配一个信用值。
规则发现算法。这包括遗传算法，该算法可产生新规则，用于改善系统的知识库。
2009-8-20 史忠植 高级人工智能 37
11.5 桶链算法桶链 (bucket brigade) 算法基于对系统的贡献,
对现有规则分配一个信用值。主要解决多条规则同时要求被激活时的竞争问题。
例如：下面的情况下应该选择哪条规则。
0111→01# #,0000 →# #00,0001→00# 0,1100
2009-8-20 史忠植 高级人工智能 38
主要问题引入信用值后的两个问题：
当多条规则同时要求被激活时，如何解决竞争问题
对一规则被激活产生过作用的那些规则如何分配信用
2009-8-20 史忠植 高级人工智能 39
桶链算法为解决上述两个问题，引入拍卖行和票据交易所：
当有多个分类器获得匹配时，每个分类器要出一个与其强度成正比的叫价 B
叫价高的分类器被激活并允许发送消息，同时通过票据交易所,将其叫价 B提供给激活的分类器。
如此继续下去，一条规则可通过消费者获利
（增加了强度），通过规则的不断激活形成一条消费者链，直至最终消费者（达到目标）直接从环境中得到补偿。
若链中一条规则导致错误结论，则序列上该规则的强度将减弱，并且沿着序列回溯，从而产生新的消费者链
2009-8-20 史忠植 高级人工智能 40
举例环境 0111，强度为 0，叫价系数为 0.1。
索引号 分类器 强度
1 01# #,0000 200
2 00# 0,1000 200
3 11# #,1000 200
4 # #00,0001 200
2009-8-20 史忠植 高级人工智能 41
第一步分类器 强度 消息 匹配 叫价
01# #,0000 200 E 20
00# 0,1000 200
11# #,1000 200
# #00,0001 200
2009-8-20 史忠植 高级人工智能 42
第二步分类器 强度 消息 匹配 叫价
01# #,0000 180 0000
00# 0,1000 200 1 20
11# #,1000 200
# #00,0001 200 1 20
两条规则同时激活
2009-8-20 史忠植 高级人工智能 43
第三步分类器 强度 消息 匹配 叫价
01# #,0000 220
00# 0,1000 180 1100
11# #,1000 200 2 20
# #00,0001 180 0001 2 18
2009-8-20 史忠植 高级人工智能 44
第四步分类器 强度 消息 匹配 叫价
01# #,0000 220
00# 0,1000 218
11# #,1000 180 1000
# #00,0001 162 3 16
2009-8-20 史忠植 高级人工智能 45
第五步分类器 强度 消息 匹配 叫价 强度
01# #,0000 220 220
00# 0,1000 218 218
11# #,1000 196 196
# #00,0001 146 0001 206
规则 4达到目标获得补偿 60。
2009-8-20 史忠植 高级人工智能 46
投标改变分类器的强度在时间 t满足 C
送去消息的分类器
),(),(),()1( 3211 tCBtCBtCBCV
1C
1C
1C
),( 1 tCB
),( 2 tCB
),( 3 tCB
对在 t-1作用的分类器投标在时间 t对分类器 C的支持
2009-8-20 史忠植 高级人工智能 47
分类器中的遗传算法遗传算法可产生新规则，用于改善系统的知识库。
可以在三种情况下应用 GA：
1) 引入一个参数 T（ 时间间隔），用于控制何时使用 GA。
2) 特殊情况时（如消息的条件都不能匹配）
使用 GA。
3) 系统的性能太差。
2009-8-20 史忠植 高级人工智能 48
算法步骤
1) t=0,随机生成集合 Bt,|Bt|=M（ 大小）；
2) 计算 Bt中全体分类器的平均强度 Vt,对每个分类器赋予一个标准强度 St(Cj)/Vt；
3) 给 Bt中的每个分类器 Cj赋予一个与其标准强度成正比的概率，并根据 Bt中的概率分布，从 Bt中选取 n个分类器,n<<M；
4) 对每个分类器应用交叉算子，生成 2n个分类器；
5) 将 Bt中的 2n个强度最低的分类器用新生成的 2n个取代；
6) t=t+1,转 (2)。
2009-8-20 史忠植 高级人工智能 49
算法说明
1) 算法中 S0(Cj)是预知的；
2) 实现时考虑结束条件；
3) 该算法是经典 GA的变种，其中没有变异算子；
4) 新分类器的强度是由旧分类器的强度决定的。
2009-8-20 史忠植 高级人工智能 50
11.6 遗传算法
遗传算法先将搜索结构编码为字符串形式,每个字符串结构被称为个体。
然后对一组字符串结构 (被称为一个群体 )进行循环操作。每次循环被称作一代,包括一个保存字符串中较优结构的过程和一个有结构的、随机的字符串间的信息交换过程。
类似于自然进化，遗传算法通过作用于染色体上的基因寻找好的染色体来求解问题。
2009-8-20 史忠植 高级人工智能 51
遗传算法
与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。
在遗传算法中，位字符串扮演染色体的作用，单个位扮演了基因的作用，随机产生一个体字符串的初始群体，每个个体给予一个数值评价，称为适应度，取消低适应度的个体，选择高适应度的个体参加操作。
常用的遗传算子有复制、杂交、变异和反转。
2009-8-20 史忠植 高级人工智能 52
遗传算法与传统优化算法的主要不同
1) 遗传算法不是直接作用在参变量集上,而是利用参变量集的某种编码 ;
2) 遗传算法不是从单个点,而是在群体中从一个点开始搜索 ;
3) 遗传算法利用适应值信息,无需导数或其它辅助信息 ;
4) 遗传算法利用概率转移规则,而非确定性规则。
2009-8-20 史忠植 高级人工智能 53
遗传算法的准备工作
1) 确定表示方案 ;
2) 确定适应值的度量 ;
3) 确定控制该算法的参数和变量 ;
4) 确定怎样指定结果及程序运行结束的标准。
2009-8-20 史忠植 高级人工智能 54
基本的遗传算法
1,随机产生一个由固定长度字符串组成的初始群体 ;
2,对于字符串群体，迭代地执行下述步骤，直到选种标准被满足为止：
1) 计算群体中的每个个体字符串的适应值 ;
2) 应用下述三种操作 (至少前两种 )来产生新的群体,
复制,把现有的个体字符串复制到新的群体中。
杂交,通过遗传重组随机选择两个现有的子字符串,
产生新的字符串。
变异,将现有字符串中某一位的字符随机变异。
3,把在后代中出现的最高适应值的个体字符串指定为遗传算法运行的结果。这一结果可以是问题的解 (或近似解 )。
2009-8-20 史忠植 高级人工智能 55
基本遗传算法的流程图
GEN=0
概率地选择遗传操作随机创建初始群体是否满足选中标准？
计算群体中每个个体的适应值
i:=0
i:=M
指定结果 结束
GEN:=GEN+1 是是否
（转下页）
2009-8-20 史忠植 高级人工智能 56
概率地选择遗传操作根据适应值选择一个个体完成杂交
i:=i+1
i:=i+1完成繁殖
p(r)繁殖
（接上页）
基于适应值选择两个个体把新的两个孩子加到群体中
p(c)杂交 变异 p(m)
把新的孩子加入到群体中完成变异根据适应值选择一个个体把变异后个体加入到群体中
2009-8-20 史忠植 高级人工智能 57
表示模式所谓模式就是一个相同的构形,它描述的是一个串的子集,这个集合中的串之间在某些位上相同。
模式的复制生长方程：
这表明,一个特定的模式按照其平均适应值与群体的平均适应值之间的比率生长。
f
HftHMtHM )(),()1,(
2009-8-20 史忠植 高级人工智能 58
杂交操作
杂交操作是个有结构、随机的字符串间信息交换过程。
简单的杂交操作分为三步
从当前群体 B(t)中选择两个结构：
随机选择一个整数
交换 a和 a‘中位置 x左边的元素,产生两个新的结构：
ll sssasssa '.,,'''.,,2121,
}1,.,,,2,1{ lx
lxxlxx ssssssss,,,'.,,''.,,'.,,1111,
2009-8-20 史忠植 高级人工智能 59
具有强度的遗传算法
1,在 t = 0时随机产生 M字符串的群体 B(t)。 计算群体 B(t)中字符串的平均强度 v(t),给群体 B(t)中的每个字符串赋以规范值 S(Cj,t)/v(t)。
2,对群体 B(t)中的每个字符串赋与一个概率值,其值与规范值成正比。然后,使用概率分布,从 B(t)中选择 n对字符串,
n<<M,并且将它们复制。
3,对每对复制字符串进行杂交操作,形成 2n个新的字符串。
4,用步骤 (3)中生成的 2n个新的字符串取代群体 B(t)中 2n个强度最低的字符串。
5,时间 t 变为 t + 1,返回步骤 (1)。
2009-8-20 史忠植 高级人工智能 60
杂交操作举例
),( tCv j
1
0
2
2
0
2
0
1
[No Offspring]
Pt,of interchange
[Crossover]jC[Parents] jC[Offspring]
1110###0#
1##0111##
0001##11#
010##1000
#00####11
0#01##10#
###100100
100##0111
6
17
1
1110##11#
0001###0#
0001##11#
#00####11
#00####11
0#01##10#
000##0111
1#01##10#
2009-8-20 史忠植 高级人工智能 61
变异操作简单的变异操作过程如下,
每个位置的字符变量都有一个变异概率,各位置互相独立。通过随机过程选择发生变异的位置：
产生一个新结构,其中 是从对应位置 的字符变量的值域中随机选择的一个取值。 可以同样得到。
lxxx,...,,21
txxxxxx ssssssssa,..'...'...' 11111 222111
1'xs
1x
kxx ss ',...,' 2
2009-8-20 史忠植 高级人工智能 62
反转操作简单反转操作的步骤如下,
1) 从当前群体中随机选择一个结构
2) 从中随机选择两个数 i’和 j’,并定义
i = min{i',j'},j=max{i',j'};
3) 颠倒 a中位置 i,j之间的部分,产生新的结构
lsssa,..21?
ljijji ssssssss,.......,12121
2009-8-20 史忠植 高级人工智能 63
遗传算法举例问题：求
（ 1） 编码：
此时取均长为 5，每个染色体
（ 2）初始群体生成：群体大小视情况而定，此处设置为 4，随机产生四个个体：
编码,01101,11000,01000,10011
解码,13 24 8 19
适应度,169 576 64 361
（ 3）适应度评价：
]31,0[,)( 2 xxxfM a x
11111~00000?x
5}1,0{
2)( xxfitn es s?
2009-8-20 史忠植 高级人工智能 64
（ 4）选择：选择概率个体,01101,11000,01000,10011
适应度,169 576 64 361
选择概率,0.14 0.49 0.06 0.31
选择结果,01101,11000,11000,10011
（ 5）交叉操作：发生交叉的概率较大哪两个个体配对交叉是随机的交叉点位置的选取是随机的（单点交叉）
0110 1 01100 11 000 11011
1100 0 11001 10 011 10000
ffP ii / 1170 f
...9.0,8.0?cP
2009-8-20 史忠植 高级人工智能 65
（ 6）变异：发生变异的概率很小
（ 7）新群体的产生：
保留上一代最优个体，一般为 10%左右，至少 1个用新个体取代旧个体，随机取代或择优取代。
11000,11011,11001,10011
（ 8）重复上述操作：
说明,GA的终止条件一般人为设置；
GA只能求次优解或满意解。
分析：按第二代新群体进行遗传操作，若无变异，永远也找不到最优解 —— 择优取代有问题。
若随机的将个体 01101选入新群体中，有可能找到最优解。
0 0 0 1.0?mP
2009-8-20 史忠植 高级人工智能 66
11.7 并行遗传算法基于离散门德尔模型的遗传算法由六部分组成：
1) 对给定问题求解的染色体表示；
2) 求解的原始物种；
3) 起环境作用的品质函数；
4) 可以生成子孙的个体的选择过程；
5) 一种遗传操纵子，如变异、重组；
6) 控制算法本身的参数。
2009-8-20 史忠植 高级人工智能 67
并行遗传算法并行遗传算法：
1) 给定具有不同开始表型的 N个个体；
2) 每个个体计算局部最大；
3) 选择 —— 在“近邻”中选择配对；
4) 用重组和突变创建子孙；
5) 返回步骤 2。
2009-8-20 史忠植 高级人工智能 68
11.8 分类器系统 Boole
Wilson 于 1987年开发了一个布尔问题的分类器系统 Boole(Wilson 1987)。 一个布尔函数变量 L 是从长度为 L的字符串到 {0,1}的映射。学习函数意味获得对任何输入字符串能给出正确输出 0 或 1的能力。
2009-8-20 史忠植 高级人工智能 69
分类器强度调整算法
1) 将与所选动作相同的分类器形成子集 [M],称作动作集 [A]。 将不在 [M]中的其它分类器放在集合
NOT[A]中。
2) 在 [A]中的全部分类器强度减少一个分数 e。
3) 如果系统决策正确，则将赢利量 R分配给 [A]的强度 ;
4) 如果系统决策错误，则将赢利量 R'(其中 0≤R'≤R)分配给 [A]的强度，从 [A]的强度减少一个分数 p。 至少 R'和 p中的一个为 0。
5) 从 NOT[A]中的强度减去一个分数 t。
2009-8-20 史忠植 高级人工智能 70
Boole的遗传算法
1) 根据 [P]中分类器的强度，通过概率选择第一个分类器 。
2) 根据概率,与步骤 (1)相同，选择分类器,并对 和进行杂交；从结果中选择一个作为子孙，另一个被抛弃。
3) 如果步骤 (2) 未完成，则复制 形成子孙。
4) 对子孙应用变异操作，以概率 改变每个分类的等位基因。
5) 如果通过杂交生成子孙，每个父母的强度减少三分之一，
子孙的初始强度等于父母减少的总和；否则减少 的一半，
而子孙的初始强度等于减少的量。
6) 将子孙加到 [P]中。
7) 根据 [P]中分类器强度的概率分布，删除最小的一个分类器。
1C
1C
2C 1C 2C
1C
2009-8-20 史忠植 高级人工智能 71
11.9 规则发现系统在规则发现系统中,学习经常是首先评价系统现有的规则质量,
然后进行修改。 Grefenstette 研制了一种规则发现系统 RUDI。
问题求解级由简化的分类器系统组成。学习级是对知识结构群体进行遗传算法操作,每一个表示为一组规则表。知识结构的整个行为控制这些结构的复制。
在 RUDI中,信用赋值方法赢利共享规划 (Profit-Sharing Plan,
简称 PSP) 和桶链算法 (BBA) 对每个规则提供互补的效用信息。
根据期望的外部奖励,PSP-强度对规则效用提供更精确的评估。
当问题求解时它被用作冲突消解。与此相反,BBA-强度表示规则之间的动态相关性,规则点火依次会聚到相似水平。这种测度可以用作一组协作规则的聚类。
2009-8-20 史忠植 高级人工智能 72
规则发现系统
Grefenstette 提出一种强度修改方案称作嬴利共享规划 PSP。
在这种方案中问题求解划分成情节,按所接受的外部奖励区分。
如果任何步情节在投标竞争中获胜,则认为该规则在该情节活动。
在情节 t,PSP 修改每个活动规则 Ri的强度 Si(t) 如下,
Si(t + 1) = Si(t) -bSi(t) + bp(t),
其中,p(t) 称作在情节结束时所获得的外部奖励,即当获得外部奖励,从每个活动规则搜集投标,每个活动规则给出一部分外部奖励。考虑 PSP 对给定规则 Ri 的影响,它按照方程 得到,
)1()()0()1()( 1 ipbibSbtS ittiiti
2009-8-20 史忠植 高级人工智能 73
规则发现系统其中,t 的范围是在该情节规则 Ri 是活动的,即 Si(t) 基本上外部奖励的权值平均 p(t),(1 - b) 作为指数衰减因子。如果
b 足够小,那么 S(t) 具有 p(t) 的平均值。如果外部奖励 p(t)
是常数,p*,那么 Si 收敛到一个平衡值 Si*:
)1()()0()1()(
1
ipbibSbtS
itt
i
i
t
i
**
1
* ])()0()1[(l i m ppbibSbS
itt
i
i
t
ti
2009-8-20 史忠植 高级人工智能 74
规则发现系统在常数赢利下,PSP 将以下列速率减少误差
Ei(t) = p* - Si(t)
)(
))((
)1()(
)()1(
*
tbE
tSpb
tStS
tEtEE
i
i
ii
iii
强度每次改变,以因子 b减少当前强度与平衡强度之差。
2009-8-20 史忠植 高级人工智能 75
规则发现系统我们看出,奖励相当是常数情况下,在 PSP下每个规则强度很快收敛到一个平衡强度,可以预测情节结束时将接收的奖励水平。
PSP的一种可能的限制是它取决于这种前提,成功外部奖励区分的情节所对应的合适区间,在这个区间里进行信用赋值。情节的选择非常重要。
2009-8-20 史忠植 高级人工智能 76
规则发现系统在桶链算法 BBA中,是基于规则之间单独处理的,可以避免有关情节的假设。假设规则 Ri 在 tau 步点火,规则 Rj 在 tau + 1
点火,那么 BBA 按照下面公式修改规则 Ri的强度 Si:
)()()()1( jiii bSbSSS
第一个改变意味 BBA 在给定的情节修改规则强度多于一次 。 第二个改变导致 PSP与 BBA基本的不同 。 PSP强度预测所期望的情节结束获得的外部奖励是在规则点火,BBA的强度预测所期望的内部奖励是在规则的下一步 。
2009-8-20 史忠植 高级人工智能 77
11.9 规则发现系统
RUDI的控制结构问题求解
BBA/PSP
遗传算法任务 执行强度新规则 信用 奖励
2009-8-20 史忠植 高级人工智能 78
PSP与 BBA比较
A
1R
C
3R
E
6R
H
B
2R
D
4R
F
6R
I
5R
G
7R
J
奖励,1000 0 300
初始状态结束状态
2009-8-20 史忠植 高级人工智能 79
不同的强度修改方案规则 PSP强度 BBA强度
1R
3R
6R
2R
4R
5R
7R
1000 648
299 567
1000 645
4 644
300 300
999 531
300 300
2009-8-20 史忠植 高级人工智能 80
11.10 进化策略进化策略模仿自然进化原理作为一种求解参数优化问题的方法。最简单的实现方法如下,
(1)定义的问题是寻找 n维的实数向量 x,它使函数
(2) 双亲向量的初始群体从每维可行范围内随机选择。
(3) 子孙向量的创建是从每个双亲向量加上零均方差高斯随机变量。
(4) 根据最小误差选择向量为下一代新的双亲。
(5) 向量的标准偏差保持不变,或者没有可用的计算方法,那么处理结束。
RRxF n?:)(
2009-8-20 史忠植 高级人工智能 81
11.11 进化程序设计进化程序设计 (evolutionary programming)的过程,可理解为从所有可能的计算机程序形成的空间中,搜索有高的适应值的计算机程序个体，在进化程序设计中，几百或几千个计算机程序参与遗传进化。
2009-8-20 史忠植 高级人工智能 82
进化程序设计步骤
1,产生出初始群体,它由关于问题 (计算机程序 )的函数随机组合而成。
2,迭代完成下述子步骤，直至满足选种标准为止,
1) 执行群体中的每个程序，根据它解决问题的能力，给它指定一个适应值
2) 应用变异等操作创造新的计算机程序群体。基于适应值根据概率从群体中选出一个计算机程序个体，然后用合适的操作作用于该计算机程序个体。 把现有的计算机程序复制到新的群体中。通过遗传随机重组两个现有的程序,创造出新的计算机程序个体。
3,在后代中适应值最高的计算机程序个体被指定为进化程序设计的结果。这一结果可能是问题的解或近似解。
