AI-05-12-进化计算与遗传算法-人工智能课程-浙江大学研究生

第十二章进化计算与遗传算法徐从富浙江高校人工智能探讨所2003年11月1本章主要参考文献：[1]陈国良,王煦法等.遗传算法及其应用.人民邮电出版社,1996.[2]王正志,薄涛.进化计算.国防科技高校出版社,2000.[3]张颖,刘艳秋.软计算方法.科学出版社,2002.pp69-108.[4]史忠植.高级人工智能.科学出版社,1998.pp249-270.[5]史忠植.学问发觉.清华高校出版社,2002.pp265-294.[6]Mitchell,T.M.著,曾华军等译.机器学习.机械工业出版社,2003.pp179-196.[7]贺前华,韦岗,陆以勤.基因算法探讨进展.电子学报,1998,26(10):118-122,103.2内容12.1概述12.2进化系统理论的形式模型12.3达尔文进化算法12.4分类器系统12.5桶链算法12.6遗传算法12.7并行遗传算法12.8分类器系统Boole12.9规则发觉系统12.10进化策略12.11进化程序设计312.1概述12.1.1背景人们对很多高度非线性问题的内部机理还很不清晰： 智能模拟 非线性优化 图像识别，等等。要解决上述问题，就须要一些具有自组织、自适应实力的大规模并行算法，模拟生物或自然现象就成为AI中的一种自然而又重要的探讨方向。因此产生了如下新方法： 人工神经网络 遗传算法、进化计算，等等。4生物进化的主要特点： 进化的结果特殊困难 进化的过程特殊简洁：繁殖、变异、竞争、选择基于自然选择的软件设计方法解决传统方法中存在的如下最大障碍：须要事先描述问题的全部特点，并说明针对问题的特点，程序应实行的措施。 利用进化机理，人们可以“培育”程序，去解决那些结构尚不清晰的问题。12.1.1背景（续）5遗传算法和进化计算的基本思想：来源于生物进化过程,它是基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的搜寻算法（以字符串表示状态空间）。遗传算法用概率搜寻过程在该状态空间中搜寻，产生新的样本。遗传算法和进化计算是一种通用的问题求解方法，它接受某种编码技术来表示各种困难的结构，并将每个编码称为一个个体。算法维持一个确定数目的编码集合，称为种群，并通过对种群中的每个个体进行某些遗传操作（如变异、交叉、选择等）来模拟进化过程，最终获得一些具有较高性能指标的编码。12.1.3基本思想6发展历史遗传算法的发展历史：1965年，Holland首次提出了人工遗传操作的重要性，并把这些应用于自然系统和人工系统中。 1967年，Bagley在他的论文中首次提出了遗传算法（GeneticAlgorithm，简称GA）这一术语，并探讨了遗传算法在自动博弈中的应用。1970年，Cavicchio把遗传算法应用于模式识别中。第一个把遗传算法应用于函数优化的是Hollstien。7发展历史（续）1975年是遗传算法探讨的历史上特殊重要的一年。这一年，Holland出版了他的著名专著“AdaptationinNaturalandArtificialSystems”(《自然和人工系统的自适应性》)该书系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论探讨和发展极为重要的模式理论（SchemataTheory），该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。同年，DeJong完成了他的重要论文“AnAnalysisoftheBehaviorofaClassofGeneticAdaptiveSystems”(《遗传自适应系统的行为分析》)。他在该论文中所做的探讨工作可看作是遗传算法发展过程中的一个里程碑，这是因为他把Holland的模式理论与他自己的试验结合起来。8发展历史（续）1988年Mayr提出新达尔文进化理论。1989年Goldberg对遗传算法从理论、方法和应用上作了系统的总结.9特点特点：通用鲁棒次优解、满足解遗传算法能解决的问题：优化NP完全问题NP难解问题高度困难的非线性问题10进化计算和遗传算法的主要应用领域：应用领域说明控制规划设计组合优化图像处理信号处理机器人人工生命瓦斯管道控制、防避导弹控制、机器人控制生产规划、并行机任务分配VLSI部局、通信网络设计、喷气发动机设计TSP问题、背包问题、图划分问题模式识别、特征抽取滤波器设计路径规划生命的遗传进化11遗传算法与自然进化的比较自然界染色体基因等位基因(allele)染色体位置(locus)基因型(genotype)表型(phenotype)遗传算法字符串字符，特征特征值字符串位置结构参数集，译码结构12面对执行的学习系统任务子系统学习子系统任务检测器……任务效应器执行效应器执行检测器13新达尔文进化理论的主要论点个体是基本的选择目标;随机过程在进化中起重大作用,遗传变异大部分是偶然现象;基因型变异大部分是重组的产物,特殊是突变;渐渐进化可能与表型不连续有关;不是全部表型变更都是自然选择的必定结果;进化是在适应中变更的,形式多样,不仅是基因的变更;选择是概率型的,而不是确定型的。1412.2进化系统理论的形式模型进化在个体群体中起作用。1974年Waddington指出基因型和表型之间关系的重要性。群体禁止异构环境。但是“后成环境”是多维空间。表型是基因型和环境的产物。然后表型通过异构“选择环境”发生作用。【注】：这种多维选择环境与后成环境空间是不同的。现在，适应性是表型空间和选择环境空间的产物。它常常被取作一维，表示多少子孙对下一代作出贡献。基于上述思想，1989年Muhlenbein和Kindermann提出了一种称为进化系统理论的形式模型。15进化系统理论的形式模型进化的主要过程后生环境遗传操作符选择环境gp16进化系统理论的形式模型其中，g是基因型

