遗传算法入门详细PPT学习课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章 遗传算法,智能优化计算,华东理工大学自动化系,2007,年,1,4.1,遗传算法简介,4.1.1,遗传算法的产生与发展,4.1.2,生物进化理论和遗传学的基本知识,4.1.3,遗传算法的思路与特点,4.1.4,遗传算法的基本操作,4.1.5,遗传算法的应用,4.2,基本遗传算法,4.2.1,简单函数优化的实例,4.2.2,遗传基因型,4.2.3,适应度函数及其尺度变换,4.2.4,遗传操作,选择,4.2.5,遗传操作,交叉,/,基因重组,4.2.6,遗传操作,变异,4.2.7,算法的设计与实现,4.2.8,模式定理,智能优化计算,华东理工大学自动化系,2007,年,2,4.3,遗传算法的改进,4.3.1 CHC,算法,4.3.2,自适应遗传算法,4.3.3,基于小生境技术的遗传算法,4.4,遗传算法的应用,4.4.1,解决带约束的函数优化问题,4.4.2,解决多目标优化问题,4.4.3,解决组合优化问题,4.4.4,遗传算法在过程建模中的应用,4.4.5,遗传算法在模式识别中的应用,智能优化计算,华东理工大学自动化系,2007,年,3,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,产生,早,在,50年代,，,一些生物学家开始研究运用数字计算机模拟生物的自然遗传,与自然进化过程,；,1963,年,，德国柏林技术大学的,I.Rechenberg,和,H.P.Schwefel,，做风洞实验时，产生了,进化策略,的初步思想；,60,年代，,L.J.Fogel,在设计有限态自动机时提出,进化规划,的思想。,1966,年,Fogel,等出版了,基于模拟进化的人工智能,，系统阐述了进化规划的思想。,4,.1.1,遗传算法的产生与发展,4,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,产生,60,年代中期，,美国Michigan大学的J,.,H,.,Holland教授,提出,借鉴生物自然遗传的基本原理,用于自然,和人工系统的自适应行为研究和串编码技术；,1967年，他的学生J,.,D,.,Bagley在博士论文中首次提出“遗传算法(Genetic,Algorithms)”一词,；,1975,年,，,Holland,出版了著名的“,Adaptation in Natural and Artificial Systems”,，标志,遗传算法的诞生,。,4,.1.1,遗传算法的产生与发展,5,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,发展,70,年代初，,Holland,提出了“模式定理”（,Schema Theorem,），一般认为是“遗传算法的基本定理”，从而奠定了遗传算法研究的理论基础；,1985,年，在美国召开了第一届遗传算法国际会议，并且成立了国际遗传算法学会,(ISGA,，,International Society of Genetic Algorithms),；,4,.1.1,遗传算法的产生与发展,6,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,发展,1989,年，,Holland,的学生,D.J.Goldherg,出版了“,Genetic Algorithms in Search,Optimization,and Machine Learning”,，对遗传算法及其应用作了全面而系统的论述；,1991,年，,L.Davis,编辑出版了,遗传算法手册,，其中包括了遗传算法在工程技术和社会生活中大量的应用实例。,4,.1.1,遗传算法的产生与发展,7,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,几个名词概念,遗传算法,进化计算,计算智能,人工智能,4,.1.1,遗传算法的产生与发展,8,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,几个名词概念,进化计算：,4,.1.1,遗传算法的产生与发展,由于遗传算法、进化规划和进化策略是不同领域的研究人员分别独立提出的，在相当长的时期里相互之间没有正式沟通。直到,90,年代，才有所交流。,他们发现彼此的基本思想具有惊人的相似之处，于是提出将这类方法统称为“进化计算”,(Evolutionary C,omputation,),。,9,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,几个名词概念,计算智能：,4,.1.1,遗传算法的产生与发展,计算智能主要包括神经计算、进化计算和模糊计算等。它们分别从不同的角度模拟人类的智能活动，以使计算机具有智能。,通常将基于符号处理的传统人工智能称为符号智能，以区别于正在兴起的计算智能。,符号智能的特点是以知识为基础，偏重于逻辑推理，而计算智能则是以数据为基础，偏重于数值计算。,10,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,达尔文的自然选择说,遗传（,heredity,）：子代和父代具有相,同或相似的性状，保证物种的稳定性；,变异（,variation,）：子代与父代，子代不同个体之间总有差异，是生命多样性的根源；,生存斗争和适者生存：具有适应性变异的个体被保留，不具适应性变异的个体被淘汰。,自然选择过程是长期的、缓慢的、连续的过程。,4,.1.2,生物进化理论和遗传学的基本知识,11,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,遗传学基本概念与术语,染色体（,chromosome,）：遗传物质的载体；,脱氧核糖核酸（,DNA,）：大分子有机聚合物，双螺旋结构；,遗传因子（,gene,）：,DNA,或,RNA,长链结构中占有一定位置的基本遗传单位；,4,.1.2,生物进化理论和遗传学的基本知识,12,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,遗传学基本概念与术语,基因型（,genotype,）：遗传因子组合的模型；,表现型（,phenotype,）：由染色体决定性状的外部表现；,4,.1.2,生物进化理论和遗传学的基本知识,1 1 1 1 1 1 1,1 1 1 0 1 1 1,13,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,遗传学基本概念与术语,基因座（,locus,）：遗传基因在染色体中所占据的位置，同一基因座可能有的全部基因称为等位基因（,allele,）；,个体（,individual,）：指染色体带有特征的实体；,种群（,population,）：个体的集合，该集合内个体数称为种群的大小；,4,.1.2,生物进化理论和遗传学的基本知识,14,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,遗传学基本概念与术语,进化（,evolution,）：生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化；,适应度（,fitness,）：度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝,;,4,.1.2,生物进化理论和遗传学的基本知识,15,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,遗传学基本概念与术语,选择（,selection,）：指决定以一定的概率从种群中选择若干个体的操作；,复制（,reproduction,）：细胞在分裂时，遗传物质,DNA,通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因,;,交叉（,crossover,）：在两个染色体的某一相同位置处,DNA,被切断，其前后两串分别交叉组合形成两个新的染色体。又称基因重组，俗称“杂交”,;,4,.1.2,生物进化理论和遗传学的基本知识,16,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,遗传学基本概念与术语,变异（,mutation,）：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使,DNA,发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状,;,编码（,coding,）：表现型到基因型的映射；,解码（,decoding,）：从基因型到表现型的映射。,4,.1.2,生物进化理论和遗传学的基本知识,17,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,进化论与遗传学的融合,1930,1947,年，达尔文进化论与遗传学走向融合，,Th.Dobzhansky1937,年发表的,遗传学与物种起源,是融合进化论与遗传学的代表作。,生物进化与智能学的关系,生物物种作为复杂系统，具有奇妙的自适应、自组织和自优化能力，这是一种生物在进化过程中体现的智能，也是人工系统梦寐以求的功能。,4,.1.2,生物进化理论和遗传学的基本知识,18,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,遗传算法的基本思路,4,.1.3,遗传算法的思路与特点,19,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,自组织、自适应和自学习性,在编码方案、适应度函数及遗传算子确定后，算法将利用进化过程中获得的信息自行组织搜索。,本质并行性,内在并行性与内含并行性,不需求导,只需目标函数和适应度函数,概率转换规则,强调概率转换规则，而不是确定的转换规则,4,.1.3,遗传算法的思路与特点,20,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,选择,适应度计算,：,按比例的适应度函数（,proportional fitness assignment,）,基于排序的适应度计算（,Rank-based fitness assignment,）,选择算法,：,轮盘赌选择（,roulette wheel selection,）,4,.1.4,遗传算法的基本操作,21,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,选择,选择算法,：,随机遍历抽样（,stochastic universal selection,）,局部选择（,local selection,）,截断选择（,truncation selection,）,锦标赛选择（,tournament selection,）,4,.1.4,遗传算法的基本操作,22,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,交叉或基因重组,实值重组（,real valued recombination,）,：,离散重组（,discrete recombination,）,中间重组（,intermediate recombination,）,线性重组（,linear recombination,）,扩展线性重组（,extended linear recombination,）,4,.1.4,遗传算法的基本操作,23,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,交叉或基因重组,二进制交叉（,binary valued crossover,）,：,单点交叉（,single-point crossover,）,多点交叉（,multiple-point crossover,）,均匀交叉（,uniform crossover,）,洗牌交叉（,shuffle crossover,）,缩小代理交叉（,crossover with reduced surrogate,）,4,.1.4,遗传算法的基本操作,24,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,变异,实值变异,二进制变异,4,.1.4,遗传算法的基本操作,25,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,简单实例,产生初始种群,计算适应度,4,.1.4,遗传算法的基本操作,0001100000 0101111001 0000000101 1001110100 1010101010,1110010110 1001011011 1100000001 1001110100 0001010011,（,8,）（,5,）（,2,）（,10,）（,7,）,（,12,）（,5,）（,19,）（,10,）（,14,）,26,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,简单实例,选择,4,.1.4,遗传算法的基本操作,个体,染色体,适应度,选择概率,累积概率,1,0001100000,8,2,0101111001,5,3,0000000101,2,4,1001110100,10,5,1010101010,7,6,1110010110,12,7,1001011011,5,8,1100000001,19,9,1001110100,10,10,0001010011,14,8,8,5,2,10,7,12,5,19,10,14,0.086957,5,8,5,2,10,7,12,5,19,10,14,0.054348,0.021739,0.108696,0.076087,0.130435,0.054348,0.206522,0.108696,0.152174,27,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,简单实例,选择,4,.1.4,遗传算法的基本操作,个体,染色体,适应度,选择概率,累积概率,1,0001100000,8,2,0101111001,5,3,0000000101,2,4,1001110100,10,5,1010101010,7,6,1110010110,12,7,1001011011,5,8,1100000001,19,9,1001110100,10,10,0001010011,14,0.086957,0.054348,0.021739,0.108696,0.076087,0.130435,0.054348,0.206522,0.108696,0.152174,0.086957,0.141304,0.163043,0.271739,0.347826,0.478261,0.532609,0.739130,0.847826,1.000000,28,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,简单实例,选择,在,0,1,之间产生一个,随机数：,4,.1.4,遗传算法的基本操作,个体,染色体,适应度,选择概率,累积概率,1,0001100000,8,2,0101111001,5,3,0000000101,2,4,1001110100,10,5,1010101010,7,6,1110010110,12,7,1001011011,5,8,1100000001,19,9,1001110100,10,10,0001010011,14,0.086957,0.054348,0.021739,0.108696,0.076087,0.130435,0.054348,0.206522,0.108696,0.152174,0.086957,0.141304,0.163043,0.271739,0.347826,0.478261,0.532609,0.739130,0.847826,1.000000,0.070221,0.545929,0.784567,0.446930,0.507893,0.291198,0.716340,0.270901,0.371435,0.854641,淘汰！,淘汰！,29,0001100000 1110010110 1100000001 1001110100 1010101010,1110010110 1001011011 1100000001 1001110100 0001010011,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,简单实例,交叉,4,.1.4,遗传算法的基本操作,0001100000 1110010110 1100000001 1001110100 1010101010,1110010110 1001011011 1001110100 1100000001 0001010011,0001,1110,100000,010110,111,100,0010110,1011011,110000,100111,0100,0001,1001110100,1100000001,1010101,0001010,010,011,30,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,简单实例,变异,4,.1.4,遗传算法的基本操作,0001100000 1110010110 1100000001 1001110100 1010101010,1110010110 1001011011 1100000001 1001110100 0001010011,0001,1110,100000,010110,111,100,0010110,1011011,110000,1001,0,1,0100,0001,1001110100,1100000001,1010101,0001010,010,011,0001100000 1110010110 1100000001 1001110100 1010101010,1110010110 1001011011 1100000001 1001110100 0001010011,0001,1110,100000,010110,111,100,0010110,1011011,110000,1001,1,1,0100,0001,1001110100,1100000001,1010101,0001010,010,011,31,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,简单实例,至下一代，适应度计算,选择交叉变异，直至满足终止条件。,4,.1.4,遗传算法的基本操作,32,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,函数优化,是遗传算法的经典应用领域,;,组合优化,实践证明，遗传算法对于组合优化中的,NP,完全问题非常有效,;,自动控制,如基于遗传算法的模糊控制器优化设计、基于遗传算法的参数辨识、利用遗传算法进行人工神经网络的结构优化设计和权值学习等,;,4,.1.5,遗传算法的应用,33,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,机器人智能控制,遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行动协调等,;,组合图像处理和模式识别,目前已在图像恢复、图像边缘持征提取、几何形状识别等方面得到了应用,;,4,.1.5,遗传算法的应用,34,4.1,遗传算法简介,智能优化计算,华东理工大学自动化系,2007,年,人工生命,基于遗传算法的进化模型是研究人工生命现象的重要理论基础，遗传算法已在其进化模型、学习模型、行为模型等方面显示了初步的应用能力；,遗传程序设计,Koza,发展了遗传程序设计的慨念，他使用了以,LISP,语言所表示的编码方法，基于对一种树型结构所进行的遗传操作自动生成计算机程序,;,4,.1.5,遗传算法的应用,35,第四章 待续,智能优化计算,华东理工大学自动化系,2007,年,36,第四章 遗传算法（续）,智能优化计算,华东理工大学自动化系,2007,年,37,4.1,遗传算法简介,4.1.1,遗传算法的产生与发展,4.1.2,生物进化理论和遗传学的基本知识,4.1.3,遗传算法的思路与特点,4.1.4,遗传算法的基本操作,4.1.5,遗传算法的应用,4.2,基本遗传算法,4.2.1,简单函数优化的实例,4.2.2,遗传基因型,4.2.3,适应度函数及其尺度变换,4.2.4,遗传操作,选择,4.2.5,遗传操作,交叉,/,基因重组,4.2.6,遗传操作,变异,4.2.7,算法的设计与实现,4.2.8,模式定理,智能优化计算,华东理工大学自动化系,2007,年,38,4.3,遗传算法的改进,4.3.1 CHC,算法,4.3.2,自适应遗传算法,4.3.3,基于小生境技术的遗传算法,4.4,遗传算法的应用,4.4.1,解决带约束的函数优化问题,4.4.2,解决多目标优化问题,4.4.3,解决组合优化问题,4.4.4,遗传算法在过程建模中的应用,4.4.5,遗传算法在模式识别中的应用,智能优化计算,华东理工大学自动化系,2007,年,39,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,问题的提出,一元函数求最大值：,4,.2.1,简单函数优化的实例,40,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,问题的提出,用微分法求取,f,(,x,),的最大值：,解有无穷多个：,4,.2.1,简单函数优化的实例,41,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,问题的提出,当,i,为奇数时,x,i,对应局部极大值点，,i,为偶数时,x,i,对应局部极小值。,x,19,即为区间,-1,2,内的最大值点：,此时，函数最大值,f,(,x,19,),比,f,(1.85)=3.85,稍大。,4,.2.1,简单函数优化的实例,42,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,编码,表现型：,x,基因型：二进制编码（串长取决于求解精度）,串长与精度之间的关系,：,若要求求解精度到,6,位小数，区间长度为,2-(-1),3,，即需将区间分为,3/0.000001=310,6,等份。,所以编码的二进制串长应为,22,位。,4,.2.1,简单函数优化的实例,43,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,产生初始种群,产生的方式：随机,产生的结果：长度为,22,的二进制串,产生的数量：种群的大小（规模），如,30,，,50,，,1111010011100001011000,1100110011101010101110,1010100011110010000100,1011110010011100111001,0001100101001100000011,0000011010010000000000,4,.2.1,简单函数优化的实例,44,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,计算适应度,不同的问题有不同的适应度计算方法,本例：直接用目标函数作为适应度函数,将某个体转化为,-1,2,区间的实数：,s,=,x,=0.637197,计算,x,的函数值（适应度）：,f,(,x,)=,x,sin(10,x,)+2.0=2.586345,4,.2.1,简单函数优化的实例,45,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,计算适应度,二进制与十进制之间的转换,：,第一步，将一个二进制串（,b,21,b,20,b,0,）转化为,10,进制数：,第二步，,x,对应的区间,-1,2,内的实数：,4,.2.1,简单函数优化的实例,(0000000000000000000000),-1,(1111111111111111111111)2,46,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,遗传操作,选择：轮盘赌选择法；,交叉：单点交叉；,变异：小概率变异,4,.2.1,简单函数优化的实例,47,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,模拟结果,设置的参数,：,种群大小,50,；交叉概率,0.75,；变异概率,0.05,；最大代数,200,。,得到的最佳个体,：,s,max,=;,x,max,=1.8506;,f,(x,max,)=3.8503;,4,.2.1,简单函数优化的实例,48,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,模拟结果,进化的过程,：,4,.2.1,简单函数优化的实例,世代数,自变量,适应度,1,1.4495,3.4494,9,1.8395,3.7412,17,1.8512,3.8499,30,1.8505,3.8503,50,1.8506,3.8503,80,1.8506,3.8503,120,1.8506,3.8503,200,1.8506,3.8503,49,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,编码原则,完备性（,completeness,）：问题空间的所有解都能表示为所设计的基因型；,健全性（,soundness,）：任何一个基因型都对应于一个可能解；,非冗余性（,non-redundancy,）：问题空间和表达空间一一对应。,4,.2.2,遗传基因型,50,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,多种编码方式,二进制编码；,浮点数编码；,格雷码编码；,符号编码；,复数编码；,DNA,编码等。,4,.2.2,遗传基因型,51,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,二进制编码与浮点数编码的比较,在交叉操作时，二进制编码比浮点数编码产生新个体的可能性多，而且产生的新个体不受父个体所构成的超体的限制；,在变异操作时，二进制编码的种群稳定性比浮点数编码差。,4,.2.2,遗传基因型,52,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,适应度函数的重要性,适应度函数的选取直接影响遗传算法的收敛速度以及能否找到最优解。,一般而言，适应度函数是由目标函数变换而成的，对目标函数值域的某种映射变换称为适应度的,尺度变换,（,fitness scaling,）。,4,.2.3,适应度函数及其尺度变换,53,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,几种常见的适应度函数,直接转换,若目标函数为最大化问题：,Fit(,f,(,x,)=,f,(,x,),若目标函数为最小化问题：,Fit(,f,(,x,)=-,f,(,x,),4,.2.3,适应度函数及其尺度变换,54,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,几种常见的适应度函数,界限构造法,1,若目标函数为最大化问题：,若目标函数为最小化问题：,4,.2.3,适应度函数及其尺度变换,55,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,几种常见的适应度函数,界限构造法,2,若目标函数为最大化问题：,若目标函数为最小化问题：,c,为目标函数的保守估计值。,4,.2.3,适应度函数及其尺度变换,56,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,适应度函数的作用,适应度函数设计不当有可能出现欺骗问题：,（,1,）进化初期，个别超常个体控制选择过程；,（,2,）进化末期，个体差异太小导致陷入局部极值。,4,.2.3,适应度函数及其尺度变换,57,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,适应度函数的设计,单值、连续、非负、最大化,合理、一致性,计算量小,通用性强,4,.2.3,适应度函数及其尺度变换,58,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,适应度函数的线性变换法,f,=,*,f,+,系数的确定满足以下条件：,f,avg,=,f,avg,f,max,=,c,mult,f,avg,c,mult,=1.02.0,4,.2.3,适应度函数及其尺度变换,59,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,适应度函数的幂函数变换法,f,=,f,k,k,与所求优化相关,4,.2.3,适应度函数及其尺度变换,k,60,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,适应度函数的指数变换法,f,=,e,-af,a,决定了复制的强制性，其值越小，复制的强制性就越趋向于那些具有最大适应性的个体。,4,.2.3,适应度函数及其尺度变换,61,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,几个概念,选择压力（,selection pressure,）,:,最佳个体选中的概率与平均个体选中概率的比值；,偏差（,bias,）：个体正规化适应度与其期望再生概率的绝对差值；,个体扩展（,spread,）：单个个体子代个数的范围；,多样化损失（,loss of diversity,）：在选择阶段未选中个体数目占种群的比例；,4,.2.4,遗传操作,选择,62,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,几个概念,选择强度（,selection intensity,）,:,将正规高斯分布应用于选择方法，期望平均适应度；,选择方差（,selection variance,）：将正规高斯分布应用于选择方法，期望种群适应度的方差。,4,.2.4,遗传操作,选择,63,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,个体选择概率的常用分配方法,按比例的适应度分配（,proportional fitness assignment,）,某个体,i,，其适应度为,f,i,，则其被选取的概率,P,i,为：,4,.2.4,遗传操作,选择,个体,f,f,2,P,1,2.5,6.25,0.18,2,1.0,1.00,0.03,3,3.0,9.00,0.26,4,1.2,1.44,0.04,5,2.1,4.41,0.13,6,0.8,0.64,0.02,7,2.5,6.25,0.18,8,1.3,1.69,0.05,9,0.9,0.81,0.02,10,1.8,3.24,0.09,64,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,个体选择概率的常用分配方法,基于排序的适应度分配（,rank-based fitness assignment,）,线性排序（,by Baker,）,为种群大小，,i,为个体序号，,max,代表选择压力。,4,.2.4,遗传操作,选择,65,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,个体选择概率的常用分配方法,基于排序的适应度分配（,rank-based fitness assignment,）,非线性排序（,by Michalewicz,）,i,为个体序号，,c,为排序第一的个体的选择概率。,4,.2.4,遗传操作,选择,66,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,常用选择方法,轮盘赌选择法（,roulette wheel selection,）,4,.2.4,遗传操作,选择,个体,1,2,3,4,5,6,7,8,9,10,11,适应度,2.0,1.8,1.6,1.4,1.2,1.0,0.8,0.6,0.4,0.2,0.1,选择概率,0.18,0.16,0.15,0.13,0.11,0.09,0.07,0.06,0.03,0.02,0.0,累计概率,0.18,0.34,0.49,0.62,0.73,0.82,0.89,0.95,0.98,1.00,1.00,67,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,常用选择方法,随机遍历抽样法（,stochastic universal sampling,）,4,.2.4,遗传操作,选择,个体,1,2,3,4,5,6,7,8,9,10,11,适应度,2.0,1.8,1.6,1.4,1.2,1.0,0.8,0.6,0.4,0.2,0.1,选择概率,0.18,0.16,0.15,0.13,0.11,0.09,0.07,0.06,0.03,0.02,0.0,累计概率,0.18,0.34,0.49,0.62,0.73,0.82,0.89,0.95,0.98,1.00,1.00,68,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,常用选择方法,局部选择法（,local selection,）,(1),线形邻集,4,.2.4,遗传操作,选择,69,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,常用选择方法,局部选择法（,local selection,）,(2),两对角邻集,4,.2.4,遗传操作,选择,70,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,常用选择方法,局部选择法（,local selection,）,(2),两对角邻集,4,.2.4,遗传操作,选择,71,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,常用选择方法,截断选择法（,truncation selection,）,个体按适应度排列，只有优秀个体能够称为父个体，参数为截断阀值（被选作父个体的百分比）。,4,.2.4,遗传操作,选择,截断阀值,1,10,20,40,50,80,选择强度,2.66,1.76,1.2,0.97,0.8,0.34,72,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,常用选择方法,锦标赛选择法（,tournament selection,）,随机从种群中挑选一定数目个体，其中最好的个体作为父个体，此过程重复进行完成个体的选择。,4,.2.4,遗传操作,选择,竞赛规模,1,2,3,5,10,30,选择强度,0,0.56,0.85,1.15,1.53,2.04,73,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,实值重组,离散重组,子个体的每个变量可以按等概率随机地挑选父个体。,4,.2.5,遗传操作,交叉,/,基因重组,父个体,1,12,25,5,父个体,2,123,4,34,子个体,1,123,4,5,子个体,2,12,4,34,74,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,实值重组,中间重组,子个体父个体,1,（父个体,2,父个体,1,）,是比例因子，由,-,d,1+,d,上均匀分布地随机数产生。,d,=0,时为中间重组，一般取,d,=0.25,。,子代的每个变量均产生一个,。,4,.2.5,遗传操作,交叉,/,基因重组,75,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,实值重组,中间重组,4,.2.5,遗传操作,交叉,/,基因重组,父个体,1,12 25 5,父个体,2,123 4 34,子个体,1,子个体,2,值样本,1,0.5 1.1 -0.1,值样本,2,0.1 0.8 0.5,12,0.5,（,123,12,）,=67.5,67.5,25,1.1,（,4,25,）,=1.9,1.9,2.1,12,0.1,（,123,12,）,=23.1,23.1,8.2,19.5,76,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,实值重组,中间重组,4,.2.5,遗传操作,交叉,/,基因重组,77,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,实值重组,线性重组,4,.2.5,遗传操作,交叉,/,基因重组,父个体,1,12 25 5,父个体,2,123 4 34,子个体,1,子个体,2,值样本,1,0.5,值样本,2,0.1,12,0.5,（,123,12,）,=67.5,67.5,25,0.5,（,4,25,）,=14.5,14.5,19.5,12,0.1,（,123,12,）,=23.1,23.1,22.9,7.9,78,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,实值重组,线性重组,4,.2.5,遗传操作,交叉,/,基因重组,79,4.2,基本遗传算法,智能优化计算,华东理工大学自动化系,2007,年,二进制交叉,单点交