高级人工智能第十五章进化理论

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

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

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

2023/1/176发展历史1989Goldberg对遗传算法从理论上，方法上和应用上作了系统的总结。1990年，Koza提出了遗传程序设计（GeneticProgramming）的概念。（用于搜索解决特定问题的最适计算机程序）2023/1/177遗传算法与自然进化的比较自然界染色体基因等位基因(allele)染色体位置(locus)基因型(genotype)表型(phenotype)遗传算法字符串字符,特征特征值字符串位置结构参数集,译码结构2023/1/178新达尔文五进化理论的主要论点个体是基本的选择目标;随机过程在进化中起重大作用,遗传变异大部分是偶然现象;基因型变异大部分是重组的产物,特别是突变;逐渐进化可能与表型不连续有关;不是所有表型变化都是自然选择的必然结果;进化是在适应中变化的,形式多样,不仅是基因的变化;选择是概率型的,而不是决定型的。2023/1/179进化计算的三大主流板块Holland提出的遗传算法(GeneticAlgorithm)。Rechenberg和Schwefel提出的进化策略(EvolutionaryStrategies)。Fogel提出的进化规划(EvolutionaryProgramming)，又称为进化程序设计。本章将着重介绍遗传算法，对进化策略和进化规划只作简单介绍。2023/1/171015.2进化系统理理论的形式式模型进化在个体体群体中起起作用。瓦瓦铤顿(Waddington)指出基因型型和表型之之间关系的的重要性(Waddington1974)。群体禁止异异构环境。。但是“后后生环境””是多维空空间。表型型是基因型型和环境的的产物。然然后表型通通过异构““选择环境境"发生作作用。注意意，这种多多维选择环环境与后生生环境空间间是不同的的。现在，，适应性是是表型空间间和选择环环境空间的的产物。它它经常被取取作一维，，表示多少少子孙对下下一代作出出贡献。基于这种想想法，莫楞楞贝(Muhlenbein)和肯德曼(Kindermann)提出了一种种称为进化系统统理论的形形式模型(Muhlenbein1989)。。2022/12/3111进化系统理理论的形式式模型进化的主要要过程后生环境遗传操作符符选择环境gp2022/12/3112进化系统理理论的形式式模型其中，g是基因型p是表型。基因gi的可能值称称为等位基基因。在门德尔(Mendel)遗传传学学中中，，假假设设每每个个基基因因有有有有限限数数的的等等位位基基因因。。2022/12/3113进化系统统理论的的形式模模型这个变换换函数给给出了模模型，说说明表型型的发展展是通过过基因与环境境的交互互作用。。变换过程程是高度度非线性性的。2022/12/3114进化系统统理论的的形式模模型质量函数数q给出了具具体选择择环境ESi下表型的的质量，，其定义如如下：质量定义义适应度度，用于于达尔文文选择。。至今已已有三种种具体范范例的通通用模型型，即门德尔遗遗传学遗传生态态学进化配子子2022/12/3115门德尔尔遗传传学在门德德尔遗遗传学学中，，基因因型被被详细细模型型化，，而表表型和和环境几几乎被被忽略略。在在遗传传生态态学中恰好好相反反。进化配配子论论是从从社会会生物物学导导出的的模型型。首先让让我们们讨论论门德德尔遗遗传学学的选选择模模型。。为了了简单单起见见，我我们假假设一一个基基因具具有n等位基因a

