智能计算及应用2-遗传算法.ppt

单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,*,*,*,单击此处编辑母版标题样式,,遗传算法,(,一,),,,遗传算法简介,,产生,,早,在,50年代,，,一些生物学家开始研究运用数字计算机模拟生物的自然遗传,与自然进化过程,；,,1963,年,，德国柏林技术大学的,I.,Rechenberg,和,H. P.,Schwefel,，做风洞实验时，产生了,进化策略,的初步思想；,,60,年代，,L. J.,Fogel,在设计有限态自动机时提出,进化规划,的思想1966,年,Fogel,等出版了,《,基于模拟进化的人工智能,》,，系统阐述了进化规划的思想1.,遗传算法的产生与发展,,遗传算法简介,,产生,,60,年代中期，,美国Michigan大学的J,.,H,.,Holland教授,提出,借鉴生物自然遗传的基本原理,用于自然,,和人工系统的自适应行为研究和串编码技术；,,1967年，他的学生J,.,D,.,Bagley在博士论文中首次提出“遗传算法(Genetic,,Algorithms)”一词,；,,1975,年,，,Holland,出版了著名的“,Adaptation in Natural and Artificial Systems”,，标志,遗传算法的诞生,。

遗传算法的产生与发展,,遗传算法简介,,发展,,70,年代初，,Holland,提出了“模式定理”（,Schema Theorem,），一般认为是“遗传算法的基本定理”，从而奠定了遗传算法研究的理论基础；,,1985,年，在美国召开了第一届遗传算法国际会议，并且成立了国际遗传算法学会,(ISGA,，,International Society of Genetic Algorithms),；,,遗传算法的产生与发展,,遗传算法简介,,发展,,1989,年，,Holland,的学生,D. J.,Goldherg,出版了“,Genetic Algorithms in Search, Optimization, and Machine Learning”,，对遗传算法及其应用作了全面而系统的论述；,,1991,年，,L. Davis,编辑出版了,《,遗传算法手册,》,，其中包括了遗传算法在工程技术和社会生活中大量的应用实例遗传算法的产生与发展,,遗传算法简介,,几个名词概念,,,遗传算法,——,智能,计算,——,人工智能,遗传算法的产生与发展,,遗传算法简介,,几个名词概念,,进化计算：,遗传算法的产生与发展,,由于遗传算法、进化规划和进化策略是不同领域的研究人员分别独立提出的，在相当长的时期里相互之间没有正式沟通。

直到,90,年代，才有所交流他们发现彼此的基本思想具有惊人的相似之处，于是提出将这类方法统称为“进化计算”,( Evolutionary C,omputation,),遗传算法简介,,几个名词概念,,计算智能：,遗传算法的产生与发展,,计算智能主要包括神经计算、进化计算和模糊计算等它们分别从不同的角度模拟人类的智能活动，以使计算机具有智能通常将基于符号处理的传统人工智能称为符号智能，以区别于正在兴起的计算智能符号智能的特点是以知识为基础，偏重于逻辑推理，而计算智能则是以数据为基础，偏重于数值计算遗传算法简介,,达尔文的自然选择说,,遗传（,heredity,）：子代和父代具有相,,同或相似的性状，保证物种的稳定性；,,变异（,variation,）：子代与父代，子代不同个体之间总有差异，是生命多样性的根源；,,生存斗争和适者生存：具有适应性变异的个体被保留，不具适应性变异的个体被淘汰自然选择过程是长期的、缓慢的、连续的过程2.,生物进化理论和遗传学的基本知识,,遗传算法简介,,遗传学基本概念与术语,,染色体（,chromosome,）：遗传物质的载体；,,脱氧核糖核酸（,DNA,）：大分子有机聚合物，双螺旋结构；,,,,遗传因子（,gene,）：,DNA,或,RNA,长链结构中占有一定位置的基本遗传单位；,生物进化理论和遗传学的基本知识,,遗传算法简介,,遗传学基本概念与术语,,基因型（,genotype,）：遗传因子组合的模型；,,表现型（,phenotype,）：由染色体决定性状的外部表现；,生物进化理论和遗传学的基本知识,,1 1 1 1 1 1 1,,,1 1 1 0 1 1 1,,遗传算法简介,,遗传学基本概念与术语,,基因座（,locus,）：遗传基因在染色体中所占据的位置，同一基因座可能有的全部基因称为等位基因（,allele,）；,,个体（,individual,）：指带有染色体特征的实体；,,种群（,population,）：个体的集合，该集合内个体数称为种群的大小；,生物进化理论和遗传学的基本知识,,遗传算法简介,,遗传学基本概念与术语,,进化（,evolution,）：生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化；,,适应度（,fitness,）：度量某个物种对于生存环境的适应程度。

