高级人工智能之进化理论

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

1967年，Bagley在他的论论文中首首次提出出了遗传传算法这这一术语语，并讨讨论了遗遗传算法法在自动动博弈中中的应用用。1970年，Cavicchio把遗传算算法应用用于模式式识别中中。第一一个把遗遗传算法法应用于于函数优优化的是是Hollstien。2020-01-155史忠植高高级级人工智智能发展历史史1975年是遗遗传算法法研究的的历史上上十分重重要的一一年。这这一年，，Holland出版了他他的著名名专著《《自然系系统和人人工系统统的适应应性》该书系统统地阐述述了遗传传算法的的基本理理论和方方法，并并提出了了对遗传传算法的的理论研研究和发发展极为为重要的的模式理理论（schematatheory）），该理论首首次确认认了结构构重组遗遗传操作作对于获获得隐并并行性的的重要性性。同年，DeJong完成了他他的重要要论文《《遗传自自适应系系统的行行为分析析》。他他在该论论文中所所做的研研究工作作可看作作是遗传传算法发发展过程程中的一一个里程程碑，这这是因为为他把Holland的模式理理论与他他的计算算使用结结合起来来。2020-01-156史忠植高高级级人工智智能发展历史史1989Goldberg对遗传算算法从理理论上，，方法上上和应用用上作了了系统的的总结。1990年，Koza提出了遗遗传程序序设计（（GeneticProgramming）的概念。。（用于于搜索解解决特定定问题的的最适计计算机程程序）2020-01-157史忠植高高级级人工智智能遗传算法法与自然然进化的的比较自然界染色体基因等位基因因(allele))染色体位位置(locus)基因型((genotype)表型(phenotype))遗传算法法字符串字符,特特征特征值字符串位位置结构参数集,,译码结结构2020-01-158史忠植高高级级人工智智能新达尔文文五进化化理论的的主要论论点个体是基基本的选选择目标标;随机过程程在进化化中起重重大作用用,遗遗传变异异大部分分是偶然然现象;;基因型变变异大部部分是重重组的产产物,特特别是是突变;;逐渐进化化可能与与表型不不连续有有关;不是所有有表型变变化都是是自然选选择的必必然结果果;进化是在在适应中中变化的的,形形式多样样,不不仅是基基因的变变化;选择是概概率型的的,而而不是是决定型型的。2020-01-159史忠植高高级级人工智智能进化计算算的三大主流流板块Holland提出的遗遗传算法法(GeneticAlgorithm)。。Rechenberg和Schwefel提出的进进化策略略(EvolutionaryStrategies)。。Fogel提出的进进化规划划(EvolutionaryProgramming)，又称称为进化化程序设设计。本章将着着重介绍绍遗传算算法，对对进化策略略和进化化规划只作简单单介绍。。2020-01-1510史忠植高高级级人工智智能15.2进化系统统理论的的形式模模型进化在个个体群体体中起作作用。瓦瓦铤顿((Waddington)指出基因因型和表表型之间间关系的的重要性性(Waddington1974)。群体禁止止异构环环境。但但是“后后生环境境”是多多维空间间。表型型是基因因型和环环境的产产物。然然后表型型通过异异构“选选择环境境"发生生作用。。注意，，这种多多维选择择环境与与后生环环境空间间是不同同的。现现在，适适应性是是表型空空间和选选择环境境空间的的产物。。它经常常被取作作一维，，表示多多少子孙孙对下一代作作出贡献献。基于这种种想法，，莫楞贝贝(Muhlenbein)和肯德曼曼(Kindermann)提出了一一种称为进化系系统理论论的形式式模型((Muhlenbein1989)。2020-01-1511史忠植高高级级人工智智能进化系统统理论的的形式模模型进化的主主要过程程后生环境境遗传操作作符选择环境境gp2020-01-1512史忠植高高级级人工智智能进化系统统理论的的形式模模型其中，g是基因型型p是表型。。基因gi的可能值值称为等等位基因因。在门德尔尔(Mendel))遗传学中中，假设设每个基基因有有有限数的的等位基基因。2020-01-1513史忠植高高级级人工智智能进化系统统理论的的形式模模型这个变换换函数给给出了模模型，说说明表型型的发展展是通过过基因与环境境的交互互作用。。变换过程程是高度度非线性性的。2020-01-1514史忠植高高级级人工智智能进化系统统理论的的形式模模型质量函数数q给出了具具体选择择环境ESi下表型的的质量，，其定义如如下：质量定义义适应度度，用于于达尔文文选择。。至今已已有三种种具体范范例的通通用模型型，即门德尔遗遗传学遗传生态态学进化配子子2020-01-1515史忠植高高级级人工智智能门德尔遗遗传学在门德尔尔遗传学学中，基基因型被被详细模模型化，，而表型型和环境几乎乎被忽略略。在遗遗传生态态学中恰好相相反。进化配子子论是从从社会生生物学导导出的模模型。首先让我我们讨论论门德尔尔遗传学学的选择择模型。。为了简简单起见见，我们们假设一一个基因因具有n等位基因因a1,…,an。二倍基因因型以元元组(ai,aj)为特征。。我们们定义pi,j为总群体体中基因因型(ai,aj)的频度。。假设基基因型与与表型相相等。质质量函数数给每个个表型赋值。。q(ai,aj)=qi,jqi,j可以被解解释为出出生率减减去死亡亡率2020-01-1516史忠植高高级级人工智智能门德尔遗遗传学假设p’i,j是下一代代表型((ai,aj)的频度。。然后达达尔文选择根据据选择方方程调整整表型的的分布::是群体的的平均适适应度。。2020-01-1517史忠植高高级级人工智智能门德尔遗遗传学设pi是群体中中等位基基因的频频率。如如果pi,j=pipj那么，我我们得到到在GS中的一个个选择方方程为2020-01-1518史忠植高高级级人工智智能门德尔遗遗传学这个离散散的选择择方程可可以用连连续方程程近似::如果qi,j=qj,i,那么2020-01-1519史忠植高高级级人工智智能门德尔遗遗传学这个方程程很容易易被证明明:这个结果果称作菲菲希尔((Fisher))基本定理理。它说说明平均均适应度度随适应应度的差差别呈正正比例增增加。实实际上，，全部可可能的基基因型仅仅有一部部分实现现。这就就是遗传传操纵子子探索基基因型空空间的任任务，其其个体数数目相当当小。这这些操纵纵子是群群体遗传传变异性性的来源源。最重要的的操纵子子是突变变和重组组。2020-01-1520史忠植高高级级人工智智能15.3达尔文进进化算法法根据定量量遗传学学，达尔尔文进化化算法采采用简单单的突变//选择动动力学。。达尔文算算法的一一般形式式可以描描述如下下：是一代的的双亲数数目，为子孙数数目。整数称作“混混杂”数数。如果两个个双亲混混合他们们的基因因，则=2。。仅是最好的的个体才才允许产产生子孙孙。逗号表示示双亲们没没有选择择，加号号表示双双亲有选选择。2020-01-1521史忠植高高级级人工智智能15.3达尔文进进化算法法建立原始始种体。。通过突变变建立子子孙。选择：返回到步步骤(1)。…2020-01-1522史忠植高高级级人工智智能遗传算法法思想来来源于生生物进化化过程,,它是是基于进进化过程程中的信信息遗传传机制和和优胜劣劣汰的自自然选择择原则的的搜索算算法(以以字符串串表示状状态空间间)。遗遗传算法法用概率率搜索过过程在该该状态空空间中搜搜索，产产生新的的样本。。15.4遗传算法法2020-01-1523史忠植高高级级人工智智能遗传算法法的特点点特点：通用鲁棒次优解、、满意解解遗传算法法能解决决的问题题：优化NP完全NP难高度复杂杂的非线线性问题题2020-01-1524史忠植高高级级人工智智能遗传算法法遗传算法法先将搜搜索结构构编码为为字符串串形式,,每个个字符串串结构被被称为个个体。然后对一一组字符符串结构构(被称称为一个个群体))进行循循环操作作。每次次循环被被称作一一代,包包括一个个保存字字符串中中较优结结构的过过程和一一个有结结构的、、随机的的字符串串间的信信息交换换过程。。类似于自自然进化化，遗传传算法通通过作用用于染色色体上的的基因寻寻找好的的染色体体来求解解问题。。2020-01-1525史忠植高高级级人工智智能遗传算法法与自然界界相似，，遗传算算法对求求解问题题的本身身一无所所知，它它所需要要的仅是是对算法法所产生生的每个个染色体体进行评评价，并并基于适适应值来来选择染染色体，，使适应应性好的的染色体体有更多多的繁殖殖机会。。在遗传算算法中，，位字符符串扮演演染色体体的作用用，单个个位扮演演了基因因的作用用，随机机产生一一个体字字符串的的初始群群体，每每个个体体给予一一个数值值评价，，称为适适应度，，取消低低适应度度的个体体，选择择高适应应度的个个体参加加操作。。常用的遗遗传算子子有复制制、杂交交、变异异和反转转。2020-01-1526史忠植高高级级人工智智能遗传算法法与传统统优化算算法的主主要不同同遗传算法法不是直直接作用用在参变变量集上上,而而是利用用参变量量集的某某种编码码;遗传算法法不是从从单个点点,而而是在群群体中从从一个点点开始搜搜索;遗传算法法利用适适应值信信息,无无需导导数或其其它辅助助信息;;遗传算法法利用概概率转移移规则,,而非非确定性性规则。。2020-01-1527史忠植高高级级人工智智能遗传算法法的准备备工作确定表示示方案;;确定适应应值的度度量;确定控制制该算法法的参数数和变量量;确定怎样样指定结结果及程程序运行行结束的的标准。。2020-01-1528史忠植高高级级人工智智能基本遗传传算法基本遗传传算法((SimpleGeneticAlgorithm::SGA)又称为简简单遗传传算法，，只使用用选择算算子、交交叉算子子和变异异算子这这三种基基本的遗遗传算子子。其遗遗传操作作简单、、容易理理解，是是其它遗遗传算法法的雏形形和基础础。基本遗传传算法的的构成要要素：1、染色色体编码码方法：：首先必必须对问问题的解解空间进进行编码码，使之之能用遗遗传算法法进行操操作。较较常用的的是二进进制编码码方法，，现在使使用非二二进制编编码的也也逐渐增增多。2、适应应度函数数（fitnessfunction，又称为适适应值／／适值函函数）用用来评价价一个染染色体的的好坏。。2020-01-1529史忠植高高级级人工智智能基本遗传传算法的的构成要要素3、遗传传算子•选择算子子(selection))：又称为复复制算子子。按照照某种策策略从父父代中挑挑选个体体进入下下一代，，如使用用比例选选择、轮轮盘式选选择。•交叉算子子(crossover))：又称为杂杂交算子子。将从从群体中中选择的的两个个个体，按按照某种种策略使使两个个个体相互互交换部部分染色色体，从从而形成成两个新新的个体体。如使使用单点点一致交交叉。•变异算子子(mutation)：：按照一定定的概率率（一般般较小）），改变变染色体体中某些些基因的的值。2020-01-1530史忠植高高级级人工智智能杂交操作作举例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#2020-01-1531史忠植高高级级人工智智能变异操作作简单的变变异操作作过程如如下:每个位置置的字符符变量都都有一个个变异概概率,各各位置置互相独独立。通通过随机机过程选选择发生生变异的的位置：：产生一个个新结构构,其中是是从对对应位置置的的字字符变量量的值域域中随机机选择的的一个取取值。可可以同样样得到。。2020-01-1532史忠植高高级级人工智智能反转操作作简单反转转操作的的步骤如如下:从当前群群体中随随机选择择一个结结构从中随机机选择两两个数i’和j’,并定义i=min{i'',j''},j=max{{i',,j'}};颠倒a中位置i、j之间的部部分,产产生新新的结构构2020-01-1533史忠植高高级级人工智智能基本遗传传算法的的构成要要素4、运行行参数N：群体大小小，即群群体中包包含的个个体的数数量。T：遗传算法法终止的的进化代代数。Pc：交叉概率率，一般般取为0.4～0..99。。Pm：变异概率率，一般般取为0.0001～0..1。。2020-01-1534史忠植高高级级人工智智能基本遗传传算法随机产生生一个由由固定长长度字符符串组成成的初始始群体;;对于字符符串群体体，迭代代地执行行下述步步骤，直直到选种种标准被被满足为为止：计算群体体中的每每个个体体字符串串的适应应值;应用下述述三种操操作(至至少前两两种)来来产生新新的群体体:复制:把把现有有的个体体字符串串复制到到新的群群体中。。杂交:通通过遗遗传重组组随机选选择两个个现有的的子字符符串,产产生生新的字字符串。。变异:将将现有有字符串串中某一一位的字字符随机机变异。。把在后代代中出现现的最高高适应值值的个体体字符串串指定为为遗传算算法运行行的结果果。这一一结果可可以是问问题的解解(或近近似解))。2020-01-1535史忠植高高级级人工智智能基本遗传传算法流流程图GEN=0概率地选择遗传操作随机创建初始群体计算群体中每个个体的适应值i:=0显示结果结束GEN:=GEN+1是是否（转下页）i=N?GEN=M？12020-01-1536史忠植高高级级人工智智能概率地选选择遗传传操作根据适应应值选择一个个个体完成交叉叉i:=i+1i:=i+1复制个体体p(r))选择（接上页页）基于适应应值选择两个个个体把新的两两个孩子加到群群体中p(c))交叉变异p(m))把新的孩孩子加入到群体体中完成变异异根据适应应值选择一个个个体把变异后后个体加入到群群体中12020-01-1537史忠植高高级级人工智智能轮盘式选选择首先计算算每个个个体i被选中的的概率然后根据据概率的的大小将将将圆盘盘分为n个扇形，，每个扇扇形的大大小为。。选选择时转转动轮盘盘，参考考点r落到扇形形i则选择个个体i。......p1p2pir2020-01-1538史忠植高高级级人工智智能单点一致致交叉首先以概概率pc从种群中中随机地地选择两两个个体体p1、p2。在{1,2,.....,,l}内随机选选择一个个数i,作为交叉叉的位置置，称为为交叉点点。然后后将两个个个体交交叉点后后面的部部分交换换。例如：01101011000110011001110001100111001011002020-01-1539史忠植高高级级人工智智能一致变异异以概率pm对种群中中所有个个体的每每一位进进行变异异。对于个体体pi的第j位，在[[0,1]的范范围内随随机地生生成一个个数r,如果r<pm,则对第j位取反，，否则保保持第j位不变。。2020-01-1540史忠植高高级级人工智智能遗传算法法举例问题：求求（1）编码：此时取均均长为5，每个个染色体体（2）初初始群体体生成：：群体大大小视情情况而定定，此处处设置为为4，随随机产生生四个个个体：编码：01101，，11000，，01000，，10011解码：1324819适应度：：16957664361（3）适适应度评评价：2020-01-1541史忠植高高级级人工智智能（4）选选择：选选择概率率个体：01101，，11000，，01000，，10011适应度：：16957664361选择概率率：0..140..490..060.31选择结果果：01101，11000，11000，10011（5）交交叉操作作：发生生交叉的的概率较较大哪两个个个体配对对交叉是是随机的的交叉点位位置的选选取是随随机的（（单点交交叉）01101011001100011011110001100110011100002020-01-1542史忠植高高级级人工智智能（6）变变异：发发生变异异的概率率很小（7）新新群体的的产生：：保留上一一代最优优个体，，一般为为10%%左右，，至少1个用新个体体取代旧旧个体，，随机取取代或择择优取代代。11000，11011，11001，10011（8）重重复上述述操作：：说明：GA的终止条条件一般般人为设设置；GA只能求次次优解或或满意解解。分析：按按第二代代新群体体进行遗遗传操作作，若无无变异，，永远也也找不到到最优解解——择择优取代代有问题题。若随机的的将个体体01101选选入新群群体中，，有可能能找到最最优解。。2020-01-1543史忠植高高级级人工智智能15.5遗传传算法的的理论基基础15.5..1模式的定定义遗传算法法的理论论基础是是遗传算算法的二二进制表表达式及及模式的的含义。。模式是是能对染染色体之之间的相相似性进进行解释释的模板板。[定义1]设设GA的个体,,记集合合则称为为一一个模式式，其中中＊是通通配符。。即模式((schema))是含有通通配符(*)的一类字字符串的的通式表表达。每每个“*”可可以取““1”或或者“0”。2020-01-1544史忠植高高级级人工智智能模式举例例模式*10101110与以下两两个字符符串匹配配：010101110110101110而模式*1010＊110与以下四四个字符符串匹配配：0101001100101011101101001101101011102020-01-1545史忠植高高级级人工智智能模式的定定义[定义2]一一个模式s的阶是出现在在模式中中的“0”和““1”的的数目，，记为o(s))。如：模式式“0*****””的阶为为1，模模式“10*1*”的的阶为3。[定义3]一一个模式s的长度是出现在在模式中中第一个个确定位位置和最最后一个个确定位位置之间间的距离离，记为为。如：模式式“01****””的长度度为1，，模式““0****1””的长度度为3。。2020-01-1546史忠植高高级级人工智智能15.5.2模模式式定理假定在给给定的时时间步t,一个个特定的的模式s在群体体P(t)中包包含由m个代表表串，记记为m==m(s,t))。首先先，我们们暂不考考虑交叉叉和变异异操作。。每个串串根据适适应值的的大小获获得不同同的复制制概率。。串i的的复制概概率为：：（1)2020-01-1547史忠植高高级级人工智智能15.5.2模模式式定理则在群体体P(t+1))中，模模式s的的代表串串的数量量的期望望值为：：其中，表表示示模式s在t时刻的所所有代表表串的适适应值的的均值，，称为模模式s的适应值值。（2）2020-01-1548史忠植高高级级人工智智能15.5.2模模式式定理若记P((t)中中所有个个体的适适应值的的平均值值为：（3）则(2))式可以以表示为为：2020-01-1549史忠植高高级级人工智智能15.5.2模模式式定理(3)式式表明，，模式s的代表表串的数数目随时时间增长长的幅度度正比于于模式s的适应应值与群群体平均均适应值值的比值值。即：：适应值值高于群群体平均均值的模模式在下下一代的的代表串串数目将将会增加加，而适适应值低低于群体体平均值值的模式式在下一一代的代代表串数数目将会会减少。。假设模式式的适应应值为,,其其中c是是一个常常数，则则(3)式可可写为：：2020-01-1550史忠植高高级级人工智智能15.5.2模模式式定理（4）上式表明明，在平平均适应应值之上上（之下下）的模模式，将将会按指指数增长长（衰减减）的方方式被复复制。2020-01-1551史忠植高高级级人工智智能15.5.2模模式式定理复制的结结果并没没有生成成新的模模式。因而，为为了探索索搜索空空间中的的未搜索索部分，，需要利利用交叉叉和变异异操作。。下面先探探索交叉叉对模式式的影响响。模式s1=““*1******0”和s2=““****10***”交叉会改改变模式式的一部部分，模模式的长长度越长长，被破破坏的概概率越大大。2020-01-1552史忠植高高级级人工智智能15.5.2模模式式定理假定模式式s在交叉后后不被破破坏的概概率为ps，则：若交叉概概率为pc,则s不被破坏坏的概率率为2020-01-1553史忠植高高级级人工智智能15.5.2模模式式定理（5）所以，再再考虑交交叉时，，(3))式可表表示为最后，考考虑变异异算子对对模式的的影响。。变异算算子以概概率pm随机地改改变个体体某一位位的值。。只有当当o(s))个确定位位的值不不被破坏坏时，模模式s才不被破破坏。2020-01-1554史忠植高高级级人工智智能15.5.2模模式式定理模式s在变异后后不被破破坏的概概率：Pm<<1,,可近似地地表示为为2020-01-1555史忠植高高级级人工智智能15.5.2模模式式定理（6）因此，考考虑交叉叉和变异异时，((3)式式可表示示为2020-01-1556史忠植高高级级人工智智能15.5.2模模式式定理由(6))我们得得到一个个重要的的定理。。[定理1]模模式定理理(SchemaTheorem)适应值在在群体适适应值之之上的、、长度较较短的、、低阶的的模式在在GA的的迭代中中将按指指数增长长方式被被复制。。2020-01-1557史忠植高高级级人工智智能15.5.3积积木木块假设设Holland和Goldberg在模式式定理的的基础上上提出了了“积木木块假设设”(BuildingBlockHypothesis):低阶、长长度较短短、高于于平均适适应度的的模式((积木块块)在遗遗传算子子的作用用下，相相互结合合，能生生成高阶阶、长度度较长、、适应度度较高的的模式，，并得到到全局最最优解。。2020-01-1558史忠植高高级级人工智智能15.5.4遗遗传传算法的的收敛性性分析算法的收收敛性可可以定义义如下：：定义：若若算法法在t时刻的种种群xt满足则称算法法收敛到到x0。关于遗传传算法的的收敛性性，Michalewicz证明了基基于压缩缩原理的的收敛性性定理。。而Rudolph证明了基基于Markov链的收敛敛性定理理。2020-01-1559史忠植高高级级人工智智能15.6遗传算法法的改进进遗传算法法的局限限性：遗传算法法得到了了广泛应应用，但但也暴露露了一些些问题，，如：遗遗传算法法在解决决某些问问题时速速度较慢慢；遗传传算法对对编码方方案的依依赖性较较强，算算法的鲁鲁棒性不不够好等等。这些问题题主要归归结为：：（1）上上位(epistasis))效应上位效应应包括两两个方面面：多基基因性和和基因多多效性。。2020-01-1560史忠植高高级级人工智智能15.6遗传算法法的改进进（2）编编码方案案最初使用用最多的的是二进进制位串串，但此此类编码码并不适适合一些些实际问问题。现现在人们们已经探探索了许许多其它它方案，，如浮点点表示、、树形表表示等等等。（3）积积木块假假设积木块假假设是否否成立，，是否一一定存在在短的、、低阶的的、高适适应值的的积木块块？若构构成问题题最优解解的所有有低阶模模式的适适应值都都较低，，这是GA很难收敛敛到最优优解，此此类问题题称为““欺骗问问题”。。2020-01-1561史忠植高高级级人工智智能15.6遗传算法法的改进进（4）早早熟收敛敛即GA收敛到一一个局部部最优解解。Schraudolph和Belew提出“动动态参数数编码””方案来来解决早早熟收敛敛问题。。关于遗传传算法的的一些改改进措施施，有兴兴趣的同同学可查查找相关关资料。。2020-01-1562史忠植高高级级人工智智能15.7遗传机器器学习－－－分分类器系系统机器学习习是人工工智能的的一个重重要研究究领域，，也是人人工智能能的一个个重要的的应用领领域。遗传机器器学习((GeneticsBasedMachineLearning,GBML)时将遗传传算法与与机器学学习系统统相结合合的产物物。2020-01-1563史忠植高高级级人工智智能遗传机器器学习系统的一一般框架架任务子系系统学习子系系统任务检测测器……任务效应应器执行效应应器执行检测测器2020-01-1564史忠植高高级级人工智智能匹兹堡方方法和密密西根方方法遗传机器器学习有有两种重重要的实实现方法法：一种是由由匹兹堡堡(Pittsburgh))大学的的DeJong和他他的学生生Smith提提出的。。该方法法用整个个规则集集合表示示一个个个体，GAs维维护一个个包含一一定数目目的候选选规则集集的种群群。这种种方法称称为匹兹兹堡方法法。2020-01-1565史忠植高高级级人工智智能匹兹堡方方法和密密西根方方法另一种方方法是由由密西根根(Michigan)大学学的Holland和和他的学学生Reitman提提出的。。该方法法每个个个体表示示一条规规则，而而整个种种群就是是规则集集。这种种方法称称为密西西根方法法。Holland提出的的分类器器系统采采用的是是密西根根方法。。2020-01-1566史忠植高高级级人工智智能分类器系系统Holland和他的同同事提出出了一种种分类器器系统的的认知模模型,其其中的规规则不是是规则集集,而而是遗传传算法操操纵的内内部实体体。图11..3给出出了分类类器系统统的一般般结构,,从分分类器系系统看学学习,它它由三三层动作作构成,,即执行子子系统、、信用赋赋值子系系统和发发现子系系统。2020-01-1567史忠植高高级级人工智智能分类器系系统发现[遗传算法]信用赋值[桶链]执行[分类器系统]消息来自输入接口支付消息送出输出接口（目标）来自内部监控器的消息图11.3分类器系统的一般结构2020-01-1568史忠植高高级级人工智智能分类器系系统执行子系系统处在在最低层层,直直接与环环境进行行交互。。它与专家系统统相同,,由产生生式规则则构成。。但是,,它们们是消息息传送,,高度平行行。这类类规则称称作分类类器。分类器系系统中的的学习,,要求求环境提提供反馈馈,确确认所希希望的状态是是否达到到。系统统将评价价这些规规则的有有效性,,这些些活动常常称作作信用赋赋值。有有些特定定算法专专门用来来实现信信用赋值值,例如,桶桶链算算法。最后一层层是发现现子系统统,该该系统必必须产生生新的规规则,取取代当当前用处处不大的的规则。。通过系系统累积积的经验验产生规规则。系系统根据据适应值值,使使用遗传传算法选选择、重组和取取代规则则。2020-01-1569史忠植高高级级人工智智能分类器系系统分类器系系统是平平行执行行、消息息传递和和基于规规则的系系统。在在简单的的方案中中,消息息采用规规定的字字母,全全部为为固定长长度。全全部规则则采用条条件/动动作形式式。每个个条件规规定必须须满足的的信息,,每个个动作规规定当条条件满足足时所发发送的消消息。为了方便便,假假设消息息采用长长度为l的二进制制字符串串记录,,字符符采用子子集{1,0,##}。2020-01-1570史忠植高高级级人工智智能规则与消消息产生式规规则：IF<<条件>THEN<动作>约定：条条件的长长度是固固定的，，用二进进制数表表示。定义：Ifsj=1orsj=0,,thenmj=sjIfsj=#,,thenmjcanbeeither1or0.2020-01-1571史忠植高高级级人工智智能规则与消消息满足要求求的全部部消息构构成子集集,即即每个子子集是在在消息空空间的一一个超平平面。分分类器系系统是由由一组分分类器{C1,C2,…,CN}、一个消息息表、输输入接口口、输出出接口构构成。每每部分的的主要功功能如下下:

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

Si(t+1))=Si(t)-bSi((t)+bp(t),其中,p(t))称作在情情节结束束时所获获得的外外部奖励励,即即当获得得外部奖奖励,从从每个活活动规则则搜集投投标,每每个活活动规则则给出一一部分外外部奖励励。考虑虑PSP对给定规规则Ri的影响,,它按按照方程程得到:2020