搜索
智能优化算法课程-2009级硕士中山大学智能交通研究中心2010年4月遗传算法原理及其应用21.遗传算法概述2.基本遗传算法(SGA)目录1.1遗传算法的产生与发展1.2遗传算法的生理学基础1.3遗传算法的原理与特点1.4遗传算法的基本操作1.5遗传算法的应用2.1基本遗传算法描述2.2基本遗传算法实现2.3基本遗传算法流程2.4简单函数优化的实例33.遗传算法的改进4.遗传算法的应用目录3.1自适应遗传算法3.2CHC算法3.3基于小生境技术的遗传算法3.4退火进化算法4.1解决带约束的函数优化问题4.2解决多目标优化问题4.3解决组合优化问题4.4遗传算法在过程建模中的应用4.5遗传算法在模式识别中的应用41.1遗传算法的产生与发展产生早在50年代，一些生物学家开始研究运用数字计算机模拟生物的自然遗传与自然进化过程；1963年，德国柏林技术大学的I.Rechenberg和H.P.Schwefel，做风洞实验时，产生了进化策略的初步思想；60年代，L.J.Fogel在设计有限态自动机时提出进化规划的思想。1966年Fogel等出版了《基于模拟进化的人工智能》，系统阐述了进化规划的思想。60年代中期，美国Michigan大学的J.H.Holland教授提出借鉴生物自然遗传的基本原理用于自然和人工系统的自适应行为研究和串编码技术；1967年，他的学生J.D.Bagley在博士论文中首次提出“遗传算法(GeneticAlgorithms)”一词；1975年，Holland出版了著名的“AdaptationinNaturalandArtificialSystems”，标志遗传算法的诞生。51.1遗传算法的产生与发展发展70年代初，Holland提出了“模式定理”（SchemaTheorem），一般认为是“遗传算法的基本定理”，从而奠定了遗传算法研究的理论基础；1985年，在美国召开了第一届遗传算法国际会议，并且成立了国际遗传算法学会(ISGA，InternationalSocietyofGeneticAlgorithms)；1989年，Holland的学生D.J.Goldherg出版了“GeneticAlgorithmsinSearch,Optimization,andMachineLearning”，对遗传算法及其应用作了全面而系统的论述；1991年，L.Davis编辑出版了《遗传算法手册》，其中包括了遗传算法在工程技术和社会生活中大量的应用实例。所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所所遗传算法——进化计算——计算智能——人工智能61.2遗传学基本概念与术语染色体（chromosome）：遗传物质的载体；脱氧核糖核酸（DNA）：大分子有机聚合物，双螺旋结构；RNA遗传因子（gene）：DNA或RNA长链结构中占有一定位置的基本遗传单位；基因型（genotype）：遗传因子组合的模型；表现型（phenotype）：由染色体决定性状的外部表现；个体（individual）：指染色体带有特征的实体；种群（population）：个体的集合，该集合内个体数称为种群的大小；111111111101117进化（evolution）：生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化；适应度（fitness）：度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝;选择（selection）：指决定以一定的概率从种群中选择若干个体的操作（实现优胜劣汰）；复制（reproduction）：细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因;8交叉（crossover）：在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合形成两个新的染色体。又称基因重组，俗称“杂交”;变异（mutation）：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状;编码（coding）：表现型到基因型的映射；解码（decoding）：从基因型到表现型的映射。大象灰颜色皮肤为例1111111编码解码91.3遗传算法的原理与特点原理遗传算法(GA)是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索方法。其采纳了自然进化模型，从代表问题可能潜在解集的一个种群开始，种群由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体；初始种群产生后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的解：在每一代，概据问题域中个体的适应度大小挑选个体；并借助遗传算子进行组合交叉和主客观变异，产生出代表新的解集的种群。这一过程循环执行，直到满足优化准则为止。最后，末代个体经解码，生成近似最优解。基于种群进化机制的遗传算法如同自然界进化一样，后生代种群比前生代更加适应于环境，通过逐代进化，逼近最优解。101.3遗传算法的原理与特点遗传算法的基本流程Fig.2逼近最优解的过程Fig.1遗传算法的基本流程算法结束?111.3遗传算法的原理与特点特点遗传算法的本质并行性。首先，遗传算法并行的方式从问题解的串集开始嫂索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。其次，算法内含并行性，遗传算法采用种群方式组织搜索，因而可同时搜索妥空间的多个区域(n-n3)，并相互交流信息，能以较小的计算获得较大的收益。遗传算法基本上不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导他的搜索方向。具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜索时，硬度大的个体具有较高的生存概率，并获得更适应环境的基因结构。遗传算法可更直接的应用，对给定的问题，可以产生许多潜在解，最终选择可以由使用者指定，通用性高，应用范围广。121.4遗传算法的基本操作遗传基因型(编码)编码方式二进制编码、浮点数编码、格雷码编码、符号编码、复数编码、DNA编码等。以大象灰色皮肤为例：二进制编码：1111111，浮点编码：127.0编码原则完备性（completeness）：问题空间的所有解都能表示为所设计的基因型；健全性（soundness）：任何一个基因型都对应于一个可能解；非冗余性（non-redundancy）：问题空间和表达空间一一对应。二进制编码与浮点数编码的比较在交叉操作时，二进制编码比浮点数编码产生新个体的可能性多，而且产生的新个体不受父个体所构成的超体的限制；在变异操作时，二进制编码的种群稳定性比浮点数编码差。131.4遗传算法的基本操作选择适应度计算：按比例的适应度函数（proportionalfitnessassignment）基于排序的适应度计算（Rank-basedfitnessassignment）选择算法：轮盘赌选择（roulettewheelselection）随机遍历抽样（stochasticuniversalselection）局部选择（localselection）截断选择（truncationselection）锦标赛选择（tournamentselection）14交叉或基因重组二进制交叉（binaryvaluedcrossover）：单点交叉（single-pointcrossover）多点交叉（multiple-pointcrossover）均匀交叉（uniformcrossover）洗牌交叉（shufflecrossover）缩小代理交叉（crossoverwithreducedsurrogate）实值重组（realvaluedrecombination）：离散重组（discreterecombination）中间重组（intermediaterecombination）线性重组（linearrecombination）（均匀、非均匀）扩展线性重组（extendedlinearrecombination15交叉方式半种群交叉(N/2)对群体中的要交叉的个体进行两两随机配对。若群体大小为M，则最多共有[M/2]对相互配对的个体组参与交叉。(若种群数为奇数，则其中任一个个体多选一次配对)2)全种群交叉(N)对群体中要交叉的个体，从种群中随机挑选一个个体与其完成交叉操作，最多共有M对相互配对的个体参与变异。16变异方法二进制变异单点变异逆序变异均匀变异实值变异随机变异边界变异非一致变异自适应变异高斯变异17变异方式基于个体的变异即对任意一个个体，判断其是否进行变异操作，如果是，则随机生成一变异基因发生变异操作。基于基因座的变异即对种群中的个体，判断每一个个体的每一位基因是否进行变异操作，如果是，则发生变异操作。181.5遗传算法的应用函数优化是遗传算法的经典应用领域;组合优化实践证明，遗传算法对于组合优化中的NP完全问题非常有效;自动控制如基于遗传算法的模糊控制器优化设计、基于遗传算法的参数辨识、利用遗传算法进行人工神经网络的结构优化设计和权值学习等;机器人智能控制遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行动协调等;组合图像处理和模式识别目前已在图像恢复、图像边缘持征提取、几何形状识别等方面得到了应用;19人工生命基于遗传算法的进化模型是研究人工生命现象的重要理论基础，遗传算法已在其进化模型、学习模型、行为模型等方面显示了初步的应用能力；遗传程序设计Koza发展了遗传程序设计的慨念，他使用了以LISP语言所表示的编码方法，基于对一种树型结构所进行的遗传操作自动生成计算机程序;机器学习机器学习学习能力是高级自适应系统所应具备的能力之一。基于遗传算法的机器学习，特别是分类器系统，在很多领域中都得到了应用。例如，遗传算法被用于学习模糊控制规则，利用遗传算法来学习隶属度函数，从而更好地改进了模糊系统的性能；基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可用于人工神经网络的网络结构优化设计；分类器系统也在学习式多机器人路径规划系统中得到了成功的应用。202基本遗传算法遗传算法在自然与社会现象的模拟、工程计算等方面得到了广泛的应用。在各个不同的应用领域，为了取得更好的结果，人们对GA进行了大量的改进。为不至于混淆，把Holland提出的算法称为基本遗传算法，简称为SGA（SimpleGeneticAlgorithm)，也有称其为(GA、CGA)。以SGA为例，阐述遗传算法的设计与实现方法。212.1基本遗传算法描述2.1.1SGA的构成要素(1)染色体编码方法基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因由二值符号集{0，1}组成。初始群体中各个个体的基因值用均匀分布的随机数来生成。如：x：100111001000101101就可表示一个个体，该个体的染色体长度是l＝18。(2)个体适应度评价基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，这里要求所有个体的适应度必须为正数或零。这样，根据不同种类的问题，必须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好当目标