第四章--遗传算法1PPT优秀课件

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