进化计算课件

第十五章进化计算史忠植中科院计算所2023/8/61史忠植高级人工智能第十五章进化计算史忠植2023/8/31史忠植内容15.1概述15.2进化系统理论的形式模型15.3达尔文进化算法15.4遗传算法15.5遗传算法的理论基础15.6遗传算法的改进15.7遗传机器学习—分类器系统15.8桶链算法15.9规则发现系统15.10进化策略15.11进化规划2023/8/62史忠植高级人工智能内容15.1概述2023/8/32史忠植高级人工智15.1概述进化计算是通过模拟自然界中生物进化机制进行搜索的一种算法。2023/8/63史忠植高级人工智能15.1概述进化计算是通过模拟自然界中生物进化发展历史进化计算的研究起源于20世纪50年代。1965年，Holland首次提出了人工遗传操作的重要性，并把这些应用于自然系统和人工系统中。大约在同一时期：Rechenberg和Schwefel提出了进化策略。Fogel提出了进化规划。2023/8/64史忠植高级人工智能发展历史进化计算的研究起源于20世纪50年代。2023/8/发展历史

1967年，Bagley在他的论文中首次提出了遗传算法这一术语，并讨论了遗传算法在自动博弈中的应用。1970年，Cavicchio把遗传算法应用于模式识别中。第一个把遗传算法应用于函数优化的是Hollstien。

2023/8/65史忠植高级人工智能发展历史2023/8/35史忠植高级人工智能发展历史1975年是遗传算法研究的历史上十分重要的一年。这一年，Holland出版了他的著名专著《自然系统和人工系统的适应性》该书系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论（schematatheory），该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。同年，DeJong完成了他的重要论文《遗传自适应系统的行为分析》。他在该论文中所做的研究工作可看作是遗传算法发展过程中的一个里程碑，这是因为他把Holland的模式理论与他的计算使用结合起来。

