高级人工智能之进化理论

第十五章进化计算史忠植中科院计算所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等位基因a1,…,an。二倍基因型以以元组(ai,aj)为特征。我我们定义pi,j为总群体中基基因型(ai,aj)的频度。假设设基因型与表表型相等。质质量函数给每每个表型赋值。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/3153模模式定理（5）所以，再考考虑交叉时时，(3)式可表示示为最后，考虑虑变异算子子对模式的的影响。变变异算子以以概率pm随机地改变变个体某一一位的值。。只有当o(s)个确定位的的值不被破破坏时，模模式s才不被破坏坏。2022/12/315415.5.2模式定定理模式s在变异后不被被破坏的概率率：Pm<<1,可近似地表示示为2022/12/315515.5.2模式定定理（6）因此，考虑交交叉和变异时时，(3)式式可表示为2022/12/3156模模式式定定理理由(6)我我们们得得到到一一个个重重要要的的定定理理。。[定定理理1]模模式式定定理理(SchemaTheorem)适应应值值在在群群体体适适应应值值之之上上的的、、长长度度较较短短的的、、低低阶阶的的模模式式在在GA的的迭迭代代中中将将按按指指数数增增长长方方式式被被复复制制。。2022/12/3157积积木块块假设设Holland和Goldberg在在模式式定理理的基基础上上提出出了““积木木块假假设””(BuildingBlockHypothesis):低阶、、长度度较短短、高高于平平均适适应度度的模模式(积木木块)在遗遗传算算子的的作用用下，，相互互结合合，能能生成成高阶阶、长长度较较长、、适应应度较较高的的模式式，并并得到到全局局最优优解。。2022/12/3158遗遗传传算法的的收敛性性分析算法的收收敛性可可以定义义如下：：定义：若若算法法在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<动作>约定：：条件件的长长度是是固定定的，，用二二进制制数表表示。。定义：：Ifsj=1orsj=0,thenmj=sjIf2022/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。。索引号 分类类器 强度度1 01##：0000 2002 00#0：1000 2003 11##：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##：000022011##：10002002202022/12/3187第四步步分类器器强强度度消消息息匹匹配叫叫价01##：000022000#0：1000218##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)作为指指数衰衰减因因子。。如果果b足够小小,那那么S(t)具有p(t)的平均均值。。如果果外部部奖励励p(t)是常数数,p*,那么Si收敛到到一个个平衡衡值Si*:2022/12/3197规则发发现系系统在常数数赢利利下,PSP将以下下列速速率减减少误误差Ei(t)=p*-Si(t)强度每每次改改变,以因子子b减少当当前强强度与与平衡衡强度度之差差。2022/12/3198规则发发现系系统我们看看出,奖奖励相相当是是常数数情况况下,在在PSP下每个个规则则强度度很快快收敛敛到一一个平平衡强强度,可可以预预测情情节结结束时时将接接收的的奖励励水平平。PSP的一种种可能能的限限制是是它取取决于于这种