文档介绍：智能优化算法课程-2009 级硕士中山大学智能交通研究中心中山大学智能交通研究中心 2010 2010 年年4 4月月遗传算法原理及其应用 2 1. 遗传算法概述 (SGA) 目录? 遗传算法的产生与发展? 遗传算法的生理学基础? 遗传算法的原理与特点? 遗传算法的基本操作? 遗传算法的应用? 基本遗传算法描述? 基本遗传算法实现? 基本遗传算法流程? 简单函数优化的实例 3 3. 遗传算法的改进 4. 遗传算法的应用目录? 自适应遗传算法? CHC 算法? 基于小生境技术的遗传算法? 退火进化算法? 解决带约束的函数优化问题? 解决多目标优化问题? 解决组合优化问题? 遗传算法在过程建模中的应用? 遗传算法在模式识别中的应用 4 遗传算法的产生与发展?产生?早在50年代,一些生物学家开始研究运用数字计算机模拟生物的自然遗传与自然进化过程; ?1963 年,德国柏林技术大学的 I. Rechenberg 和 H. P. Schwefel ,做风洞实验时,产生了进化策略的初步思想; ?60年代, L. J. Fogel 在设计有限态自动机时提出进化规划的思想。 1966 年 Fogel 等出版了《基于模拟进化的人工智能》,系统阐述了进化规划的思想。?60年代中期,美国 Michigan 大学的 J. H. Holland 教授提出借鉴生物自然遗传的基本原理用于自然和人工系统的自适应行为研究和串编码技术; ?1967 年,他的学生 J. D. Bagley 在博士论文中首次提出“遗传算法(ic Algorithms) ”一词; ?1975 年, Holland 出版了著名的“ Adaptation in Natural and Artificial Systems ”,标志遗传算法的诞生。 5 遗传算法的产生与发展?发展?70年代初, Holland 提出了“模式定理”( Schema Theorem ),一般认为是“遗传算法的基本定理”, 从而奠定了遗传算法研究的理论基础; ?1985 年,在美国召开了第一届遗传算法国际会议,并且成立了国际遗传算法学会(ISGA , International Society of ic Algorithms) ; ?1989 年, Holland 的学生 D. J. Goldherg 出版了“ ic Algorithms in Search, Optimization, and Machine Learning ”,对遗传算法及其应用作了全面而系统的论述; ?1991 年, L. Davis 编辑出版了《遗传算法手册》,其中包括了遗传算法在工程技术和社会生活中大量的应用实例。遗传算法——进化计算——计算智能——人工智能 6 遗传学基本概念与术语?染色体( chromosome ):遗传物质的载体; ?脱氧核糖核酸( DNA ):大分子有机聚合物,双螺旋结构; ? RNA ?遗传因子( gene ): DNA 或 RNA 长链结构中占有一定位置的基本遗传单位; ?基因型( genotype ):遗传因子组合的模型; ?表现型( phenotype ):由染色体决定性状的外部表现; ?个体( individual ):指染色体带有特征的实体; ?种群( population ):个体的集合,该集合内个体数称为种群的大小; 1 1 1 1 1 1 1 1 1 1 0 1 1 1 7 ?进化( evolution ):生物在其延续生存的过程中,逐渐适应其生存环境,使得其品质不断得到改良,这种生命现象称为进化; ?适应度( fitness ):度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会,而对生存环境适应程度较低的物种,其繁殖机会就会相对较少,甚至逐渐灭绝; ?选择( selection ):指决定以一定的概率从种群中选择若干个体的操作(实现优胜劣汰); ?复制( reproduction ):细胞在分裂时,遗传物质 DNA 通过复制而转移到新产生的细胞中,新的细胞就继承了旧细胞的基因;8 ?交叉( crossover ):在两个染色体的某一相同位置处 DNA 被切断,其前后两串分别交叉组合形成两个新的染色体。又称基因重组,俗称“杂交”;?变异( mutation ):在细胞进行复制时可能以很小的概率产生某些复制差错,从而使 DNA 发生某种变异,产生出新的染色体,这些新