遗传算法原理及其应用.ppt

智能优化算法课程智能优化算法课程-2009级硕士级硕士中山大学智能交通研究中心中山大学智能交通研究中心20102010年年4 4月月遗传算法原理及其应用遗传算法原理及其应用 12/18/20221.遗传算法概述遗传算法概述2.基本遗传算法基本遗传算法(SGA)目目 录录l1.1 遗传算法的产生与发展遗传算法的产生与发展l1.2 遗传算法的生理学基础遗传算法的生理学基础 l1.3 遗传算法的原理与特点遗传算法的原理与特点l1.4 遗传算法的基本操作遗传算法的基本操作l1.5 遗传算法的应用遗传算法的应用 l 2.1 基本遗传算法描述基本遗传算法描述l 2.2 基本遗传算法实现基本遗传算法实现l 2.3 基本遗传算法流程基本遗传算法流程l 2.4 简单函数优化的实例简单函数优化的实例23.遗传算法的改进遗传算法的改进4.遗传算法的应用遗传算法的应用目目 录录l 3.1 自适应遗传算法自适应遗传算法l 3.2 CHC算法算法 l 3.3 基于小生境技术的遗传算法基于小生境技术的遗传算法l 3.4 退火进化算法退火进化算法l 4.1 解决带约束的函数优化问题解决带约束的函数优化问题l 4.2 解决多目标优化问题解决多目标优化问题l 4.3 解决组合优化问题解决组合优化问题l 4.4 遗传算法在过程建模中的应用遗传算法在过程建模中的应用l 4.5 遗传算法在模式识别中的应用遗传算法在模式识别中的应用31.1 遗传算法的产生与发展遗传算法的产生与发展v产生产生早在50年代，一些生物学家开始研究运用数字计算机模拟生物的自然遗传与自然进化过程；1963年，德国柏林技术大学的I.Rechenberg和H.P.Schwefel，做风洞实验时，产生了进化策略的初步思想；60年代，L.J.Fogel在设计有限态自动机时提出进化规划的思想。1966年Fogel等出版了基于模拟进化的人工智能，系统阐述了进化规划的思想。60年代中期，美国Michigan大学的J.H.Holland教授提出借鉴生物自然遗传的基本原理用于自然 和人工系统的自适应行为研究和串编码技术；1967年，他的学生J.D.Bagley在博士论文中首次提出“遗传算法(Genetic Algorithms)”一词；1975年，Holland出版了著名的“Adaptation in Natural and Artificial Systems”，标志遗传算法的诞生。41.1 遗传算法的产生与发展遗传算法的产生与发展v发展发展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编辑出版了遗传算法手册，其中包括了遗传算法在工程技术和社会生活中大量的应用实例。遗传算法遗传算法进化计算进化计算计算智能计算智能人工智能人工智能51.2 遗传学基本概念与术语遗传学基本概念与术语v染色体（chromosome）：遗传物质的载体；脱氧核糖核酸（DNA）：大分子有机聚合物，双螺旋结构；RNAv遗传因子（gene）：DNA或RNA长链结构中占有一定位置的基本遗传单位；v基因型（genotype）：遗传因子组合的模型；v表现型（phenotype）：由染色体决定性状的外部表现；v个体（individual）：指染色体带有特征的实体；v种群（population）：个体的集合，该集合内个体数称为种群的大小；1 1 1 1 1 1 1 1 1 1 0 1 1 1 6v进化（evolution）：生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化；v适应度（fitness）：度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝;v选择（selection）：指决定以一定的概率从种群中选择若干个体的操作（实现优胜劣汰）；v复制（reproduction）：细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因;7v交叉（crossover）：在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合形成两个新的染色体。又称基因重组，俗称“杂交”;v变异（mutation）：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状;v编码（coding）：表现型到基因型的映射；v解码（decoding）：从基因型到表现型的映射。大象灰颜色皮肤为例1 1 1 1 1 1 1 编码编码解码解码81.3 遗传算法的原理与特点遗传算法的原理与特点 v原理原理遗传算法(GA)是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索自适应全局优化概率搜索方法。其采纳了自然进化模型自然进化模型，从代表问题可能潜在解集的一个种群种群开始，种群由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体；初始种群产生后，按照适者生存和优胜劣汰适者生存和优胜劣汰的原理，逐代演化产生出越来越好的解：n在每一代，概据问题域中个体的适应度大小挑选个体；n并借助遗传算子进行组合交叉和主客观变异，产生出代表新的解集的种群。n这一过程循环执行，直到满足优化准则为止。最后，末代个体经解码，生成近似最优解。基于种群进化机制的遗传算法如同自然界进化一样，后生代种群比前生代更加适应于环境，通过逐代进化，逼近最优解。91.3 遗传算法的原理与特点遗传算法的原理与特点v遗传算法的基本流程遗传算法的基本流程Fig.2逼近最优解的过程逼近最优解的过程Fig.1 遗传算法的基本流程遗传算法的基本流程算法结束算法结束?101.3 遗传算法的原理与特点遗传算法的原理与特点v特点遗传算法的本质并行性本质并行性。n首先，遗传算法并行的方式从问题解的串集开始嫂索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。n其次，算法内含并行性，遗传算法采用种群方式组织搜索，因而可同时搜索妥空间的多个区域(n-n3)，并相互交流信息，能以较小的计算获得较大的收益。遗传算法基本上不用搜索空间的知识或其它辅助信息不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。遗传算法不是采用确定性规则不是采用确定性规则，而是采用概率的变迁规则来指导他的搜索方向。具有自组织、自适应和自学习性自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜索时，硬度大的个体具有较高的生存概率，并获得更适应环境的基因结构。遗传算法可更直接的应用直接的应用，对给定的问题，可以产生许多潜在解，最终选择可以由使用者指定，通用性高，应用范围广。111.4 遗传算法的基本操作遗传算法的基本操作v遗传基因型遗传基因型(编码编码)编码方式n二进制编码二进制编码、浮点数编码浮点数编码、格雷码编码、符号编码、复数编码、DNA编码等。n以大象灰色皮肤为例：二进制编码：1111111，浮点编码：127.0编码原则编码原则完备性（完备性（completeness）：问题空间的所有解都能表示为所设计的基因型；）：问题空间的所有解都能表示为所设计的基因型；健全性（健全性（soundness）：任何一个基因型都对应于一个可能解；）：任何一个基因型都对应于一个可能解；非冗余性（非冗余性（non-redundancy）：问题空间和表达空间一一对应。）：问题空间和表达空间一一对应。二进制编码与浮点数编码的比较二进制编码与浮点数编码的比较在交叉操作时，二进制编码比浮点数编码产生新个体的可能性多，而且产生在交叉操作时，二进制编码比浮点数编码产生新个体的可能性多，而且产生的新个体不受父个体所构成的超体的限制；的新个体不受父个体所构成的超体的限制；在变异操作时，二进制编码的种群稳定性比浮点数编码差。在变异操作时，二进制编码的种群稳定性比浮点数编码差。121.4 遗传算法的基本操作遗传算法的基本操作v选择适应度计算适应度计算：按比例的适应度函数（按比例的适应度函数（proportional fitness assignment）基于排序的适应度计算（基于排序的适应度计算（Rank-based fitness assignment）选择算法选择算法：轮盘赌选择（轮盘赌选择（roulette wheel selection）随机遍历抽样（随机遍历抽样（stochastic universal selection）局部选择（局部选择（local selection）截断选择（截断选择（truncation selection）锦标赛选择（锦标赛选择（tournament selection）13v交叉或基因重组交叉或基因重组二进制交叉（二进制交叉（binary valued crossover）：单点交叉（单点交叉（single-point crossover）多点交叉（多点交叉（multiple-point crossover）均匀交叉（均匀交叉（uniform crossover）洗牌交叉（洗牌交叉（shuffle crossover）缩小代理交叉（缩小代理交叉（crossover with reduced surrogate）实值重组（实值重组（real valued recombination）：离散重组（离散重组（discrete recombination）中间重组（中间重组（intermediate recombination）线性重组（线性重组（linear recombination）（均匀、非均匀）（均匀、非均匀）扩展线性重组（扩展线性重组（extended linear recombination14v 交叉方式半种群交叉(N/2)n对群体中的要交叉的个体进行两两随机配对。若群体大小为M，则最多共有 M/2 对相互配对的个体组参与交叉。(若种群数为奇数，则其中任一个个体多选一次配对)2)全种群交叉(N)n对群体中要交叉的个体，从种群中随机挑选一个个体与其完成交叉操作，最多共有M对相互配对的个体参与变异。15v变异方法变异方法 二进制变异二进制变异n单点变异单点变异 n逆序变异逆序变异n均匀变异均匀变异实值变异实值变异n随机变异随机变异n边界变异边界变异n非一致变异非一致变异n自适应变异自适应变异n高斯变异高斯变异16v变异方式基于个体的变异n即对任意一个个体，判断其是否进行变异操作，如果是，则随机生成一变异基因发生变异操作。基于基因座的变异n即对种群中的个体，判断每一个个体的每一位基因是否进行变异操作，如果是，则发生变异操作。171.5 遗传算法的应用遗传算法的应用v函数优化函数优化 是遗传算法的经典应用领域是遗传算法的经典应用领域;v组合优化组合优化 实践证明，遗传算法对于组合优化中的实践证明，遗传算法对于组合优化中的NP完全问题非常有效完全问题非常有效;v自动控制自动控制 如基于遗传算法的模糊控制器优化设计、基于遗传算法的参数辨识、利用遗如基于遗传算法的模糊控制器优化设计、基于遗传算法的参数辨识、利用遗传算法进行人工神经网络的结构优化设计和权值学习等传算法进行人工神经网络的结构优化设计和权值学习等;v机器人智能控制机器人智能控制 遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行动协调等运动学求解、细胞机器人的结构优化和行动协调等;v组合图像处理和模式识别组合图像处理和模式识别 目前已在图像恢复、图像边缘持征提取、几何形状识别等方面得到了应用目前已在图像恢复、图像边缘持征提取、几何形状识别等方面得到了应用;18v人工生命人工生命 基于遗传算法的进化模型是研究人工生命现象的重要理论基础，遗传算法已基于遗传算法的进化模型是研究人工生命现象的重要理论基础，遗传算法已在其进化模型、学习模型、行为模型等方面显示了初步的应用能力；在其进化模型、学习模型、行为模型等方面显示了初步的应用能力；v遗传程序设计遗传程序设计 Koza发展了遗传程序设计的慨念，他使用了以发展了遗传程序设计的慨念，他使用了以LISP语言所表示的编码方法，语言所表示的编码方法，基于对一种树型结构所进行的遗传操作自动生成计算机程序基于对一种树型结构所进行的遗传操作自动生成计算机程序;v机器学习机器学习机器学习学习能力是高级自适应系统所应具备的能力之一。基于遗传算法的机器学习学习能力是高级自适应系统所应具备的能力之一。基于遗传算法的机器学习，特别是分类器系统，在很多领域中都得到了应用。例如，遗传算机器学习，特别是分类器系统，在很多领域中都得到了应用。例如，遗传算法被用于学习模糊控制规则，利用遗传算法来学习隶属度函数，从而更好地法被用于学习模糊控制规则，利用遗传算法来学习隶属度函数，从而更好地改进了模糊系统改进了模糊系统 的性能；基于遗传算法的机器学习可用来调整人工神经网络的性能；基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可用于人工神经网络的网络结构优化设计；分类器系统也在学的连接权，也可用于人工神经网络的网络结构优化设计；分类器系统也在学习式多机器人路径规习式多机器人路径规 划系统中得到了成功的应用。划系统中得到了成功的应用。192 基本遗传算法基本遗传算法v遗传算法在自然与社会现象的模拟、工程计算等方面得到了广泛的应用。v在各个不同的应用领域，为了取得更好的结果，人们对GA进行了大量的改进。v为不至于混淆，把Holland提出的算法称为基本遗传算法，简称为SGA（Simple Genetic Algorithm)，也有称其为(GA、CGA)。v以SGA为例，阐述遗传算法的设计与实现方法。202.1 基本遗传算法描述基本遗传算法描述2.1.1 SGA的构成要素(1)(1)染色体编码方法染色体编码方法染色体编码方法染色体编码方法 基本遗传算法使用基本遗传算法使用固定长度的二进制符号串固定长度的二进制符号串固定长度的二进制符号串固定长度的二进制符号串来表示群体中的个体，其等位来表示群体中的个体，其等位基因由二值符号集基因由二值符号集0，1组成。组成。初始群体中各个个体的基因值用均匀分布的随机数来生成。如：初始群体中各个个体的基因值用均匀分布的随机数来生成。如：x：就可表示一个个体，该个体的染色体长度是就可表示一个个体，该个体的染色体长度是 l18。(2)个体适应度评价个体适应度评价 基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。传到下一代群体中的机会多少。为正确计算这个概率，这里要求所有个体的适应度必须为正数或零。这样，为正确计算这个概率，这里要求所有个体的适应度必须为正数或零。这样，根据不同种类的问题，必须预先确定好由目标函数根据不同种类的问题，必须预先确定好由目标函数 值到个体适应度之间的转值到个体适应度之间的转换规则，特别是要预先确定好当目标函数值为负数时的处理方法。换规则，特别是要预先确定好当目标函数值为负数时的处理方法。21(3)(3)遗传算子遗传算子遗传算子遗传算子 基本遗传算法使用下述三种遗传算子：基本遗传算法使用下述三种遗传算子：选择运算：使用选择运算：使用比例选择算子比例选择算子比例选择算子比例选择算子；交叉运算：使用交叉运算：使用单点交叉算子单点交叉算子单点交叉算子单点交叉算子；变异运算：使用变异运算：使用基本位变异算子基本位变异算子基本位变异算子基本位变异算子。(4)(4)基本遗传算法的运行参数基本遗传算法的运行参数基本遗传算法的运行参数基本遗传算法的运行参数 基本遗传算法有下述基本遗传算法有下述4个运行参数需要提前设定：个运行参数需要提前设定：MM：群体大小，即群体中所含个体的数量，一般取为：群体大小，即群体中所含个体的数量，一般取为20 100。T T：遗传运算的终止进化代数，一般取为：遗传运算的终止进化代数，一般取为100 500 p pc c：交叉概率，一般取为：交叉概率，一般取为0.4 0.99 p pmm：变异概率，一般取为：变异概率，一般取为 0.0001 0.1*这这4个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目前个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目前 尚无合理选择它们的理论依据。在遗传算法的实际应用中，往往需要经过多次试尚无合理选择它们的理论依据。在遗传算法的实际应用中，往往需要经过多次试 算后才能确定出这些参数合理的取值大小或取值范围。算后才能确定出这些参数合理的取值大小或取值范围。222.1.2 2.1.2 基本遗传算法的描述基本遗传算法的描述基本遗传算法的描述基本遗传算法的描述 基本遗传算法可定义为一个基本遗传算法可定义为一个7元组：元组：GAGA (M,F,s,c,m,p (M,F,s,c,m,pc c,p,pmm)M群体大小；群体大小；F个体适应度评价函数；个体适应度评价函数；s选择操作算于；选择操作算于；c交叉操作算子：交叉操作算子：m变异操作算于；变异操作算于；pc交叉概率；交叉概率；pm变异概率；变异概率；232.2 基本遗传算法的实现基本遗传算法的实现2.2.1 2.2.1 编码与解码编码与解码编码与解码编码与解码 (1)(1)编码编码编码编码 假设某一参数的取值范围是假设某一参数的取值范围是umin,umax，我们用长度为，我们用长度为l的二进制编码符的二进制编码符号串来表示该参数，则它总共能够产生号串来表示该参数，则它总共能够产生 2l种不同的编码，参数编码时的对应种不同的编码，参数编码时的对应关系如下：关系如下：00000000000000000 umin 00000000000000011 umin+1111111111111111=2l1 umax 其中，其中，为二进制编码的编码精度，其公式为：为二进制编码的编码精度，其公式为：=Umax umin2l 1 24 x=umin+(bi 2i-1)1 1i=lUmax umin2l 1 (2)(2)解码解码解码解码 假设某一个体的编码是：假设某一个体的编码是：x：bl l bl l-1 bl l-2b2b1 则对应的解码公式为：则对应的解码公式为：25例例 设设 -3.0 x 12.1 ,精度要求精度要求 =1/10000，由公式：，由公式：Umax umin2l=+11/1000012.1+3.0+1=151001151001 即：即：217 151001 00 if f(X)-Cmin 0F(X)=Cmax-f(X)if f(X)Cmax0 if f(X)Cmax 282.2.3 2.2.3 比例选择算子比例选择算子比例选择算子比例选择算子指个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比。指个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比。pi=fi/fi (i=1,2,M)式中式中 pi个体个体i被选中的概率；被选中的概率；fi个体个体i的适应度；的适应度；fi群体的累加适应度。群体的累加适应度。显然，个体适应度愈高，被选中的概率愈大。但是，适应度小的个体也有可显然，个体适应度愈高，被选中的概率愈大。但是，适应度小的个体也有可 能被选中，以便增加下一代群体的多样性。能被选中，以便增加下一代群体的多样性。执行比例选择的手段是轮盘选择。执行比例选择的手段是轮盘选择。执行比例选择的手段是轮盘选择。执行比例选择的手段是轮盘选择。个体被选中的概率取决于个体的相对适应度：个体被选中的概率取决于个体的相对适应度：从统计意义讲，适应度大的个体，从统计意义讲，适应度大的个体，其刻度长，被选中的可能性大；反之，适应度小的个体被选中的可能性小，但有其刻度长，被选中的可能性大；反之，适应度小的个体被选中的可能性小，但有时也会被时也会被“破格破格”选中。选中。292.2.4 2.2.4 单点交叉算子单点交叉算子单点交叉算子单点交叉算子 .对群体中的个体进行两两对群体中的个体进行两两随机随机配对。配对。若群体大小为若群体大小为M，则共有，则共有 M/2 对相互对相互 配对的个体组。配对的个体组。.每一对相互配对的个体，每一对相互配对的个体，随机随机设置某一基因座之后的位置为交叉点。设置某一基因座之后的位置为交叉点。若染色体的长度为若染色体的长度为l，则共有，则共有(l-1)个可能的交个可能的交叉点位置。叉点位置。.对对每一每一对对相互配相互配对对的个体，依的个体，依设设定的交叉概率定的交叉概率pc在其在其交交叉点叉点处处相互交相互交换换两个个两个个 体的部分染色体，从而体的部分染色体，从而产产生出两个新的个体。生出两个新的个体。单单点交叉运算的示点交叉运算的示例例如下所示如下所示:单点交叉单点交叉A；10110111 00 A：10110111 11B：00011100 11 B：00011100 00 交叉概率交叉概率交叉概率交叉概率 pc=McM 式中式中 M群体中个体的数目；群体中个体的数目；Mc群体中被交换个体的数目。群体中被交换个体的数目。302.2.5 2.2.5 基本位变异算子基本位变异算子基本位变异算子基本位变异算子对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作 的某一基因座上的原有基因值为的某一基因座上的原有基因值为0，则变异操作将该基因值变为，则变异操作将该基因值变为1，反之，若原有，反之，若原有 基因值为基因值为1，则变异操作将其变为，则变异操作将其变为0。基本位变异因子的具体执行过程是：基本位变异因子的具体执行过程是：基本位变异因子的具体执行过程是：基本位变异因子的具体执行过程是：.对个体的每一个基因座，依变异概率对个体的每一个基因座，依变异概率pm指定其为变异点。指定其为变异点。.对每一个指定的变异点，对其基因值做取反运算或用其它等位基因值来代替，对每一个指定的变异点，对其基因值做取反运算或用其它等位基因值来代替，从而产生出一个新的个体。从而产生出一个新的个体。基本位变异运算的示例如下所示：基本位变异运算的示例如下所示：A：1010 1 01010 A：1010 0 01010 变异点变异点基本位变异基本位变异31 变异是针对个体的某一个或某一些基因座上的基因值执行的，因此变异概率变异是针对个体的某一个或某一些基因座上的基因值执行的，因此变异概率pm 也是针对基因而言，即：也是针对基因而言，即：式中式中 B每代中变异的基因数目；每代中变异的基因数目；M每代中群体拥有的个体数目每代中群体拥有的个体数目 l个体中基因串长度。个体中基因串长度。Pm=B M l 变异概率变异概率变异概率变异概率322.3 GA算法流程图算法流程图开始开始Gen=0编码编码随机产生随机产生M个初始个体个初始个体满足终止条件满足终止条件?计算群体中各个体适应度计算群体中各个体适应度从左至右依次执行遗传算子从左至右依次执行遗传算子j=0j=0j=0根据适应度选择复制个体根据适应度选择复制个体选择两个交叉个体选择两个交叉个体选择个体变异点选择个体变异点执行变异执行变异执行交叉执行交叉执行复制执行复制将复制的个体添入将复制的个体添入新群体中新群体中将交叉后的两个新个体将交叉后的两个新个体添入新群体中添入新群体中将变异后的个体添入将变异后的个体添入新群体中新群体中j=j+1j=j+2j=j+1 j=M?j=pcM?j=pmLM?Gen=Gen+1输出结果输出结果终止终止YNYYYNNNpcpm33v问题的提出问题的提出 一元函数求最大值：一元函数求最大值：2.4 简单函数优化实例简单函数优化实例34v编码编码 表现型：表现型：x 基因型：二进制编码（串长取决于求解精度）基因型：二进制编码（串长取决于求解精度）按编码按编码原理：假设原理：假设要求求解精度到要求求解精度到6位小数，区间长度为位小数，区间长度为2-(-1)3，即需将区间分为，即需将区间分为3/0.000001=3106等份。等份。所以编码的二进制串长应为所以编码的二进制串长应为22位。位。35v产生初始种群产生初始种群 产生的方式：随机产生的方式：随机 产生的结果：长度为产生的结果：长度为22的二进制串的二进制串 产生的数量：种群的大小（规模），如产生的数量：种群的大小（规模），如30，50，36v计算适应度计算适应度直接用目标函数作为适应度函数直接用目标函数作为适应度函数 解码：将个体解码：将个体s转化为转化为-1,2区间的实数：区间的实数：s x=0.637197 计算计算x的函数值（适应度）：的函数值（适应度）：f(x)=xsin(10 x)+2.0=2.58634537v遗传操作遗传操作 选择：比例选择法；选择：比例选择法；交叉：单点交叉；交叉：单点交叉；变异：小概率变异变异：小概率变异38v模拟结果模拟结果 设置的参数设置的参数：种群大小种群大小50；交叉概率；交叉概率0.75；变异概率；变异概率0.05；最大代数；最大代数200。得到的最佳个体得到的最佳个体：smax xmax=1.8506;f(xmax)=3.8503;39v模拟结果模拟结果 进化的过程进化的过程：世代数世代数自变量自变量适应度适应度11.44953.449491.83953.7412171.85123.8499301.85053.8503501.85063.8503801.85063.85031201.85063.85032001.85063.8503403 遗传算法的改进遗传算法的改进v传统的GA在解决时就存在如下问题：首先，模型复杂，参数太多难以达到优化目的，优化速度慢且达不到最优解。其次，约束条件复杂、繁多，算法收敛的时候很难满足约束条件。因此，在处理交通控制问题上扬长避短，需要改进遗传算法，使其达到智能控制的效果。v改进措施改变遗传算法的组成成分；改变遗传算法的组成成分；采用混合遗传算法；采用混合遗传算法；采用动态自适应技术；采用动态自适应技术；采用非标准的遗传操作算子；采用非标准的遗传操作算子；采用并行遗传算法等。采用并行遗传算法等。41v参数分析参数分析交叉概率交叉概率Pc和变异概率和变异概率Pm的选择是影响遗传算法行为和性的选择是影响遗传算法行为和性能的关键，直接影响算法的收敛性；能的关键，直接影响算法的收敛性；Pc越大，新个体产生的速度就越快，但过大会使优秀个体的越大，新个体产生的速度就越快，但过大会使优秀个体的结构很快被破坏；结构很快被破坏；Pc过小，搜索过程缓慢，以至停止不前；过小，搜索过程缓慢，以至停止不前；Pm过小，不易产生新个体结构，过小，不易产生新个体结构，Pm过大，变成纯粹的随机过大，变成纯粹的随机搜索；搜索；42v自适应策略自适应策略Srinvivas等提出一种自适应遗传算法，等提出一种自适应遗传算法，Pc和和Pm能够随适应能够随适应度自动改变：度自动改变：当种群各个体适应度趋于一致或趋于局部最优时，使当种群各个体适应度趋于一致或趋于局部最优时，使Pc和和Pm增加；而当群体适应度比较分散时，使增加；而当群体适应度比较分散时，使Pc和和Pm减少；减少；对于适应度较高的个体，对应于较低的对于适应度较高的个体，对应于较低的Pc和和Pm；而较低适；而较低适应度的个体，对应于较高的应度的个体，对应于较高的Pc和和Pm。43v自适应方法自适应方法 fmax群体中最大的适应度值；群体中最大的适应度值；favg每代群体的平均适应度值；每代群体的平均适应度值；f要交叉的两个个体中较大的适应度值；要交叉的两个个体中较大的适应度值；f要交叉或变异的个体适应度值；要交叉或变异的个体适应度值；k1、k2、k3、k4取取(0,1)的值的值44v自适应方法进一步改进自适应方法进一步改进适用于进化后期，不适于进化前期，因为前期的优秀个体适用于进化后期，不适于进化前期，因为前期的优秀个体有可能是局部最优点；有可能是局部最优点；使最大适应度个体的交叉概率和变异概率由使最大适应度个体的交叉概率和变异概率由0提高到提高到Pc2和和Pm2；采用精英选择策略；采用精英选择策略；45v自适应方法进一步改进自适应方法进一步改进46v改进思路改进思路1991年年Eshelman提出的一种改进遗传算法；提出的一种改进遗传算法；C：跨世代精英选择（：跨世代精英选择（Cross generational elitist selection）策）策略；略；H：异物种重组（：异物种重组（Heterogeneous recombination）；）；C：大变异（：大变异（Cataclysmic mutation）。）。4 4.3.1 CHC.3.1 CHC算法算法算法算法 47v选择选择上一代种群与通过新的交叉方法产生的个体群混合起来，上一代种群与通过新的交叉方法产生的个体群混合起来，从中按一定概率选择较优的个体；从中按一定概率选择较优的个体；即使交叉操作产生较劣个体偏多，由于原种群大多数个体即使交叉操作产生较劣个体偏多，由于原种群大多数个体残留，不会引起个体的评价值降低；残留，不会引起个体的评价值降低；可以更好地保持遗传多样性；可以更好地保持遗传多样性；排序方法，克服比例适应度计算的尺度问题。排序方法，克服比例适应度计算的尺度问题。48v交叉交叉均匀交叉的改进：当两个父个体位值相异的位数为均匀交叉的改进：当两个父个体位值相异的位数为m时，从时，从中随机选取中随机选取m/2个位置，实行父个体位值的交换；个位置，实行父个体位值的交换；确定一阈值，当个体间距离低于该阈值时，不进行交叉操确定一阈值，当个体间距离低于该阈值时，不进行交叉操作。进化收敛的同时，逐渐地减小该阈值。作。进化收敛的同时，逐渐地减小该阈值。49v变异变异在进化前期不采取变异操作，当种群进化到一定收敛时期，在进化前期不采取变异操作，当种群进化到一定收敛时期，从最优个体中选择一部分个体进行初始化；从最优个体中选择一部分个体进行初始化；初始化：选择一定比例（扩散率，一般初始化：选择一定比例（扩散率，一般0.35）的基因座，随）的基因座，随机地决定它们的位值。机地决定它们的位值。4 4.3.1 CHC.3.1 CHC算法算法算法算法 50v小生境概念小生境概念小生境（小生境（niche）：生物学中，特定环境中的一种组织功能；）：生物学中，特定环境中的一种组织功能；在在SGA中，容易中，容易“近亲繁殖近亲繁殖”；NGA（Niche Generic Algorithm），将每一代个体划分为若），将每一代个体划分为若干类，每类选出优秀个体组成一个种群；干类，每类选出优秀个体组成一个种群；优势：保持解的多样性，提高全局搜索能力，适合复杂多优势：保持解的多样性，提高全局搜索能力，适合复杂多峰函数的优化。峰函数的优化。4 4.3.3 .3.3 基于小生境技术的遗传算法基于小生境技术的遗传算法基于小生境技术的遗传算法基于小生境技术的遗传算法 51v选择策略选择策略预选择机制、排挤机制、分享机制；预选择机制、排挤机制、分享机制；v预选择（预选择（preselection,1970）机制）机制当子个体的适应度超过其父个体适应度时，子个体才可以当子个体的适应度超过其父个体适应度时，子个体才可以替代父个体，否则父个体仍保留；替代父个体，否则父个体仍保留；有效维持种群多样性，造就小生境进化环境。有效维持种群多样性，造就小生境进化环境。4 4.3.3 .3.3 基于小生境技术的遗传算法基于小生境技术的遗传算法基于小生境技术的遗传算法基于小生境技术的遗传算法 52v排挤（排挤（crowding,1975）机制）机制设置排挤因子设置排挤因子CF（CF=2或或3），随机选取），随机选取1/CF个个体组成个个体组成排挤成员，排挤与其相似（用距离来度量）的个体；排挤成员，排挤与其相似（用距离来度量）的个体；个体之间的相似性可用个体编码串之间的海明距离来度量。个体之间的相似性可用个体编码串之间的海明距离来度量。4 4.3.3 .3.3 基于小生境技术的遗传算法基于小生境技术的遗传算法基于小生境技术的遗传算法基于小生境技术的遗传算法 53v共享（共享（sharing,1987）机制）机制通过个体之间的相似性程度的共享函数来调整各个体的适通过个体之间的相似性程度的共享函数来调整各个体的适应度；应度；共享函数的目的：将搜索空间的多个峰值在地理上区分开共享函数的目的：将搜索空间的多个峰值在地理上区分开来，每一个峰值处接受一定比例数目的个体，比例数目与来，每一个峰值处接受一定比例数目的个体，比例数目与峰值高度有关；峰值高度有关；4 4.3.3 .3.3 基于小生境技术的遗传算法基于小生境技术的遗传算法基于小生境技术的遗传算法基于小生境技术的遗传算法 54v共享（共享（sharing,1987）机制）机制共享函数的值越大，表明个体之间越相似，记为共享函数的值越大，表明个体之间越相似，记为Sh(dij)，dij为两个个体为两个个体i和和j之间的距离；之间的距离；share是是niche的半径，由使用者给定。的半径，由使用者给定。4 4.3.3 .3.3 基于小生境技术的遗传算法基于小生境技术的遗传算法基于小生境技术的遗传算法基于小生境技术的遗传算法 55v共享（共享（sharing,1987）机制）机制共享法将个体的适应度降低，即适应度值共享法将个体的适应度降低，即适应度值fi除以一个除以一个niche计计数数mi：在距离为在距离为share的范围内的个体彼此削减适应度，这些个体的范围内的个体彼此削减适应度，这些个体将收敛在一个将收敛在一个niche内，避免了整个种群的收敛。内，避免了整个种群的收敛。4 4.3.3 .3.3 基于小生境技术的遗传算法基于小生境技术的遗传算法基于小生境技术的遗传算法基于小生境技术的遗传算法 56退火进化算法退火进化算法v退火进化算法(annealing evolution algorithm,AEA）遗传算法（GA)模拟退火算法（SA）是人工智能中用于解决组合优化问题的经典但是，SA 在全局搜索能力方面不足，GA 在局部搜索能力方面不足。而退火进化算法（annealing evolution algorithm,AEA)综合了SA和GA算法，优势互补，发挥SA 局部搜索能力和GA 全局搜索能力,克服SA 全局搜索能力差及效率不高的问题和GA 局部搜索能力差及其早熟现象。AEA把SA算法与GA结合在一起，通过变异与选择不断改善解群体，并行搜索解空间，从而有可能更迅速地找到全局最优解。由于在选择中采用Metropolis准则，因而保留了SA算法易跳出某局部极值“陷阱”的优点，易于向全局极小值快速收敛。算法求解过程如下：(1)初始化进化代数计数器k0，随机给出种群P(k)初值，给定初试退火温度T0。(2)评价当前群体P(k)的适应度。(3)个体交叉操作（附带保优操作）：P(k)CrossoverP(k)。(4)个体变异操作（附带保优操作）：P(k)”MutationP(k)。(5)由SA状态函数产生新个体。(6)个体模拟退火操作(Metropolis准则接受新个体)：P(k)”SAP(k)”。(7)判断SA抽样是否稳定，若