文档介绍：中山大学智能交通研究中心
2010年4月
遗传算法原理及其应用
1/23/2018
1. 遗传算法概述
(SGA)
目录
遗传算法的产生与发展
遗传算法的生理学基础
遗传算法的原理与特点
遗传算法的基本操作
遗传算法的应用
基本遗传算法描述
基本遗传算法实现
基本遗传算法流程
简单函数优化的实例
2
3. 遗传算法的改进
4. 遗传算法的应用
目录
自适应遗传算法
CHC算法
基于小生境技术的遗传算法
退火进化算法
解决带约束的函数优化问题
解决多目标优化问题
解决组合优化问题
遗传算法在过程建模中的应用
遗传算法在模式识别中的应用
3
遗传算法的产生与发展
产生
早在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”,标志遗传算法的诞生。
4
遗传算法的产生与发展
发展
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编辑出版了《遗传算法手册》,其中包括了遗传算法在工程技术和社会生活中大量的应用实例。
遗传算法——进化计算——计算智能——人工智能
5
遗传学基本概念与术语
染色体(chromosome):遗传物质的载体;
脱氧核糖核酸(DNA):大分子有机聚合物,双螺旋结构;
RNA
遗传因子(gene):DNA或RNA长链结构中占有一定位置的基本遗传单位;
基因型(genotype):遗传因子组合的模型;
表现型(phenotype):由染色体决定性状的外部表现;
个体(individual):指染色体带有特征的实体;
种群(population):个体的集合,该集合内个体数称为种群的大小;
1 1 1 1 1 1 1
1 1 1 0 1 1 1
6
进化(evolution):生物在其延续生存的过程中,逐渐适应其生存环境,使得其品质不断得到改良,这种生命现象称为进化;
适应度(fitness):度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会,而对生存环境适应程度较低的物种,其繁殖机会就会相对较少,甚至逐渐灭绝;
选择(selection):指决定以一定的概率从种群中选择若干个体的操作(实现优胜劣汰);
复制(reproduction):细胞在分裂时,遗传物质DNA通过复制而转移到新产生的细胞中,新的细胞就继承了旧细胞的基因;
7
交叉(crossover):在两个染色体的某一相同位置处DNA被切断,其前后两串分别交叉组合形成两个新的染色体。又称基因重组,俗称“杂交”;
变异(mutation):在细胞进行复制时可能以很小的概率产生某些复制差错,从而使DNA发生某种变异,产生出新的染色体,这些新的染色体表现出新的性状;
编码(coding):表现型到基因型的映射;
解码(decoding):从基因型到表现型的映射。
大象灰颜色皮肤为例
1 1 1 1 1 1 1
编码
解码
8
遗传算法的原理与特点
原理
遗传算法(GA)是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