对生存环境适应程度较高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝,;,生物进化理论和遗传学的基本知识,,遗传算法简介,,遗传学基本概念与术语,,选择（,selection,）：指决定以一定的概率从种群中选择若干个体的操作 ；,,复制（,reproduction,）：细胞在分裂时，遗传物质,DNA,通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因,;,,交叉（,crossover,）：在两个染色体的某一相同位置处,DNA,被切断，其前后两串分别交叉组合形成两个新的染色体又称基因重组，俗称“杂交”,;,生物进化理论和遗传学的基本知识,,遗传算法简介,,遗传学基本概念与术语,,变异（,mutation,）：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使,DNA,发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状,;,,编码（,coding,）：表现型到基因型的映射；,,解码（,decoding,）：从基因型到表现型的映射生物进化理论和遗传学的基本知识,,遗传算法基本概念与术语,,个体,（,individual,）：,GA,所处理的基本对象、结构。

群体,（,population,）：个体的集合位串,（,bit String,）：个体的表示形式对应于遗传学中的染色体（,Chromosome,）,,基因,（,gene,）：位串中的元素，表示不同的特征对应于生物学中的遗传物质单位，以,DNA,序列形式把遗传信息译成编码遗传算法基本概念与术语,,位串结构空间,（,bit String Space,）：等位基因任意组合构成的位串集合，基因操作在位串结构空间进行，对应于遗传学中的基因型的集合参数空间,（,Parameters Space,）：是位串空间在物理系统中的映射对应于遗传学中的表现型的集合适应值,（,fitness,）：某一个体对于环境的适应程度，或者在环境压力下的生存能力，取决于遗传特性复制、选择,（,reproduction or selection,）：在有限资源空间上的排他性竞争逆转或倒位,（,inversion,）：反转位串上的一段基因的排列顺序对应于染色体上的一部分，在脱离之后反转,180o,再连接起来遗传算法基本概念与术语,,单倍体,（,haploid,，,monoploid,）：细胞核中有,n,个正常的不配对染色体二倍体,（,diploid,）、多倍体（,polyploid,）：细胞核中有,2n,或更多个正常的配对染色体。

基因型,（,genotype,）：或称遗传型，指用基因组定义遗传特征和表现对应于,GA,中的位串表现型,（,phenotype,）：生物体的基因型在特定环境下的表现特性对应于,GA,中的位串解码后的参数基因连结,（,linkage,）：两个或更多的等位基因出现在同一个染色体上对应于,GA,中的模式的概念上位遗传或者基因关联,（即,epistasis,）：两个非等位基因之间的相互作用，使得其中之一（上位基因）对另一个（下位基因）的表现型产生干扰或抑制对应于优化函数的非线性特征（,non-linearity,）,,遗传算法基本概念与术语,,基因多效性,（,pleiotropy,）：指单一基因对生物体多个物理性状的影响对应于,GA,求解多目标优化问题中，某个变量对多个目标函数的影响多基因效性,（,polygeny,）：指生物体某个物理性状由多个基因共同决定对应于,GA,求解多目标优化问题中，某个目标函数的值由多个变量的状态所决定遗传源变或遗传漂移,（,genetic dift,）：指群体的遗传组成的随机变化，不含自然选择的影响局部环境,（,environmental niches,）：具有某种特征的子环境，其中生物体具有特定的染色体结构，表现出特定的物理性状。