2023/8/66史忠植高级人工智能发展历史1975年是遗传算法研究的历史上十分重要的一年。这一发展历史1989Goldberg对遗传算法从理论上，方法上和应用上作了系统的总结。1990年，Koza提出了遗传程序设计（GeneticProgramming）的概念。（用于搜索解决特定问题的最适计算机程序）2023/8/67史忠植高级人工智能发展历史1989Goldberg对遗传算法从理论上，方法上遗传算法与自然进化的比较自然界染色体基因等位基因(allele)染色体位置(locus)基因型(genotype)表型(phenotype)遗传算法字符串字符,特征特征值字符串位置结构参数集,译码结构2023/8/68史忠植高级人工智能遗传算法与自然进化的比较自然界染色体基因等位基因(allel新达尔文五进化理论的主要论点个体是基本的选择目标;随机过程在进化中起重大作用,遗传变异大部分是偶然现象;基因型变异大部分是重组的产物,特别是突变;逐渐进化可能与表型不连续有关;不是所有表型变化都是自然选择的必然结果;进化是在适应中变化的,形式多样,不仅是基因的变化;选择是概率型的,而不是决定型的。2023/8/69史忠植高级人工智能新达尔文五进化理论的主要论点个体是基本的选择目标;2023/进化计算的三大主流板块Holland提出的遗传算法(GeneticAlgorithm)。Rechenberg和Schwefel提出的进化策略(EvolutionaryStrategies)。Fogel提出的进化规划(EvolutionaryProgramming)，又称为进化程序设计。本章将着重介绍遗传算法，对进化策略和进化规划只作简单介绍。2023/8/610史忠植高级人工智能进化计算的三大主流板块Holland提出的遗传算法(Gene15.2进化系统理论的形式模型进化在个体群体中起作用。瓦铤顿(Waddington)指出基因型和表型之间关系的重要性(Waddington1974)。群体禁止异构环境。但是“后生环境”是多维空间。表型是基因型和环境的产物。然后表型通过异构“选择环境"发生作用。注意，这种多维选择环境与后生环境空间是不同的。现在，适应性是表型空间和选择环境空间的产物。它经常被取作一维，表示多少子孙对下一代作出贡献。基于这种想法，莫楞贝(Muhlenbein)和肯德曼(Kindermann)提出了一种称为进化系统理论的形式模型(Muhlenbein1989)。2023/8/611史忠植高级人工智能15.2进化系统理论的形式模型进化在个体群体中起进化系统理论的形式模型进化的主要过程后生环境遗传操作符选择环境gp2023/8/612史忠植高级人工智能进化系统理论的形式模型进化的主要过程后生环境遗传操作符选进化系统理论的形式模型其中，g是基因型

p是表型。基因gi的可能值称为等位基因。在门德尔(Mendel)遗传学中，假设每个基因有有限数的等位基因。2023/8/613史忠植高级人工智能进化系统理论的形式模型其中，g是基因型2023/8进化系统理论的形式模型这个变换函数给出了模型，说明表型的发展是通过基因与环境的交互作用。变换过程是高度非线性的。2023/8/614史忠植高级人工智能进化系统理论的形式模型这个变换函数给出了模型，说明表型的发展进化系统理论的形式模型质量函数q给出了具体选择环境ESi下表型的质量，其定义如下：质量定义适应度，用于达尔文选择。至今已有三种具体范例的通用模型，即

门德尔遗传学

遗传生态学

进化配子2023/8/615史忠植高级人工智能进化系统理论的形式模型质量函数q给出了具体选择环境ESi下表

门德尔遗传学在门德尔遗传学中，基因型被详细模型化，而表型和环境几乎被忽略。在遗传生态学中恰好相反。进化配子论是从社会生物学导出的模型。首先让我们讨论门德尔遗传学的选择模型。为了简单起见，我们假设一个基因具有n等位基因a1,…,an。二倍基因型以元组(ai,aj)为特征。我们定义pi,j

为总群体中基因型(ai,aj)的频度。假设基因型与表型相等。质量函数给每个表型赋值。

q(ai,aj)=qi,jqi,j可以被解释为出生率减去死亡率2023/8/616史忠植高级人工智能门德尔遗传学在门德尔遗传学中，基因型被详细模型化，而表型和

门德尔遗传学假设p’i,j是下一代表型(ai,aj)的频度。然后达尔文选择根据选择方程调整表型的分布:是群体的平均适应度。2023/8/617史忠植高级人工智能门德尔遗传学假设p’i,j是下一代表型(ai,aj)的

门德尔遗传学设

pi

是群体中等位基因的频率。如果

pi,j=pipj那么，我们得到在

GS中的一个选择方程为

2023/8/618史忠植高级人工智能门德尔遗传学设pi是群体中等位基因的频率。如果202

门德尔遗传学这个离散的选择方程可以用连续方程近似:

如果qi,j=qj,i,那么2023/8/619史忠植高级人工智能门德尔遗传学这个离散的选择方程可以用连续方程近似:如果q

门德尔遗传学这个方程很容易被证明:这个结果称作菲希尔(Fisher)基本定理。它说明平均适应度随适应度的差别呈正比例增加。实际上，全部可能的基因型仅有一部分实现。这就是遗传操纵子探索基因型空间的任务，其个体数目相当小。这些操纵子是群体遗传变异性的来源。最重要的操纵子是突变和重组。2023/8/620史忠植高级人工智能门德尔遗传学这个方程很容易被证明:这个结果称作菲希尔(Fi15.3达尔文进化算法根据定量遗传学，达尔文进化算法采用简单的突变/选择动力学。达尔文算法的一般形式可以描述如下：

是一代的双亲数目，为子孙数目。整数

称作“混杂”数。如果两个双亲混合他们的基因，则=2。仅

是最好的个体才允许产生子孙。逗号表示双亲们没有选择，加号表示双亲有选择。

2023/8/621史忠植高级人工智能15.3达尔文进化算法根据定量遗传学，达尔文进化算法采用15.3达尔文进化算法建立原始种体。通过突变建立子孙。选择：返回到步骤(1)。…2023/8/622史忠植高级人工智能15.3达尔文进化算法建立原始种体。…2023/8/32 遗传算法思想来源于生物进化过程,它是基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的搜索算法(以字符串表示状态空间)。遗传算法用概率搜索过程在该状态空间中搜索，产生新的样本。15.4遗传算法2023/8/623史忠植高级人工智能 遗传算法思想来源于生物进化过程,它是基于进化遗传算法的特点特点：通用鲁棒次优解、满意解遗传算法能解决的问题：优化NP完全NP难高度复杂的非线性问题2023/8/624史忠植高级人工智能遗传算法的特点特点：2023/8/324史忠植高级人工智遗传算法遗传算法先将搜索结构编码为字符串形式,每个字符串结构被称为个体。然后对一组字符串结构(被称为一个群体)进行循环操作。每次循环被称作一代,包括一个保存字符串中较优结构的过程和一个有结构的、随机的字符串间的信息交换过程。类似于自然进化，遗传算法通过作用于染色体上的基因寻找好的染色体来求解问题。2023/8/625史忠植高级人工智能遗传算法遗传算法先将搜索结构编码为字符串形式,每个字符串结遗传算法与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。在遗传算法中，位字符串扮演染色体的作用，单个位扮演了基因的作用，随机产生一个体字符串的初始群体，每个个体给予一个数值评价，称为适应度，取消低适应度的个体，选择高适应度的个体参加操作。常用的遗传算子有复制、杂交、变异和反转。2023/8/626史忠植高级人工智能遗传算法与自然界相似，遗传算法对求解问题的本身一无所知，遗传算法与传统优化算法的主要不同遗传算法不是直接作用在参变量集上,而是利用参变量集的某种编码;遗传算法不是从单个点,而是在群体中从一个点开始搜索;遗传算法利用适应值信息,无需导数或其它辅助信息;遗传算法利用概率转移规则,而非确定性规则。2023/8/627史忠植高级人工智能遗传算法与传统优化算法的主要不同遗传算法不是直接作用在参变量遗传算法的准备工作确定表示方案;确定适应值的度量;确定控制该算法的参数和变量;确定怎样指定结果及程序运行结束的标准。2023/8/628史忠植高级人工智能遗传算法的准备工作确定表示方案;2023/8/328史忠植基本遗传算法基本遗传算法(SimpleGeneticAlgorithm:SGA)又称为简单遗传算法，只使用选择算子、交叉算子和变异算子这三种基本的遗传算子。其遗传操作简单、容易理解，是其它遗传算法的雏形和基础。基本遗传算法的构成要素：1、染色体编码方法：首先必须对问题的解空间进行编码，使之能用遗传算法进行操作。较常用的是二进制编码方法，现在使用非二进制编码的也逐渐增多。2、适应度函数（fitnessfunction，又称为适应值／适值函数）用来评价一个染色体的好坏。2023/8/629史忠植高级人工智能基本遗传算法基本遗传算法(SimpleGeneticAl基本遗传算法的构成要素3、遗传算子•选择算子(selection)：又称为复制算子。按照某种策略从父代中挑选个体进入下一代，如使用比例选择、轮盘式选择。•交叉算子(crossover)：又称为杂交算子。将从群体中选择的两个个体，按照某种策略使两个个体相互交换部分染色体，从而形成两个新的个体。如使用单点一致交叉。•变异算子(mutation)：按照一定的概率（一般较小），改变染色体中某些基因的值。2023/8/630史忠植高级人工智能基本遗传算法的构成要素3、遗传算子2023/8/330史忠植杂交操作举例10220201[NoOffspring]Pt.ofinterchange[Crossover][Parents][Offspring]1110###0#1##0111##0001##11#010##1000#00####110#01##10####100100100##011161711110##11#0001###0#0001##11##00####11#00####110#01##10#000##01111#01##10#2023/8/631史忠植高级人工智能杂交操作举例10220201[NoOffspring]Pt变异操作简单的变异操作过程如下:每个位置的字符变量都有一个变异概率,各位置互相独立。通过随机过程选择发生变异的位置：产生一个新结构,其中是从对应位置的字符变量的值域中随机选择的一个取值。可以同样得到。2023/8/632史忠植高级人工智能变异操作简单的变异操作过程如下:2023/8/332史忠植反转操作简单反转操作的步骤如下:从当前群体中随机选择一个结构从中随机选择两个数i’和j’,并定义i=min{i',j'},j=max{i',j'};颠倒a中位置i、j之间的部分,产生新的结构2023/8/633史忠植高级人工智能反转操作简单反转操作的步骤如下:2023/8/333史忠植基本遗传算法的构成要素4、运行参数N：群体大小，即群体中包含的个体的数量。T：遗传算法终止的进化代数。Pc：交叉概率，一般取为0.4～0.99。Pm：变异概率，一般取为0.0001～0.1。2023/8/634史忠植高级人工智能基本遗传算法的构成要素4、运行参数2023/8/334史忠植基本遗传算法随机产生一个由固定长度字符串组成的初始群体;对于字符串群体，迭代地执行下述步骤，直到选种标准被满足为止：计算群体中的每个个体字符串的适应值;应用下述三种操作(至少前两种)来产生新的群体:复制:把现有的个体字符串复制到新的群体中。杂交:通过遗传重组随机选择两个现有的子字符串,产生新的字符串。变异:将现有字符串中某一位的字符随机变异。把在后代中出现的最高适应值的个体字符串指定为遗传算法运行的结果。这一结果可以是问题的解(或近似解)。2023/8/635史忠植高级人工智能基本遗传算法随机产生一个由固定长度字符串组成的初始群体;20基本遗传算法流程图GEN=0概率地选择遗传操作随机创建初始群体计算群体中每个个体的适应值i:=0显示结果结束GEN:=GEN+1是是否（转下页）i=N?GEN=M？12023/8/636史忠植高级人工智能基本遗传算法流程图GEN=0概率地选择遗传操作随机创建初始群概率地选择遗传操作根据适应值选择一个个体完成交叉i:=i+1i:=i+1复制个体p(r)选择（接上页）基于适应值选择两个个体把新的两个孩子加到群体中p(c)交叉变异p(m)把新的孩子加入到群体中完成变异根据适应值选择一个个体把变异后个体加入到群体中12023/8/637史忠植高级人工智能概率地选择遗传操作根据适应值选完成交叉i:=i+1i:=i+轮盘式选择首先计算每个个体i被选中的概率然后根据概率的大小将将圆盘分为n个扇形，每个扇形的大小为。选择时转动轮盘，参考点r落到扇形i则选择个体i。......p1p2pir2023/8/638史忠植高级人工智能轮盘式选择首先计算每个个体i被选中的概率......p1单点一致交叉首先以概率pc从种群中随机地选择两个个体p1、p2。在{1,2,...,l}内随机选择一个数i,作为交叉的位置，称为交叉点。然后将两个个体交叉点后面的部分交换。例如：

01101011000110011001110001100111001011002023/8/639史忠植高级人工智能单点一致交叉首先以概率pc从种群中随机地选择两个个体p1、p一致变异以概率pm对种群中所有个体的每一位进行变异。对于个体pi的第j位，在[0,1]的范围内随机地生成一个数r,如果r<pm,则对第j位取反，否则保持第j位不变。2023/8/640史忠植高级人工智能一致变异以概率pm对种群中所有个体的每一位进行变异。2023遗传算法举例问题：求（1）编码：

此时取均长为5，每个染色体（2）初始群体生成：群体大小视情况而定，此处设置为4，随机产生四个个体：编码：01101，11000，01000，10011解码：1324819适应度：16957664361（3）适应度评价：2023/8/641史忠植高级人工智能遗传算法举例问题：求2023/8/341史忠植高级人工智（4）选择：选择概率个体：01101，11000，01000，10011适应度：16957664361选择概率：0.140.490.060.31选择结果：01101，11000，11000，10011（5）交叉操作：发生交叉的概率较大哪两个个体配对交叉是随机的交叉点位置的选取是随机的（单点交叉）01101011001100011011110001100110011100002023/8/642史忠植高级人工智能（4）选择：选择概率2023/8/342史忠植高级人工智（6）变异：发生变异的概率很小（7）新群体的产生：保留上一代最优个体，一般为10%左右，至少1个用新个体取代旧个体，随机取代或择优取代。11000，11011，11001，10011（8）重复上述操作：说明：GA的终止条件一般人为设置；

GA只能求次优解或满意解。分析：按第二代新群体进行遗传操作，若无变异，永远也找不到最优解——择优取代有问题。若随机的将个体01101选入新群体中，有可能找到最优解。2023/8/643史忠植高级人工智能（6）变异：发生变异的概率很小2023/8/343史忠植15.5遗传算法的理论基础15.5.1模式的定义遗传算法的理论基础是遗传算法的二进制表达式及模式的含义。模式是能对染色体之间的相似性进行解释的模板。[定义1]设GA的个体,记集合则称为一个模式，其中＊是通配符。即模式(schema)是含有通配符(*)的一类字符串的通式表达。每个“*”可以取“1”或者“0”。2023/8/644史忠植高级人工智能15.5遗传算法的理论基础15.5.1模式的定义2023模式举例模式*10101110与以下两个字符串匹配：010101110110101110而模式*1010＊110与以下四个字符串匹配：0101001100101011101101001101101011102023/8/645史忠植高级人工智能模式举例模式*101011102023/8/345史忠植模式的定义[定义2]一个模式s的阶是出现在模式中的“0”和“1”的数目，记为o(s)。如：模式“0****”的阶为1，模式“10*1*”的阶为3。[定义3]一个模式s的长度是出现在模式中第一个确定位置和最后一个确定位置之间的距离，记为。如：模式“01***”的长度为1，模式“0***1”的长度为3。2023/8/646史忠植高级人工智能模式的定义[定义2]一个模式s的阶是出现在模式中的“0”和15.5.2模式定理假定在给定的时间步t,一个特定的模式s在群体P(t)中包含由m个代表串，记为m=m(s,t)。首先，我们暂不考虑交叉和变异操作。每个串根据适应值的大小获得不同的复制概率。串i的复制概率为：（1)2023/8/647史忠植高级人工智能15.5.2模式定理假定在给定的时间步t,一个特定的模式15.5.2模式定理则在群体P(t+1)中，模式s的代表串的数量的期望值为：其中，表示模式s在t时刻的所有代表串的适应值的均值，称为模式s的适应值。（2）2023/8/648史忠植高级人工智能15.5.2模式定理则在群体P(t+1)中，模式s的代表15.5.2模式定理若记P(t)中所有个体的适应值的平均值为：（3）则(2)式可以表示为：2023/8/649史忠植高级人工智能15.5.2模式定理若记P(t)中所有个体的适应值的平均15.5.2模式定理(3)式表明，模式s的代表串的数目随时间增长的幅度正比于模式s的适应值与群体平均适应值的比值。即：适应值高于群体平均值的模式在下一代的代表串数目将会增加，而适应值低于群体平均值的模式在下一代的代表串数目将会减少。假设模式的适应值为,其中c是一个常数，则(3)式可写为：2023/8/650史忠植高级人工智能15.5.2模式定理(3)式表明，模式s的代表串的数目随15.5.2模式定理（4）上式表明，在平均适应值之上（之下）的模式，将会按指数增长（衰减）的方式被复制。2023/8/651史忠植高级人工智能15.5.2模式定理（4）上式表明，在平均适应值之上（之15.5.2模式定理复制的结果并没有生成新的模式。因而，为了探索搜索空间中的未搜索部分，需要利用交叉和变异操作。下面先探索交叉对模式的影响。模式s1=“*1****0”和s2=“***10**”交叉会改变模式的一部分，模式的长度越长，被破坏的概率越大。2023/8/652史忠植高级人工智能15.5.2模式定理复制的结果并没有生成新的模式。因而，15.5.2模式定理假定模式s在交叉后不被破坏的概率为ps，则：若交叉概率为pc,则s不被破坏的概率为2023/8/653史忠植高级人工智能15.5.2模式定理假定模式s在交叉后不被破坏的概率为p15.5.2模式定理（5）所以，再考虑交叉时，(3)式可表示为最后，考虑变异算子对模式的影响。变异算子以概率pm随机地改变个体某一位的值。只有当o(s)个确定位的值不被破坏时，模式s才不被破坏。2023/8/654史忠植高级人工智能15.5.2模式定理（5）所以，再考虑交叉时，(3)式可15.5.2模式定理模式s在变异后不被破坏的概率：Pm<<1,可近似地表示为2023/8/655史忠植高级人工智能15.5.2模式定理模式s在变异后不被破坏的概率：20215.5.2模式定理（6）因此，考虑交叉和变异时，(3)式可表示为2023/8/656史忠植高级人工智能15.5.2模式定理（6）因此，考虑交叉和变异时，(3)15.5.2模式定理由(6)我们得到一个重要的定理。[定理1]模式定理(SchemaTheorem)适应值在群体适应值之上的、长度较短的、低阶的模式在GA的迭代中将按指数增长方式被复制。2023/8/657史忠植高级人工智能15.5.2模式定理由(6)我们得到一个重要的定理。2015.5.3积木块假设Holland和Goldberg在模式定理的基础上提出了“积木块假设”(BuildingBlockHypothesis):低阶、长度较短、高于平均适应度的模式(积木块)在遗传算子的作用下，相互结合，能生成高阶、长度较长、适应度较高的模式，并得到全局最优解。2023/8/658史忠植高级人工智能15.5.3积木块假设Holland和Goldberg在15.5.4遗传算法的收敛性分析算法的收敛性可以定义如下：定义：若算法在t时刻的种群xt满足则称算法收敛到x0。关于遗传算法的收敛性，Michalewicz证明了基于压缩原理的收敛性定理。而Rudolph证明了基于Markov链的收敛性定理。2023/8/659史忠植高级人工智能15.5.4遗传算法的收敛性分析算法的收敛性可以定义如下15.6遗传算法的改进遗传算法的局限性：遗传算法得到了广泛应用，但也暴露了一些问题，如：遗传算法在解决某些问题时速度较慢；遗传算法对编码方案的依赖性较强，算法的鲁棒性不够好等。这些问题主要归结为：（1）上位(epistasis)效应上位效应包括两个方面：多基因性和基因多效性。2023/8/660史忠植高级人工智能15.6遗传算法的改进遗传算法的局限性：2023/8/315.6遗传算法的改进（2）编码方案最初使用最多的是二进制位串，但此类编码并不适合一些实际问题。现在人们已经探索了许多其它方案，如浮点表示、树形表示等等。（3）积木块假设积木块假设是否成立，是否一定存在短的、低阶的、高适应值的积木块？若构成问题最优解的所有低阶模式的适应值都较低，这是GA很难收敛到最优解，此类问题称为“欺骗问题”。2023/8/661史忠植高级人工智能15.6遗传算法的改进（2）编码方案2023/8/36115.6遗传算法的改进（4）早熟收敛即GA收敛到一个局部最优解。Schraudolph和Belew提出“动态参数编码”方案来解决早熟收敛问题。关于遗传算法的一些改进措施，有兴趣的同学可查找相关资料。2023/8/662史忠植高级人工智能15.6遗传算法的改进（4）早熟收敛2023/8/36215.7遗传机器学习

－－分类器系统机器学习是人工智能的一个重要研究领域，也是人工智能的一个重要的应用领域。遗传机器学习(GeneticsBasedMachineLearning,GBML)时将遗传算法与机器学习系统相结合的产物。2023/8/663史忠植高级人工智能15.7遗传机器学习

－－分类器系统机器学习是人工智能的遗传机器学习系统的一般框架任务子系统学习子系统任务检测器……任务效应器执行效应器执行检测器2023/8/664史忠植高级人工智能遗传机器学习系统的一般框架任务子系统学习子系统任务检测器……匹兹堡方法和密西根方法遗传机器学习有两种重要的实现方法：一种是由匹兹堡(Pittsburgh)大学的DeJong和他的学生Smith提出的。该方法用整个规则集合表示一个个体，GAs维护一个包含一定数目的候选规则集的种群。这种方法称为匹兹堡方法。2023/8/665史忠植高级人工智能匹兹堡方法和密西根方法遗传机器学习有两种重要的实现方法：20匹兹堡方法和密西根方法另一种方法是由密西根(Michigan)大学的Holland和他的学生Reitman提出的。该方法每个个体表示一条规则，而整个种群就是规则集。这种方法称为密西根方法。Holland提出的分类器系统采用的是密西根方法。2023/8/666史忠植高级人工智能匹兹堡方法和密西根方法另一种方法是由密西根(Michigan分类器系统Holland和他的同事提出了一种分类器系统的认知模型,其中的规则不是规则集,而是遗传算法操纵的内部实体。图11.3给出了分类器系统的一般结构,从分类器系统看学习,它由三层动作构成,即执行子系统、信用赋值子系统和发现子系统。2023/8/667史忠植高级人工智能分类器系统Holland和他的同事提出了一种分类器系统的认知分类器系统发现[遗传算法]信用赋值[桶链]执行[分类器系统]消息来自输入接口支付消息送出输出接口（目标）来自内部监控器的消息图11.3分类器系统的一般结构2023/8/668史忠植高级人工智能分类器系统发现[遗传算法]信用赋值[桶链]执行[分类器系统分类器系统

执行子系统处在最低层,直接与环境进行交互。它与专家系统相同,由产生式规则构成。但是,它们是消息传送,高度平行。这类规则称作分类器。

分类器系统中的学习,要求环境提供反馈,确认所希望的状态是否达到。系统将评价这些规则的有效性,这些活动常常称作信用赋值。有些特定算法专门用来实现信用赋值,例如,桶链算法。

最后一层是发现子系统,该系统必须产生新的规则,取代当前用处不大的规则。通过系统累积的经验产生规则。系统根据适应值,使用遗传算法选择、重组和取代规则。2023/8/669史忠植高级人工智能分类器系统执行子系统处在最低层,直接与环境进行分类器系统分类器系统是平行执行、消息传递和基于规则的系统。在简单的方案中,消息采用规定的字母,全部为固定长度。全部规则采用条件/动作形式。每个条件规定必须满足的信息,每个动作规定当条件满足时所发送的消息。为了方便,假设消息采用长度为l的二进制字符串记录,字符采用子集{1,0,#}。2023/8/670史忠植高级人工智能分类器系统分类器系统是平行执行、消息传递和基于规规则与消息产生式规则：IF<条件>THEN<动作>约定：条件的长度是固定的，用二进制数表示。定义：Ifsj=1orsj=0,thenmj=sjIfsj=#,thenmjcanbeeither1or0.2023/8/671史忠植高级人工智能规则与消息产生式规则：IF<条件>THEN<动作>I规则与消息满足要求的全部消息构成子集,即每个子集是在消息空间的一个超平面。分类器系统是由一组分类器{C1,C2,…,CN}、一个消息表、输入接口、输出接口构成。每部分的主要功能如下:

(1)输入接口将当前环境状态翻译成标准消息。

(2)分类器根据规则,规定系统处理消息的过程。

(3)消息表包含当前全部消息。

(4)输出接口将结果消息翻译成效应器动作,修改环境状态。2023/8/672史忠植高级人工智能规则与消息满足要求的全部消息构成子集,即每个子集是在分类器系统的基本结构分类器消息表(a)全部消息进行条件测试条件消息规约输出接口送到环境输入接口来自环境(a)(b)(b)选中分类器产生新消息2023/8/673史忠植高级人工智能分类器系统的基本结构分类器消息表(a)全部消息进行条件测试条分类器基本算法将输入接口全部消息放入消息表。将消息表中的全部消息与全部分类器所有条件比较,记录所有匹配。满足分类器条件部分的每组匹配,将其动作部分所规定的消息送到新的消息表。用新的消息表取代消息表中的全部消息。将消息表中的消息翻译成输出接口的要求,产生系统当前的输出。返回到步骤(1)。2023/8/674史忠植高级人工智能分类器基本算法将输入接口全部消息放入消息表。2023/8/3简单的视觉分类器系统视觉向量视野运动向量对象检测器11110…消息2023/8/675史忠植高级人工智能简单的视觉分类器系统视觉向量视野运动向量对象检测器11110性质检测器规定的值1，如果移动对象0，其它(0,0)，如果对象在视野的中间(1,0)，如果对象在中心的左边(0,1)，如果对象在中心的右边1，如果系统是对象的近邻0，其它1，如果对象很大0，其它1，如果对象是狭长的0，其它2023/8/676史忠植高级人工智能性质检测器规定的值1，如果移动对象0，其它(0,0)，如果对规则表示规则：IF如果有“捕食(prey)”(small,moving,nonstripedobject),处于视野中间(centered),非邻近(nonadjacent),THEN迅速移向对象(ALIGN),(FAST).可以表示为：00#########000001/0100000000000000,ALIGN,FAST.2023/8/677史忠植高级人工智能规则表示规则：2023/8/377史忠植高级人工智能网络图[MOVING][SMALL][NOTSTRIPED][NEAR][FAR]01001[ALERT]10001[TARGET]11001[PORSUE]11010[APPROACH]11011[FLEE]11100[FREEZE]10010[DANGER]2023/8/678史忠植高级人工智能网络图[MOVING][SMALL][NOTSTRIPED网络图的规则表示MOVING和ALERT之间的箭头：00#############1/01001###########SMALL，NOTSTRIPEDandALERT到TARGET的箭头：00########00####，01001###########/10001###########2023/8/679史忠植高级人工智能网络图的规则表示MOVING和ALERT之间的箭头：2023学习机制分类器系统使用两个学习机制，桶链(bucketbrigade)算法。基于对系统的贡献,对现有规则分配一个信用值。规则发现算法。这包括遗传算法，该算法可产生新规则，用于改善系统的知识库。2023/8/680史忠植高级人工智能学习机制分类器系统使用两个学习机制，2023/8/380史忠15.8桶链算法桶链(bucketbrigade)算法基于对系统的贡献,对现有规则分配一个信用值。主要解决多条规则同时要求被激活时的竞争问题。例如：下面的情况下应该选择哪条规则。0111→01##：0000→##00：0001→00#0：11002023/8/681史忠植高级人工智能15.8桶链算法桶链(bucketbrigad主要问题引入信用值后的两个问题：当多条规则同时要求被激活时，如何解决竞争问题对一规则被激活产生过作用的那些规则如何分配信用2023/8/682史忠植高级人工智能主要问题引入信用值后的两个问题：2023/8/382史忠植桶链算法为解决上述两个问题，引入拍卖行和票据交易所：当有多个分类器获得匹配时，每个分类器要出一个与其强度成正比的叫价B叫价高的分类器被激活并允许发送消息，同时通过票据交易所,将其叫价B提供给激活的分类器。如此继续下去，一条规则可通过消费者获利（增加了强度），通过规则的不断激活形成一条消费者链，直至最终消费者（达到目标）直接从环境中得到补偿。若链中一条规则导致错误结论，则序列上该规则的强度将减弱，并且沿着序列回溯，从而产生新的消费者链2023/8/683史忠植高级人工智能桶链算法为解决上述两个问题，引入拍卖行和票据交易所：2023举例环境0111，强度为0，叫价系数为0.1。索引号 分类器 强度1 01##：0000 2002 00#0：1000 2003 11##：1000 2004 ##00：0001 2002023/8/684史忠植高级人工智能举例环境0111，强度为0，叫价系数为0.1。2023/8/第一步分类器 强度消息匹配叫价01##：0000200E2000#0：100020011##：1000200##00：00012002023/8/685史忠植高级人工智能第一步分类器 强度消息匹配第二步分类器 强度消息匹配叫价01##：0000180000000#0：100020012011##：1000200##00：0001200120两条规则同时激活2023/8/686史忠植高级人工智能第二步分类器 强度消息匹配第三步分类器 强度消息匹配叫价01##：000022000#0：1000180110011##：1000200220##00：000118000012182023/8/687史忠植高级人工智能第三步分类器 强度消息匹配第四步分类器 强度消息匹配叫价01##：000022000#0：100021811##：10001801000##00：00011623162023/8/688史忠植高级人工智能第四步分类器 强度消息匹配第五步分类器 强度消息匹配叫价强度01##：000022022000#0：100021821811##：1000196196##00：00011460001206规则4达到目标获得补偿60。2023/8/689史忠植高级人工智能第五步分类器 强度消息匹配叫价投标改变分类器的强度在时间t满足C送去消息的分类器对在t-1作用的分类器投标在时间t对分类器C的支持2023/8/690史忠植高级人工智能投标改变分类器的强度在时间t满足C对在t-1作在时间t对分类分类器中的遗传算法遗传算法可产生新规则，用于改善系统的知识库。可以在三种情况下应用GA：引入一个参数T（时间间隔），用于控制何时使用GA。特殊情况时（如消息的条件都不能匹配）使用GA。系统的性能太差。2023/8/691史忠植高级人工智能分类器中的遗传算法遗传算法可产生新规则，用于改善系统的知识库算法步骤t=0，随机生成集合Bt，|Bt|=M（大小）；计算Bt中全体分类器的平均强度Vt，对每个分类器赋予一个标准强度St(Cj)/Vt；给Bt中的每个分类器Cj赋予一个与其标准强度成正比的概率，并根据Bt中的概率分布，从Bt中选取n个分类器，n<<M；对每个分类器应用交叉算子，生成2n个分类器；将Bt中的2n个强度最低的分类器用新生成的2n个取代；t=t+1，转(2)。2023/8/692史忠植高级人工智能算法步骤t=0，随机生成集合Bt，|Bt|=M（大小）；20算法说明算法中S0(Cj)是预知的；实现时考虑结束条件；该算法是经典GA的变种，其中没有变异算子；新分类器的强度是由旧分类器的强度决定的。2023/8/693史忠植高级人工智能算法说明算法中S0(Cj)是预知的；2023/8/393史忠分类器强度调整算法将与所选动作相同的分类器形成子集[M]，称作动作集[A]。将不在[M]中的其它分类器放在集合NOT[A]中。在[A]中的全部分类器强度减少一个分数e。如果系统决策正确，则将赢利量R分配给[A]的强度;如果系统决策错误，则将赢利量R'(其中0≤R'≤R)分配给[A]的强度，从[A]的强度减少一个分数p。至少R'和p中的一个为0。从NOT[A]中的强度减去一个分数t。2023/8/694史忠植高级人工智能分类器强度调整算法将与所选动作相同的分类器形成子集[M]，15.9规则发现系统在规则发现系统中,学习经常是首先评价系统现有的规则质量,然后进行修改。Grefenstette研制了一种规则发现系统RUDI。问题求解级由简化的分类器系统组成。学习级是对知识结构群体进行遗传算法操作,每一个表示为一组规则表。知识结构的整个行为控制这些结构的复制。在RUDI中,信用赋值方法赢利共享规划(Profit-SharingPlan,简称PSP)和桶链算法(BBA)对每个规则提供互补的效用信息。根据期望的外部奖励,PSP-强度对规则效用提供更精确的评估。当问题求解时它被用作冲突消解。与此相反,BBA-强度表示规则之间的动态相关性,规则点火依次会聚到相似水平。这种测度可以用作一组协作规则的聚类。

2023/8/695史忠植高级人工智能15.9规则发现系统在规则发现系统中,学习经常规则发现系统

Grefenstette提出一种强度修改方案称作嬴利共享规划PSP。在这种方案中问题求解划分成情节,按所接受的外部奖励区分。如果任何步情节在投标竞争中获胜,则认为该规则在该情节活动。在情节t,PSP修改每个活动规则Ri的强度Si(t)如下:

Si(t+1)=Si(t)-bSi(t)+bp(t),其中,p(t)称作在情节结束时所获得的外部奖励,即当获得外部奖励,从每个活动规则搜集投