第十一章 进化计算史忠植中科院计算所内容
11.1 概述
11.2 进化系统理论的形式模型
11.3 达尔文进化算法
11.4 分类器系统
11.5 桶链算法
11.6 遗传算法
11.7 并行遗传算法
11.8 分类器系统 Boole
11.9 规则发现系统
11.10 进化策略
11.11 进化程序设计
11.1 概述遗传算法思想来源于生物进化过程,它是基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的搜索算法 (以字符串表示状态空间 )。遗传算法用概率搜索过程在该状态空间中搜索，产生新的样本。
发展历史遗传算法的发展历史：
60年代开始
70年代热门
国内 90年代有了研究特点特点：
通用
鲁棒
次优解、满意解遗传算法能解决的问题：
优化
NP完全
NP难
高度复杂的非线性问题遗传算法与自然进化的比较自然界染色体基因等位基因 (allele)
染色体位置 (locus)
基因型 (genotype)
表型 (phenotype)
遗传算法字符串字符，特征特征值字符串位置结构参数集，译码结构面向执行的学习系统任务子系统学习子系统任务检测器 …
1d
md
…
1e
me
任务效应器执行效应器执行检测器新达尔文进化理论的主要论点
1) 个体是基本的选择目标 ;
2) 随机过程在进化中起重大作用,遗传变异大部分是偶然现象 ;
3) 基因型变异大部分是重组的产物,特别是突变 ;
4) 逐渐进化可能与表型不连续有关 ;
5) 不是所有表型变化都是自然选择的必然结果 ;
6) 进化是在适应中变化的,形式多样,不仅是基因的变化 ;
7) 选择是概率型的,而不是决定型的。
11.2 进化系统理论的形式模型进化的主要过程后生环境遗传操作符 选择环境
g p
进化系统理论的形式模型
}),,.,,,({ 1 iin AaaagGS基因型空间：
}),,.,,,({ 1 IRppppPS im表型空间：
},...,{ 1 kEPEPEP?后生环境：
),( EPgfp
PSEPGSf
：变换函数：
IRtESpq i ),,(质量函数：
11.3 达尔文进化算法
1) 建立原始种体。
2) 通过突变建立子孙。
3) 选择：
4) 返回到步骤 (1)。
11' sgs?
111 '' Zsxx …
sgs?'
Zsxx ''
)}'({m a x)( 1 xQxQ i
11.4 分类器系统分类器系统的一般结构发现
[遗传算法 ]
信用赋值
[桶链 ]
执行
[分类器系统 ]
消息来自输入接口支付消息送出输出接口
（目标）
来自内部监控器的消息规则与消息产生式规则,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 /::
学习机制分类器系统使用两个学习机制，
桶链 (bucket brigade) 算法。基于对系统的贡献,对现有规则分配一个信用值。
规则发现算法。这包括遗传算法，该算法可产生新规则，用于改善系统的知识库。
分类器系统的基本结构分类器消息表
(a)全部消息进行条件测试条件 消息规约输出接口送到环境输入接口来自环境
(a)
(b)
(b)选中分类器产生新消息分类器基本算法
1) 将输入接口全部消息放入消息表。
2) 将消息表中的全部消息与全部分类器所有条件比较,记录所有匹配。
3) 满足分类器条件部分的每组匹配,将其动作部分所规定的消息送到新的消息表。
4) 用新的消息表取代消息表中的全部消息。
5) 将消息表中的消息翻译成输出接口的要求,
产生系统当前的输出。
6) 返回到步骤 (1)。
简单的视觉分类器系统视觉向量 视野 运动向量对象检测器
1 1 1 10…
消息
1d
2d
3d
4d
性质检测器规定的值
1d
1，如果移动对象
0，其它
),( 32 dd
(0,0)，如果对象在视野的中间
(1,0)，如果对象在中心的左边
(0,1)，如果对象在中心的右边
4d
1，如果系统是对象的近邻
0，其它
5d
1，如果对象很大
0，其它
6d
1，如果对象是狭长的
0，其它规则表示规则：
IF 如果有“捕食 (prey)”(small,moving,nonstriped object),
处于视野中间 (centered),非邻近 (nonadjacent),
THEN 迅速移向对象 (ALIGN),(FAST).
可以表示为：
00#########000001 / 0100000000000000,ALIGN,FAST.
网络图
[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]
网络图的规则表示
MOVING和 ALERT之间的箭头：
00#############1/01001###########
SMALL,NOT STRIPED and ALERT到
TARGET的箭头：
00########00####,01001###########/
10001###########
11.5 桶链算法桶链 (bucket brigade) 算法基于对系统的贡献,
对现有规则分配一个信用值。主要解决多条规则同时要求被激活时的竞争问题。
例如：下面的情况下应该选择哪条规则。
0111→01# #,0000 →# #00,0001→00# 0,1100
主要问题引入信用值后的两个问题：
当多条规则同时要求被激活时，如何解决竞争问题
对一规则被激活产生过作用的那些规则如何分配信用桶链算法为解决上述两个问题，引入拍卖行和票据交易所：
当有多个分类器获得匹配时，每个分类器要出一个与其强度成正比的叫价 B
叫价高的分类器被激活并允许发送消息，同时通过票据交易所将其叫价 B提供给激活改分类器的分类器。
如此继续下去，一条规则可通过消费者获利
（增加了强度），通过规则的不断激活形成一条消费者链，直至最终消费者（达到目标）直接从环境中得到补偿。
若链中一条规则导致错误结论，则序列上改规则的强度将减弱，并且沿着序列回溯，从而产生新的消费者链举例环境 0111，强度为 0，叫价系数为 0.1。
索引号 分类器 强度
1 01# #,0000 200
2 00# 0,1000 200
3 11# #,1000 200
4 # #00,0001 200
第一步分类器 强度 消息 匹配 叫价
01# #,0000 200 E 20
00# 0,1000 200
11# #,1000 200
# #00,0001 200
第二步分类器 强度 消息 匹配 叫价
01# #,0000 180 0000
00# 0,1000 200 1 20
11# #,1000 200
# #00,0001 200 1 20
两条规则同时激活第三步分类器 强度 消息 匹配 叫价
01# #,0000 220
00# 0,1000 180 1100
11# #,1000 200 2 20
# #00,0001 180 0001 2 18
第四步分类器 强度 消息 匹配 叫价
01# #,0000 220
00# 0,1000 218
11# #,1000 180 1000
# #00,0001 162 3 16
第五步分类器 强度 消息 匹配 叫价 强度
01# #,0000 220 220
00# 0,1000 218 218
11# #,1000 196 196
# #00,0001 146 0001 206
规则 4达到目标获得补偿 60。
投标改变分类器的强度在时间 t满足 C
送去消息的分类器
),(),(),()1( 3211 tCBtCBtCBCV
1C
1C
1C
),( 1 tCB
),( 2 tCB
),( 3 tCB
对在 t-1作用的分类器投标在时间 t对分类器 C的支持分类器中的遗传算法遗传算法可产生新规则，用于改善系统的知识库。
可以在三种情况下应用 GA：
1) 引入一个参数 T（ 时间间隔），用于控制何时使用 GA。
2) 特殊情况时（如消息的条件都不能匹配）
使用 GA。
3) 系统的性能太差。
算法步骤
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)。
算法说明
1) 算法中 S0(Cj)是预知的；
2) 实现时考虑结束条件；
3) 该算法是经典 GA的变种，其中没有变异算子；
4) 新分类器的强度是由旧分类器的强度决定的。
11.6 遗传算法
遗传算法先将搜索结构编码为字符串形式,每个字符串结构被称为个体。
然后对一组字符串结构 (被称为一个群体 )进行循环操作。
每次循环被称作一代,包括一个保存字符串中较优结构的过程和一个有结构的、随机的字符串间的信息交换过程。
类似于自然进化，遗传算法通过作用于染色体上的基因寻找好的染色体来求解问题。
与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。
在遗传算法中，位字符串扮演染色体的作用，单个位扮演了基因的作用，随机产生一个体字符串的初始群体，每个个体给予一个数值评价，称为适应度，取消低适应度的个体，选择高适应度的个体参加操作。
常用的遗传算子有复制、杂交、变异和反转。
遗传算法与传统优化算法的主要不同
1) 遗传算法不是直接作用在参变量集上,而是利用参变量集的某种编码 ;
2) 遗传算法不是从单个点,而是在群体中从一个点开始搜索 ;
3) 遗传算法利用适应值信息,无需导数或其它辅助信息 ;
4) 遗传算法利用概率转移规则,而非确定性规则。
遗传算法的准备工作
1) 确定表示方案 ;
2) 确定适应值的度量 ;
3) 确定控制该算法的参数和变量 ;
4) 确定怎样指定结果及程序运行结束的标准。
基本的遗传算法
1,随机产生一个由固定长度字符串组成的初始群体 ;
2,对于字符串群体，迭代地执行下述步骤，直到选种标准被满足为止：
1) 计算群体中的每个个体字符串的适应值 ;
2) 应用下述三种操作 (至少前两种 )来产生新的群体,
复制,把现有的个体字符串复制到新的群体中。
杂交,通过遗传重组随机选择两个现有的子字符串,
产生新的字符串。
变异,将现有字符串中某一位的字符随机变异。
3,把在后代中出现的最高适应值的个体字符串指定为遗传算法运行的结果。这一结果可以是问题的解 (或近似解 )。
基本遗传算法的流程图
GEN=0
概率地选择遗传操作随机创建初始群体是否满足选中标准？
计算群体中每个个体的适应值
i:=0
i:=M
指定结果 结束
GEN:=GEN+1 是是否
（转下页）
概率地选择遗传操作根据适应值选择一个个体完成杂交
i:=i+1
i:=i+1完成繁殖
p(r)繁殖
（接上页）
基于适应值选择两个个体把新的两个孩子加到群体中
p(c)杂交 变异 p(m)
把新的孩子加入到群体中完成变异根据适应值选择一个个体把变异后个体加入到群体中表示模式所谓模式就是一个相同的构形,它描述的是一个串的子集,这个集合中的串之间在某些位上相同。
模式的复制生长方程：
这表明,一个特定的模式按照其平均适应值与群体的平均适应值之间的比率生长。
f
HftHMtHM )(),()1,(
杂交操作
杂交操作是个有结构、随机的字符串间信息交换过程。
简单的杂交操作分为三步
从当前群体 B(t)中选择两个结构：
随机选择一个整数
交换 a和 a‘中位置 x左边的元素,产生两个新的结构：
ll sssasssa '.,,'''.,,2121,
}1,.,,,2,1{ lx
lxxlxx ssssssss,,,'.,,''.,,'.,,1111,
具有强度的遗传算法
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)。
杂交操作举例
),( 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#
变异操作简单的变异操作过程如下,
每个位置的字符变量都有一个变异概率,各位置互相独立。通过随机过程选择发生变异的位置：
产生一个新结构,其中 是从对应位置 的字符变量的值域中随机选择的一个取值。 可以同样得到。
lxxx,...,,21
txxxxxx ssssssssa,..'...'...' 11111 222111
1'xs
1x
kxx ss ',...,' 2
反转操作简单反转操作的步骤如下,
1) 从当前群体中随机选择一个结构
2) 从中随机选择两个数 i’和 j’,并定义
i = min{i',j'},j=max{i',j'};
3) 颠倒 a中位置 i,j之间的部分,产生新的结构
lsssa,..21?
ljijji ssssssss,.......,12121
遗传算法举例问题：求
（ 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?
（ 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
（ 6）变异：发生变异的概率很小
（ 7）新群体的产生：
保留上一代最优个体，一般为 10%左右，至少 1个用新个体取代旧个体，随机取代或择优取代。
11000,11011,11001,10011
（ 8）重复上述操作：
说明,GA的终止条件一般人为设置；
GA只能求次优解或满意解。
分析：按第二代新群体进行遗传操作，若无变异，永远也找不到最优解 —— 择优取代有问题。
若随机的将个体 01101选入新群体中，有可能找到最优解。
0 0 0 1.0?mP
11.7 并行遗传算法基于离散门德尔模型的遗传算法由六部分组成：
1) 对给定问题求解的染色体表示；
2) 求解的原始物种；
3) 起环境作用的品质函数；
4) 可以生成子孙的个体的选择过程；
5) 一种遗传操纵子，如变异、重组；
6) 控制算法本身的参数。
并行遗传算法并行遗传算法：
1) 给定具有不同开始表型的 N个个体；
2) 每个个体计算局部最大；
3) 选择 —— 在“近邻”中选择配对；
4) 用重组和突变创建子孙；
5) 返回步骤 2。
11.8 分类器系统 Boole
Wilson 于 1987年开发了一个布尔问题的分类器系统 Boole(Wilson 1987)。 一个布尔函数变量 L 是从长度为 L的字符串到 {0,1}的映射。学习函数意味获得对任何输入字符串能给出正确输出 0 或 1的能力。
分类器强度调整算法
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。
Boole的遗传算法
1) 根据 [P]中分类器的强度，通过概率选择第一个分类器 。
2) 根据概率,与步骤 (1)相同，选择分类器,并对 和进行杂交；从结果中选择一个作为子孙，另一个被抛弃。
3) 如果步骤 (2) 未完成，则复制 形成子孙。
4) 对子孙应用变异操作，以概率 改变每个分类的等位基因。
5) 如果通过杂交生成子孙，每个父母的强度减少三分之一，
子孙的初始强度等于父母减少的总和；否则减少 的一半，
而子孙的初始强度等于减少的量。
6) 将子孙加到 [P]中。
7) 根据 [P]中分类器强度的概率分布，删除最小的一个分类器。
1C
1C
2C 1C 2C
1C
11.9 规则发现系统
RUDI的控制结构问题求解
BBA/PSP
遗传算法任务 执行弧度新规则 信用 奖励
PSP与 BBA比较
A
1R
C
3R
E
6R
H
B
2R
D
4R
F
6R
I
5R
G
7R
J
奖励,1000 0 300
初始状态结束状态不同的强度修改方案规则 PSP强度 BBA强度
1R
3R
6R
2R
4R
5R
7R
1000 648
299 567
1000 645
4 644
300 300
999 531
300 300
11.10 进化策略进化策略模仿自然进化原理作为一种求解参数优化问题的方法。最简单的实现方法如下,
(1)定义的问题是寻找 n维的实数向量 x,它使函数
(2) 双亲向量的初始群体从每维可行范围内随机选择。
(3) 子孙向量的创建是从每个双亲向量加上零均方差高斯随机变量。
(4) 根据最小误差选择向量为下一代新的双亲。
(5) 向量的标准偏差保持不变,或者没有可用的计算方法,那么处理结束。
RRxF n?:)(
11.11 进化程序设计进化程序设计 (evolutionary programming)的过程,可理解为从所有可能的计算机程序形成的空间中,搜索有高的适应值的计算机程序个体，在进化程序设计中，几百或几千个计算机程序参与遗传进化。
进化程序设计步骤
1,产生出初始群体,它由关于问题 (计算机程序 )的函数随机组合而成。
2,迭代完成下述子步骤，直至满足选种标准为止,
1) 执行群体中的每个程序，根据它解决问题的能力，给它指定一个适应值
2) 应用变异等操作创造新的计算机程序群体。基于适应值根据概率从群体中选出一个计算机程序个体，然后用合适的操作作用于该计算机程序个体。 把现有的计算机程序复制到新的群体中。通过遗传随机重组两个现有的程序,创造出新的计算机程序个体。
3,在后代中适应值最高的计算机程序个体被指定为进化程序设计的结果。这一结果可能是问题的解或近似解。
11.1 概述
11.2 进化系统理论的形式模型
11.3 达尔文进化算法
11.4 分类器系统
11.5 桶链算法
11.6 遗传算法
11.7 并行遗传算法
11.8 分类器系统 Boole
11.9 规则发现系统
11.10 进化策略
11.11 进化程序设计
11.1 概述遗传算法思想来源于生物进化过程,它是基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的搜索算法 (以字符串表示状态空间 )。遗传算法用概率搜索过程在该状态空间中搜索，产生新的样本。
发展历史遗传算法的发展历史：
60年代开始
70年代热门
国内 90年代有了研究特点特点：
通用
鲁棒
次优解、满意解遗传算法能解决的问题：
优化
NP完全
NP难
高度复杂的非线性问题遗传算法与自然进化的比较自然界染色体基因等位基因 (allele)
染色体位置 (locus)
基因型 (genotype)
表型 (phenotype)
遗传算法字符串字符，特征特征值字符串位置结构参数集，译码结构面向执行的学习系统任务子系统学习子系统任务检测器 …
1d
md
…
1e
me
任务效应器执行效应器执行检测器新达尔文进化理论的主要论点
1) 个体是基本的选择目标 ;
2) 随机过程在进化中起重大作用,遗传变异大部分是偶然现象 ;
3) 基因型变异大部分是重组的产物,特别是突变 ;
4) 逐渐进化可能与表型不连续有关 ;
5) 不是所有表型变化都是自然选择的必然结果 ;
6) 进化是在适应中变化的,形式多样,不仅是基因的变化 ;
7) 选择是概率型的,而不是决定型的。
11.2 进化系统理论的形式模型进化的主要过程后生环境遗传操作符 选择环境
g p
进化系统理论的形式模型
}),,.,,,({ 1 iin AaaagGS基因型空间：
}),,.,,,({ 1 IRppppPS im表型空间：
},...,{ 1 kEPEPEP?后生环境：
),( EPgfp
PSEPGSf
：变换函数：
IRtESpq i ),,(质量函数：
11.3 达尔文进化算法
1) 建立原始种体。
2) 通过突变建立子孙。
3) 选择：
4) 返回到步骤 (1)。
11' sgs?
111 '' Zsxx …
sgs?'
Zsxx ''
)}'({m a x)( 1 xQxQ i
11.4 分类器系统分类器系统的一般结构发现
[遗传算法 ]
信用赋值
[桶链 ]
执行
[分类器系统 ]
消息来自输入接口支付消息送出输出接口
（目标）
来自内部监控器的消息规则与消息产生式规则,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 /::
学习机制分类器系统使用两个学习机制，
桶链 (bucket brigade) 算法。基于对系统的贡献,对现有规则分配一个信用值。
规则发现算法。这包括遗传算法，该算法可产生新规则，用于改善系统的知识库。
分类器系统的基本结构分类器消息表
(a)全部消息进行条件测试条件 消息规约输出接口送到环境输入接口来自环境
(a)
(b)
(b)选中分类器产生新消息分类器基本算法
1) 将输入接口全部消息放入消息表。
2) 将消息表中的全部消息与全部分类器所有条件比较,记录所有匹配。
3) 满足分类器条件部分的每组匹配,将其动作部分所规定的消息送到新的消息表。
4) 用新的消息表取代消息表中的全部消息。
5) 将消息表中的消息翻译成输出接口的要求,
产生系统当前的输出。
6) 返回到步骤 (1)。
简单的视觉分类器系统视觉向量 视野 运动向量对象检测器
1 1 1 10…
消息
1d
2d
3d
4d
性质检测器规定的值
1d
1，如果移动对象
0，其它
),( 32 dd
(0,0)，如果对象在视野的中间
(1,0)，如果对象在中心的左边
(0,1)，如果对象在中心的右边
4d
1，如果系统是对象的近邻
0，其它
5d
1，如果对象很大
0，其它
6d
1，如果对象是狭长的
0，其它规则表示规则：
IF 如果有“捕食 (prey)”(small,moving,nonstriped object),
处于视野中间 (centered),非邻近 (nonadjacent),
THEN 迅速移向对象 (ALIGN),(FAST).
可以表示为：
00#########000001 / 0100000000000000,ALIGN,FAST.
网络图
[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]
网络图的规则表示
MOVING和 ALERT之间的箭头：
00#############1/01001###########
SMALL,NOT STRIPED and ALERT到
TARGET的箭头：
00########00####,01001###########/
10001###########
11.5 桶链算法桶链 (bucket brigade) 算法基于对系统的贡献,
对现有规则分配一个信用值。主要解决多条规则同时要求被激活时的竞争问题。
例如：下面的情况下应该选择哪条规则。
0111→01# #,0000 →# #00,0001→00# 0,1100
主要问题引入信用值后的两个问题：
当多条规则同时要求被激活时，如何解决竞争问题
对一规则被激活产生过作用的那些规则如何分配信用桶链算法为解决上述两个问题，引入拍卖行和票据交易所：
当有多个分类器获得匹配时，每个分类器要出一个与其强度成正比的叫价 B
叫价高的分类器被激活并允许发送消息，同时通过票据交易所将其叫价 B提供给激活改分类器的分类器。
如此继续下去，一条规则可通过消费者获利
（增加了强度），通过规则的不断激活形成一条消费者链，直至最终消费者（达到目标）直接从环境中得到补偿。
若链中一条规则导致错误结论，则序列上改规则的强度将减弱，并且沿着序列回溯，从而产生新的消费者链举例环境 0111，强度为 0，叫价系数为 0.1。
索引号 分类器 强度
1 01# #,0000 200
2 00# 0,1000 200
3 11# #,1000 200
4 # #00,0001 200
第一步分类器 强度 消息 匹配 叫价
01# #,0000 200 E 20
00# 0,1000 200
11# #,1000 200
# #00,0001 200
第二步分类器 强度 消息 匹配 叫价
01# #,0000 180 0000
00# 0,1000 200 1 20
11# #,1000 200
# #00,0001 200 1 20
两条规则同时激活第三步分类器 强度 消息 匹配 叫价
01# #,0000 220
00# 0,1000 180 1100
11# #,1000 200 2 20
# #00,0001 180 0001 2 18
第四步分类器 强度 消息 匹配 叫价
01# #,0000 220
00# 0,1000 218
11# #,1000 180 1000
# #00,0001 162 3 16
第五步分类器 强度 消息 匹配 叫价 强度
01# #,0000 220 220
00# 0,1000 218 218
11# #,1000 196 196
# #00,0001 146 0001 206
规则 4达到目标获得补偿 60。
投标改变分类器的强度在时间 t满足 C
送去消息的分类器
),(),(),()1( 3211 tCBtCBtCBCV
1C
1C
1C
),( 1 tCB
),( 2 tCB
),( 3 tCB
对在 t-1作用的分类器投标在时间 t对分类器 C的支持分类器中的遗传算法遗传算法可产生新规则，用于改善系统的知识库。
可以在三种情况下应用 GA：
1) 引入一个参数 T（ 时间间隔），用于控制何时使用 GA。
2) 特殊情况时（如消息的条件都不能匹配）
使用 GA。
3) 系统的性能太差。
算法步骤
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)。
算法说明
1) 算法中 S0(Cj)是预知的；
2) 实现时考虑结束条件；
3) 该算法是经典 GA的变种，其中没有变异算子；
4) 新分类器的强度是由旧分类器的强度决定的。
11.6 遗传算法
遗传算法先将搜索结构编码为字符串形式,每个字符串结构被称为个体。
然后对一组字符串结构 (被称为一个群体 )进行循环操作。
每次循环被称作一代,包括一个保存字符串中较优结构的过程和一个有结构的、随机的字符串间的信息交换过程。
类似于自然进化，遗传算法通过作用于染色体上的基因寻找好的染色体来求解问题。
与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。
在遗传算法中，位字符串扮演染色体的作用，单个位扮演了基因的作用，随机产生一个体字符串的初始群体，每个个体给予一个数值评价，称为适应度，取消低适应度的个体，选择高适应度的个体参加操作。
常用的遗传算子有复制、杂交、变异和反转。
遗传算法与传统优化算法的主要不同
1) 遗传算法不是直接作用在参变量集上,而是利用参变量集的某种编码 ;
2) 遗传算法不是从单个点,而是在群体中从一个点开始搜索 ;
3) 遗传算法利用适应值信息,无需导数或其它辅助信息 ;
4) 遗传算法利用概率转移规则,而非确定性规则。
遗传算法的准备工作
1) 确定表示方案 ;
2) 确定适应值的度量 ;
3) 确定控制该算法的参数和变量 ;
4) 确定怎样指定结果及程序运行结束的标准。
基本的遗传算法
1,随机产生一个由固定长度字符串组成的初始群体 ;
2,对于字符串群体，迭代地执行下述步骤，直到选种标准被满足为止：
1) 计算群体中的每个个体字符串的适应值 ;
2) 应用下述三种操作 (至少前两种 )来产生新的群体,
复制,把现有的个体字符串复制到新的群体中。
杂交,通过遗传重组随机选择两个现有的子字符串,
产生新的字符串。
变异,将现有字符串中某一位的字符随机变异。
3,把在后代中出现的最高适应值的个体字符串指定为遗传算法运行的结果。这一结果可以是问题的解 (或近似解 )。
基本遗传算法的流程图
GEN=0
概率地选择遗传操作随机创建初始群体是否满足选中标准？
计算群体中每个个体的适应值
i:=0
i:=M
指定结果 结束
GEN:=GEN+1 是是否
（转下页）
概率地选择遗传操作根据适应值选择一个个体完成杂交
i:=i+1
i:=i+1完成繁殖
p(r)繁殖
（接上页）
基于适应值选择两个个体把新的两个孩子加到群体中
p(c)杂交 变异 p(m)
把新的孩子加入到群体中完成变异根据适应值选择一个个体把变异后个体加入到群体中表示模式所谓模式就是一个相同的构形,它描述的是一个串的子集,这个集合中的串之间在某些位上相同。
模式的复制生长方程：
这表明,一个特定的模式按照其平均适应值与群体的平均适应值之间的比率生长。
f
HftHMtHM )(),()1,(
杂交操作
杂交操作是个有结构、随机的字符串间信息交换过程。
简单的杂交操作分为三步
从当前群体 B(t)中选择两个结构：
随机选择一个整数
交换 a和 a‘中位置 x左边的元素,产生两个新的结构：
ll sssasssa '.,,'''.,,2121,
}1,.,,,2,1{ lx
lxxlxx ssssssss,,,'.,,''.,,'.,,1111,
具有强度的遗传算法
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)。
杂交操作举例
),( 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#
变异操作简单的变异操作过程如下,
每个位置的字符变量都有一个变异概率,各位置互相独立。通过随机过程选择发生变异的位置：
产生一个新结构,其中 是从对应位置 的字符变量的值域中随机选择的一个取值。 可以同样得到。
lxxx,...,,21
txxxxxx ssssssssa,..'...'...' 11111 222111
1'xs
1x
kxx ss ',...,' 2
反转操作简单反转操作的步骤如下,
1) 从当前群体中随机选择一个结构
2) 从中随机选择两个数 i’和 j’,并定义
i = min{i',j'},j=max{i',j'};
3) 颠倒 a中位置 i,j之间的部分,产生新的结构
lsssa,..21?
ljijji ssssssss,.......,12121
遗传算法举例问题：求
（ 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?
（ 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
（ 6）变异：发生变异的概率很小
（ 7）新群体的产生：
保留上一代最优个体，一般为 10%左右，至少 1个用新个体取代旧个体，随机取代或择优取代。
11000,11011,11001,10011
（ 8）重复上述操作：
说明,GA的终止条件一般人为设置；
GA只能求次优解或满意解。
分析：按第二代新群体进行遗传操作，若无变异，永远也找不到最优解 —— 择优取代有问题。
若随机的将个体 01101选入新群体中，有可能找到最优解。
0 0 0 1.0?mP
11.7 并行遗传算法基于离散门德尔模型的遗传算法由六部分组成：
1) 对给定问题求解的染色体表示；
2) 求解的原始物种；
3) 起环境作用的品质函数；
4) 可以生成子孙的个体的选择过程；
5) 一种遗传操纵子，如变异、重组；
6) 控制算法本身的参数。
并行遗传算法并行遗传算法：
1) 给定具有不同开始表型的 N个个体；
2) 每个个体计算局部最大；
3) 选择 —— 在“近邻”中选择配对；
4) 用重组和突变创建子孙；
5) 返回步骤 2。
11.8 分类器系统 Boole
Wilson 于 1987年开发了一个布尔问题的分类器系统 Boole(Wilson 1987)。 一个布尔函数变量 L 是从长度为 L的字符串到 {0,1}的映射。学习函数意味获得对任何输入字符串能给出正确输出 0 或 1的能力。
分类器强度调整算法
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。
Boole的遗传算法
1) 根据 [P]中分类器的强度，通过概率选择第一个分类器 。
2) 根据概率,与步骤 (1)相同，选择分类器,并对 和进行杂交；从结果中选择一个作为子孙，另一个被抛弃。
3) 如果步骤 (2) 未完成，则复制 形成子孙。
4) 对子孙应用变异操作，以概率 改变每个分类的等位基因。
5) 如果通过杂交生成子孙，每个父母的强度减少三分之一，
子孙的初始强度等于父母减少的总和；否则减少 的一半，
而子孙的初始强度等于减少的量。
6) 将子孙加到 [P]中。
7) 根据 [P]中分类器强度的概率分布，删除最小的一个分类器。
1C
1C
2C 1C 2C
1C
11.9 规则发现系统
RUDI的控制结构问题求解
BBA/PSP
遗传算法任务 执行弧度新规则 信用 奖励
PSP与 BBA比较
A
1R
C
3R
E
6R
H
B
2R
D
4R
F
6R
I
5R
G
7R
J
奖励,1000 0 300
初始状态结束状态不同的强度修改方案规则 PSP强度 BBA强度
1R
3R
6R
2R
4R
5R
7R
1000 648
299 567
1000 645
4 644
300 300
999 531
300 300
11.10 进化策略进化策略模仿自然进化原理作为一种求解参数优化问题的方法。最简单的实现方法如下,
(1)定义的问题是寻找 n维的实数向量 x,它使函数
(2) 双亲向量的初始群体从每维可行范围内随机选择。
(3) 子孙向量的创建是从每个双亲向量加上零均方差高斯随机变量。
(4) 根据最小误差选择向量为下一代新的双亲。
(5) 向量的标准偏差保持不变,或者没有可用的计算方法,那么处理结束。
RRxF n?:)(
11.11 进化程序设计进化程序设计 (evolutionary programming)的过程,可理解为从所有可能的计算机程序形成的空间中,搜索有高的适应值的计算机程序个体，在进化程序设计中，几百或几千个计算机程序参与遗传进化。
进化程序设计步骤
1,产生出初始群体,它由关于问题 (计算机程序 )的函数随机组合而成。
2,迭代完成下述子步骤，直至满足选种标准为止,
1) 执行群体中的每个程序，根据它解决问题的能力，给它指定一个适应值
2) 应用变异等操作创造新的计算机程序群体。基于适应值根据概率从群体中选出一个计算机程序个体，然后用合适的操作作用于该计算机程序个体。 把现有的计算机程序复制到新的群体中。通过遗传随机重组两个现有的程序,创造出新的计算机程序个体。
3,在后代中适应值最高的计算机程序个体被指定为进化程序设计的结果。这一结果可能是问题的解或近似解。