p是表型基因gi的可能值称为等位基因。

在门德尔(Mendel)遗传学中，假设每个基因有有限个等位基因。17进化系统理论的形式模型这个变换函数给出了模型，说明表型的发展是通过基因与环境的交互作用而实现的。

变换过程是高度非线性的。18进化系统理论的形式模型质量函数q给出了具体选择环境ESi下表型的质量，其定义如下：质量函数定义适应度，用于达尔文选择。目前主要有三种通用模型，即

门德尔遗传学

遗传生态学

进化配子19

门德尔遗传学在门德尔遗传学中，基因型被具体模型化，而表型和环境几乎被忽视；在遗传生态学中恰好相反；进化配子论是从社会生物学导出的模型。首先，探讨门德尔遗传学的选择模型。为简洁起见，假设一个基因具有n个等位基因a1,…,an。二倍基因型以元组(ai,aj)为特征。定义pi,j为总群体中基因型(ai,aj)的频度。假设基因型与表型相等。质量函数给每个表型赋值。q(ai,aj)=qi,jqi,j可被说明为诞生率减去死亡率。20

门德尔遗传学假设p’i,j是下一代表型(ai,aj)的频度。然后达尔文选择依据选择方程调整表型的分布:其中，Q是群体的平均适应度。21

门德尔遗传学设pi是群体中等位基因的频率。假如 pi,j=pipj那么，可得基因型空间GS中的一个选择方程为：22

门德尔遗传学这个离散的选择方程可以用连续方程近似:假如qi,j=qj,i,那么这个离散的选择方程可以用连续方程近似:

23

门德尔遗传学这个方程很简洁被证明:这个结果称作Fisher基本定理。它说明平均适应度随适应度的差别呈正比例增加。事实上，全部可能的基因型仅有一部分实现。这就是遗传操纵子探究基因型空间的任务，其个体数目相当小。这些操纵子是群体遗传变异性的来源。最重要的操纵子是突变和重组。2412.3达尔文进化算法依据定量遗传学，达尔文进化算法接受简洁的突变/选择动力学。达尔文算法的一般形式可以描述如下：其中，：是一代的双亲数目，：为子孙数目，：称作“混杂”数，若双亲混合其基因，则=2。【注】：仅当是最好的个体才允许产生子孙。逗号“,”表示双亲们没有选择，加号“+”表示双亲有选择。

2512.3达尔文进化算法建立原始种体。通过突变建立子孙。选择：返回到步骤(1)。…2612.4分类器系统Holland和他的同事提出了一种分类器系统的认知模型,其中的规则不是规则集,而是遗传算法操纵的内部实体。下图给出了分类器系统的一般结构,它由三层动作构成,即执行子系统、信用赋值子系统和发觉子系统。27分类器系统（1）执行子系统处在最低层,干脆与环境进行交互。它与专家系统相同,由产生式规则构成。但是,它们是通过消息传送,高度并行工作。这类规则称作分类器。

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

