资源描述
单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,人 工 智,能,第5,章 计算智能,(2),Computational Intelligence,进化计算,人工生命,进化计算包括：,遗传算法,(,genetic algorithms,，,GA),进化策略,(,evolutionary strategies),进化编程,(,evolutionary programming),遗传编程,(,genetic programming),人类不满足于模仿生物进化行为，希望能够建立具有自然生命特征的人造生命和人造生命系统。,人工生命是人工智能和计算智能的一个新的研究热点。,3,5.1,遗传算法,遗传算法是模仿生物遗传学和自然选择机理，通过人工方式所构造的一类优化搜索算法，是对生物进化过程进行的一种数学仿真，是进化计算的最重要的形式。,遗传算法为那些难以找到传统数学模型的难题指出了一个解决方法。,进化计算和遗传算法借鉴了生物科学中的某些知识，这也体现了人工智能这一交叉学科的特点。,4,5.1.1,遗传算法的基本机理,霍兰德的遗传算法通常称为简单遗传算法（,SGA,）。,现以此作为讨论主要对象，加上适应的改进，来分析遗传算法的结构和机理。,编码与解码,适应度函数,遗传操作,5.1,遗传算法,5,1.,编码与解码,将问题结构变换为位串形式编码表示的过程叫,编码,；而相反将位串形式编码表示变换为原问题结构的过程叫,解码或译码,。把位串形式编码表示叫染色体，有时也叫,个体,。,遗传算法的编码方法有二进制编码、浮点数编码方法、格雷码、符号编码方法、多参数编码方法等。,6,二进制编码,最常用的编码方法,假设某一参数的取值范围是,A,，,B,，,A,B,。,用长度为,l,的二进制编码串来表示该参数，将,A,，,B,等分成,2,l,-1,个子部分，记每一个等分的长度为,。,参数编码的对应关系:,解码,假设某一个体的编码是：,X：,x,l,x,l-1,x,l-2,x,2,x,1,，,则上述二进制编码所对应的解码公式为：,00000000 ,00000000,=0 ,A,00000000 00000001=1 A+, ,11111111 11111111= -1 B,7,二进制编码的最大缺点之一是长度较大，对很多问题用其他主编码方法可能更有利,符号编码方法,是指个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集。,例如，对于,TSP,问题，采用符号编码方法，按一条回路中城市的次序进行编码，一般情况是从城市,w,1,开始，依次经过城市,w,2,，,w,n,，,最后回到城市,w,1,，,我们就有如下编码表示：,由于是回路，记,w,n+1,=,w,1,。,它其实是,1，,n,的一个循环排列。要注意,w,1,，,w,2,，,w,n,是互不相同的。,8,2.,适应度函数,体现染色体的适应能力，对问题中的每一个染色体都能进行度量的函数，叫,适应度函数（,fitness function）,对优化问题，适应度函数就是目标函数。,TSP,的目标是路径总长度为最短，路径总长度可作为,TSP,问题的适应度函数：,9,3.,遗传操作,简单遗传算法的遗传操作主要有有三种,:,选择,(,selection)、,交叉,(,crossover)、,变异,(,mutation)。,改进的遗传算法大量扩充了遗传操作，以达到更高的效率。,选择操作,也叫复制（,reproduction）,操作，根据个体的适应度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。,一般地说，选择将使适应度较大（优良）个体有较大的存在机会，而适应度较小（低劣）的个体继续存在的机会也较小。,10,交叉操作,交叉操作的简单方式是将被选择出的两个个体,P1,和,P2,作为父母个体，将两者的部分码值进行交换,假设有八位长的二个体，产生一个在,1到8,之间的随机数,c，,假如现在产生的是,3,，将,P1,和,P2,的低三位交换,1,0,0,0,1,1,1,0,1,1,0,1,1,0,0,1,P1,P2,1,1,0,0,0,1,11,变异操作,返回,变异操作的简单方式是改变数码串的某个位置上的数码,二进制编码表示的简单变异操作是将,0与1,互换：,0,变异为,1，1,变异为,0,TSP,的变异操作：随机产生一个,1至,n,之间的数,k，,对回路中的第,k,个城市的代码,w,k,作变异操作，又产生一个,1至,n,之间的数,w，,替代,w,k,，,并将,w,k,加到尾部，得到：,12,5.1.2,遗传算法的求解步骤,1.,遗传算法的特点,(1),遗传算法是对参数集合的编码而非针对参数本身进行进化；,(2),遗传算法是从问题解的编码组开始而非从单个解开始搜索；,(3),遗传算法利用目标函数的适应度这一信息而非利用导数或其它辅助信息来指导搜索；,(4),遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作。,5.1,遗传算法,13,2.,遗传算法的框图,(图5.2),(1),初始化种群,;,(2),计算种群上每个个体的适应度值,;,(3),按由个体适应度值所决定的某个规则选,择将进入下一代的个体,;,(4),按概率,Pc,进行交叉操作,;,(5),按概率,Pm,进行变异操作,;,(6),若没有满足某种停止条件，则转第,(2),步，,否则进入下一步。,(7),输出种群中适应度值最优的染色体作为问题的满意解或最优解。,5.1,遗传算法,14,初始化种群,变异操作,计算适应度值,选择操作,交叉操作,最优解输出,终止条件？,图5.2,算法框图,返回,5.1,遗传算法,否,是,开始,结束,(1),(2),(3),(4),(5),(6),(7),15,遗传算法的一般结构表示,Procedure: Genetic Algorithms,begin,t 0;,initialize P(t);evaluate P(t);,while (not termination condition ) do,begin,recombine P(t) to yield C(t);,evaluate C(t);,select P(t+1) from P(t) and C(t);,t t+1;,end,end,5.1,遗传算法,16,3.,遗传算法求解举例,5.1,遗传算法,设,用,SGA,求,遗传算法归纳为五个基本组成部份,方案表示,种群初始化,适应度函数,遗传操作,算法参数,17,5.1.3,SGA,及其模式定理,回顾,：,（1）,GA,的,基本原理与算法框架,；,（2）,GA,的,基本遗传算子,；,问题,：,（1）基本遗传算法（,SGA）,的算法步骤；,（2）,GA,的计算实例；,（3）,GA,有效性的理论证明；,5.1,遗传算法,18,SGA,的算法步骤,5.1,遗传算法,(1),编码：,随机产生一个由确定长度的特征字符串组成的初始种群。,(2),进化：,对该字符串种群迭代的执行下面的步和步 ，直到满足停止标准：, 计算种群中每个个体字符串的,适应值,；, 应用,复制、交叉和变异,等遗传算子产生下一代种群。,(3),解码：,把在后代中出现的最好的个体字符串指定为遗传算法的执行结果，这个结果可以表示问题的一个解。,19,产生初始种群,计算每个个体的适应值,GEN:=GEN+1,依概率选择遗传操作,执行复制,选择一个个体,i,:=,i,+1,选择两个个体,选择一个个体,执行变异,i,:=0,复制到新种群,i,:=,i,+1,将两个后代插入新种群,插入到新种群,执行杂交,指定结果,是,否,是,否,变异,复制,交叉,结束,GEN:=0,是否满足停止准则,i=M?,5.1,遗传算法,20,SGA,的伪代码描述,Procedure: Simple Genetic Algorithms,begin,t 0;,initialize P(t);evaluate P(t);,while (not termination condition ) do,begin,recombine P(t) to yield C(t);,P(t) C(t);,evaluate P(t);,t t+1;,end,end,5.1,遗传算法,21,一个简单的计算实例,例：极大值问题,max,f,(,x,)=,x,2,x,0,31,1. 编码：5位二进制数；,2.,初始群体：群体规模为4个个体，随机产生；,假设为：01101，11000，01000，10011,3. 适应度计算： （适应值直接取,f,(,x,) ）,4.,选择复制产生下一代群体；（选择概率按适应值大小采用轮盘赌的随机策略）,5.1,遗传算法,31,0,f=x,2,个体编号,初始群体,基因译码,适应度计算,f,(,x,i,)/,f,(,x,i,),f,(,x,i,)/,f,下一代群体复制数,1,01101,13,169,0.14,0.58,1,2,11000,24,576,0.49,1.97,2,3,01000,8,64,0.06,0.22,0,4,10011,19,361,0.31,1.23,1,22,5. 个体基因交叉；（一般交叉概率较大0.70.9）,6.,个体基因变异（一般变异概率较小0.0010.01 ）,7. 转3直至算法终止。,个体编号,复制后的群体,基因译码,适应度计算,交叉对象,交叉位置,交叉后的群体,适应度计算,1,01101,13,169,2,4,01100,144,2,11000,24,576,1,4,11001,625,3,11000,24,576,4,3,11011,729,4,10011,19,361,3,3,10000,256,5.1,遗传算法,23,模式的定义,思考：,（1）,SGA,优化搜索中遗传算子的作用？,（2）,怎样从理论上证明,SGA,能依概率搜索到优良解答的有效性？,模式：,我们将群体中的个体即基因串中的相似样板称为“模式”。,模式表示基因串某些特征位相同的结构。,它描述的是一个串中的子集，在二进制编码的串中，模式是基于三个字符集（0，1，*）的字符串，符号* 代表任意字符，即0或1。例如模式*1*描述了一个四个元的子集010,011,110,111。,一般一个模式代表了多个个体，一个个体符合多个模式；,5.1,遗传算法,24,模式的阶与定义距,模式阶：,模式,H,中确定位置的个数成为模式,H,的模式阶，记作,O,（,H,）,。,例如,O,（0 1 1 * 1 * ）4。,模式阶用来反映不同模式间确定性的差异，模式阶数越高，模式的确定性就越高，所匹配的样本个数就越少。,定义距（长度）：,模式,H,中的第一个确定位置和最后一个确定位置之间的距离称为模式的定义距，记作,(H),。,例如，,(0 1 1 * 1 * * ),4,。,在遗传查找中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就反映了这种性质的差异。,5.1,遗传算法,25,模式定理,模式定理（,Schema Theorem）,：,如果在给定的时间步,t,，,一个特定的模式,H,有,m,个代表串包含在种群,A,(,t,),中，记为,m,(,H,t,),，,f,(,H,),表示在时间步,t,模式,H,的串平均适应度，整个种群的平均适应度为,f,，,l,为二进制染色体基因串长，,p,c,为交叉概率，,p,m,为变异概率，则在基本遗传算法（,SGA）,的机制下有：,结论2.3.1.1 若遗传算法只采用选择复制操作，有下式成立，,结论2.3.1.2 若遗传算法同时考虑选择复制与交叉操作，有下式成立，,结论2.3.1.3 若遗传算法同时考虑选择复制、交叉与变异操作，有下式成立，,5.1,遗传算法,26,模式定理的意义,模式定理的意义：,在遗传算子选择、交叉、变异的作用下，具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代中呈指数增长。,积木块假说；,SGA,最新的理论研究：,（1）浓度模型；,（2）概率模型；,5.1,遗传算法,27,GA,与,进化计算的发展,进化计算（,Evolutionary,computing,）,灵感计算（,inspired computing,）,自然计算（,Nature,computing,）,进化计算,蚁群系统,量子遗传算法,人工免疫系统,人工内分泌系统,复杂自适应系统,28,5.2,进化策略,进化策略,(,Evolution Strategies，ES),是一类模仿自然进化原理以求解参数优化问题的算法。,它是由雷切伯格（,Rechenberg,）、,施韦费尔（,Schwefel,）,和彼得,比纳特（,Peter,Bienert,）,于1964,年提出的，并在德国共同建立的。,29,5.2.1,进化策略的算法模型,寻求与函数极值关联的实,n,维矢量,x,。,随机选择父矢量的初始种群。,父矢量,x,i,i,=1,p,产生子代矢量,x,i,。,对误差,(,i,=1,p,),排序以选择和决定保持哪些矢量。,继续产生新的试验数据以及选择最小误差矢量。,5.2,进化策略,30,5.2.2,进化策略和遗传算法的区别,进化策略和遗传算法有着很强的相似性，它们都是一类模仿自然进化原理的算法。,两者也存在着区别，其中最基本的区别是它们的研究领域不同。,进化策略是一种数值优化的方法，它采用一个具有自适应步长和倾角的特定爬山方法。,遗传算法从广义上说是一种自适应搜索技术。,5.2,进化策略,31,5.3,进化编程,进化编程,(,Evolutionary Programming，EP)，,又称为进化规划（,Evolutionary Planning），,是由福格尔（,Fogel,）,在1962,年提出的一种模仿人类智能的方法。,进化编程根据正确预测的符号数来度量适应值。通过变异，为父代种群中的每个机器状态产生一个子代。父代和子代中最好的部分被选择生存下来。,它的提出是受自然生物进化机制的启发。,32,5.3.1,进化编程的机理与表示,进化编程的过程，可理解为从所有可能的计算机程序形成的空间中，搜索具有高的适应度的计算机程序个体。,进化编程设计强调种群行为的变化。进化编程系统的表示自然地面向任务级。一旦选定一种适应性表示，就可以定义依赖于该表示的变异操作，在具体的父辈行为上创建后代。,5.3,进化编程,33,5.3.2,进化编程的步骤,进化编程分为三个步骤：,产生出初始种群。,迭代完成下述子步骤，直至满足选种标准为止：,执行种群中的每个程序。,应用变异等操作创造新程序种群。,在后代中适应值最高的计算机程序个体被指定为进化编程的结果。,5.3,进化编程,34,变异和创造子代,评估已存在的,FSM,用最好的状态机预测和添加符号,选择父代,初始化观测顺序,是,否,初始化种群,图5.6,进化编程的基本过程,5.3,进化编程,是否预测,35,5.4,人工生命,自然界是生命之源。自然生命千千万万，千姿百态，千差万别，巧夺天工，奇妙无穷。,人工生命（,Artificial Life,，,AL,）,试图通过人工方法建造具有自然生命特征的人造系统。,人工生命是生命科学、信息科学和系统科学等学科交叉研究的产物，其研究成果必将促进人工智能的发展。,36,5.4.1,人工生命研究的起源和发展,人类长期以来一直力图用科学技术方法模拟自然界，包括人脑本身。,1943,年麦卡络奇和皮茨提出了,MP,神经学网络模型。,人工生命的许多早期研究工作也源于人工智能。,20,世纪,70,年代以来，康拉德（,Conrad,）,等提出不断完善的“人工世界”模型。,80,年代,90,年代,5.4,人工生命,37,5.4.2,人工生命的定义和研究意义,人工生命是一项抽象地提取控制生物现象的基本动态原理，并且通过物理媒介（如计算机）来模拟生命系统动态发展过程的研究工作。,通俗地讲，人工生命即人造的生命，非自然的生命。然而，要对人工生命做出严格的定义，却需要对问题进行深入研究。,5.4,人工生命,38,人工生命系统,1987,年兰德提出的人工生命定义为：“人工生命是研究能够演示出自然生命系统特征行为的人造系统”。,通过计算机或其它机器对类似生命的行为进行综合研究，以便对传统生物科学起互补作用。,兰德在计算机上演示了他们研制的具有生命特征的软件系统，并把这类具有生命现象和特征的人造系统称为人工生命系统。,5.4,人工生命,39,自然生命的共同特征和现象,自繁殖、自进化、自寻优,自成长、自学习、自组织,自稳定、自适应、自协调,物质构造,能量转换,信息处理,5.4,人工生命,40,研究人工生命的意义,人工生命是自然生命的模拟、延伸与扩展，其研究开发有重大的科学意义和广泛的应用价值。,开发基于人工生命的工程技术新方法、新系统、新产品,为自然生命的研究提供新模型、新工具、新环境,延伸人类寿命、减缓衰老、防治疾病,扩展自然生命，人工进化、优生优育,促进生命、信息、系统科学的交叉与发展,5.4,人工生命,41,5.4.3,人工生命的研究内容和方法,1.,人工生命的研究内容,人工生命的研究内容大致可分为两类：,(1),构成生物体的内部系统，包括脑、神经系统、内分泌系统、免疫系统、遗传系统、酶系统、代谢系统等。,(2),在生物体及其种群的外部系统，包括环境适应系统和遗传进化系统等。,5.4,人工生命,42,人工生命的科学框架,生命现象仿生系统,生命现象的建模与仿真,进化动力学,人工生命的计算理论和工具,进化机器人,进化和学习等的结合,人工生命的应用,5.4,人工生命,43,2.,人工生命的研究方法,（1,）信息模型法,根据内部和外部系统所表现的生命行为来建造信息模型。,（,2,）工作原理法,生命行为所显示的自律分数和非线性行为，其工作原理是混沌和分形，以此为基础研究人工生命的机理。,5.4,人工生命,44,人工生命的研究技术途径,(1),工程技术途径,利用计算机、自动化、微电子、精密机械、光电通信、人工智能、神经网络等有关工程技术方法和途径，研究开发、设计制造人工生命。通过计算机屏幕，以三维动画，虚拟现实的软件方法或采用光机电一体化的硬件装置来演示和体现人工生命。,5.4,人工生命,45,(2),生物科学途径,利用生物科学方法和技术，通过人工合成、基因控制，无性繁殖过程，培育生成人工生命。,由于伦理学、社会学、人类学等方面的问题，通过生物科学途径生成的人工生命，如克隆人引起了不少争论。需要研究和制订相应的社会监督、国家法律和国际公约。,5.4,人工生命,46,5.4.4,人工生命的实例,人工脑,波兰人工智能和心理学教授安奇,布勒（,Andrzej,Buller,）,及一些日本学者在日本现代通讯研究所进化系统研究室对人工脑的研究，已取得重要进展。,计算机病毒,计算机进程,细胞自动机,人工核苷酸,5.4,人工生命,47,5.5,小结,进化计算,遗传算法,进化策略,进化编程,人工生命,计算智能研究的最新领域之一,重要科学意义和社会效益,研究内容、发展前景和应用领域,48,
展开阅读全文