对应于多模态函数中局部极值点的邻域遗传算法简介,,进化论与遗传学的融合,,,1930,～,1947,年，达尔文进化论与遗传学走向融合，,Th. Dobzhansky1937,年发表的,《,遗传学与物种起源,》,是融合进化论与遗传学的代表作生物进化与智能学的关系,,生物物种作为复杂系统，具有奇妙的自适应、自组织和自优化能力，这是一种生物在进化过程中体现的智能，也是人工系统梦寐以求的功能生物进化理论和遗传学的基本知识,,遗传算法简介,,遗传算法的基本思路,,3,遗传算法的思路与特点,,遗传算法简介,,自组织、自适应和自学习性,,在编码方案、适应度函数及遗传算子确定后，算法将利用进化过程中获得的信息自行组织搜索本质并行性,,内在并行性与内含并行性,,不需求导,,只需目标函数和适应度函数,,概率转换规则,,强调概率转换规则，而不是确定的转换规则,遗传算法的特点,,遗传算法简介,,选择,,,适应度计算,：,,计算结果非负,,,,选择算法,：,,两类,,基于适应度比例的,,基于适应度排序的,4,遗传算法的基本操作,,遗传算法简介,,选择,,,选择算法,：,,轮盘赌选择（,roulette wheel selection,）,,随机遍历抽样（,stochastic universal selection,）,,局部选择（,local selection,）,,截断选择（,truncation selection,）,,锦标赛选择（,tournament selection,）,遗传算法的基本操作,,遗传算法简介,,交叉或基因重组,,,实值重组（,real valued recombination,）,：,,离散重组（,discrete recombination,）,,中间重组（,intermediate recombination,）,,线性重组（,linear recombination,）,,扩展线性重组（,extended linear recombination,）,,遗传算法的基本操作,,遗传算法简介,,交叉或基因重组,,,二进制交叉（,binary valued crossover,）,：,,单点交叉（,single-point crossover,）,,多点交叉（,multiple-point crossover,）,,均匀交叉（,uniform crossover,）,,洗牌交叉（,shuffle crossover,）,,缩小代理交叉（,crossover with reduced surrogate,）,遗传算法的基本操作,,遗传算法简介,,变异,,,实值变异,,,二进制变异,遗传算法的基本操作,,遗传算法简介,,简单实例,,产生初始种群,,,,,,计算适应度,遗传算法的基本操作,,0001100000 0101111001 0000000101 1001110100 1010101010,,,1110010110 1001011011 1100000001 1001110100 0001010011,,,（,8,） （,5,） （,2,） （,10,） （,7,）,,,（,12,） （,5,） （,19,） （,10,） （,14,）,遗传算法简介,,简单实例,,选择,,遗传算法的基本操作,,个体,染色体,适应度,选择概率,累积概率,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,遗传算法简介,,简单实例,,选择,,遗传算法的基本操作,,个体,染色体,适应度,选择概率,累积概率,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,～,1,之间产生一个,,随机数：,遗传算法的基本操作,,个体,染色体,适应度,选择概率,累积概率,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,淘汰！,淘汰！,0001100000 1110010110 1100000001 1001110100 1010101010,,1110010110 1001011011 1100000001 1001110100 0001010011,遗传算法简介,,简单实例,,交叉,遗传算法的基本操作,,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,遗传算法简介,,简单实例,,变异,遗传算法的基本操作,,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,遗传算法简介,,简单实例,,至下一代，适应度计算,→选择→交叉→变异，直至满足终止条件。

