第四章__遗传算法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,模式定理,智能优化计算,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,遗传算法在模式识别中的应用,智能优化计算,4.1,遗传算法简介,智能优化计算,产生,早,在,50年代,，,一些生物学家开始研究运用数字计算机模拟生物的自然遗传,与自然进化过程,；,1963,年,，德国柏林技术大学的,I.,Rechenberg,和,H. P.,Schwefel,，做风洞实验时，产生了,进化策略,的初步思想；,60,年代，,L. J.,Fogel,在设计有限态自动机时提出,进化规划,的思想。,1966,年,Fogel,等出版了,基于模拟进化的人工智能,，系统阐述了进化规划的思想。,4,.1.1,遗传算法的产生与发展,4.1,遗传算法简介,智能优化计算,产生,60,年代中期，,美国Michigan大学的J,.,H,.,Holland教授,提出,借鉴生物自然遗传的基本原理,用于自然,和人工系统的自适应行为研究和串编码技术；,1967年，他的学生J,.,D,.,Bagley在博士论文中首次提出“遗传算法(Genetic,Algorithms)”一词,；,1975,年,，,Holland,出版了著名的“,Adaptation in Natural and Artificial Systems”,，标志,遗传算法的诞生,。,4,.1.1,遗传算法的产生与发展,4.1,遗传算法简介,智能优化计算,发展,70,年代初，,Holland,提出了“模式定理”（,Schema Theorem,），一般认为是“遗传算法的基本定理”，从而奠定了遗传算法研究的理论基础；,1985,年，在美国召开了第一届遗传算法国际会议，并且成立了国际遗传算法学会,(ISGA,，,International Society of Genetic Algorithms),；,4,.1.1,遗传算法的产生与发展,4.1,遗传算法简介,智能优化计算,发展,1989,年，,Holland,的学生,D. J.,Goldherg,出版了“,Genetic Algorithms in Search, Optimization, and Machine Learning”,，对遗传算法及其应用作了全面而系统的论述；,1991,年，,L. Davis,编辑出版了,遗传算法手册,，其中包括了遗传算法在工程技术和社会生活中大量的应用实例。,4,.1.1,遗传算法的产生与发展,4.1,遗传算法简介,智能优化计算,几个名词概念,遗传算法,进化计算,计算智能,人工智能,4,.1.1,遗传算法的产生与发展,4.1,遗传算法简介,智能优化计算,几个名词概念,进化计算：,4,.1.1,遗传算法的产生与发展,由于遗传算法、进化规划和进化策略是不同领域的研究人员分别独立提出的，在相当长的时期里相互之间没有正式沟通。直到,90,年代，才有所交流。,他们发现彼此的基本思想具有惊人的相似之处，于是提出将这类方法统称为“进化计算”,( Evolutionary C,omputation,),。,4.1,遗传算法简介,智能优化计算,几个名词概念,计算智能：,4,.1.1,遗传算法的产生与发展,计算智能主要包括神经计算、进化计算和模糊计算等。它们分别从不同的角度模拟人类的智能活动，以使计算机具有智能。,通常将基于符号处理的传统人工智能称为符号智能，以区别于正在兴起的计算智能。,符号智能的特点是以知识为基础，偏重于逻辑推理，而计算智能则是以数据为基础，偏重于数值计算。,4.1,遗传算法简介,智能优化计算,达尔文的自然选择说,遗传（,heredity,）：子代和父代具有相,同或相似的性状，保证物种的稳定性；,变异（,variation,）：子代与父代，子代不同个体之间总有差异，是生命多样性的根源；,生存斗争和适者生存：具有适应性变异的个体被保留，不具适应性变异的个体被淘汰。,自然选择过程是长期的、缓慢的、连续的过程。,4,.1.2,生物进化理论和遗传学的基本知识,4.1,遗传算法简介,智能优化计算,遗传学基本概念与术语,染色体（,chromosome,）：遗传物质的载体；,脱氧核糖核酸（,DNA,）：大分子有机聚合物，双螺旋结构；,遗传因子（,gene,）：,DNA,或,RNA,长链结构中占有一定位置的基本遗传单位；,4,.1.2,生物进化理论和遗传学的基本知识,4.1,遗传算法简介,智能优化计算,遗传学基本概念与术语,基因型（,genotype,）：遗传因子组合的模型；,表现型（,phenotype,）：由染色体决定性状的外部表现；,4,.1.2,生物进化理论和遗传学的基本知识,1 1 1 1 1 1 1,1 1 1 0 1 1 1,4.1,遗传算法简介,智能优化计算,遗传学基本概念与术语,基因座（,locus,）：遗传基因在染色体中所占据的位置，同一基因座可能有的全部基因称为等位基因（,allele,）；,个体（,individual,）：指染色体带有特征的实体；,种群（,population,）：个体的集合，该集合内个体数称为种群的大小；,4,.1.2,生物进化理论和遗传学的基本知识,4.1,遗传算法简介,智能优化计算,遗传学基本概念与术语,进化（,evolution,）：生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化；,适应度（,fitness,）：度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝,;,4,.1.2,生物进化理论和遗传学的基本知识,4.1,遗传算法简介,智能优化计算,遗传学基本概念与术语,选择（,selection,）：指决定以一定的概率从种群中选择若干个体的操作 ；,复制（,reproduction,）：细胞在分裂时，遗传物质,DNA,通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因,;,交叉（,crossover,）：在两个染色体的某一相同位置处,DNA,被切断，其前后两串分别交叉组合形成两个新的染色体。又称基因重组，俗称“杂交”,;,4,.1.2,生物进化理论和遗传学的基本知识,4.1,遗传算法简介,智能优化计算,遗传学基本概念与术语,变异（,mutation,）：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使,DNA,发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状,;,编码（,coding,）：表现型到基因型的映射；,解码（,decoding,）：从基因型到表现型的映射。,4,.1.2,生物进化理论和遗传学的基本知识,4.1,遗传算法简介,智能优化计算,进化论与遗传学的融合,1930,1947,年，达尔文进化论与遗传学走向融合，,Th. Dobzhansky1937,年发表的,遗传学与物种起源,是融合进化论与遗传学的代表作。,生物进化与智能学的关系,生物物种作为复杂系统，具有奇妙的自适应、自组织和自优化能力，这是一种生物在进化过程中体现的智能，也是人工系统梦寐以求的功能。,4,.1.2,生物进化理论和遗传学的基本知识,4.1,遗传算法简介,智能优化计算,遗传算法的基本思路,4,.1.3,遗传算法的思路与特点,4.1,遗传算法简介,智能优化计算,自组织、自适应和自学习性,在编码方案、适应度函数及遗传算子确定后，算法将利用进化过程中获得的信息自行组织搜索。,本质并行性,内在并行性与内含并行性,不需求导,只需目标函数和适应度函数,概率转换规则,强调概率转换规则，而不是确定的转换规则,4,.1.3,遗传算法的思路与特点,4.1,遗传算法简介,智能优化计算,选择,适应度计算,：,按比例的适应度函数（,proportional fitness assignment,）,基于排序的适应度计算（,Rank-based fitness assignment,）,选择算法,：,轮盘赌选择（,roulette wheel selection,）,4,.1.4,遗传算法的基本操作,4.1,遗传算法简介,智能优化计算,选择,选择算法,：,随机遍历抽样（,stochastic universal selection,）,局部选择（,local selection,）,截断选择（,truncation selection,）,锦标赛选择（,tournament selection,）,4,.1.4,遗传算法的基本操作,4.1,遗传算法简介,智能优化计算,交叉或基因重组,实值重组（,real valued recombination,）,：,离散重组（,discrete recombination,）,中间重组（,intermediate recombination,）,线性重组（,linear recombination,）,扩展线性重组（,extended linear recombination,）,4,.1.4,遗传算法的基本操作,4.1,遗传算法简介,智能优化计算,交叉或基因重组,二进制交叉（,binary valued crossover,）,：,单点交叉（,single-point crossover,）,多点交叉（,multiple-point crossover,）,均匀交叉（,uniform crossover,）,洗牌交叉（,shuffle crossover,）,缩小代理交叉（,crossover with reduced surrogate,）,4,.1.4,遗传算法的基本操作,4.1,遗传算法简介,智能优化计算,变异,实值变异,二进制变异,4,.1.4,遗传算法的基本操作,4.1,遗传算法简介,智能优化计算,简单实例,产生初始种群,计算适应度,4,.1.4,遗传算法的基本操作,0001100000 0101111001 0000000101 1001110100 1010101010,1110010110 1001011011 1100000001 1001110100 0001010011,（,8,） （,5,） （,2,） （,10,） （,7,）,（,12,） （,5,） （,19,） （,10,） （,14,）,4.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,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,4.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,4.1,遗传算法简介,智能优化计算,简单实例,选择,在,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,淘汰！,淘汰！,0001100000 1110010110 1100000001 1001110100 1010101010,1110010110 1001011011 1100000001 1001110100 0001010011,4.1,遗传算法简介,智能优化计算,简单实例,交叉,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,4.1,遗传算法简介,智能优化计算,简单实例,变异,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,4.1,遗传算法简介,智能优化计算,简单实例,至下一代，适应度计算,选择交叉变异，直至满足终止条件。,4,.1.4,遗传算法的基本操作,4.1,遗传算法简介,智能优化计算,函数优化,是遗传算法的经典应用领域,;,组合优化,实践证明，遗传算法对于组合优化中的,NP,完全问题非常有效,;,自动控制,如基于遗传算法的模糊控制器优化设计、基于遗传算法的参数辨识、利用遗传算法进行人工神经网络的结构优化设计和权值学习等,;,4,.1.5,遗传算法的应用,4.1,遗传算法简介,智能优化计算,机器人智能控制,遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行动协调等,;,组合图像处理和模式识别,目前已在图像恢复、图像边缘持征提取、几何形状识别等方面得到了应用,;,4,.1.5,遗传算法的应用,4.1,遗传算法简介,智能优化计算,人工生命,基于遗传算法的进化模型是研究人工生命现象的重要理论基础，遗传算法已在其进化模型、学习模型、行为模型等方面显示了初步的应用能力；,遗传程序设计,Koza,发展了遗传程序设计的慨念，他使用了以,LISP,语言所表示的编码方法，基于对一种树型结构所进行的遗传操作自动生成计算机程序,;,4,.1.5,遗传算法的应用,再见！,智能优化计算,