q(ai,aj)=qi,jqi,j可以被解释为出生率减去死亡率2022/12/3116门德尔遗传传学假设p’i,j是下一代表表型(ai,aj)的频度。然然后达尔文文选择根据选选择方程调调整表型的的分布:是群体的平平均适应度度。2022/12/3117门德尔遗传传学设pi是群体中等等位基因的的频率。如如果pi,j=pipj那么，我们们得到在GS中的一个选选择方程为为2022/12/3118门德德尔尔遗遗传传学学这个个离离散散的的选选择择方方程程可可以以用用连连续续方方程程近近似似:如果果qi,j=qj,i,那么么2022/12/3119门德德尔尔遗遗传传学学这个个方方程程很很容容易易被被证证明明:这个个结结果果称称作作菲菲希希尔尔(Fisher)基本本定定理理。。它它说说明明平平均均适适应应度度随随适适应应度度的的差差别别呈呈正正比比例例增增加加。。实实际际上上，，全全部部可可能能的的基基因因型型仅仅有有一一部部分分实实现现。。这这就就是是遗遗传传操操纵纵子子探探索索基基因因型型空空间间的的任任务务，，其其个个体体数数目目相相当当小小。。这这些些操操纵纵子子是是群群体体遗遗传传变变异异性性的的来来源源。。最重重要要的的操操纵纵子子是是突突变变和和重重组组。。2022/12/312015.3达尔文进化算算法根据定量遗传传学，达尔文文进化算法采采用简单的突变/选择择动力学。达尔文算法的的一般形式可可以描述如下下：是一代的双亲亲数目，为子孙数目。。整数称作“混杂””数。如果两个双亲亲混合他们的的基因，则=2。仅是最好的个体体才允许产生生子孙。逗号表示双亲亲们没有选择择，加号表示示双亲有选择择。2022/12/312115.3达尔文进化算算法建立原始种体体。通过突变建立立子孙。选择：返回到步骤(1)。…2022/12/3122遗传算法思想想来源于生物物进化过程,它是基于于进化过程中中的信息遗传传机制和优胜胜劣汰的自然然选择原则的的搜索算法(以字符串表表示状态空间间)。遗传算算法用概率搜搜索过程在该该状态空间中中搜索，产生生新的样本。。15.4遗传算法2022/12/3123遗传算法的特特点特点：通用鲁棒次优解、满意意解遗传算法能解解决的问题：：优化NP完全NP难高度复杂的非非线性问题2022/12/3124遗传算算法遗传传算算法法先先将将搜搜索索结结构构编编码码为为字字符符串串形形式式,每每个个字字符符串串结结构构被被称称为为个个体体。。然后后对对一一组组字字符符串串结结构构(被被称称为为一一个个群群体体)进进行行循循环环操操作作。。每每次次循循环环被被称称作作一一代代,包包括括一一个个保保存存字字符符串串中中较较优优结结构构的的过过程程和和一一个个有有结结构构的的、、随随机机的的字字符符串串间间的的信信息息交交换换过过程程。。类似于自自然进化化，遗传传算法通通过作用用于染色色体上的的基因寻寻找好的的染色体体来求解解问题。。2022/12/3125遗传算法法与自然界界相似，，遗传算算法对求求解问题题的本身身一无所所知，它它所需要要的仅是是对算法法所产生生的每个个染色体体进行评评价，并并基于适适应值来来选择染染色体，，使适应应性好的的染色体体有更多多的繁殖殖机会。。在遗传算算法中，，位字符符串扮演演染色体体的作用用，单个个位扮演演了基因因的作用用，随机机产生一一个体字字符串的的初始群群体，每每个个体体给予一一个数值值评价，，称为适适应度，，取消低低适应度度的个体体，选择择高适应应度的个个体参加加操作。。常用的遗遗传算子子有复制制、杂交交、变异异和反转转。2022/12/3126遗传算法法与传统统优化算算法的主主要不同同遗传算法法不是直直接作用用在参变变量集上上,而而是利用用参变量量集的某某种编码码;遗传算法法不是从从单个点点,而而是在群群体中从从一个点点开始搜搜索;遗传算法法利用适适应值信信息,无无需导导数或其其它辅助助信息;遗传算法法利用概概率转移移规则,而非非确定性性规则。。2022/12/3127遗传算法的的准备工作作确定表示方方案;确定适应值值的度量;确定控制该该算法的参参数和变量量;确定怎样指指定结果及及程序运行行结束的标标准。2022/12/3128基本遗传算算法基本遗传算算法(SimpleGeneticAlgorithm:SGA)又称为简单单遗传算法法，只使用用选择算子子、交叉算算子和变异异算子这三三种基本的的遗传算子子。其遗传传操作简单单、容易理理解，是其其它遗传算算法的雏形形和基础。。基本遗传算算法的构成成要素：1、染色体体编码方法法：首先必必须对问题题的解空间间进行编码码，使之能能用遗传算算法进行操操作。较常常用的是二二进制编码码方法，现现在使用非非二进制编编码的也逐逐渐增多。。2、适应度度函数（fitnessfunction，，又称为适应应值／适值值函数）用用来评价一一个染色体体的好坏。。2022/12/3129基本遗传算算法的构成成要素3、遗传算算子•选择算子(selection)：又称为复制制算子。按按照某种策策略从父代代中挑选个个体进入下下一代，如如使用比例例选择、轮轮盘式选择择。•交叉算子(crossover)：又称为杂交交算子。将将从群体中中选择的两两个个体，，按照某种种策略使两两个个体相相互交换部部分染色体体，从而形形成两个新新的个体。。如使用单单点一致交交叉。•变异算子(mutation)：按照一定的概概率（一般较较小），改变变染色体中某某些基因的值值。2022/12/3130杂交操作举例例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#2022/12/3131变异操操作简单的的变异异操作作过程程如下下:每个位位置的的字符符变量量都有有一个个变异异概率率,各各位位置互互相独独立。。通过过随机机过程程选择择发生生变异异的位位置：：产生一一个新新结构构,其中是是从从对应应位置置的的字字符变变量的的值域域中随随机选选择的的一个个取值值。可可以以同样样得到到。2022/12/3132反转操操作简单反反转操操作的的步骤骤如下下:从当前前群体体中随随机选选择一一个结结构从中随随机选选择两两个数数i’和j’,并定义义i=min{i',j'},j=max{i',j'};颠倒a中位置置i、j之间间的的部部分分,产产生生新新的的结结构构2022/12/3133基本本遗遗传传算算法法的的构构成成要要素素4、、运运行行参参数数N：：群体体大大小小，，即即群群体体中中包包含含的的个个体体的的数数量量。。T：遗传算算法终终止的的进化化代数数。Pc：交叉概概率，，一般般取为为0.4～0.99。。Pm：变异概概率，，一般般取为为0.0001～～0.1。。2022/12/3134基本遗遗传算算法随机产产生一一个由由固定定长度度字符符串组组成的的初始始群体体;对于字字符串串群体体，迭迭代地地执行行下述述步骤骤，直直到选选种标标准被被满足足为止止：计算群群体中中的每每个个个体字字符串串的适适应值值;应用下下述三三种操操作(至少少前两两种)来产产生新新的群群体:复制:把把现有有的个个体字字符串串复制制到新新的群群体中中。杂交:通通过遗遗传重重组随随机选选择两两个现现有的的子字字符串串,产产生新新的字字符串串。变异:将将现有有字符符串中中某一一位的的字符符随机机变异异。把在后后代中中出现现的最最高适适应值值的个个体字字符串串指定定为遗遗传算算法运运行的的结果果。这这一结结果可可以是是问题题的解解(或或近似似解)。2022/12/3135基本遗遗传算算法流流程图图GEN=0概率地选择遗传操作随机创建初始群体计算群体中每个个体的适应值i:=0显示结果结束GEN:=GEN+1是是否（转下页）i=N?GEN=M？12022/12/3136概率地地选择择遗传传操作作根据适适应值值选择一个个个体体完成交交叉i:=i+1i:=i+1复制个个体p(r)选择（接上上页））基于适适应值值选择两个个个体体把新的的两个个孩子加到到群体体中p(c)交叉变异p(m)把新的孩子子加入到群体中中完成变异根据适应值值选择一个个体体把变异后个个体加入到群体体中12022/12/3137轮盘式选择择首先计算每每个个体i被选中的概概率然后根据概概率的大小小将将圆盘盘分为n个扇形，每每个扇形的的大小为。。选选择时转动动轮盘，参参考点r落到扇形i则选择个体体i。......p1p2pir2022/12/3138单点点一一致致交交叉叉首先以概率pc从种群中随机机地选择两个个个体p1、p2。在{1,2,...,l}内随机选择一一个数i,作为交叉的位位置，称为交交叉点。然后后将两个个体体交叉点后面面的部分交换换。例如：2022/12/3139一致变异以概率pm对种群中所有有个体的每一一位进行变异异。对于个体pi的第j位，在[0,1]的范围围内随机地生生成一个数r,如果r<pm,则对第j位取反，否则则保持第j位不变。2022/12/3140遗传算法举例例问题：求（1）编码：此时取取均长长为5，每每个染染色体体（2））初始始群体体生成成：群群体大大小视视情况况而定定，此此处设设置为为4，，随机机产生生四个个个体体：编码：：01101，11000，01000，10011解码：：1324819适应度（3））适应应度评评价：：2022/12/3141（4））选择择：选选择概概率个体：：01101，11000，01000，10011适应度选择概概率：选择结结果：：01101，，11000，，11000，，10011（5））交叉叉操作作：发发生交交叉的的概率率较大大哪两个个个体体配对对交叉叉是随随机的的交叉点点位置置的选选取是是随机机的（（单点点交叉叉）2022/12/3142（6））变异异：发发生变变异的的概率率很小小（7））新群群体的的产生生：保留上上一代代最优优个体体，一一般为为10%左左右，，至少少1个个用新个个体取取代旧旧个体体，随随机取取代或或择优优取代代。11000，11011，11001，10011（8））重复复上述述操作作：说明：：GA的终止条件件一般人为为设置；GA只能求次优优解或满意意解。分析：按第第二代新群群体进行遗遗传操作，，若无变异异，永远也也找不到最最优解———择优取代代有问题。。若随机的将将个体01101选选入新群体体中，有可可能找到最最优解。2022/12/314315.5遗遗传算法法的理论基基础1模式的定义义遗传算法的的理论基础础是遗传算算法的二进进制表达式式及模式的的含义。模模式是能对对染色体之之间的相似似性进行解解释的模板板。[定义1]设GA的个体,记记集合则称为为一个个模式，其其中＊是通通配符。即模式(schema)是含有通配配符(*)的一类字字符串的的通式表表达。每每个“*”可可以取““1”或或者“0”。2022/12/3144模式举例模式*10101110与以下两个个字符串匹匹配：而模式*1010＊110与以下四个个字符串匹匹配：2022/12/3145模式的定义义[定义2]一个模式s的阶是出现在模模式中的““0”和““1”的数数目，记为为o(s)。。如：模式“0****”的阶阶为1，模模式“10*1*””的阶为3。[定义3]一个模式s的长度是出现在模模式中第一一个确定位位置和最后后一个确定定位置之间间的距离，，记为。如：模式“01***”的长长度为1，，模式“0***1”的长度度为3。2022/12/3146模模式定理假定在给定定的时间步步t,一个个特定的模模式s在群群体P(t)中包含含由m个代代表串，记记为m=m(s,t)。首先先，我们暂暂不考虑交交叉和变异异操作。每每个串根据据适应值的的大小获得得不同的复复制概率。。串i的复复制概率为为：（1)2022/12/3147模模式式定定理理则在在群群体体P(t+1)中中，，模模式式s的的代代表表串串的的数数量量的的期期望望值值为为：：其中中，，表表示示模模式式s在t时刻刻的的所所有有代代表表串串的的适适应应值值的的均均值值，，称称为为模模式式s的适适应应值值。。（2））2022/12/3148模模式定定理若记P(t)中中所有有个体体的适适应值值的平平均值值为：：（3））则(2)式式可以以表示示为：：2022/12/3149模模式定定理(3)式表表明，，模式式s的的代表表串的的数目目随时时间增增长的的幅度度正比比于模模式s的适适应值值与群群体平平均适适应值值的比比值。。即：：适应应值高高于群群体平平均值值的模模式在在下一一代的的代表表串数数目将将会增增加，，而适适应值值低于于群体体平均均值的的模式式在下下一代代的代代表串串数目目将会会减少少。假设模模式的的适应应值为为,其中中c是是一个个常数数，则则(3)式可可写为为：2022/12/3150模模式式定理（4）上式表明明，在平平均适应应值之上上（之下下）的模模式，将将会按指指数增长长（衰减减）的方方式被复复制。2022/12/3151模模式式定理复制的结结果并没没有生成成新的模模式。因而，为为了探索索搜索空空间中的的未搜索索部分，，需要利利用交叉叉和变异异操作。。下面先探索交交叉对模式的的影响。模式s1=“*1****0”和s2=“***10**”交叉会改变模模式的一部分分，模式的长长度越长，被被破坏的概率率越大。2022/12/3152模模式定理假定模式s在交叉后不不被破坏的的概率为ps，则：若交叉概率率为pc,则s不被破坏的的概率为2022/12/315315.5.2模式定定理（5）所以，再考虑虑交叉时，(3)式可表表示为最后，考虑变变异算子对模模式的影响。。变异算子以以概率pm随机地改变个个体某一位的的值。只有当当o(s)个确定位的值值不被破坏时时，模式s才不被破坏。。2022/12/315415.5.2模式定定理模式s在变异后不被被破坏的概率率：Pm<<1,可近似地表示示为2022/12/315515.5.2模式定定理（6）因此，考虑交交叉和变异时时，(3)式式可表示为2022/12/315615.5.2模式定定理由(6)我们们得到一个重重要的定理。。[定理1]模模式定理(SchemaTheorem)适应值在群体体适应值之上上的、长度较较短的、低阶阶的模式在GA的迭代中中将按指数增增长方式被复复制。2022/12/315715.5.3积木块块假设Holland和Goldberg在模式定理理的基础上提提出了“积木木块假设”(BuildingBlockHypothesis):低阶、长度较较短、高于平平均适应度的的模式(积木木块)在遗传传算子的作用用下，相互结结合，能生成成高阶、长度度较长、适应应度较高的模模式，并得到到全局最优解解。2022/12/315815.5.4遗传算算法的收敛性性分析算法的收敛性性可以定义如如下：定义：若算算法在t时刻的种群xt满足则称算法收敛敛到x0。关于遗传算法法的收敛性，，Michalewicz证明了基于压压缩原理的收收敛性定理。。而Rudolph证明了基于Markov链的收敛性定定理。2022/12/315915.6遗传算算法的的改进进遗传算算法的的局限限性：：遗传算算法得得到了了广泛泛应用用，但但也暴暴露了了一些些问题题，如如：遗遗传算算法在在解决决某些些问题题时速速度较较慢；；遗传传算法法对编编码方方案的的依赖赖性较较强，，算法法的鲁鲁棒性性不够够好等等。这些问问题主主要归归结为为：（1））上位位(epistasis)效应上位效效应包包括两两个方方面：：多基基因性性和基基因多多效性性。2022/12/316015.6遗传算算法的的改进进（2））编码码方案案最初使使用最最多的的是二二进制制位串串，但但此类类编码码并不不适合合一些些实际际问题题。现现在人人们已已经探探索了了许多多其它它方案案，如如浮点点表示示、树树形表表示等等等。。（3））积木木块假假设积木块块假设设是否否成立立，是是否一一定存存在短短的、、低阶阶的、、高适适应值值的积积木块块？若若构成成问题题最优优解的的所有有低阶阶模式式的适适应值值都较较低，，这是是GA很难收收敛到到最优优解，，此类类问题题称为为“欺欺骗问问题””。2022/12/316115.6遗传算法的的改进（4）早熟熟收敛即GA收敛到一个个局部最优优解。Schraudolph和Belew提出“动态态参数编码码”方案来来解决早熟熟收敛问题题。关于遗传算算法的一些些改进措施施，有兴趣趣的同学可可查找相关关资料。2022/12/316215.7遗传机器学学习

