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

1第十二章进化计算与遗传算法徐从富浙江大学人工智能研究所2003年11月2本章主要参考文献：[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.3内容12.1概述12.2进化系统理论的形式模型12.3达尔文进化算法12.4分类器系统12.5桶链算法12.6遗传算法12.7并行遗传算法12.8分类器系统Boole12.9规则发现系统12.10进化策略12.11进化程序设计412.1概述12.1.1背景人们对很多高度非线性问题的内部机理还很不清楚：智能模拟非线性优化图像识别，等等。要解决上述问题，就需要一些具有自组织、自适应能力的大规模并行算法，模拟生物或自然现象就成为AI中的一种自然而又重要的研究方向。因此产生了如下新方法：人工神经网络遗传算法、进化计算，等等。5生物进化的主要特点：进化的结果非常复杂进化的过程非常简单：繁殖、变异、竞争、选择基于自然选择的软件设计方法解决传统方法中存在的如下最大障碍：需要事先描述问题的全部特点，并说明针对问题的特点，程序应采取的措施。利用进化机理，人们可以“培育”程序，去解决那些结构尚不清楚的问题。12.1.1背景（续）6遗传算法和进化计算的基本思想：来源于生物进化过程,它是基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的搜索算法（以字符串表示状态空间）。遗传算法用概率搜索过程在该状态空间中搜索，产生新的样本。遗传算法和进化计算是一种通用的问题求解方法，它采用某种编码技术来表示各种复杂的结构，并将每个编码称为一个个体。算法维持一个一定数目的编码集合，称为种群，并通过对种群中的每个个体进行某些遗传操作（如变异、交叉、选择等）来模拟进化过程，最终获得一些具有较高性能指标的编码。12.1.3基本思想7发展历史遗传算法的发展历史：1965年，Holland首次提出了人工遗传操作的重要性，并把这些应用于自然系统和人工系统中。1967年，Bagley在他的论文中首次提出了遗传算法（GeneticAlgorithm，简称GA）这一术语，并讨论了遗传算法在自动博弈中的应用。1970年，Cavicchio把遗传算法应用于模式识别中。第一个把遗传算法应用于函数优化的是Hollstien。8发展历史（续）•1975年是遗传算法研究的历史上十分重要的一年。这一年，Holland出版了他的著名专著“AdaptationinNaturalandArtificialSystems”(《自然和人工系统的自适应性》)该书系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论（SchemataTheory），该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。•同年，DeJong完成了他的重要论文“AnAnalysisoftheBehaviorofaClassofGeneticAdaptiveSystems”(《遗传自适应系统的行为分析》)。他在该论文中所做的研究工作可看作是遗传算法发展过程中的一个里程碑，这是因为他把Holland的模式理论与他自己的实验结合起来。9发展历史（续）•1988年Mayr提出新达尔文进化理论。•1989年Goldberg对遗传算法从理论、方法和应用上作了系统的总结.10特点特点：通用鲁棒次优解、满意解遗传算法能解决的问题：优化NP完全问题NP难解问题高度复杂的非线性问题11进化计算和遗传算法的主要应用领域：应用领域说明控制规划设计组合优化图像处理信号处理机器人人工生命瓦斯管道控制、防避导弹控制、机器人控制生产规划、并行机任务分配VLSI部局、通信网络设计、喷气发动机设计TSP问题、背包问题、图划分问题模式识别、特征抽取滤波器设计路径规划生命的遗传进化12遗传算法与自然进化的比较自然界染色体基因等位基因(allele)染色体位置(locus)基因型(genotype)表型(phenotype)遗传算法字符串字符，特征特征值字符串位置结构参数集，译码结构13面向执行的学习系统任务子系统学习子系统任务检测器…1dmd…1eme任务效应器执行效应器执行检测器14新达尔文进化理论的主要论点1)个体是基本的选择目标;2)随机过程在进化中起重大作用,遗传变异大部分是偶然现象;3)基因型变异大部分是重组的产物,特别是突变;4)逐渐进化可能与表型不连续有关;5)不是所有表型变化都是自然选择的必然结果;6)进化是在适应中变化的,形式多样,不仅是基因的变化;7)选择是概率型的,而不是决定型的。1512.2进化系统理论的形式模型进化在个体群体中起作用。1974年Waddington指出基因型和表型之间关系的重要性。群体禁止异构环境。但是“后成环境”是多维空间。表型是基因型和环境的产物。然后表型通过异构“选择环境”发生作用。【注】：这种多维选择环境与后成环境空间是不同的。现在，适应性是表型空间和选择环境空间的产物。它经常被取作一维，表示多少子孙对下一代作出贡献。基于上述思想，1989年Muhlenbein和Kindermann提出了一种称为进化系统理论的形式模型。16进化系统理论的形式模型进化的主要过程后生环境遗传操作符选择环境gp17进化系统理论的形式模型}),,...,({1iinAaaagGS基因型空间：}),,...,({1IRppppPSim表型空间：其中，g是基因型p是表型基因gi的可能值称为等位基因。在门德尔(Mendel)遗传学中，假设每个基因有有限个等位基因。18进化系统理论的形式模型},...,{1kEPEPEP后生环境：),(EPgfpPSEPGSf：变换函数：IRtESpqi),,(质量函数：这个变换函数给出了模型，说明表型的发展是通过基因与环境的交互作用而实现的。变换过程是高度非线性的。19进化系统理论的形式模型IRtESpqi),,(质量函数：质量函数q给出了具体选择环境ESi下表型的质量，其定义如下：质量函数定义适应度，用于达尔文选择。目前主要有三种通用模型，即门德尔遗传学遗传生态学进化配子20门德尔遗传学在门德尔遗传学中，基因型被详细模型化，而表型和环境几乎被忽略；在遗传生态学中恰好相反；进化配子论是从社会生物学导出的模型。首先，讨论门德尔遗传学的选择模型。为简单起见，假设一个基因具有n个等位基因a1,…,an。二倍基因型以元组(ai,aj)为特征。定义pi,j为总群体中基因型(ai,aj)的频度。假设基因型与表型相等。质量函数给每个表型赋值。q(ai,aj)=qi,jqi,j可被解释为出生率减去死亡率。21门德尔遗传学假设p’i,j是下一代表型(ai,aj)的频度。然后达尔文选择根据选择方程调整表型的分布:Qqppjijiji,,,'jijijipqQ,,,其中，Q是群体的平均适应度。22门德尔遗传学设pi是群体中等位基因的频率。如果pi,j=pipj那么，可得基因型空间GS中的一个选择方程为：'/iiippQQjjjiipqQ,23门德尔遗传学这个离散的选择方程可以用连续方程近似:QQQpdtdpiii/)(如果qi,j=qj,i,那么这个离散的选择方程可以用连续方程近似:)(QQpdtdpiii24门德尔遗传学这个方程很容易被证明:0)(2))((222QVarQQEdtQd这个结果称作Fisher基本定理。它说明平均适应度随适应度的差别呈正比例增加。实际上，全部可能的基因型仅有一部分实现。这就是遗传操纵子探索基因型空间的任务，其个体数目相当小。这些操纵子是群体遗传变异性的来源。最重要的操纵子是突变和重组。2512.3达尔文进化算法根据定量遗传学，达尔文进化算法采用简单的突变/选择动力学。达尔文算法的一般形式可以描述如下：)/(),/(其中，：是一代的双亲数目，：为子孙数目，：称作“混杂”数，若双亲混合其基因，则=2。【注】：仅当是最好的个体才允许产生子孙。逗号“,”表示双亲们没有选择，加号“+”表示双亲有选择。2612.3达尔文进化算法1)建立原始种体。2)通过突变建立子孙。3)选择：4)返回到步骤(1)。11'sgs111''Zsxx…sgs'Zsxx'')}'({max)(1xQxQi2712.4分类器系统Holland和他的同事提出了一种分类器系统的认知模型,其中的规则不是规则集,而是遗传算法操纵的内部实体。下图给出了分类器系统的一般结构,它由三层动作构成,即执行子系统、信用赋值子系统和发现子系统。28分类器系统（1）执行子系统处在最低层,直接与环境进行交互。它与专家系统相同,由产生式规则构成。但是,它们是通过消息传送,高度并行工作。这类规则称作分类器。（2）分类器系统中的学习,要求环境提供反馈,确认所希望的状态是否达到。系统将评价这些规则的有效性,这些活动常常称作信用赋值。有些特定算法专门用来实现信用赋值,例如,桶链算法。（3）最后一层是发现子系统,该系统必须产生新的规则,取代当前用处不大的规则。通过系统累积的经验产生规则。系统根据适应值,使用遗传算法选择、重组和取代规则。29分类器系统分类器系统的一般结构发现[遗传算法]信用赋值[桶链]执行[分类器系统]消息来自输入接口支付消息送出输出接口（目标）来自内部监控器的消息30分类器系统分类器系统是平行执行、消息传递和基于规则的系统。在简单的方案中,消息采用规定的字母,全部为固定长度。全部规则采用条件/动作形式。每个条件规定必须满足的信息,每个动作规定当条件满足时所发送的消息。为了方便,假设消息采用长度为l的二进制字符串记录,字符采用子集{1,0,#}。31规则与消息产生式规则：IF条件THEN动作约定：条件的长度是固定的，用二进制数表示。定义：kimmmmmessageik,...,1},1,0{,,...,,::21为通配符#,,...,1},#,1,0{,,...,,::21kissssconditionikmessageconditionclassifier/::Ifsj=1orsj=0,thenmj=sjIfsj=#,thenmjcanbeeither1or0.32规则与消息满足要求的全部消息构成子集,即每个子集是在消息空间的一个超平面。分类器系统是由一组分类器{C1,C2,…,CN}、一个消息表、输入接口、输出接口构成。每部分的主要功能如下:(1)输入接口将当前环境状态翻译成标准消息。(2)分类器根据规则,规定系统处理消息的过程。(3)消息表包含当前全部消息。(4)输出接口将结果消息翻译成效应器动作,修改环境状态。33分类器系统的基本结构分类器消息表(a)全部消息进行条件测试条件消息规约输出接口送到环境输入接口来自环境(a)(b)(b)选中分类器产生新消息34分类器基本算法1)将输入接口全部消息放入消息表。2)将消息表中的全部消息与全部分类器所有条件比较,记录所有匹配。3)满足分类器条件部分的每组匹配,将其动作部分所规定的消息送到新的消息表。4)用新的消息表取代消息表中的全部消息。5)将消息表中的消息翻译成输出接口的要求,产生系统当前的输出。6)返回到步骤(1)。35简单的视觉分类器系统视觉向量视野运动向量对象检测器11110…消息1d2d3d4d36性质检测器规定的值1d1，如果移动对象0，其它),(32dd(0,0)，如果对象在视野的中间(1,0)，如果对象在中心的左