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

《遗传算法原理及其应用课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、中山大学智能交通研究中心2010年4月遗传算法原理及其应用8/5/20211.遗传算法概述2.基本遗传算法(SGA)目录1.1遗传算法的产生与发展1.2遗传算法的生理学基础1.3遗传算法的原理与特点1.4遗传算法的基本操作1.5遗传算法的应用2.1基本遗传算法描述2.2基本遗传算法实现2.3基本遗传算法流程2.4简单函数优化的实例23.遗传算法的改进4.遗传算法的应用目录3.1自适应遗传算法3.2CHC算法3.3基于小生境技术的遗传算法3.4退火进化算法4.1解决带约束的函数优化问题4.2解决多目标优化问题4.3解决组合优

2、化问题4.4遗传算法在过程建模中的应用4.5遗传算法在模式识别中的应用31.1遗传算法的产生与发展产生早在50年代，一些生物学家开始研究运用数字计算机模拟生物的自然遗传与自然进化过程；1963年，德国柏林技术大学的I.Rechenberg和H.P.Schwefel，做风洞实验时，产生了进化策略的初步思想；60年代，L.J.Fogel在设计有限态自动机时提出进化规划的思想。1966年Fogel等出版了《基于模拟进化的人工智能》，系统阐述了进化规划的思想。60年代中期，美国Michigan大学的J.H.Holland教授提出借

3、鉴生物自然遗传的基本原理用于自然和人工系统的自适应行为研究和串编码技术；1967年，他的学生J.D.Bagley在博士论文中首次提出“遗传算法(GeneticAlgorithms)”一词；1975年，Holland出版了著名的“AdaptationinNaturalandArtificialSystems”，标志遗传算法的诞生。41.1遗传算法的产生与发展发展70年代初，Holland提出了“模式定理”（SchemaTheorem），一般认为是“遗传算法的基本定理”，从而奠定了遗传算法研究的理论基础；1985年，在美国召开

4、了第一届遗传算法国际会议，并且成立了国际遗传算法学会(ISGA，InternationalSocietyofGeneticAlgorithms)；1989年，Holland的学生D.J.Goldherg出版了“GeneticAlgorithmsinSearch,Optimization,andMachineLearning”，对遗传算法及其应用作了全面而系统的论述；1991年，L.Davis编辑出版了《遗传算法手册》，其中包括了遗传算法在工程技术和社会生活中大量的应用实例。遗传算法——进化计算——计算智能——人工智能51.

5、2遗传学基本概念与术语染色体（chromosome）：遗传物质的载体；脱氧核糖核酸（DNA）：大分子有机聚合物，双螺旋结构；RNA遗传因子（gene）：DNA或RNA长链结构中占有一定位置的基本遗传单位；基因型（genotype）：遗传因子组合的模型；表现型（phenotype）：由染色体决定性状的外部表现；个体（individual）：指染色体带有特征的实体；种群（population）：个体的集合，该集合内个体数称为种群的大小；111111111101116进化（evolution）：生物在其延续生存的过程中，逐渐适应

6、其生存环境，使得其品质不断得到改良，这种生命现象称为进化；适应度（fitness）：度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝;选择（selection）：指决定以一定的概率从种群中选择若干个体的操作（实现优胜劣汰）；复制（reproduction）：细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因;7交叉（crossover）：在两个染色体的某一相同位置处DNA被切断，其

7、前后两串分别交叉组合形成两个新的染色体。又称基因重组，俗称“杂交”;变异（mutation）：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状;编码（coding）：表现型到基因型的映射；解码（decoding）：从基因型到表现型的映射。大象灰颜色皮肤为例1111111编码解码81.3遗传算法的原理与特点原理遗传算法(GA)是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索方法。其采纳了自然进化模型，从代表问题可能潜在解集的一个

8、种群开始，种群由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体；初始种群产生后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的解：在每一代，概据问题域中个体的适应度大小挑选个体；并借助遗传算子进行组合交叉和主客观变异，产生出代表新的解集的种群。这一过程循环执行，直到满足优