－－－分类器系系统机器学习是是人工智能能的一个重重要研究领领域，也是是人工智能能的一个重重要的应用用领域。遗传机器学学习(GeneticsBasedMachineLearning,GBML)时将遗传算算法与机器器学习系统统相结合的的产物。2022/12/3163遗传机器器学习系统的一一般框架架任务子系系统学习子系系统任务检测测器……任务效应应器执行效应应器执行检测测器2022/12/3164匹兹堡方方法和密密西根方方法遗传机器器学习有有两种重重要的实实现方法法：一种是由由匹兹堡堡(Pittsburgh)大学的的DeJong和他他的学生生Smith提提出的。。该方法法用整个个规则集集合表示示一个个个体，GAs维维护一个个包含一一定数目目的候选选规则集集的种群群。这种种方法称称为匹兹兹堡方法法。2022/12/3165匹兹堡方方法和密密西根方方法另一种方方法是由由密西根根(Michigan)大学学的Holland和和他的学学生Reitman提提出的。。该方法法每个个个体表示示一条规规则，而而整个种种群就是是规则集集。这种种方法称称为密西西根方法法。Holland提出的的分类器器系统采采用的是是密西根根方法。。2022/12/3166分类器系系统Holland和他的同同事提出出了一种种分类器器系统的的认知模模型,其其中的规规则不是是规则集集,而而是遗传传算法操操纵的内内部实体体。图11.3给出出了分类类器系统统的一般般结构,从分分类器系系统看学学习,它它由三三层动作作构成,即执行行子系统统、信用用赋值子子系统和和发现子子系统。。2022/12/3167分类器系系统发现[遗传算法]信用赋值[桶链]执行[分类器系统]消息来自输入接口支付消息送出输出接口（目标）来自内部监控器的消息图11.3分类器系统的一般结构2022/12/3168分类器器系统统执行子子系统统处在在最低低层,直直接与与环境境进行行交互互。它它与专家系系统相相同,由产产生式式规则则构成成。但但是,它它们是是消息息传送送,高度平平行。。这类类规则则称作作分类类器。。分类器器系统统中的的学习习,要要求求环境境提供供反馈馈,确确认认所希希望的状态态是否否达到到。系系统将将评价价这些些规则则的有有效性性,这这些些活动动常常称称作信信用赋赋值。。有些些特定定算法法专门门用来来实现现信用用赋值值,例如,桶桶链算算法。。最后一一层是是发现现子系系统,该该系统统必须须产生生新的的规则则,取取代代当前前用处处不大大的规规则。。通过过系统统累积积的经经验产产生规规则。。系统统根据据适应应值,2022/12/3169分类器器系统统分类器器系统统是平平行执执行、、消息息传递递和基基于规规则的的系统统。在在简单单的方方案中中,消消息采采用规规定的的字母母,全全部部为固固定长长度。。全部部规则则采用用条件件/动动作形形式。。每个个条件件规定定必须须满足足的信信息,每每个动动作规规定当当条件件满足足时所所发送送的消消息。。为了方方便,假假设消消息采采用长长度为为l的二进进制字字符串串记录录,字字符符采用用子集集{1,0,#}。2022/12/3170规则与与消息息产生式式规则则：IF<条件>THEN<动作>约定：：条件件的长长度是是固定定的，，用二二进制制数表表示。。定义：：IfIfsj=#,thenmjcanbeeither1or0.2022/12/3171规则与与消息息满足要要求的的全部部消息息构成成子集集,即即每每个子子集是是在消消息空空间的的一个个超平平面。。分类类器系系统是是由一一组分分类器器{C1,C2,…,CN}、一个消消息表表、输输入接接口、、输出出接口口构成成。每每部分分的主主要功功能如如下:(1)输输入入接接口口将将当当前前环环境境状状态态翻翻译译成成标标准准消消息息。。(2)分分类类器器根根据据规规则则,规规定定系系统统处处理理消消息息的的过过程程。。(3)消消息息表表包包含含当当前前全全部部消消息息。。(4)输出接口口将结果果消息翻翻译成效效应器动动作,修改环境境状态。。2022/12/3172分类器系系统的基基本结构构分类器消息表(a)全部消息息进行条条件测试试条件消息规约输出接口送到环境输入接口来自环境(a)(b)(b)选中分类器器产生新消消息2022/12/3173分类器基本本算法将输入接口口全部消息息放入消息息表。将消息表中中的全部消消息与全部部分类器所所有条件比比较,记记录所有匹匹配。满足分类器器条件部分分的每组匹匹配,将将其动作部部分所规定定的消息送送到新的消消息表。用新的消息息表取代消消息表中的的全部消息息。将消息表中中的消息翻翻译成输出出接口的要要求,产产生系统当当前的输出出。返回到步骤骤(1)。。2022/12/3174简单的视觉分分类器系统视觉向量视野运动向量对象检测器11110…消息2022/12/3175性质检测器规规定的值1，如果移动动对象0，其它(0,0)，，如果对象在在视野的中间间(1,0)，，如果对象在在中心的左边边(0,1)，，如果对象在在中心的右边边1，如果系统统是对象的近近邻0，其它1，如果对象象很大0，其它1，如果对象象是狭长的0，其它2022/12/3176规则表示规则：IF如果有“捕食食(prey)””(small,moving,nonstripedobject),处于视野中间间(centered),非邻近(nonadjacent),THEN迅速移向对象象(ALIGN),(FAST).可以表示为：：ALIGN,FAST.2022/12/3177网络图[MOVING][SMALL][NOTSTRIPED][NEAR][FAR]01001[ALERT]10001[TARGET]11001[PORSUE]11010[APPROACH]11011[FLEE]11100[FREEZE]10010[DANGER]2022/12/3178网络络图图的的规规则则表表示示MOVING和ALERT之间间的的箭箭头头：：00#############1/01001###########SMALL，，NOTSTRIPEDandALERT到TARGET的箭箭头头：：00########00####，，01001###########/10001###########2022/12/3179学习习机机制制分类类器器系系统统使使用用两两个个学学习习机机制制，，桶链链(bucketbrigade)算法法。。基基于于对对系系统统的的贡贡献献,对对现现有有规规则则分分配配一一个个信信用用值值。。规则则发发现现算算法法。。这这包包括括遗遗传传算算法法，，该该算算法法可可产产生生新新规规则则，，用用于于改改善善系系统统的的知知识识库库。。2022/12/318015.8桶链链算算法法桶链链(bucketbrigade)算法法基基于于对对系系统统的的贡贡献献,对对现现有有规规则则分分配配一一个个信信用用值值。。主主要要解解决决多多条条规规则则同同时时要要求求被被激激活活时时的的竞竞争争问问题题。。例如如：：下下面面的的情情况况下下应应该该选选择择哪哪条条规规则则。。0111→→01##：：0000→##00：：0001→00#0：：11002022/12/3181主要问问题引入信信用值值后的的两个个问题题：当多条条规则则同时时要求求被激激活时时，如如何解解决竞竞争问问题对一规规则被被激活活产生生过作作用的的那些些规则则如何何分配配信用用2022/12/3182桶链算算法为解决决上述述两个个问题题，引引入拍拍卖行行和票票据交交易所所：当有多多个分分类器器获得得匹配配时，，每个个分类类器要要出一一个与与其强强度成成正比比的叫叫价B叫价高高的分分类器器被激激活并并允许许发送送消息息，同同时通通过票票据交交易所所,将将其叫叫价B提供给给激活活的分分类器器。如此继继续下下去，，一条条规则则可通通过消消费者者获利利（增增加了了强度度），，通过过规则则的不不断激激活形形成一一条消消费者者链，，直至至最终终消费费者（（达到到目标标）直直接从从环境境中得得到补补偿。。若链中一条条规则导致致错误结论论，则序列列上该规则则的强度将将减弱，并并且沿着序序列回溯，，从而产生生新的消费费者链2022/12/3183举例环境0111，，强度为为0，叫叫价系数数为0.1。索引号分分类器器强强度101##：0000 200200#0：1000 200311##：1000 2004##00：0001 2002022/12/3184第一步分类器强强度消消息匹匹配叫叫价01##：0000200E2000#0：100020011##：1000200##00：00012002022/12/3185第二步分类器强强度消消息匹匹配配叫叫价价01##：：0000180000000#0：：100020012011##：：1000200##00：：0001200120两条规则同时时激活2022/12/3186第三步分类器强强度消消息匹匹配配叫叫价价01##：：000022000#0：11##：：1000200220##00：2022/12/3187第四步分类器强强度消消息匹匹配配叫叫价价01##：：000022000#0：：100021811##：##00：：00011623162022/12/3188第五步分类器强强度消消息匹匹配叫叫价强强度01##：000022022000#0：100021821811##：1000196196规则则4达达到到目目标标获获得得补补偿偿60。。2022/12/3189投标标改改变变分分类类器器的的强强度度在时时间间t满足足C送去去消消息息的的分分类器器对在在t-1作用的的分分类类器投投标标在时时间间t对分分类类器器C的支支持持2022/12/3190分类器中中的遗传传算法遗传算法法可产生生新规则则，用于于改善系系统的知知识库。。可以在三三种情况况下应用用GA：引入一个个参数T（时间间隔隔），用用于控制制何时使使用GA。特殊情况况时（如如消息的的条件都都不能匹匹配）使使用GA。系统的性性能太差差。2022/12/3191算法步骤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)。。2022/12/3192算法说明算法中S0(Cj)是预知的；；实现时考虑虑结束条件件；该算法是经经典GA的变种，其其中没有变变异算子；；新分类器的的强度是由由旧分类器器的强度决决定的。2022/12/3193分类器强度度调整算法法将与与所所选选动动作作相相同同的的分分类类器器形形成成子子集集[M]，，称作作动动作作集集[A]。。将不不在在[M]中的的其其它它分分类类器器放放在在集集合合NOT[A]中。。在[A]中的的全全部部分分类类器器强强度度减减少少一一个个分分数数e。。如果果系系统统决决策策正正确确，，则则将将赢赢利利量量R分配给[A]的强度;如果系统决策策错误，则将将赢利量R'(其中0≤R'≤R)分配给[A]的强度，从[A]的强度减少一一个分数p。至少R'和p中的一个为0。从NOT[A]中的强度减去去一个分数t。2022/12/319415.9规则发现系统统在规则发现系系统中,学学习经常是首首先评价系统统现有的规则则质量,然然后进行修改改。Grefenstette研制了一种规规则发现系统统RUDI。问题求解级由由简化的分类类器系统组成成。学习级是是对知识结构构群体进行遗遗传算法操作作,每一个表示为为一组规则表表。知识结构构的整个行为为控制这些结结构的复制。。在RUDI中,信用赋赋值方法赢利利共享规划(Profit-SharingPlan,简称PSP)和桶链算法(BBA)对每个规则提提供互补的效效用信息。根根据期望的外外部奖励,PSP-强度对规则效效用提供更精精确的评估。。当问题求解解时它被用作作冲突消解。。与此相反,BBA-强度表示规则则之间的动态态相关性,规规则点火依依次会聚到相相似水平。这这种测度可以以用作一组协协作规则的聚聚类。2022/12/3195规则发现系统统Grefenstette提出一种强度度修改方案称称作嬴利共享享规划PSP。在这种方案中中问题求解划划分成情节,按所接受受的外部奖励励区分。如果果任何步情节节在投标竞争争中获胜,则则认为该规规则在该情节节活动。在情情节t,PSP修改每个活动动规则Ri的强度Si(t)如下:Si(t+1)=Si(t)-bSi(t)+bp(t),其中,p(t)称作在情节结结束时所获得得的外部奖励励,即当获获得外部奖励励,从每个活活动规则搜集集投标,每每个活动规则则给出一部分分外部奖励。。考虑PSP对给定规则Ri的影响,它它按照方程得到:2022/12/3196规则发现系统统其中,t的范围是在该该情节规则Ri是活动的,即即Si(t)基本上外部奖奖励的权值平平均p(t),(1-b)作为指数衰减减因子。如果果