经典算法之遗传算法课件

遗传算法遗传算法 遗传算法简介遗传算法简介 l产生产生早早在在50年代年代，一些生物学家开始研究运用数字计算一些生物学家开始研究运用数字计算机模拟生物的自然遗传机模拟生物的自然遗传与自然进化过程与自然进化过程；1963年年，德国柏林技术大学的，德国柏林技术大学的I.Rechenberg和和H.P.Schwefel，做风洞实验时，产生了，做风洞实验时，产生了进化策略进化策略的初步的初步思想；思想；60年代，年代，L.J.Fogel在设计有限态自动机时提出在设计有限态自动机时提出进进化规划化规划的思想。的思想。1966年年Fogel等出版了等出版了基于模拟基于模拟进化的人工智能进化的人工智能，系统阐述了进化规划的思想。，系统阐述了进化规划的思想。1.1.遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展 遗传算法简介遗传算法简介 l产生产生60年代中期，年代中期，美国美国Michigan大学的大学的J.H.Holland教教授授提出提出借鉴生物自然遗传的基本原理借鉴生物自然遗传的基本原理用于自然用于自然 和人工系统的自适应行为研究和串编码技术；和人工系统的自适应行为研究和串编码技术；1967年，他的学生年，他的学生J.D.Bagley在博士论文中首次提在博士论文中首次提出出“遗传算法遗传算法(Genetic Algorithms)”一词一词；1975年年，Holland出版了著名的出版了著名的“Adaptation in Natural and Artificial Systems”，标志，标志遗传算法的遗传算法的诞生诞生。遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展 遗传算法简介遗传算法简介 l发展发展70年代初，年代初，Holland提出了提出了“模式定理模式定理”（Schema Theorem），一般认为是），一般认为是“遗传算法遗传算法的基本定理的基本定理”，从而奠定了遗传算法研究的理论基，从而奠定了遗传算法研究的理论基础；础；1985年，在美国召开了第一届遗传算法国际会议，年，在美国召开了第一届遗传算法国际会议，并且成立了国际遗传算法学会并且成立了国际遗传算法学会(ISGA，International Society of Genetic Algorithms)；遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展 遗传算法简介遗传算法简介 l发展发展1989年，年，Holland的学生的学生D.J.Goldherg出版了出版了“Genetic Algorithms in Search,Optimization,and Machine Learning”，对遗传算法及其应用作了全，对遗传算法及其应用作了全面而系统的论述；面而系统的论述；1991年，年，L.Davis编辑出版了编辑出版了遗传算法手册遗传算法手册，其中包括了遗传算法在工程技术和社会生活中大量其中包括了遗传算法在工程技术和社会生活中大量的应用实例。的应用实例。遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展 遗传算法简介遗传算法简介 l几个名词概念几个名词概念 进化计算：进化计算：遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展 由于遗传算法、进化规划和进化策略是不同领域由于遗传算法、进化规划和进化策略是不同领域的研究人员分别独立提出的，在相当长的时期里的研究人员分别独立提出的，在相当长的时期里相互之间没有正式沟通。直到相互之间没有正式沟通。直到90年代，才有所交年代，才有所交流。流。他们发现彼此的基本思想具有惊人的相似之处，他们发现彼此的基本思想具有惊人的相似之处，于是提出将这类方法统称为于是提出将这类方法统称为“进化计算进化计算”(Evolutionary Computation)。遗传算法简介遗传算法简介 l达尔文的自然选择说达尔文的自然选择说遗传（遗传（heredity）：子代和父代具有相）：子代和父代具有相 同或相似的性状，保证物种的稳定性；同或相似的性状，保证物种的稳定性；变异（变异（variation）：子代与父代，子代不同个体之）：子代与父代，子代不同个体之间总有差异，是生命多样性的根源；间总有差异，是生命多样性的根源；生存斗争和适者生存：具有适应性变异的个体被保生存斗争和适者生存：具有适应性变异的个体被保留，不具适应性变异的个体被淘汰。留，不具适应性变异的个体被淘汰。自然选择过程是长期的、缓慢的、连续的过程。自然选择过程是长期的、缓慢的、连续的过程。2.2.生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识 遗传算法简介遗传算法简介 l遗传学基本概念与术语遗传学基本概念与术语染色体（染色体（chromosome）：遗传物质的载体；）：遗传物质的载体；脱氧核糖核酸（脱氧核糖核酸（DNA）：大分子有机聚合物，双螺）：大分子有机聚合物，双螺旋结构；旋结构；遗传因子（遗传因子（gene）：）：DNA或或RNA长链结构中占有长链结构中占有一定位置的基本遗传单位；一定位置的基本遗传单位；生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识 遗传算法简介遗传算法简介 l遗传学基本概念与术语遗传学基本概念与术语基因型（基因型（genotype）：遗传因子组合的模型；）：遗传因子组合的模型；表现型（表现型（phenotype）：由染色体决定性状的外部）：由染色体决定性状的外部表现；表现；生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识 1 1 1 1 1 1 1 1 1 1 0 1 1 1 遗传算法简介遗传算法简介 l遗传学基本概念与术语遗传学基本概念与术语基因座（基因座（locus）：遗传基因在染色体中所占据的）：遗传基因在染色体中所占据的位置，同一基因座可能有的全部基因称为等位基因位置，同一基因座可能有的全部基因称为等位基因（allele）；）；个体（个体（individual）：指带有染色体特征的实体；）：指带有染色体特征的实体；种群（种群（population）：个体的集合，该集合内个体）：个体的集合，该集合内个体数称为种群的大小；数称为种群的大小；生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识 遗传算法简介遗传算法简介 l遗传学基本概念与术语遗传学基本概念与术语进化（进化（evolution）：生物在其延续生存的过程中，）：生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化；这种生命现象称为进化；适应度（适应度（fitness）：度量某个物种对于生存环境的）：度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝种，其繁殖机会就会相对较少，甚至逐渐灭绝;生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识 遗传算法简介遗传算法简介 l遗传学基本概念与术语遗传学基本概念与术语选择（选择（selection）：指决定以一定的概率从种群）：指决定以一定的概率从种群中选择若干个体的操作中选择若干个体的操作；复制（复制（reproduction）：细胞在分裂时，遗传物质）：细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新的细胞通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因就继承了旧细胞的基因;交叉（交叉（crossover）：在两个染色体的某一相同位）：在两个染色体的某一相同位置处置处DNA被切断，其前后两串分别交叉组合形成两被切断，其前后两串分别交叉组合形成两个新的染色体。又称基因重组，俗称个新的染色体。又称基因重组，俗称“杂交杂交”;生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识 遗传算法简介遗传算法简介 l遗传学基本概念与术语遗传学基本概念与术语变异（变异（mutation）：在细胞进行复制时可能以很小）：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使的概率产生某些复制差错，从而使DNA发生某种变发生某种变异，产生出新的染色体，这些新的染色体表现出新异，产生出新的染色体，这些新的染色体表现出新的性状的性状;编码（编码（coding）：表现型到基因型的映射；）：表现型到基因型的映射；解码（解码（decoding）：从基因型到表现型的映射。）：从基因型到表现型的映射。生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识 l遗传算法基本概念与术语遗传算法基本概念与术语l个体个体（individual）：GA所处理的基本对象、结构。l群体群体（population）：个体的集合。l位串位串（bitString）：个体的表示形式。对应于遗传学中的染色体（Chromosome）l基因基因（gene）：位串中的元素，表示不同的特征。对应于生物学中的遗传物质单位，以DNA序列形式把遗传信息译成编码。l遗传算法基本概念与术语遗传算法基本概念与术语l位串结构空间位串结构空间（bitStringSpace）：等位基因任意组合构成的位串集合，基因操作在位串结构空间进行，对应于遗传学中的基因型的集合。l参数空间参数空间（ParametersSpace）：是位串空间在物理系统中的映射。对应于遗传学中的表现型的集合。l适应值适应值（fitness）：某一个体对于环境的适应程度，或者在环境压力下的生存能力，取决于遗传特性。l复制、选择复制、选择（reproductionorselection）：在有限资源空间上的排他性竞争。l逆转或倒位逆转或倒位（inversion）：反转位串上的一段基因的排列顺序。对应于染色体上的一部分，在脱离之后反转180o再连接起来。遗传算法简介遗传算法简介 l进化论与遗传学的融合进化论与遗传学的融合 19301947年，达尔文进化论与遗传学走向融合，年，达尔文进化论与遗传学走向融合，Th.Dobzhansky1937年发表的年发表的遗传学与物种起源遗传学与物种起源是融合进化论与遗传学的代表作。是融合进化论与遗传学的代表作。l生物进化与智能学的关系生物进化与智能学的关系 生物物种作为复杂系统，具有奇妙的自适应、自组生物物种作为复杂系统，具有奇妙的自适应、自组织和自优化能力，这是一种生物在进化过程中体现织和自优化能力，这是一种生物在进化过程中体现的智能，也是人工系统梦寐以求的功能。的智能，也是人工系统梦寐以求的功能。生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识 遗传算法简介遗传算法简介 l遗传算法的基本思路遗传算法的基本思路3 3 遗传算法的思路与特点遗传算法的思路与特点遗传算法的思路与特点遗传算法的思路与特点 遗传算法简介遗传算法简介 l自组织、自适应和自学习性自组织、自适应和自学习性 在编码方案、适应度函数及遗传算子确定后，算法在编码方案、适应度函数及遗传算子确定后，算法将利用进化过程中获得的信息自行组织搜索。将利用进化过程中获得的信息自行组织搜索。l本质并行性本质并行性 内在并行性与内含并行性内在并行性与内含并行性l不需求导不需求导 只需目标函数和适应度函数只需目标函数和适应度函数l概率转换规则概率转换规则 强调概率转换规则，而不是确定的转换规则强调概率转换规则，而不是确定的转换规则遗传算法的特点遗传算法的特点遗传算法的特点遗传算法的特点 遗传算法简介遗传算法简介 l选择选择 适应度计算适应度计算：计算结果非负计算结果非负 选择算法选择算法：两类两类基于适应度比例的基于适应度比例的基于适应度排序的基于适应度排序的4 4 遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 遗传算法简介遗传算法简介 l选择选择 选择算法选择算法：轮盘赌选择（轮盘赌选择（roulette wheel selection）随机遍历抽样（随机遍历抽样（stochastic universal selection）局部选择（局部选择（local selection）截断选择（截断选择（truncation selection）锦标赛选择（锦标赛选择（tournament selection）遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 遗传算法简介遗传算法简介 l交叉或基因重组交叉或基因重组 实值重组（实值重组（real valued recombination）：离散重组（离散重组（discrete recombination）中间重组（中间重组（intermediate recombination）线性重组（线性重组（linear recombination）扩展线性重组（扩展线性重组（extended linear recombination）遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 遗传算法简介遗传算法简介 l交叉或基因重组交叉或基因重组 二进制交叉（二进制交叉（binary valued crossover）：单点交叉（单点交叉（single-point crossover）多点交叉（多点交叉（multiple-point crossover）均匀交叉（均匀交叉（uniform crossover）洗牌交叉（洗牌交叉（shuffle crossover）缩小代理交叉（缩小代理交叉（crossover with reduced surrogate）遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 遗传算法简介遗传算法简介 l变异变异 实值变异实值变异 二进制变异二进制变异遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 遗传算法简介遗传算法简介 l简单实例简单实例1.产生初始种群产生初始种群2.计算适应度计算适应度遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 0001100000010111100100000001011001110100101010101011100101101001011011110000000110011101000001010011（8）（5）（2）（10）（7）（12）（5）（19）（10）（14）遗传算法简介遗传算法简介 l简单实例简单实例3.选择选择遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 个体个体染色体染色体适应度适应度选择概率选择概率累积概率累积概率10001100000820101111001530000000101241001110100105101010101076111001011012710010110115811000000011991001110100101000010100111488521071251910140.08695758521071251910140.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.152174遗传算法简介遗传算法简介 l简单实例简单实例3.选择选择遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 个体个体染色体染色体适应度适应度选择概率选择概率累积概率累积概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.000000遗传算法简介遗传算法简介 l简单实例简单实例3.选择选择在在01之间产生一个之间产生一个随机数：随机数：遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 个体个体染色体染色体适应度适应度选择概率选择概率累积概率累积概率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淘汰！淘汰！淘汰！淘汰！0001100000111001011011000000011001110100101010101011100101101001011011110000000110011101000001010011遗传算法简介遗传算法简介 l简单实例简单实例4.交叉交叉遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 0001100000111001011011000000011001110100101010101011100101101001011011100111010011000000010001010011000111101000000101101111001100001001110100000110011101001100000001010011遗传算法简介遗传算法简介 l简单实例简单实例5.变异变异遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 00011000001110010110110000000110011101001010101010111001011010010110111100000001100111010000010100110001111010000001011011110011000010010101000001100111010011000000010100110001100000111001011011000000011001110100101010101011100101101001011011110000000110011101000001010011000111101000000101101111001100001001110100000110011101001100000001010011遗传算法简介遗传算法简介 l简单实例简单实例6.至下一代，适应度计算至下一代，适应度计算选择选择交叉交叉变异，直变异，直至满足终止条件。至满足终止条件。遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 遗传算法简介遗传算法简介 l函数优化函数优化 是遗传算法的经典应用领域是遗传算法的经典应用领域;l组合优化组合优化 实践证明，遗传算法对于组合优化中的实践证明，遗传算法对于组合优化中的NP完全问完全问题非常有效题非常有效;l自动控制自动控制 如基于遗传算法的模糊控制器优化设计、基于遗传如基于遗传算法的模糊控制器优化设计、基于遗传算法的参数辨识等算法的参数辨识等;5 5 遗传算法的应用遗传算法的应用遗传算法的应用遗传算法的应用 遗传算法简介遗传算法简介 l机器人智能控制机器人智能控制 遗传算法已经在移动机器人路径规划、关节机器人遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行动协调等的结构优化和行动协调等;l组合图像处理和模式识别组合图像处理和模式识别 目前已在图像恢复、图像边缘持征提取、几何形状目前已在图像恢复、图像边缘持征提取、几何形状识别等方面得到了应用识别等方面得到了应用;遗传算法的应用遗传算法的应用遗传算法的应用遗传算法的应用 遗传算法简介遗传算法简介 l人工生命人工生命 基于遗传算法的进化模型是研究人工生命现象的重基于遗传算法的进化模型是研究人工生命现象的重要理论基础，遗传算法已在其进化模型、学习模型、要理论基础，遗传算法已在其进化模型、学习模型、行为模型等方面显示了初步的应用能力；行为模型等方面显示了初步的应用能力；l遗传程序设计遗传程序设计 Koza发展了遗传程序设计的慨念，他使用了以发展了遗传程序设计的慨念，他使用了以LISP语言所表示的编码方法，基于对一种树型结构语言所表示的编码方法，基于对一种树型结构所进行的遗传操作自动生成计算机程序所进行的遗传操作自动生成计算机程序;遗传算法的应用遗传算法的应用遗传算法的应用遗传算法的应用 2 基本遗传算法基本遗传算法 l问题的提出问题的提出 一元函数求最大值：一元函数求最大值：1 1 简单函数优化的实例简单函数优化的实例简单函数优化的实例简单函数优化的实例 基本遗传算法基本遗传算法 l问题的提出问题的提出 用微分法求取用微分法求取f(x)的最大值：的最大值：解有无穷多个：解有无穷多个：简单函数优化的实例简单函数优化的实例简单函数优化的实例简单函数优化的实例 基本遗传算法基本遗传算法 l问题的提出问题的提出 当当i为奇数时为奇数时xi对应局部极大值点，对应局部极大值点，i为偶数时为偶数时xi对应对应局部极小值。局部极小值。x19即为区间即为区间-1,2内的最大值点：内的最大值点：此时，函数最大值此时，函数最大值f(x19)比比f(1.85)=3.85稍大。稍大。简单函数优化的实例简单函数优化的实例简单函数优化的实例简单函数优化的实例 基本遗传算法基本遗传算法 l编码编码 表现型：表现型：x 基因型：二进制编码（串长取决于求解精度）基因型：二进制编码（串长取决于求解精度）串长与精度之间的关系串长与精度之间的关系：若要求求解精度到若要求求解精度到6位小数，区间长度为位小数，区间长度为2-(-1)3，即需将区间分为，即需将区间分为3/0.000001=3106等份。等份。所以编码的二进制串长应为所以编码的二进制串长应为22位。位。简单函数优化的实例简单函数优化的实例简单函数优化的实例简单函数优化的实例 基本遗传算法基本遗传算法 l产生初始种群产生初始种群 产生的方式：随机产生的方式：随机 产生的结果：长度为产生的结果：长度为22的二进制串的二进制串 产生的数量：种群的大小（规模），如产生的数量：种群的大小（规模），如30，50，11111011000 11010101110 10010000100 11100111001 10000000000 简单函数优化的实例简单函数优化的实例简单函数优化的实例简单函数优化的实例 基本遗传算法基本遗传算法 l计算适应度计算适应度 不同的问题有不同的适应度计算方法不同的问题有不同的适应度计算方法 本例：直接用目标函数作为适应度函数本例：直接用目标函数作为适应度函数 将某个体转化为将某个体转化为-1,2区间的实数：区间的实数：s=x=0.637197 计算计算x的函数值（适应度）：的函数值（适应度）：f(x)=xsin(10 x)+2.0=2.586345简单函数优化的实例简单函数优化的实例简单函数优化的实例简单函数优化的实例 基本遗传算法基本遗传算法 l计算适应度（简单函数值替换）计算适应度（简单函数值替换）二进制与十进制之间的转换二进制与十进制之间的转换：第一步，将一个二进制串（第一步，将一个二进制串（b21b20b0）转化为）转化为10进制进制数：数：第二步，第二步，x对应的区间对应的区间-1,2内的实数：内的实数：简单函数优化的实例简单函数优化的实例简单函数优化的实例简单函数优化的实例 )-1(1111111111111111111111)2基本遗传算法基本遗传算法 l遗传操作遗传操作 选择：轮盘赌选择法；选择：轮盘赌选择法；交叉：单点交叉；交叉：单点交叉；变异：小概率变异变异：小概率变异简单函数优化的实例简单函数优化的实例简单函数优化的实例简单函数优化的实例 基本遗传算法基本遗传算法 l模拟结果模拟结果 设置的参数设置的参数：种群大小种群大小50；交叉概率；交叉概率0.75；变异概率；变异概率0.05；最大；最大迭代数迭代数200。得到的最佳个体得到的最佳个体：smax=;xmax=1.8506;f(xmax)=3.8503;简单函数优化的实例简单函数优化的实例简单函数优化的实例简单函数优化的实例 基本遗传算法基本遗传算法 l模拟结果模拟结果 进化的过程进化的过程：简单函数优化的实例简单函数优化的实例简单函数优化的实例简单函数优化的实例 世代数世代数自变量自变量适应度适应度11.44953.449491.83953.7412171.85123.8499301.85053.8503501.85063.8503801.85063.85031201.85063.85032001.85063.8503基本遗传算法基本遗传算法 l编码原则编码原则完备性（完备性（completeness）：问题空间的所有解都）：问题空间的所有解都能表示为所设计的基因型；能表示为所设计的基因型；健全性（健全性（soundness）：任何一个基因型都对应）：任何一个基因型都对应于一个可能解；于一个可能解；非冗余性（非冗余性（non-redundancy）：问题空间和表达空）：问题空间和表达空间一一对应。间一一对应。2 2 遗传基因型遗传基因型遗传基因型遗传基因型 基本遗传算法基本遗传算法 l多种编码方式多种编码方式二进制编码；二进制编码；浮点数编码；浮点数编码；格雷码编码；格雷码编码；符号编码；符号编码；复数编码；复数编码；DNA编码等。编码等。遗传基因型遗传基因型遗传基因型遗传基因型 基本遗传算法基本遗传算法 l二进制编码与浮点数编码的比较二进制编码与浮点数编码的比较在交叉操作时，二进制编码比浮点数编码产生新个在交叉操作时，二进制编码比浮点数编码产生新个体的可能性多，而且产生的新个体不受父个体所构体的可能性多，而且产生的新个体不受父个体所构成的超体的限制；成的超体的限制；在变异操作时，二进制编码的种群稳定性比浮点数在变异操作时，二进制编码的种群稳定性比浮点数编码差。编码差。遗传基因型遗传基因型遗传基因型遗传基因型 基本遗传算法基本遗传算法 l适应度函数的重要性适应度函数的重要性 适应度函数的选取直接影响遗传算法的收敛速度以适应度函数的选取直接影响遗传算法的收敛速度以及能否找到最优解。及能否找到最优解。一般而言，适应度函数是由目标函数变换而成的，一般而言，适应度函数是由目标函数变换而成的，对目标函数值域的某种映射变换称为适应度的对目标函数值域的某种映射变换称为适应度的尺度尺度变换变换（fitness scaling）。）。3 3 适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换 基本遗传算法基本遗传算法 l几种常见的适应度函数几种常见的适应度函数直接转换直接转换 若目标函数为最大化问题：若目标函数为最大化问题：Fit(f(x)=f(x)若目标函数为最小化问题：若目标函数为最小化问题：Fit(f(x)=-f(x)适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换 基本遗传算法基本遗传算法 l几种常见的适应度函数几种常见的适应度函数界限构造法界限构造法1 若目标函数为最大化问题：若目标函数为最大化问题：若目标函数为最小化问题：若目标函数为最小化问题：适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换 基本遗传算法基本遗传算法 l几种常见的适应度函数几种常见的适应度函数界限构造法界限构造法2 若目标函数为最大化问题：若目标函数为最大化问题：若目标函数为最小化问题：若目标函数为最小化问题：c为目标函数的保守估计值。为目标函数的保守估计值。适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换 基本遗传算法基本遗传算法 l适应度函数的作用适应度函数的作用 适应度函数设计不当有可能出现欺骗问题：适应度函数设计不当有可能出现欺骗问题：（1）进化初期，个别超常个体控制选择过程；）进化初期，个别超常个体控制选择过程；（2）进化末期，个体差异太小导致进化缓慢。）进化末期，个体差异太小导致进化缓慢。适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换 基本遗传算法基本遗传算法 l适应度函数的设计适应度函数的设计单值、连续、非负、最大化单值、连续、非负、最大化合理、一致性合理、一致性计算量小计算量小通用性强通用性强适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换 基本遗传算法基本遗传算法 l适应度函数的线性变换法适应度函数的线性变换法 f=*f+系数的确定满足以下条件：系数的确定满足以下条件：favg=favg fmax=cmult favg cmult=1.02.0适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换 基本遗传算法基本遗传算法 l适应度函数的幂函数变换法适应度函数的幂函数变换法 f=f k k与所求优化相关与所求优化相关适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换 k基本遗传算法基本遗传算法 l适应度函数的指数变换法适应度函数的指数变换法 f=e-af a决定了复制的强制性，其值越小，复制的强制性决定了复制的强制性，其值越小，复制的强制性就越趋向于那些具有最大适应性的个体。就越趋向于那些具有最大适应性的个体。适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换 基本遗传算法基本遗传算法 l几个概念几个概念选择压力（选择压力（selection pressure）:最佳个体选中的最佳个体选中的概率与平均个体选中概率的比值；概率与平均个体选中概率的比值；偏差（偏差（bias）：个体正规化适应度与其期望再生概）：个体正规化适应度与其期望再生概率的绝对差值；率的绝对差值；个体扩展（个体扩展（spread）：单个个体子代个数的范围；）：单个个体子代个数的范围；多样化损失（多样化损失（loss of diversity）：在选择阶段未选）：在选择阶段未选中个体数目占种群的比例；中个体数目占种群的比例；4 4 遗传操作遗传操作遗传操作遗传操作选择选择选择选择 基本遗传算法基本遗传算法 l几个概念几个概念选择强度（选择强度（selection intensity）:将正规高斯分布应用于选择方法，将正规高斯分布应用于选择方法，期望平均适应度；期望平均适应度；选择方差（选择方差（selection variance）：）：将正规高斯分布应用于选择方法，将正规高斯分布应用于选择方法，期望种群适应度的方差。期望种群适应度的方差。遗传操作遗传操作遗传操作遗传操作选择选择选择选择 基本遗传算法基本遗传算法 l个体选择概率的常用分配方法个体选择概率的常用分配方法按比例的适应度分配（按比例的适应度分配（proportional fitness assignment）某个体某个体i，其适应度为，其适应度为fi，则其被选取的概率，则其被选取的概率Pi为：为：遗传操作遗传操作遗传操作遗传操作选择选择选择选择 个体个体ff2P12.56.250.1821.01.000.0333.09.000.2641.21.440.0452.14.410.1360.80.640.0272.56.250.1881.31.690.0590.90.810.02101.83.240.09基本遗传算法基本遗传算法 l个体选择概率的常用分配方法个体选择概率的常用分配方法基于排序的适应度分配（基于排序的适应度分配（rank-based fitness assignment）线性排序（线性排序（by Baker）为种群大小，为种群大小，i为个体序号，为个体序号，max代表选择压力。代表选择压力。遗传操作遗传操作遗传操作遗传操作选择选择选择选择 基本遗传算法基本遗传算法 l个体选择概率的常用分配方法个体选择概率的常用分配方法基于排序的适应度分配（基于排序的适应度分配（rank-based fitness assignment）非线性排序（非线性排序（by Michalewicz）i为个体序号，为个体序号，c为排序第一的个体的选择概率。为排序第一的个体的选择概率。遗传操作遗传操作遗传操作遗传操作选择选择选择选择 基本遗传算法基本遗传算法 l常用选择方法常用选择方法轮盘赌选择法（轮盘赌选择法（roulette wheel selection）遗传操作遗传操作遗传操作遗传操作选择选择选择选择 个体个体1234567891011适应度适应度2.01.81.61.41.21.00.80.60.40.20.1选择概率选择概率0.180.160.150.130.110.090.070.060.030.020.0累计概率累计概率0.180.340.490.620.730.820.890.950.981.001.00基本遗传算法基本遗传算法 l常用选择方法常用选择方法随机遍历抽样法（随机遍历抽样法（stochastic universal sampling）遗传操作遗传操作遗传操作遗传操作选择选择选择选择 个体个体1234567891011适应度适应度2.01.81.61.41.21.00.80.60.40.20.1选择概率选择概率0.180.160.150.130.110.090.070.060.030.020.0累计概率累计概率0.180.340.490.620.730.820.890.950.981.001.00设定n为需要选择的个体数目，等距离选择个体，选择指针的距离为1n。第一个指针的位置由0，ln区间的均匀随机数决定。如图所示，需要选择6个个体，指针间的距离为l6o.167，第一个指针的随机位置为0.1，按这种选择方法被选中作为交配集个体为：12，34，6，8。基本遗传算法基本遗传算法 l常用选择方法常用选择方法局部选择法（局部选择法（local selection）(1)线形邻集线形邻集遗传操作遗传操作遗传操作遗传操作选择选择选择选择 在在局局部部选选择择法法中中，每每个个个个体体处处于于一一个个约约束束环环境境中中，称称为为局局部部邻邻域域(而而其其他他选选择择方方法法中中视视整整个个种种群群为为个个体体之之邻邻域域)，个个体体仅仅与与其其邻邻近近个个体体产产生生交交互互，该该邻邻域域的的定定义义由由种种群群的的分分布布结结构构给给出出。邻域可被当作潜在的交配伙伴。邻域可被当作潜在的交配伙伴。首首先先均均匀匀随随机机地地选选择择一一半半交交配配种种群群，选选择择方方法法可可以以是是随随机机遍遍历历方方法法也也可可以以是是截截断断选选择择方方法法，然然后后对对每每个个被被选选个个体体定定义义其其局局部部邻邻域域，在在邻邻域域内内部部选选择择交交配配伙伴。伙伴。基本遗传算法基本遗传算法 l常用选择方法常用选择方法局部选择法（局部选择法（local selection）(2)两对角邻集两对角邻集遗传操作遗传操作遗传操作遗传操作选择选择选择选择 基本遗传算法基本遗传算法 l常用选择方法常用选择方法局部选择法（局部选择法（local selection）(2)两对角邻集两对角邻集遗传操作遗传操作遗传操作遗传操作选择选择选择选择 基本遗传算法基本遗传算法 l常用选择方法常用选择方法截断选择法（截断选择法（truncation selection）个体按适应度排列，只有优秀个体能够成为父个体，个体按适应度排列，只有优秀个体能够成为父个体，参数为截断阀值（被选作父个体的百分比）。参数为截断阀值（被选作父个体的百分比）。遗传操作遗传操作遗传操作遗传操作选择选择选择选择 截断阀值截断阀值11020405080选择强度选择强度2.661.761.20.970.80.34基本遗传算法基本遗传算法 l常用选择方法常用选择方法锦标赛选择法（锦标赛选择法（tournament selection）随机从种群中挑选一定数目个体，其中最好的个体随机从种群中挑选一定数目个体，其中最好的个体作为父个体，此过程重复进行完成个体的选择。作为父个体，此过程重复进行完成个体的选择。遗传操作遗传操作遗传操作遗传操作选择选择选择选择 竞赛规模竞赛规模12351030选择强度选择强度00.560.851.151.532.04基本遗传算法基本遗传算法 l实值重组实值重组离散重组离散重组 子个体的每个变量可以按等概率随机地挑选父个体。子个体的每个变量可以按等概率随机地挑选父个体。5 5 遗传操作遗传操作遗传操作遗传操作交叉交叉交叉交叉/基因重组基因重组基因重组基因重组 父个体父个体1 12 25 5父个体父个体2 123 4 34子个体子个体1 123 4 5子个体子个体2 12 4 34基本遗传算法基本遗传算法 l实值重组实值重组中间重组中间重组 子个体父个体子个体父个体1（父个体（父个体2父个体父个体1）是比例因子，由是比例因子，由-d,1+d上均匀分布地随机数产生。上均匀分布地随机数产生。一般取一般取d=0.25。子代的每个变量均产生一个子代的每个变量均产生一个。遗传操作遗传操作遗传操作遗传操作交叉交叉交叉交叉/基因重组基因重组基因重组基因重组 基本遗传算法基本遗传算法 l实值重组实值重组中间重组示例中间重组示例 遗传操作遗传操作遗传操作遗传操作交叉交叉交叉交叉/基因重组基因重组基因重组基因重组 父个体父个体1 12 25 5父个体父个体2 123 4 34子个体子个体1子个体子个体2值样本值样本1 0.5 1.1 -0.1值样本值样本2 0.1 0.8 0.5120.5（12312）=67.567.5251.1（425）=1.91.92.1120.1（12312）=23.123.18.219.5基本遗传算法基本遗传算法 l实值重组实值重组中间重组中间重组 遗传操作遗传操作遗传操作遗传操作交叉交叉交叉交叉/基因重组基因重组基因重组基因重组 基本遗传算法基本遗传算法 l实值重组实值重组线性重组线性重组 遗传操作遗传操作遗传操作遗传操作交叉交叉交叉交叉/基因重组基因重组基因重组基因重组 父个体父个体1 12 25 5父个体父个体2 123 4 34子个体子个体1子个体子个体2值样本值样本1 0.5值样本值样本2 0.1120.5（12312）=67.567.5250.5（425）=14.514.519.5120.1（12312）=23.123.122.97.9基本遗传算法基本遗传算法 l实值重组实值重组线性重组线性重组 遗传操作遗传操作遗传操作遗传操作交叉交叉交叉交叉/基因重组基因重组基因重组基因重组 基本遗传算法基本遗传算法 l二进制交叉二进制交叉单点交叉单点交叉 遗传操作遗传操作遗传操作遗传操作交叉交叉交叉交叉/基因重组基因重组基因重组基因重组 基本遗传算法基本遗传算法 l二进制交叉二进制交叉多点交叉多点交叉 遗传操作遗传操作遗传操作遗传操作交叉交叉交叉交叉/基因重组基因重组基因重组基因重组 基本遗传算法基本遗传算法 l实值变异实值变异 一般采用：一般采用：l二进制变异二进制变异 6 6 遗传操作遗传操作遗传操作遗传操作变异变异变异变异 4.2 基本遗传算法基本遗传算法 l运行程序运行程序 4 4.2.7 .2.7 算法的设计与实现算法的设计与实现算法的设计与实现算法的设计与实现 基本遗传算法基本遗传算法 l运行程序运行程序 算法的设计与实现算法的设计与实现算法的设计与实现算法的设计与实现 4.2 基本遗传算法基本遗传算法 l运行程序运行程序 4 4.2.7 .2.7 算法的设计与实现算法的设计与实现算法的设计与实现算法的设计与实现 4.2 基本遗传算法基本遗传算法 l运行程序运行程序 4 4.2.7 .2.7 算法的设计与实现算法的设计与实现算法的设计与实现算法的设计与实现 3 遗传算法的改进遗传算法的改进 l改进的途径改进的途径改变遗传算法的组成成分；改变遗传算法的组成成分；采用混合遗传算法；采用混合遗传算法；采用动态自适应技术；采用动态自适应技术；采用非标准的遗传操作算子；采用非标准的遗传操作算子；采用并行遗传算法等。采用并行遗传算法等。遗传算法的改进遗传算法的改进 l改进思路改进思路1991年年Eshelman提出的一种改进遗传算法；提出的一种改进遗传算法；C：跨代精英选择（：跨代精英选择（Cross generational elitist selection）策略；）策略；H：异物种重组（：异物种重组（Heterogeneous recombination）；）；C：大变异（：大变异（Cataclysmic mutation）。）。1.CHC1.CHC算法算法算法算法 遗传算法的改进遗传算法的改进 l选择选择上一代种群与通过新的交叉方法产生的个体群混合上一代种群与通过新的交叉方法产生的个体群混合起来，从中按一定概率选择较优的个体；起来，从中按一定概率选择较优的个体；即使交叉操作产生较劣个体偏多，由于原种群大多即使交叉操作产生较劣个体偏多，由于原种群大多数个体残留，不会引起个体的评价值降低；数个体残留，不会引起个体的评价值降低；可以更好地保持遗传多样性；可以更好地保持遗传多样性；排序方法，克服比例适应度计算的尺度问题。排序方法，克服比例适应度计算的尺度问题。CHCCHC算法算法算法算法 遗传算法的改进遗传算法的改进 l交叉交叉均匀交叉的改进：当两个父个体位值相异的位数为均匀交叉的改进：当两个父个体位值相异的位数为m时，从中随机选取时，从中随机选取m/2个位置，实行父个体位值的个位置，实行父个体位值的交换；交换；显然，这样的操作对模式具有很强的破坏性。显然，这样的操作对模式具有很强的破坏性。确定一阈值，当个体间距离低于该阈值时，不进行确定一阈值，当个体间距离低于该阈值时，不进行交叉操作。进化收敛的同时，逐渐地减小该阈值。交叉操作。进化收敛的同时，逐渐地减小该阈值。CHCCHC算法算法算法算法 遗传算法的改进遗传算法的改进 l变异变异在进化前期不采取变异操作，当种群进化到一定收在进化前期不采取变异操作，当种群进化到一定收敛时期，从最优个体中选择一部分个体进行初始化；敛时期，从最优个体中选择一部分个体进行初始化；初始化：选择一定比例（扩散率，一般初始化：选择一定比例（扩散率，一般0.35）的基）的基因座，随机地决定它们的位值。因座，随机地决定它们的位值。CHCCHC算法算法算法算法 遗传算法的改进遗传算法的改进 l参数分析参数分析交叉概率交叉概率Pc和变异概率和变异概率Pm的选择是影响遗传算法行的选择是影响遗传算法行为和性能的关键，直接影响算法的收敛性；为和性能的关键，直接影响算法的收敛性；Pc越大，新个体产生的速度就越快，但过大会使优越大，新个体产生的速度就越快，但过大会使优秀个体的结构很快被破坏；秀个体的结构很快被破坏；Pc过小，搜索过程缓慢，过小，搜索过程缓慢，以至停止不前；以至停止不前；Pm过小，不易产生新个体结构，过小，不易产生新个体结构，Pm过大，变成纯过大，变成纯粹的随机搜索；粹的随机搜索；2 2 自适应遗传算法自适应遗传算法自适应遗传算法自适应遗传算法 遗传算法的改进遗传算法的改进 l自适应策略自适应策略Srinvivas等提出一种自适应遗传算法，等提出一种自适应遗传算法，Pc和和Pm能够能够随适应度自动改变：随适应度自动改变：当种群各个体适应度趋于一致或趋于局部最优时，当种群各个体适应度趋于一致或趋于局部最优时，使使Pc和和Pm增加；而当群体适应度比较分散时，使增加；而当群体适应度比较分散时，使Pc和和Pm减少；减少；对于适应度较高的个体，对应于较低的对于适应度较高的个体，对应于较低的Pc和和Pm；而较低适应度的个体，对应于较高的而较低适应度的个体，对应于较高的Pc和和Pm。自适应遗传算法自适应遗传算法自适应遗传算法自适应遗传算法 遗传算法的改进遗传算法的改进 l自适应方法自适应方法 fmax群体中最大的适应度值；群体中最大的适应度值；favg每代群体的平均适应度值；每代群体的平均适应度值；f要交叉的两个个体中较大的适应度值；要交叉的两个个体中较大的适应度值；f要交叉或变异的个体适应度值；要交叉或变异的个体适应度值；自适应遗传算法自适应遗传算法自适应遗传算法自适应遗传算法 k1、k2、k3、k4取取(0,1)的值的值遗传算法的改进遗传算法的改进 l自适应方法进一步改进自适应方法进一步改进适用于进化后期，不适于进化前期，因为前期的优适用于进化后期，不适于进化前期，因为前期的优秀个体有可能是局部最优点；秀个体有可能是局部最优点；使最大适应度个体的交叉概率和变异概率由使最大适应度个体的交叉概率和变异概率由0提高提高到到Pc2和和Pm2；采用精英选择策略；采用精英选择策略；自适应遗传算法自适应遗传算法自适应遗传算法自适应遗传算法 遗传算法的改进遗传算法的改进 l自适应方法进一步改进自适应方法进一步改进自适应遗传算法自适应遗传算法自适应遗传算法自适应遗传算法 遗传算法的改进遗传算法的改进 l小生境概念小生境概念l小生境（小生境（niche）：生物学中，特定环境中的一种组）：生物学中，特定环境中的一种组织功能；在自然界中，往往特征、性状相似的物种相织功能；在自然界中，往往特征、性状相似的物种相聚在一起，并在同类中交配繁衍后代。聚在一起，并在同类中交配繁衍后代。在在SGA中，容易中，容易“近亲繁殖近亲繁殖”；NGA（Niche Generic Algorithm），将每一代个体划），将每一代个体划分为若干类，每类选出优秀个体组成一个种群；分为若干类，每类选出优秀个体组成一个种群；优势：保持解的多样性，提高全局搜索能力，适合复优势：保持解的多样性，提高全局搜索能力，适合复杂多峰函数的优化。杂多峰函数的优化。3 3 基于小生境技术的遗传算法基于小生境技术的遗传算法基于小生境技术的遗传算法基于小生境技术的遗传算法 遗传算法的改进遗传算法的改进 l选择策略选择策略预选择机制、排挤机制、分享机制；预选择机制、排挤机制、分享机制；l预选择（预选择（preselection,1970）机制）机制当子个体的适应度超过其父个体适应度时，子个体当子个体的适应度超过其父个体适应度时，子个体才可以替代父个体，否则父个体仍保留；才可以替代父个体，否则父个体仍保留；有效维持种群多样性，造就小生境进化环境。有效维持种群多样性，造就小生境进化环境。基于小生境技术的遗传算法基于小生境技术的遗传算法基于小生境技术的遗传算法基于小生境技术的遗传算法 遗传算法的改进遗传算法的改进 l排挤（排挤（crowding,1975）机制）机制设置排挤因子设置排挤因子CF（CF=2或或3）