遗传算法的基本操作,,遗传算法简介,,函数优化,,是遗传算法的经典应用领域,;,,组合优化,,实践证明，遗传算法对于组合优化中的,NP,完全问题非常有效,;,,自动控制,,如基于遗传算法的模糊控制器优化设计、基于遗传算法的参数辨识等,;,5,遗传算法的应用,,遗传算法简介,,机器人智能控制,,遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行动协调等,;,,组合图像处理和模式识别,,目前已在图像恢复、图像边缘持征提取、几何形状识别等方面得到了应用,;,遗传算法的应用,,遗传算法简介,,人工生命,,基于遗传算法的进化模型是研究人工生命现象的重要理论基础，遗传算法已在其进化模型、学习模型、行为模型等方面显示了初步的应用能力；,,遗传程序设计,,,Koza,发展了遗传程序设计的慨念，他使用了以,LISP,语言所表示的编码方法，基于对一种树型结构所进行的遗传操作自动生成计算机程序,;,遗传算法的应用,,2,基本遗传算法,,问题的提出,,一元函数求最大值：,1,简单函数优化的实例,,基本遗传算法,,问题的提出,,用微分法求取,f,(,x,),的最大值：,,,,解有无穷多个：,简单函数优化的实例,,基本遗传算法,,问题的提出,,当,i,为奇数时,x,i,对应局部极大值点，,i,为偶数时,x,i,对应局部极小值。

x,19,即为区间,[-1,2],内的最大值点：,,,,此时，函数最大值,f,(,x,19,),比,f,(1.85)=3.85,稍大简单函数优化的实例,,基本遗传算法,,编码,,表现型：,x,,,基因型：二进制编码（串长取决于求解精度）,,,串长与精度之间的关系,：,,若要求求解精度到,6,位小数，区间长度为,2-(-1),＝,3,，即需将区间分为,3/0.000001=3×10,6,等份所以编码的二进制串长应为,22,位简单函数优化的实例,,基本遗传算法,,产生初始种群,,产生的方式：随机,,产生的结果：长度为,22,的二进制串,,产生的数量：种群的大小（规模），如,30,，,50,，,…,,,,,,,,……,简单函数优化的实例,,基本遗传算法,,计算适应度,,不同的问题有不同的适应度计算方法,,本例：直接用目标函数作为适应度函数,,①将某个体转化为,[-1,2],区间的实数：,,,s,→,x,=0.637197,,②,计算,x,的函数值（适应度）：,,,f,(,x,)=,x,sin(10,π,x,)+2.0=2.586345,简单函数优化的实例,,基本遗传算法,,计算适应度（简单函数值替换）,,,二进制与十进制之间的转换,：,,第一步，将一个二进制串（,b,21,b,20,…,b,0,）转化为,10,进制数：,,,第二步，,x’,对应的区间,[-1,2],内的实数：,简单函数优化的实例,,(0000000000000000000000),→-1,,基本遗传算法,,遗传操作,,选择：轮盘赌选择法；,,,交叉：单点交叉；,,,变异：小概率变异,简单函数优化的实例,,基本遗传算法,,模拟结果,,,设置的参数,：,,种群大小,50,；交叉概率,0.75,；变异概率,0.05,；最大迭代数,200,。

得到的最佳个体,：,,,s,max,,x,max,=1.8506;,,f,(x,max,)=3.8503;,简单函数优化的实例,,基本遗传算法,,模拟结果,,,进化的过程,：,简单函数优化的实例,,世代数,自变量,适应度,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,基本遗传算法,,编码原则,,完备性（,completeness,）：问题空间的所有解都能表示为所设计的基因型；,,健全性（,soundness,）：任何一个基因型都对应于一个可能解；,,非冗余性（,non-redundancy,）：问题空间和表达空间一一对应2,遗传基因型,,基本遗传算法,,多种编码方式,,二进制编码；,,浮点数编码；,,格雷码编码；,,符号编码；,,复数编码；,,DNA,编码等遗传基因型,,基本遗传算法,,二进制编码与浮点数编码的比较,,在交叉操作时，二进制编码比浮点数编码产生新个体的可能性多，而且产生的新个体不受父个体所构成的超体的限制；,,在变异操作时，二进制编码的种群稳定性比浮点数编码差。

