计算智能-进化计算.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,计算智能是信息科学、生命科学、认知科学等不同学科相互交叉的产物。它主要借鉴仿生学的思想，基于人们对生物体智能机理的认识，采用数值计算的方法去模拟和实现人类的智能。,计算智能主要研究领域包括：神经计算、进化计算、模糊计算、免疫计算、,DNA,计算、粗糙集等。,2.1,概述,2.1.1,什么是计算智能,2.1.2,计算智能的产生与发展,2.1.3,计算智能与人工智能的关系,2.2,进化计算,第,2,讲,计算智能之进化计算,1,2.1.1,什么是计算智能,概念解释,计算智能（,Computational Intelligence,，,CI,）目前还没有一个统一的的定义，使用较多的是美国科学家贝慈德克（,J.C.Bezdek,）从计算智能系统角度所给出的定义。,从计算智能系统角度,如果一个系统仅处理低层的数值数据，含有模式识别部件，没有使用人工智能意义上的知识，且具有计算适应性、计算容错力、接近人的计算速度和近似于人的误差率这,4,个特性，则它是计算智能的。,从学科范畴看,计算智能是在神经网络（,Neural Networks,NN,）、进化计算（,Evolutionary Computation,EC,）及模糊系统（,Fuzzy System,FS,）这,3,个领域发展相对成熟的基础上形成的一个统一的学科概念。,2,2.1.1,什么是计算智能,研究领域,神经网络,是一种对人类智能的结构模拟方法，它是通过对大量人工神经元的广泛并行互联，构造人工神经网络系统去模拟生物神经系统的智能机理的。,进化计算,是一种对人类智能的演化模拟方法，它是通过对生物遗传和演化过程的认识，用进化算法去模拟人类智能的进化规律的。,模糊计算,是一种对人类智能的逻辑模拟方法，它是通过对人类处理模糊现象的认知能力的认识，用模糊逻辑去模拟人类的智能行为的。,综合解释,从贝慈德克的定义和上述学科范畴可以看出以下两点：,第一，计算智能是借鉴仿生学的思想，基于生物神经系统的结构、进化和认知对自然智能进行模拟的。,第二，计算智能是一种以模型（计算模型、数学模型）为基础，以分布、并行计算为特征的自然智能模拟方法。,3,2.1.2,计算智能的产生与发展,1992,年，贝慈德克在,Approximate Reasoning,学报上首次 提出了“计算智能”的概念。,1994,年,6,月底到,7,月初，,IEEE,在美国佛罗里达州的奥兰多市召开了首届国际计算智能大会,(,简称,WCCI94),。会议第一次将神经网络、进化计算和模糊系统这三个领域合并在一起，形成了“计算智能”这个统一的学科范畴。,在此之后，,WCCI,大会就成了,IEEE,的一个系列性学术会议，开始是,4,年举办一次，现在是每,2,年举办一次。,1998,年,5,月，在美国阿拉斯加州的安克雷奇市又召开了第,2,届计算智能国际会议,WCCI98,。,2002,年,5,月，在美国夏威夷州首府火奴鲁鲁市又召开了第,3,届计算智能国际会议,WCCI02,。,WCCI2014,在北京召开。,此外，,IEEE,还出版了一些与计算智能有关的刊物,:IEEE Trans.Neural Networks,IEEE Trans.Fuzzy Systems,IEEE Trans.Evolutionary Computation,。,目前，计算智能已成为智能科学技术一个重要的研究领域。,4,2.1.3,计算智能与人工智能的关系,目前，对计算智能与人工智能的关系有,2,种观点，一种认为计算智能是人工智能的一个子集，另一种认为计算智能和人工智能是不同的范畴。,第一种观点的代表人物是贝慈德克。他把智能（,Intelligence,，,I,）和神经网络（,Neural Network,，,NN,）都分为计算的（,Computational,，,C,）、人工的（,Artificial,，,A,）和生物的（,Biological,B,）,3,个层次，并以模式识别（,PR,）为例，给出了下图所示的智能的层次结构。,在该图中，底层是计算智能（,CI,），它通过数值计算来实现，其基础是,CNN,；中间层是人工智能（,AI,），它通过人造的符号系统实现，其基础是,ANN,；顶层是生物智能（,BI,），它通过生物神经系统来实现，其基础是,BNN,。,按照贝慈德克的观点，,CNN,是指按生物激励模型构造的,NN,，,ANN,是指,CNN+,知识，,BNN,是指人脑，即,ANN,包含了,CNN,，,BNN,又包含了,ANN,。对智能也一样，贝慈德克认为,AI,包含了,CI,，,BI,又包含了,AI,，即计算智能是人工智能的一个子集。,5,CNN,CPR,CI,ANN,APR,AI,BNN,BPR,BI,人类知识,(+),传感输入,知识,(+),传感数据,计算,(+),传感器,B,生物的,A,符号的,C,数值的,复杂性,复杂性,输入,层次,贝慈德克的智能的,3,个层次,2.1.3,计算智能与人工智能的关系,6,第二种观点是大多数学者所持有的观点，其代表人物是艾伯哈特（,R.C.Eberhart,）。他们认为：虽然人工智能与计算智能之间有重合，但计算智能是一个全新的学科领域，无论是生物智能还是机器智能，计算智能都是其最核心的部分，而人工智能则是外层。,事实上，,CI,和传统的,AI,只是智能的两个不同层次，各自都有自身的优势和局限性，相互之间只应该互补，而不能取代。,大量实践证明，只有把,AI,和,CI,很好地结合起来，才能更好地模拟人类智能，才是智能科学技术发展的正确方向。,2.1.3,计算智能与人工智能的关系,7,2,.1,概述,2.2,进化计算,2.2.1,进化计算概述,2.3.2,遗传算法,第,2,讲 计算智能之进化计算,8,进化计算（,Evolutionary Computation,EC,）是在达尔文（,Darwin,）的进化论和孟德尔（,Mendel,）的遗传变异理论的基础上产生的一种在基因和种群层次上模拟自然界生物进化过程与机制的问题求解技术。它主要包括,遗传算法（,Genetic Algorithm,，,GA,）,进化策略（,Evolutionary Strategy,ES,）,进化规划（,Evolutionary Programming,EP,）,遗传规划（,Genetic Programming,GP,）四大分支。,其中，第一个分支是进化计算中最初形成的一种具有普遍影响的模拟进化优化算法。因此我们主要讨论遗传算法。,2.2,进化计算,9,进化计算是一种模拟自然界生物进化过程与机制进行问题求解的自组织、自适应的随机搜索技术。它以达尔文进化论的“物竟天择、适者生存”作为算法的进化规则，并结合孟德尔的遗传变异理论，将生物进化过程中的,繁殖（,Reproduction,）,变异（,Mutation,）,竞争（,Competition,）,选择（,Selection,）,引入到了算法中。,2.2.1,进化计算概述,1.,进化计算及其生物学基础,(1/3),(,1),什么是进化计算,10,(2),进化计算的生物学基础,自然界生物进化过程是进化计算的生物学基础，它主要包括遗传,(Heredity),、变异,(Mutation),和进化,(Evolution),理论。,遗传理论,遗传是指父代（或亲代）利用遗传基因将自身的基因信息传递给下一代（或子代），使子代能够继承其父代的特征或性状的这种生命现象。,在自然界，构成生物基本结构与功能的单位是细胞（,Cell,）。,细胞中含有一种包含着所有遗传信息的复杂而又微小的丝状化合物，人们称其为染色体（,Chromosome,）。,在染色体中，遗传信息由基因（,Gene,）所组成，基因决定着生物的性状，是遗传的基本单位。,染色体的形状是一种双螺旋结构，构成染色体的主要物质叫做脱氧核糖核酸,(DNA),，每个基因都在,DNA,长链中占有一定的位置。,一个细胞中的所有染色体所携带的遗传信息的全体称为一个基因组。,2.2.1,进化计算概述,1.,进化计算及其生物学基础,(2/3),11,变异理论,变异是指子代和父代之间，以及子代的各个不同个体之间产生差异的现象。变异是一种随机、不可逆现象，是生物多样性的基础。,引起变异的主要原因：,杂交，是指有性生殖生物在繁殖下一代时两个同源染色体之间的交配重组。,复制差错，是指在细胞复制过程中因,DNA,上某些基因结构的随机改变而产生出新的染色体。,进化论,进化是指在生物延续生存过程中，逐渐适应其生存环境，使得其品质不断得到改良的这种生命现象。遗传和变异是生物进化的两种基本现象，优胜劣汰、适者生存是生物进化的基本规律。,达尔文的自然选择学说：在生物进化中，一种基因有可能发生变异而产生出另一种新的基因。这种新基因将依据其与生存环境的适应性而决定其增殖能力。通常，适应性强的基因会不断增多，而适应性差的基因则会逐渐减少。通过这种自然选择，物种将逐渐向适应于生存环境的方向进化，甚至会演变成为另一个新的物种，而那些不适应于环境的物种将会逐渐被淘汰。,2.2.1,进化计算概述,1.,进化计算及其生物学基础,(3/3),12,进化计算自,20,世纪,50,年代以来，其发展过程大致可分为三个阶段。,(1),萌芽阶段,这一阶段是从,20,世纪,50,年代后期到,70,年代中期。,20,世纪,50,年代后期，一些生物学家在研究如何用计算机模拟生物遗传系统中，产生了遗传算法的基本思想，并于,1962,年由美国密执安（,Michigan,）大学霍兰德（,Holland,）提出。,1965,年德国数学家雷切伯格（,Rechenberg,）等人提出了一种只有单个个体参与进化，并且仅有变异这一种进化操作的进化策略。同年，美国学者弗格尔（,Fogel,）提出了一种具有多个个体和仅有变异一种进化操作的进化规划。,1969,年美国密执安（,Michigan,）大学的霍兰德（,Holland,）提出了系统本身和外部环境相互协调的遗传算法。至此，进化计算的三大分支基本形成。,(2),成长阶段,这一阶段是从,20,世纪,70,年代中期到,80,年代后期。,1975,年，霍兰德出版专著,自然和人工系统的适应性（,Adaptation in Natural and Artificial System,）,，全面介绍了遗传算法。同年，德国学者施韦费尔（,Schwefel,）在其博士论文中提出了一种由多个个体组成的群体参与进化的，并且包括了变异和重组这两种进化操作的进化策略。,1989,年，霍兰德的学生戈尔德伯格（,Goldberg,）博士出版专著,遗传算法,-,搜索、优化及机器学习（,Genetic Algorithm-in Search Optimization and Machine Learning,）,，使遗传算法得到了普及与推广。,2.2.1,进化计算概述,2.,进化计算的产生与发展,(1/2),13,(3),发展阶段,这一阶段是从,20,世纪,90,年代至今。,1989,年，美国斯坦福（,Stanford,）大学的科扎（,Koza,）提出了遗传规划的新概念，并于,1992,年出版了专著,遗传规划,-,应用自然选择法则的计算机程序设计（,Genetic Programming:on the Programming of Computer by Means of Natural Selection,）,该书全面介绍了遗传规划的基本原理及应用实例，标志着遗传规划作为计算智能的一个分支已基本形成。,进入,20,世纪,90,年代以来，进化计算得到了众多研究机构和学者的高度重视，新的研究成果不断出现、应用领域不断扩大。,2.2.1,进化计算概述,2.,进化计算的产生与发展,(2/2),14,进化计算尽管有多个重要分支，但它们却有着共同的进化框架。,若假设,P,为种群,(Population,，或称为群体,),，,t,为进化代数，,P(t,),为第,t,代种群,则进化计算的基本结构可粗略描述如下：,确定编码形式并生成搜索空间；,初始化各个进化参数，并设置进化代数,t=0,；,初始化种群,P(0);,对初始种群进行评价（即适应度计算）；,while,（不满足终止条件）,do,t=t+1;,利用选择操作从,P(t-1),代中选出,P(t,),代群体；,对,P(t,),代种群执行进化操作；,对执行完进化操作后的种群进行评价（即适应度计算）；,可以看出，上述基本结构包含了生物进化中所必需的选择操作、进化操作和适应度评价等过程。,2.2.1,进化计算概述,3.,进化计算的基本结构,15,遗传算法的基本思想是从初始种群出发，采用优胜劣汰、适者生存的自然法则选择个体，并通过杂交、变异来产生新一代种群，如此逐代进化，直到满足目标为止。遗传算法所涉及到的基本概念主要有以下几个：,种群,（,Population,）：种群是指用遗传算法求解问题时，初始给定的多个解的集合。遗传算法的求解过程是从这个子集开始的。,个体（,Individual,）：个体是指种群中的单个元素，它通常由一个用于描述其基本遗传结构的数据结构来表示。,染色体（,Chromos,）：染色体是指对个体进行编码后所得到的编码串。其中的每,1,位称为基因，若干个基因构成的一个有效信息段称为基因组。,适应度（,Fitness,）函数：适应度函数是一种用来对种群中各个个体的环境适应性进行度量的函数。,遗传操作（,Genetic Operator,）：遗传操作是指作用于种群而产生新的种群的操作。标准的遗传操作包括以下,3,种基本形式：,选择（,Selection,）,交叉（,Crosssover,）,变异（,Mutation,）,2.2.2,遗传算法,1.,遗传算法的基本概念,16,遗传算法主要由染色体编码、初始种群设定、适应度函数设定、遗传操作设计等几大部分所组成，其算法主要内容和基本步骤可描述如下：,(1),选择编码策略，将问题搜索空间中每个可能的点用相应的编码策略表示出来，即形成染色体；,(2),定义遗传策略，包括种群规模,N,，交叉、变异方法，以及选择概率,P,r,、交叉概率,P,c,、变异概率,P,m,等遗传参数；,(3),令,t=0,，随机选择,N,个染色体初始化种群,P(0),；,(4),定义适应度函数,f,（,f0,）；,(5),计算,P(t,),中每个染色体的适应值；,(6)t=t+1,；,(7),运用选择算子，从,P(t-1),中得到,P(t,),；,(8),对,P(t,),中的每个染色体，按概率,P,c,参与交叉；,(9),对染色体中的基因，以概率,P,m,参与变异运算；,(10),判断群体性能是否满足预先设定的终止标准，若不满足则返回,(5),。,2.2.2,遗传算法,2.,遗传算法的基本过程,(1/2),17,计算种群中各个个体的适应度，并进行评价,满足终止条件吗？,终止,选择,交叉,变异,Y,图,2-18,基本遗传算法的算法流程图,编码和生成初始种群,N,选择,其算法流程如图,2-18,所示。,2.2.2,遗传算法,2.,遗传算法的基本结构,(2/2),18,常用的遗传编码算法有霍兰德二进制码、格雷码（,Gray Code,）、实数编码和字符编码等。,(1),二进制编码（,Binary encoding,）,二进制编码是将原问题的结构变换为染色体的位串结构。在二进制编码中，首先要确定二进制字符串的长度,l,，该长度与变量的定义域和所求问题的计算精度有关。,例,5.5,假设变量,x,的定义域为,5,，,10,，要求的计算精度为,10,-5,，则需要将,5,，,10,至少分为,6,10,5,个等长小区间，每个小区间用一个二进制串表示。于是，串长至少等于,20,，原因是：,524288=2,19,6000002,20,=1048576,这样，对应于区间,5,，,10,内满足精度要求的每个值,x,，都可用一个,20,位编码的二进制串,来表示。,二进制编码存在的主要缺点是汉明（,Hamming,）悬崖。,例如，,7,和,8,的二进制数分别为,0111,和,1000,，当算法从,7,改进到,8,时，就必须改变所有的位。,2.2.2,遗传算法,3.,遗传编码,(1/3),19,2.2.2,遗传算法,3.,遗传编码,(2/3),(2),格雷编码（,Gray encoding,）,格雷编码是对二进制编码进行变换后所得到的一种编码方法。这种编码方法要求两个连续整数的编码之间只能有一个码位不同，其余码位都是完全相同的。它有效地解决了汉明悬崖问题，其基本原理如下：,设有二进制串,b,1,b,2,b,n,，对应的格雷串为,a,1,a,2,a,n,，则从二进制编码到格雷编码的变换为：,(2.9),其中，,表示模,2,加法（等同于异或运算）。而从一个格雷串到二进制串的变换为：,(2.10),例,2.6,十进制数,7,和,8,的二进制编码分别为,0111,和,1000,，而其格雷编码分别为,0100,和,1100,。,20,(3),实数编码（,Real encoding,）,实数编码是将每个个体的染色体都用某一范围的一个实数（浮点数）来表示，其编码长度等于该问题变量的个数。,这种编码方法是将问题的解空间映射到实数空间上，然后在实数空间上进行遗传操作。由于实数编码使用的是变量的真实值，因此这种编码方法也叫做真值编码方法。,实数编码适应于那种多维、高精度要求的连续函数优化问题。,2.2.2,遗传算法,3.,遗传编码,(3/3),21,适应度函数是一个用于对个体的适应性进行度量的函数。通常，一个个体的适应度值越大，它被遗传到下一代种群中的概率也就越大。,(1),常用的适应度函数,在遗传算法中，有许多计算适应度的方法，其中最常用的适应度函数有以下两种：,原始适应度函数,它是直接将待求解问题的目标函数,f(x,),定义为遗传算法的适应度函数。例如，在求解极值问题,时，,f(x,),即为,x,的原始适应度函数。,采用原始适应度函数的优点是能够直接反映出待求解问题的最初求解目标，其缺点是有可能出现适应度值为负的情况。,2.2.2,遗传算法,4.,适应度函数,(1/5),22,标准适应度函数,在遗传算法中，一般要求适应度函数非负，并其适应度值越大越好。这就往往需要对原始适应函数进行某种变换，将其转换为标准的度量方式，以满足进化操作的要求，这样所得到的适应度函数被称为标准适应度函数,f,Normal,(x,),。例如下面的极小化和极大化问题：,极小化问题,对极小化问题，其标准适应度函数可定义为,(2.11),其中，,f,max,(x),是原始适应函数,f(x),的一个上界。如果,f,max,(x),未知，则可用当前代或到目前为止各演化代中的,f(x),的最大值来代替。可见，,f,max,(x),是会随着进化代数的增加而不断变化的。,2.2.2,遗传算法,4.,适应度函数,(2/5),23,极大化问题,对极大化问题，其标准适应度函数可定义为,(2.12),其中，,f,min,(x),是原始适应函数,f(x),的一个下界。如果,f,min,(x),未知，则可用当前代或到目前为止各演化代中的,f(x),的最小值来代替。,2.2.2,遗传算法,4.,适应度函数,(3/5),24,(2),适应度函数的加速变换,在某些情况下，需要对适应度函数进行加速速度。,适应度函数的加速变换有两种基本方法,线性加速的适应度函数的定义如下：,f(x)=f(x)+,其中，,f(x),是加速转换前的适应度函数；,f(x),是加速转换后的适应度函数；,和,是转换系数,它们应满足如下条件：,变化后得到的新的适应度函数平均值要等于原适应度函数的平均值。即,（,2.13,）,其中，,x,i,(i,=1,n),为当前代中的染色体。,2.2.2,遗传算法,4.,适应度函数,(4/5),25,变换后所得到的新的种群个体所具有的最大适应度要等于其平均适应度的指数倍数。即有关系：,（,2.14,）,式中，,x,i,(i=1,n),为当前代中的染色体，,M,是指将当前的最大适应度放大为平均值的,M,倍。目的是通过,M,拉开不同染色体适应度值的差距。,非线性加速,幂函数变换方法,f(x)=f(x),k,(2.15),指数变换方法,f(x)=exp(f(x)(2.16),2.2.2,遗传算法,4.,适应度函数,(5/5),26,遗传算法中的基本遗传操作包括选择、交叉和变异,3,种，而每种操作又包括多种不同的方法，下面分别对它们进行介绍。,(1).,选择操作,选择（,Selection,）操作是指根据选择概率按某种策略从当前种群中挑选出一定数目的个体，使它们能够有更多的机会被遗传到下一代中。,常用的选择策略可分为比例选择、排序选择和竞技选择三种类型。,比例选择,比例选择方法（,Proportional Model,）的基本思想是：各个个体被选中的概率与其适应度大小成正比。,常用的比例选择策略包括,轮盘赌选择,繁殖池选择,2.2.2,遗传算法,5.,基本遗传操作,(1/11),27,轮盘赌选择,轮盘赌选择法又被称为转盘赌选择法或轮盘选择法。在这种方法中，个体被选中的概率取决于该个体的相对适应度。而相对适应度的定义为：,其中，,P(x,i,),是个体,x,i,的相对适应度，即个体,x,i,被选中的概率；,f(x,i,),是个体,x,i,的原始适应度。,轮盘赌选择算法的基本思想是：根据每个个体的选择概率,P(x,i,),将一个圆盘分成,N,个扇区，其中第,i,个扇区的中心角为：,再设立一个移动指针，将圆盘的转动等价为指针的移动。选择时，假想转动圆盘，若静止时指针指向第,i,个扇区，则选择个体,i,。其物理意义如图,2-19,所示。,2.2.2,遗传算法,5.,基本遗传操作,(2/11),28,P(x,1,),P(x,2,),P(x,N,),P(x,i,),2,p(x,i,),图,2-19,轮盘赌选择,从统计角度看，个体的适应度值越大，其对应的扇区的面积越大，被选中的可能性也越大。这种方法有点类似于发放奖品使用的轮盘，并带有某种赌博的意思，因此亦被称为轮盘赌选择。,2.2.2,遗传算法,5.,基本遗传操作,(3/11),29,(2),交叉操作,交叉（,Crossover,）操作是指按照某种方式对选择的父代个体的染色体的部分基因进行交配重组，从而形成新的个体。交配重组是自然界中生物遗传进化的一个主要环节，也是遗传算法中产生新的个体的最主要方法。根据个体编码方法的不同，遗传算法中的交叉操作可分为二进制交叉和实值交叉两种类型。,二进制交叉,二进制交叉（,Binary Valued Crossover,）是指二进制编码情况下所采用的交叉操作，它主要包括单点交叉、两点交叉、多点交叉和均匀交叉等方法。,2.2.2,遗传算法,5.,基本遗传操作,(4/11),30,单点交叉,单点交叉也称简单交叉，它是先在两个父代个体的编码串中随机设定一个交叉点，然后对这两个父代个体交叉点前面或后面部分的基因进行交换，并生成子代中的两个新的个体。假设两个父代的个体串分别是：,X=x,1,x,2,x,k,x,k+1,x,n,Y=y,1,y,2,y,k,y,k+1,y,n,随机选择第,k,位为交叉点，若采用对交叉点后面的基因进行交换的方法，但点交叉是将,X,中的,x,k+1,到,x,n,部分与,Y,中的,y,k+1,到,y,n,部分进行交叉，交叉后生成的两个新的个体是：,X=x,1,x,2,x,k,y,k+1,y,n,Y=y,1,y,2,y,k,x,k+1,x,n,例,2.7,设有两个父代的个体串,A=0 0 1 1 0 1,和,B=1 1 0 0 1 0,，若随机交叉点为,4,，则交叉后生成的两个新的个体是：,A=0 0 1 1 1 0,B=1 1 0 0 0 1,2.2.2,遗传算法,5.,基本遗传操作,(5/11),31,两点交叉,两点交叉是指先在两个父代个体的编码串中随机设定两个交叉点，然后再按这两个交叉点进行部分基因交换，生成子代中的两个新的个体。,假设两个父代的个体串分别是：,X=x,1,x,2,x,i,x,j,x,n,Y=y,1,y,2,y,i,y,j,y,n,随机设定第,i,、,j,位为两个交叉点（其中,ijn,），两点交叉是将,X,中的,x,i+1,到,x,j,部分与,Y,中的,y,i+1,到,y,j,部分进行交换，交叉后生成的两个新的个体是：,X=x,1,x,2,x,i,y,i+1,y,j,x,j+1,x,n,Y=y,1,y,2,y,i,x,i+1,x,j,y,j+1,y,n,例,2.8,设有两个父代的个体串,A=0 0 1 1 0 1,和,B=1 1 0 0 1 0,，若随机交叉点为,3,和,5,，则交叉后的两个新的个体是：,A=0 0 1 0 1 1,B=1 1 0 1 0 0,2.2.2,遗传算法,5.,基本遗传操作,(6/11),32,多点交叉,多点交是指先随机生成多个交叉点，然后再按这些交叉点分段地进行部分基因交换，生成子代中的两个新的个体。,假设交叉点个数为,m,，则可将个体串划分为,m+1,个分段，其划分方法是：,当,m,为偶数时，对全部交叉点依次进行两两配对，构成,m/2,个交叉段。,当,m,为奇数时，对前,(m-1),个交叉点依次进行两两配对，构成,(m-1)/2,个交叉段，而第,m,个交叉点则按单点交叉方法构成一个交叉段。,下面以,m=3,为例进行讨论。假设两个父代的个体串分别是,X=x,1,x,2,x,i,x,j,x,k,x,n,和,Y=y,1,y,2,y,i,y,j,y,k,y,n,，,随机设定第,i,、,j,、,k,位为三个交叉点（其中,ijkn,），则将构成两个交叉段。交叉后生成的两个新的个体是：,X=x,1,x,2,x,i,y,i+1,y,j,x,j+1,x,k,y,k+1,y,n,Y=y,1,y,2,y,i,x,i+1,x,j,y,j+1,y,k,x,k+1,x,n,例,2.9,设有两个父代的个体串,A=0 0 1 1 0 1,和,B=1 1 0 0 1 0,，若随机交叉点为,1,、,3,和,5,，则交叉后的两个新的个体是：,A=0 1 0 1 0 0,B=1 0 1 0 1 1,2.2.2,遗传算法,5.,基本遗传操作,(7/11),33,均匀交叉,均匀交叉（,Uniform Crossover,）是先随机生成一个与父串具有相同长度，并被称为交叉模版（或交叉掩码）的二进制串，然后再利用该模版对两个父串进行交叉，即将模版中,1,对应的位进行交换，而,0,对应的位不交换，依此生成子代中的两个新的个体。事实上，这种方法对父串中的每一位都是以相同的概率随机进行交叉的。,例,2.10,设有两个父代的个体串,A=001101,和,B=110010,，若随机生成的模版,T=010011,，则交叉后的两个新的个体是,A=011010,和,B=100101,。即,A,：,0 0 1 1 0 1,B,：,1 1 0 0 1 0,T,：,0 1 0 0 1 1,A,：,0 1 1 1 1 0,B,：,1 0 0 0 0 1,2.2.2,遗传算法,5.,基本遗传操作,(8/11),34,实值交叉,实值交叉是在实数编码情况下所采用的交叉操作，主要包括离散交叉和算术交叉，下面主要讨论离散交叉（部分离散交叉和整体离散交叉）。,部分离散交叉是先在两个父代个体的编码向量中随机选择一部分分量，然后对这部分分量进行交换，生成子代中的两个新的个体。,整体交叉则是对两个父代个体的编码向量中的所有分量，都以,1/2,的概率进行交换，从而生成子代中的两个新的个体。,以部分离散交叉为例，假设两个父代个体的,n,维实向量分别是,X=x,1,x,2,x,i,x,k,x,n,和,Y=y,1,y,2,y,i,y,k,y,n,，若随机选择对第,k,个分量以后的所有分量进行交换，则生成的两个新的个体向量是：,X=x,1,x,2,x,k,y,k+1,y,n,Y=y,1,y,2,y,k,x,k+1,x,n,例,2.11,设有两个父代个体向量,A=20 16 19 32 18 26,和,B=36 25 38 12 21 30,，若随机选择对第,3,个分量以后的所有分量进行交叉，则交叉后两个新的个体向量是：,A=20 16 19 12 21 30,B=36 25 38 32 18 26,2.2.2,遗传算法,5.,基本遗传操作,(9/11),35,(3),变异操作,变异（,Mutation,）是指对选中个体的染色体中的某些基因进行变动，以形成新的个体。变异也是生物遗传和自然进化中的一种基本现象，它可增强种群的多样性。遗传算法中的变异操作增加了算法的局部随机搜索能力，从而可以维持种群的多样性。根据个体编码方式的不同，变异操作可分为二进制变异和实值变异两种类型。,二进制变异,当个体的染色体采用二进制编码表示时，其变异操作应采用二进制变异方法。该变异方法是先随机地产生一个变异位，然后将该变异位置上的基因值由“,0”,变为“,1”,，或由“,1”,变为“,0”,，产生一个新的个体。,例,2.12,设变异前的个体为,A=0 0 1 1 0 1,，若随机产生的变异位置是,2,，则该个体的第,2,位由“,0”,变为“,1”,。,变异后的新的个体是,A=0 1 1 1 0 1,。,2.2.2,遗传算法,5.,基本遗传操作,(10/11),36,实值变异,当个体的染色体采用实数编码表示时，其变异操作应采用实值变异方法。该方法是用另外一个在规定范围内的随机实数去替换原变异位置上的基因值，产生一个新的个体。最常用的实值变异操作有,:,基于位置的变异方法,该方法是先随机地产生两个变异位置，然后将第二个变异位置上的基因移动到第一个变异位置的前面。,例,2.13,设选中的个体向量,C=20 16 19 12 21 30,，若随机产生的两个变异位置分别时,2,和,4,，则变异后的新的个体向量是：,C=20 12 16 19 21 30,基于次序的变异,该方法是先随机地产生两个变异位置，然后交换这两个变异位置上的基因。,例,2.14,设选中的个体向量,D=20 12 16 19 21 30,，若随机产生的两个变异位置分别时,2,和,4,，则变异后的新的个体向量是：,D=20 19 16 12 21 30,2.2.2,遗传算法,5.,基本遗传操作,(11/11),37,例,2.15,用遗传算法求函数,f(x)=x,2,的最大值，其中,x,为,0,，,31,间的整数。,解：这个问题本身比较简单，其最大值很显然是在,x=31,处。但作为一个例子，它有着较好的示范性和可理解性。,按照遗传算法，其求解过程如下：,(1),编码,由于,x,的定义域是区间,0,，,31,上的整数，由,5,位二进制数即可全部表示。因此，可采用二进制编码方法，其编码串的长度为,5,。,例如，用二进制串,00000,来表示,x=0,11111,来表示,x=31,等。其中的,0,和,1,为基因值。,(2),生成初始种群,若假设给定的种群规模,N=4,，则可用,4,个随机生成的长度为,5,的二进制串作为初始种群。再假设随机生成的初始种群（即第,0,代种群）为：,s,01,=0 1 1 0 1 s,02,=1 1 0 0 1,s,03,=0 1 0 0 0 s,04,=1 0 0 1 0,2.2.2,遗传算法,6.,遗传算法应用简例,(1/10),38,(3),计算适应度,要计算个体的适应度，首先应该定义适应度函数。由于本例是求,f(x),的最大值，因此可直接用,f(x),来作为适应度函数。即：,f(s)=f(x),其中的二进制串,s,对应着变量,x,的值。根据此函数，初始种群中各个个体的适应值及其所占比例如表,2-5,所示。,表,2-5,初始种群情况表,编号,个体串（染色体）,x,适应值,百分比,%,累计百分比,%,选中次数,S,01,01101,13,169,14.30,14.30,1,S,02,11001,25,625,52.88,67.18,2,S,03,01000,8,64,5.41,72.59,0,S,04,10010,18,324,27.41,100,1,2.2.2,遗传算法,6.,遗传算法应用简例,(2/10),可以看出，在,4,个个体中,S,02,的适应值最大，是当前最佳个体。,39,(4),选择操作,假设采用轮盘赌方式选择个体，且依次生成的,4,个随机数（相当于轮盘上指针所指的数）为,0.85,、,0.32,、,0.12,和,0.46,，经选择后得到的新的种群为：,S,01,=10010,S,02,=11001,S,03,=01101,S,04,=11001,其中，染色体,11001,在种群中出现了,2,次，而原染色体,01000,则因适应值太小而被淘汰,2.2.2,遗传算法,6.,遗传算法应用简例,(3/10),40,(5),交叉,假设交叉概率,P,i,为,50%,，则种群中只有,1/2,的染色体参与,交叉,。若规定种群中的染色体按顺序两两配对交叉，且有,S,01,与,S,02,交叉，,S,03,与,S,04,不交叉，则交叉情况如表,2-6,所示。,表,2-6,初始种群的交叉情况表,编号,个体串（染色体）,交叉对象,交叉位,子代,适应值,S,01,10010,S,02,3,100,01,289,S,02,11001,S,01,3,110,10,676,S,03,01101,S,04,N,01101,169,S,04,11001,S,03,N,11001,625,2.2.2,遗传算法,6.,遗传算法应用简例,(4/10),可见，经交叉后得到的新的种群为：,S,01,=10001,S,02,=11010,S,03,=01101,S,04,=11001,41,(6),变异,变异概率,P,m,一般都很小，假设本次循环中没有发生变异，则变异前的种群即为进化后所得到的第,1,代种群。即：,S,11,=10001,S,12,=11010,S,13,=01101,S,14,=11001,然后，对第,1,代种群重复上述,(4)-(6),的操作,2.2.2,遗传算法,6.,遗传算法应用简例,(5/10),42,其中若假设按轮盘赌选择时依次生成的,4,个随机数为,0.14,、,0.51,、,0.24,和,0.82,，经选择后得到的新的种群为：,S,11,=10001,S,12,=11010,S,13,=11010,S,14,=11001,可见,，,染色体11010被选择了2次,，,而原染色体01101则因适应值太小而被淘汰。,编号,个体串（染色体）,x,适应值,百分比,%,累计百分比,%,选中次数,S,11,10001,17,289,16.43,16.43,1,S,12,11010,26,676,38.43,54.86,2,S,13,01101,13,169,9.61,64.47,0,S,14,11001,25,625,35.53,100,1,2.2.2,遗传算法,6.,遗传算法应用简例,(6/10),对第,1,代种群，同样重复上述,(4)-(6),的操作。其选择情况如表,2-7,所示。,表,2-7,第,1,代种群的选择情况表,43,可见，经杂交后得到的新的种群为：,S,11,=10010,S,12,=11001,S,13,=11001,S,14,=11010,可以看出，第,3,位基因均为,0,，已经不可能通过交配达到最优解。这种过早陷入局部最优解的现象称为早熟。为解决这一问题，需要采用变异操作。,编号,个体串（染色体）,交叉对象,交叉位,子代,适应值,S,11,10001,S,12,3,100,10,324,S,12,11010,S,11,3,110,01,625,S,13,11010,S,14,2,11,001,625,S,14,11001,S,13,2,11,010,675,2.2.2,遗传算法,6.,遗传算法应用简例,(7/10),对第,1,代种群，其交叉情况如表,2-8,所示。,表,2-8,第,1,代种群的交叉情况表,