（3）最终一层是发觉子系统,该系统必需产生新的规则,取代当前用处不大的规则。通过系统累积的阅历产生规则。系统依据适应值,运用遗传算法选择、重组和取代规则。28分类器系统分类器系统的一般结构发觉[遗传算法]信用赋值[桶链]执行[分类器系统]消息来自输入接口支付消息送出输出接口（目标）来自内部监控器的消息29分类器系统分类器系统是平行执行、消息传递和基于规则的系统。在简洁的方案中,消息接受规定的字母,全部为固定长度。全部规则接受条件/动作形式。每个条件规定必需满足的信息,每个动作规定当条件满足时所发送的消息。为了便利,假设消息接受长度为l的二进制字符串记录,字符接受子集{1,0,#}。30规则与消息产生式规则：IF<条件>THEN<动作>约定：条件的长度是固定的，用二进制数表示。定义：

Ifsj=1orsj=0,thenmj=sjIfsj=#,thenmjcanbeeither1or0.31规则与消息满足要求的全部消息构成子集,即每个子集是在消息空间的一个超平面。分类器系统是由一组分类器{C1,C2,…,CN}、一个消息表、输入接口、输出接口构成。每部分的主要功能如下:

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

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

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

(4)输出接口将结果消息翻译成效应器动作,修改环境状态。32分类器系统的基本结构分类器消息表(a)全部消息进行条件测试条件消息规约输出接口送到环境输入接口来自环境(a)(b)(b)选中分类器产生新消息33分类器基本算法将输入接口全部消息放入消息表。将消息表中的全部消息与全部分类器全部条件比较,记录全部匹配。满足分类器条件部分的每组匹配,将其动作部分所规定的消息送到新的消息表。用新的消息表取代消息表中的全部消息。将消息表中的消息翻译成输出接口的要求,产生系统当前的输出。返回到步骤(1)。34简洁的视觉分类器系统视觉向量视野运动向量对象检测器11110…消息35性质检测器规定的值1，假如移动对象0，其它(0,0)，假如对象在视野的中间(1,0)，假如对象在中心的左边(0,1)，假如对象在中心的右边1，假如系统是对象的近邻0，其它1，假如对象很大0，其它1，假如对象是狭长的0，其它36规则表示规则：IF假如有“捕食(prey)”(small,moving,nonstripedobject),处于视野中间(centered),非邻近(nonadjacent),THEN快速移向对象(ALIGN),(FAST).可以表示为：00#########000001/0100000000000000,ALIGN,FAST.37网络图[MOVING][SMALL][NOTSTRPED][NEAR][FAR]01001[ALERT]10001[TARGET]11001[PORSUE]11010[APPROACH]11011[FLEE]11100[FREEZE]10010[DANGER]38网络图的规则表示MOVING和ALERT之间的箭头：00#############1/01001###########SMALL，NOTSTRIPEDandALERT到TARGET的箭头：00########00####，01001###########/10001###########39学习机制分类器系统运用两个学习机制，桶链(bucketbrigade)算法。基于对系统的贡献,对现有规则支配一个信用值。规则发觉算法。这包括遗传算法，该算法可产生新规则，用于改善系统的学问库。4012.5桶链算法桶链(bucketbrigade)算法基于对系统的贡献,对现有规则支配一个信用值。主要解决多条规则同时要求被激活时的竞争问题。例如：下面的状况下应当选择哪条规则。0111→01##：0000→##00：0001→00#0：110041主要问题引入信用值后的两个问题：当多条规则同时要求被激活时，如何解决竞争问题对一规则被激活产生过作用的那些规则如何支配信用42桶链算法为解决上述两个问题，引入拍卖行和票据交易所：当有多个分类器获得匹配时，每个分类器要出一个与其强度成正比的叫价B叫价高的分类器被激活并允许发送消息，同时通过票据交易所,将其叫价B供应应激活的分类器。如此接着下去，一条规则可通过消费者获利（增加了强度），通过规则的不断激活形成一条消费者链，直至最终消费者（达到目标）干脆从环境中得到补偿。若链中一条规则导致错误结论，则序列上该规则的强度将减弱，并且沿着序列回溯，从而产生新的消费者链43举例环境0111，强度为0，叫价系数为0.1。索引号 分类器 强度1 01##：0000 2002 00#0：1000 2003 11##：1000 2004 ##00：0001 20044第一步分类器 强度消息匹配叫价01##：0000200E2000#0：100020011##：1000200##00：000120045其次步分类器 强度消息匹配叫价01##：0000180000000#0：100020012011##：1000200##00：0001200120两条规则同时激活46第三步分类器 强度消息匹配叫价01##：000022000#0：1000180110011##：1000200220##00：0001180000121847第四步分类器 强度消息匹配叫价01##：000022000#0：100021811##：10001801000##00：000116231648第五步分类器 强度消息匹配叫价强度01##：000022022000#0：100021821811##：1000196196##00：00011460001206规则4达到目标获得补偿60。49投标变更分类器的强度在时间t满足C送去消息的分类器对在t-1作用的分类器投标在时间t对分类器C的支持50分类器中的遗传算法遗传算法可产生新规则，用于改善系统的学问库。可以在三种状况下应用GA：引入一个参数T（时间间隔），用于限制何时运用GA。特殊状况时（如消息的条件都不能匹配）运用GA。系统的性能太差。51算法步骤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)。52算法说明算法中S0(Cj)是预知的；实现时考虑结束条件；该算法是经典GA的变种，其中没有变异算子；新分类器的强度是由旧分类器的强度确定的。5312.6遗传算法遗传算法先将搜寻结构编码为字符串形式,每个字符串结构被称为个体。然后对一组字符串结构(被称为一个群体)进行循环操作。每次循环被称作一代,包括一个保存字符串中较优结构的过程和一个有结构的、随机的字符串间的信息交换过程。类似于自然进化，遗传算法通过作用于染色体上的基因找寻好的染色体来求解问题。54遗传算法与自然界相像，遗传算法对求解问题的本身一窍不通，它所须要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。在遗传算法中，位字符串扮演染色体的作用，单个位扮演了基因的作用，随机产生一个体字符串的初始群体，每个个体赐予一个数值评价，称为适应度，取消低适应度的个体，选择高适应度的个体参与操作。常用的遗传算子有复制、杂交、变异和反转。55遗传算法与传统优化算法的主要不同遗传算法不是干脆作用在参变量集上,而是利用参变量集的某种编码;遗传算法不是从单个点,而是在群体中从一个点起先搜寻;遗传算法利用适应值信息,无需导数或其它帮助信息;遗传算法利用概率转移规则,而非确定性规则。56遗传算法的准备工作确定表示方案;确定适应值的度量;确定限制该算法的参数和变量;确定怎样指定结果及程序运行结束的标准。57基本的遗传算法随机产生一个由固定长度字符串组成的初始群体;对于字符串群体，迭代地执行下述步骤，直到选种标准被满足为止：计算群体中的每个个体字符串的适应值;应用下述三种操作(至少前两种)来产生新的群体:复制:把现有的个体字符串复制到新的群体中。杂交:通过遗传重组随机选择两个现有的子字符串,产生新的字符串。变异:将现有字符串中某一位的字符随机变异。把在后代中出现的最高适应值的个体字符串指定为遗传算法运行的结果。这一结果可以是问题的解(或近似解)。58基本遗传算法的流程图GEN=0概率地选择遗传操作随机创建初始群体是否满足选中标准？计算群体中每个个体的适应值i:=0i:=M指定结果结束GEN:=GEN+1是是否（转下页）59概率地选择遗传操作依据适应值选择一个个体完成杂交i:=i+1i:=i+1完成繁殖p(r)繁殖（接上页）基于适应值选择两个个体把新的两个孩子加到群体中p(c)杂交变异p(m)把新的孩子加入到群体中完成变异依据适应值选择一个个体把变异后个体加入到群体中60表示模式所谓模式就是一个相同的构形,它描述的是一个串的子集,这个集合中的串之间在某些位上相同。模式的复制生长方程：这表明,一个特定的模式依据其平均适应值与群体的平均适应值之间的比率生长。61杂交操作杂交操作是个有结构、随机的字符串间信息交换过程。简洁的杂交操作分为三步从当前群体B(t)中选择两个结构：随机选择一个整数交换a和a‘中位置x左边的元素,产生两个新的结构：62具有强度的遗传算法在t=0时随机产生M字符串的群体B(t)。计算群体B(t)中字符串的平均强度v(t),给群体B(t)中的每个字符串赋以规范值S(Cj,t)/v(t)。对群体B(t)中的每个字符串赋与一个概率值,其值与规范值成正比。然后,运用概率分布,从B(t)中选择n对字符串,n<<M,并且将它们复制。对每对复制字符串进行杂交操作,形成2n个新的字符串。用步骤(3)中生成的2n个新的字符串取代群体B(t)中2n个强度最低的字符串。时间t变为t+1,返回步骤(1)。63杂交操作举例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#64变异操作简洁的变异操作过程如下:每个位置的字符变量都有一个变异概率,各位置相互独立。通过随机过程选择发生变异的位置：产生一个新结构,其中是从对应位置的字符变量的值域中随机选择的一个取值。可以同样得到。65反转操作简洁反转操作的步骤如下:从当前群体中随机选择一个结构从中随机选择两个数i’和j’,并定义i=min{i',j'},j=max{i',j'};颠倒a中位置i、j之间的部分,产生新的结构66遗传算法举例问题：求（1）编码：此时取均长为5，每个染色体（2）初始群体生成：群体大小视状况而定，此处设置为4，随机产生四个个体：编码：01101，11000，01000，10011解码：1324819适应度：16957664361（3）适应度评价：67（4）选择：选择概率个体：01101，11000，01000，10011适应度：16957664361选择概率：0.140.490.060.31选择结果：01101，11000，11000，10011（5）交叉操作：发生交叉的概率较大哪两个个体配对交叉是随机的交叉点位置的选取是随机的（单点交叉）011010110011000110111100011001100111000068（6）变异：发生变异的概率很小（7）新群体的产生：保留上一代最优个体，一般为10%左右，至少1个用新个体取代旧个体，随机取代或择优取代。11000，11011，11001，10011（8）重复上述操作：说明：GA的终止条件一般人为设置；GA只能求次优解或满足解。分析：按其次代新群体进行遗传操作，若无变异，恒久也找不到最优解——择优取代有问题。若随机的将个体01101选入新群体中，有可能找到最优解。6912.7并行遗传算法基于离散门德尔模型的遗传算法由六部分组成：对给定问题求解的染色体表示；求解的原始物种；起环境作用的品质函数；可以生成子孙的个体的选择过程；一种遗传操纵子，如变异、重组；限制算法本身的参数。70并行遗传算法并行遗传算法：给定具有不同起先表型的N个个体；每个个体计算局部最大；选择——在“近邻”中选择配对；用重组和突变创建子孙；返回步骤2。7112.8分类器系统BooleWilson于1987年开发了一个布尔问题的分类器系统Boole(Wilson1987)。一个布尔函数变量L是从长度为L的字符串到{0,1}的映射。学习函数意味获得对任何输入字符串能给出正确输出0或1的实力。72分类器强度调整算法将与所选动作相同的分类器形成子集[M]，称作动作集[A]。将不在[M]中的其它分类器放在集合NOT[A]中。在[A]中的全部分类器强度削减一个分数e。假如系统决策正确，则将赢利量R支配给[A]的强度;假如系统决策错误，则将赢利量R'(其中0≤R'≤R)支配给[A]的强度，从[A]的强度削减一个分数p。至少R'和p中的一个为0。从NOT[A]中的强度减去一个分数t。73Boole的遗传算法依据[P]中分类器的强度，通过概率选择第一个分类器。依据概率,与步骤(1)相同，选择分类器，并对和进行杂交；从结果中选择一个作为子孙，另一个被抛弃。假如步骤(2)未完成，则复制形成子孙。对子孙应用变异操作，以概率变更每个分类的等位基因。假如通过杂交生成子孙，每个父母的强度削减三分之一，子孙的初始强度等于父母削减的总和；否则削减的一半，而子孙的初始强度等于削减的量。将子孙加到[P]中。依据[P]中分类器强度的概率分布，删除最小的一个分类器。7412.9规则发觉系统在规则发觉系统中,学习常常是首先评价系统现有的规则质量,然后进行修改。Grefenstette研制了一种规则发觉系统RUDI。问题求解级由简化的分类器系统组成。学习级是对学问结构群体进行遗传算法操作,每一个表示为一组规则表。学问结构的整个行为限制这些结构的复制。在RUDI中,信用赋值方法赢利共享规划(Profit-SharingPlan,简称PSP)和桶链算法(BBA)对每个规则供应互补的效用信息。依据期望的外部嘉奖,PSP-强度对规则效用供应更精确的评估。当问题求解时它被用作冲突消解。与此相反,BBA-强度表示规则之间的动态相关性,规则点火依次会聚到相像水平。这种测度可以用作一组协作规则的聚类。75规则发觉系统Grefenstette提出一种强度修改方案称作嬴利共享规划PSP。在这种方案中问题求解划分成情节,按所接受的外部嘉奖区分。假如任何步情节在投标竞争中获胜,则认为该规则在该情节活动。在情节t,PSP修改每个活动规则Ri的强度Si(t)如下:

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