遗传基因型,,基本遗传算法,,适应度函数的重要性,,适应度函数的选取直接影响遗传算法的收敛速度以及能否找到最优解一般而言，适应度函数是由目标函数变换而成的，对目标函数值域的某种映射变换称为适应度的,尺度变换,（,fitness scaling,）3,适应度函数及其尺度变换,,基本遗传算法,,几种常见的适应度函数,,直接转换,,若目标函数为最大化问题：,Fit (,f,(,x,) )=,f,(,x,),,,若目标函数为最小化问题：,Fit (,f,(,x,) )= -,f,(,x,),,,适应度函数及其尺度变换,,基本遗传算法,,几种常见的适应度函数,,界限构造法,1,,,若目标函数为最大化问题：,,,,,若目标函数为最小化问题：,,适应度函数及其尺度变换,,基本遗传算法,,几种常见的适应度函数,,界限构造法,2,,,若目标函数为最大化问题：,,,,若目标函数为最小化问题：,,,,c,为目标函数的保守估计值适应度函数及其尺度变换,,基本遗传算法,,适应度函数的作用,,适应度函数设计不当有可能出现欺骗问题：,,（,1,）进化初期，个别超常个体控制选择过程；,,（,2,）进化末期，个体差异太小导致进化缓慢。

适应度函数及其尺度变换,,基本遗传算法,,适应度函数的设计,,单值、连续、非负、最大化,,合理、一致性,,计算量小,,通用性强,适应度函数及其尺度变换,,基本遗传算法,,适应度函数的线性变换法,,,f,’=,α,*,f,+,β,,,系数的确定满足以下条件：,,①,f,’,avg,=,f,avg,,②,f,’,max,=,c,mult,f,’,avg,,c,mult,=1.0~2.0,适应度函数及其尺度变换,,基本遗传算法,,适应度函数的幂函数变换法,,,f,’=,f,k,,,k,与所求优化相关,适应度函数及其尺度变换,,k,基本遗传算法,,适应度函数的指数变换法,,,f,’=,e,-af,,,a,决定了复制的强制性，其值越小，复制的强制性就越趋向于那些具有最大适应性的个体适应度函数及其尺度变换,,α,基本遗传算法,,几个概念,,选择压力（,selection pressure,）,:,最佳个体选中的概率与平均个体选中概率的比值；,,偏差（,bias,）：个体正规化适应度与其期望再生概率的绝对差值；,,个体扩展（,spread,）：单个个体子代个数的范围；,,多样化损失（,loss of diversity,）：在选择阶段未选中个体数目占种群的比例；,4,遗传操作,——,选择,,基本遗传算法,,几个概念,,选择强度（,selection intensity,）,:,将正规高斯分布应用于选择方法，期望平均适应度；,,选择方差（,selection variance,）：将正规高斯分布应用于选择方法，期望种群适应度的方差。

遗传操作,——,选择,,基本遗传算法,,个体选择概率的常用分配方法,,按比例的适应度分配（,proportional fitness assignment,）,,某个体,i,，其适应度为,f,i,，则其被选取的概率,P,i,为：,遗传操作,——,选择,,个体,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,基本遗传算法,,个体选择概率的常用分配方法,,基于排序的适应度分配（,rank-based fitness assignment,）,,线性排序（,by Baker,）,,,,,μ,为种群大小，,i,为个体序号，,η,max,代表选择压力遗传操作,——,选择,,基本遗传算法,,个体选择概率的常用分配方法,,基于排序的适应度分配（,rank-based fitness assignment,）,,非线性排序（,by,Michalewicz,）,,,,,i,为个体序号，,c,为排序第一的个体的选择概率。

遗传操作,——,选择,,基本遗传算法,,常用选择方法,,轮盘赌选择法（,roulette wheel selection,）,,,,遗传操作,——,选择,,个体,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,基本遗传算法,,常用选择方法,,随机遍历抽样法（,stochastic universal sampling,）,,,,遗传操作,——,选择,,个体,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,设定,n,为需要选择的个体数目，等距离选择个体，选择指针的距离为,1,／,n,。

第一个指针的位置由,[0,，,l,／,n],区间的均匀随机数决定如图所示，需要选择,6,个个体，指针间的距离为,l,／,6,＝,o.167,，第一个指针的随机位置为,0.1,，按这种选择方法被选中作为交配集个体为：,1,．,2,，,3,．,4,，,6,，,8,基本遗传算法,,常用选择方法,,局部选择法（,local selection,）,,,(1),线形邻集,遗传操作,——,选择,,,,在局部选择法中，每个个体处于一个约束环境中，称为局部邻域,(,而其他选择方法中视整个种群为个体之邻域,),，个体仅与其邻近个体产生交互，该邻域的定义由种群的分布结构给出邻域可被当作潜在的交配伙伴首先均匀随机地选择一半交配种群，选择方法可以是随机遍历方法也可以是截断选择方法，然后对每个被选个体定义其局部邻域，在邻域内部选择交配伙伴基本遗传算法,,常用选择方法,,局部选择法（,local selection,）,,,(2),两对角邻集,遗传操作,——,选择,,基本遗传算法,,常用选择方法,,局部选择法（,local selection,）,,,(2),两对角邻集,遗传操作,——,选择,,,,基本遗传算法,,常用选择方法,,截断选择法（,truncation selection,）,,个体按适应度排列，只有优秀个体能够成为父个体，参数为截断阀值（被选作父个体的百分比）。

遗传操作,——,选择,,截断阀值,1,％,10,％,20,％,40,％,50,％,80,％,选择强度,2.66,1.76,1.2,0.97,0.8,0.34,基本遗传算法,,常用选择方法,,锦标赛选择法（,tournament selection,）,,随机从种群中挑选一定数目个体，其中最好的个体作为父个体，此过程重复进行完成个体的选择遗传操作,——,选择,,竞赛规模,1,2,3,5,10,30,选择强度,0,0.56,0.85,1.15,1.53,2.04,基本遗传算法,,实值重组,,离散重组,,子个体的每个变量可以按等概率随机地挑选父个体5,遗传操作,——,交叉,/,基因重组,,父个体,1,12,,25,,5,,父个体,2,123,,4,,34,子个体,1,123,,4,,5,,子个体,2,12,,4,,34,基本遗传算法,,实值重组,,中间重组,,子个体＝父个体,1,＋,α,×,（父个体,2,－父个体,1,）,,,α,是比例因子，由,[-,d,,1+,d,],上均匀分布地随机数产生一般取,d,=0.25,子代的每个变量均产生一个,α,,遗传操作,——,交叉,/,基因重组,,基本遗传算法,,实值重组,,中间重组示例,,,遗传操作,——,交叉,/,基因重组,,父个体,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,基本遗传算法,,实值重组,,中间重组,,,遗传操作,——,交叉,/,基因重组,,基本遗传算法,,实值重组,,线性重组,,,遗传操作,——,交叉,/,基因重组,,父个体,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,基本遗传算法,,实值重组,,线性重组,,,遗传操作,——,交叉,/,基因重组,,基本遗传算法,,二进制交叉,,单点交叉,,,遗传操作,——,交叉,/,基因重组,,基本遗传算法,,二进制交叉,,多点交叉,,,遗传操作,——,交叉,/,基因重组,,基本遗传算法,,实值变异,,一般采用：,,,,,,,二进制变异,,,6,遗传操作,——,变异,,4.2,基本遗传算法,,运行程序,,,,4,.2.7,算法的设计与实现,,基本遗传算法,,运行程序,,,算法的设计与实现,,4.2,基本遗传算法,,运行程序,,,,4,.2.7,算法的设计与实现,,4.2,基本遗传算法,,运行程序,,,,4,.2.7,算法的设计与实现,,基本遗传算法,,模式,,将种群中的个体即基因串中的相似样板称为,模式,。

在二进制编码的串中，模式是基于三个字符集（,0,，,1,，*）的字符串，符号*代表任意字符，即,0,或,1,如模式 *,1*,描述了一个四个元的子集,{010,，,011,，,110,，,111},8,模式定理,,4.2,基本遗传算法,,模式阶和定义距,,模式,H,中确定位置的个数称为模式,H,的,模式阶,，记作,O,(,H,),，如,O,(0 1 1 * 1 *)=4,模式阶用来反映不同模式间确定性的差异，模式阶越高，模式的确定性就越高，所匹配的样本个数就越少4,.2.8,模式定理,,基本遗传算法,,模式阶和定义距,,模式,H,中第一个确定位置和最后一个确定位置之间的距离称为模式的,定义距,，记作,δ,(,H,),，如,,,δ,(0 1 1 * 1 * *)=4,阶数相同的模式会有不同的性质，定义距就反映了这种性质的差异模式定理,,基本遗传算法,,模式,定理（,schema theorem,）,,在给定时间步,t,,,一个特定模式,H,有,,m,个代表串包含在种群,A,(,t,),中，记为,m,=,m,(,H,,,t,),，在再生阶段，每个串根据它的适应值进行复制，一个串,A,i,,的再生概率为,模式定理,,基本遗传算法,,模式,定理（,schema theorem,）,,当采用非重叠的,n,,个串的种群替代种群,A,(,t,),，可以得到：,,,,其中,f,(,H,),是在时间,t,,表示模式,H,,的串的平均适应度。

模式定理,,基本遗传算法,,模式定理,,模式,定理（,schema theorem,）,,假设从,t,=0,开始，某一特定模式适应度值保持在种群平均适应度以上一个,cf,（,c,为一常数），则模式的选择生长方程为,上式表明，在种群平均值以上,(,以下,),的模式将按指数增长,(,衰减,),的方式被复制基本遗传算法,,模式,定理（,schema theorem,）,,考虑交叉操作，模式,H,,被破坏的概率为,δ,(,H,)/(,l,-1),，模式,H,,生存概率为,1-,δ,(,H,)/(,l,-1),，若交叉操作发生的概率为,p,c,，因此对于模式,H,,的生存概率计算为：,,,,同时考虑选择、交叉操作对模式的影响，可得：,模式定理,,H1= * 1 * * * * 0,,H2= * * * 1 0 * *,该式表明，模式增长或衰减依赖于两个因素．一个因素是模式的适应值是在平均适应值之上还是在平均适应值之下，另一个因素是模式具有相对长还是相对短的定义距那些既在种群平均适应度值之上同时又具有短的定义距的模式将校指数增长率被采样基本遗传算法,,模式,定理（,schema theorem,）,,考虑变异操作，单个等位基因变异的概率为,p,m,,，当模式,H,,中,O,(,H,),个确定位都存活时，模式,H,,才被保留，存活概率为：,,,,同时考虑选择、交叉和变异操作对模式的影响，可得：,模式定理,,H1= * 1 * * * * 0,,H2= * * * 1 0 * 0,4.2,基本遗传算法,,模式,定理（,schema theorem,）,,,模式定理,：在遗传算子选择、交叉、变异的作用下，具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代中呈指数增长。

具有低阶、短定义距以及平均适应度高于种群平均适应度的模式被定义为,积木块,4,.2.8,模式定理,,基本遗传算法,,积木块假设,（,building block hypothesis,）,,遗传算法通过短定义距、低阶以及高平均适应度的模式（积木块），产生适应度更高的个体，从而找到更优的可行解模式定理,,骗问题,,我们已经知道，遗传算法适用于大多数经常碰到的问题，但也存在着一些遗传算法难以解决的问题，即最终的搜索往往偏离全局最优解，这类问题被称作,GA-,难的这一节我们探讨所谓的,骗问题,（,deceptive Problem,），即,构造一个问题，给定一些带欺骗性质的初始条件，“迷惑”遗传算法，使其偏离全局最优解为此，,要最大限度地违背积木块假设，即使得低阶、短距、高于平均适应度的模式生成局部最优点由模式理论，一个问题能否用遗传算法有效地求解，取决于问题编码是否满足积木块假设，满足者用遗传算法求解效率较高，不满足者效率 较低、甚至找不到满意解谢谢！,。