算法之遗传算法.pptx
《算法之遗传算法.pptx》由会员分享,可在线阅读,更多相关《算法之遗传算法.pptx(97页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、遗传算法简介遗传算法简介遗传算法简介遗传算法简介 l产生产生早早在在50年代年代,一些生物学家开始研究运用数字计算一些生物学家开始研究运用数字计算机模拟生物的自然遗传机模拟生物的自然遗传与自然进化过程与自然进化过程;1963年年,德国柏林技术大学的,德国柏林技术大学的I.Rechenberg和和H.P.Schwefel,做风洞实验时,产生了,做风洞实验时,产生了进化策略进化策略的初步的初步思想;思想;60年代,年代,L.J.Fogel在设计有限态自动机时提出在设计有限态自动机时提出进进化规划化规划的思想。的思想。1966年年Fogel等出版了等出版了基于模拟基于模拟进化的人工智能进化的人工智能
2、,系统阐述了进化规划的思想。,系统阐述了进化规划的思想。1.1.遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展 第1页/共97页遗传算法简介遗传算法简介遗传算法简介遗传算法简介 l产生产生60年代中期,年代中期,美国美国Michigan大学的大学的J.H.Holland教教授授提出提出借鉴生物自然遗传的基本原理借鉴生物自然遗传的基本原理用于自然用于自然 和人工系统的自适应行为研究和串编码技术;和人工系统的自适应行为研究和串编码技术;1967年,他的学生年,他的学生J.D.Bagley在博士论文中首次提在博士论文中首次提出出“遗传算法遗传算法(Genetic A
3、lgorithms)”一词一词;1975年年,Holland出版了著名的出版了著名的“Adaptation in Natural and Artificial Systems”,标志,标志遗传算法的遗传算法的诞生诞生。遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展 第2页/共97页遗传算法简介遗传算法简介遗传算法简介遗传算法简介 l发展发展70年代初,年代初,Holland提出了提出了“模式定理模式定理”(Schema Theorem),一般认为是),一般认为是“遗传算法的基本定理遗传算法的基本定理”,从而奠定了遗传算法研究的理论基础;,从而奠定了遗传算法研究
4、的理论基础;1985年,在美国召开了第一届遗传算法国际会议,年,在美国召开了第一届遗传算法国际会议,并且成立了国际遗传算法学会并且成立了国际遗传算法学会(ISGA,International Society of Genetic Algorithms);遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展 第3页/共97页遗传算法简介遗传算法简介遗传算法简介遗传算法简介 l发展发展1989年,年,Holland的学生的学生D.J.Goldherg出版了出版了“Genetic Algorithms in Search,Optimization,and Machine
5、Learning”,对遗传算法及其应用作了全,对遗传算法及其应用作了全面而系统的论述;面而系统的论述;1991年,年,L.Davis编辑出版了编辑出版了遗传算法手册遗传算法手册,其中包括了遗传算法在工程技术和社会生活中大量其中包括了遗传算法在工程技术和社会生活中大量的应用实例。的应用实例。遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展 第4页/共97页遗传算法简介遗传算法简介遗传算法简介遗传算法简介 l几个名词概念几个名词概念 进化计算:进化计算:遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展 由于遗传算法、进化规划和进化策略
6、是不同领域由于遗传算法、进化规划和进化策略是不同领域的研究人员分别独立提出的,在相当长的时期里的研究人员分别独立提出的,在相当长的时期里相互之间没有正式沟通。直到相互之间没有正式沟通。直到90年代,才有所交年代,才有所交流。流。他们发现彼此的基本思想具有惊人的相似之处,他们发现彼此的基本思想具有惊人的相似之处,于是提出将这类方法统称为于是提出将这类方法统称为“进化计算进化计算”(Evolutionary Computation)。第5页/共97页遗传算法简介遗传算法简介遗传算法简介遗传算法简介 l达尔文的自然选择说达尔文的自然选择说遗传(遗传(heredity):子代和父代具有相):子代和父代
7、具有相 同或相似的性状,保证物种的稳定性;同或相似的性状,保证物种的稳定性;变异(变异(variation):子代与父代,子代不同个体之间):子代与父代,子代不同个体之间总有差异,是生命多样性的根源;总有差异,是生命多样性的根源;生存斗争和适者生存:具有适应性变异的个体被保生存斗争和适者生存:具有适应性变异的个体被保留,不具适应性变异的个体被淘汰。留,不具适应性变异的个体被淘汰。自然选择过程是长期的、缓慢的、连续的过程。自然选择过程是长期的、缓慢的、连续的过程。2.2.生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识 第6
8、页/共97页遗传算法简介遗传算法简介遗传算法简介遗传算法简介 l遗传学基本概念与术语遗传学基本概念与术语染色体(染色体(chromosome):遗传物质的载体;):遗传物质的载体;脱氧核糖核酸(脱氧核糖核酸(DNA):大分子有机聚合物,双螺):大分子有机聚合物,双螺旋结构;旋结构;遗传因子(遗传因子(gene):):DNA或或RNA长链结构中占有一长链结构中占有一定位置的基本遗传单位;定位置的基本遗传单位;生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识 第7页/共97页遗传算法简介遗传算法简介遗传算法简介遗传算法简介 l
9、遗传学基本概念与术语遗传学基本概念与术语基因型(基因型(genotype):遗传因子组合的模型;):遗传因子组合的模型;表现型(表现型(phenotype):由染色体决定性状的外部表):由染色体决定性状的外部表现;现;生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识 1 1 1 1 1 1 1 1 1 1 0 1 1 1 第8页/共97页遗传算法简介遗传算法简介遗传算法简介遗传算法简介 l遗传学基本概念与术语遗传学基本概念与术语基因座(基因座(locus):遗传基因在染色体中所占据的位):遗传基因在染色体中所占据的位置,同
10、一基因座可能有的全部基因称为等位基因置,同一基因座可能有的全部基因称为等位基因(allele););个体(个体(individual):指带有染色体特征的实体;):指带有染色体特征的实体;种群(种群(population):个体的集合,该集合内个体数):个体的集合,该集合内个体数称为种群的大小;称为种群的大小;生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识 第9页/共97页遗传算法简介遗传算法简介遗传算法简介遗传算法简介 l遗传学基本概念与术语遗传学基本概念与术语进化(进化(evolution):生物在其延续生存的过程中
11、,):生物在其延续生存的过程中,逐渐适应其生存环境,使得其品质不断得到改良,逐渐适应其生存环境,使得其品质不断得到改良,这种生命现象称为进化;这种生命现象称为进化;适应度(适应度(fitness):度量某个物种对于生存环境的):度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会,而对生存环境适应程度较低的物更多的繁殖机会,而对生存环境适应程度较低的物种,其繁殖机会就会相对较少,甚至逐渐灭绝种,其繁殖机会就会相对较少,甚至逐渐灭绝;生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知
12、识生物进化理论和遗传学的基本知识 第10页/共97页遗传算法简介遗传算法简介遗传算法简介遗传算法简介 l遗传学基本概念与术语遗传学基本概念与术语选择(选择(selection):指决定以一定的概率从种群中):指决定以一定的概率从种群中选择若干个体的操作选择若干个体的操作;复制(复制(reproduction):细胞在分裂时,遗传物质):细胞在分裂时,遗传物质DNA通过复制而转移到新产生的细胞中,新的细胞通过复制而转移到新产生的细胞中,新的细胞就继承了旧细胞的基因就继承了旧细胞的基因;交叉(交叉(crossover):在两个染色体的某一相同位置):在两个染色体的某一相同位置处处DNA被切断,其前
13、后两串分别交叉组合形成两个被切断,其前后两串分别交叉组合形成两个新的染色体。又称基因重组,俗称新的染色体。又称基因重组,俗称“杂交杂交”;生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识 第11页/共97页遗传算法简介遗传算法简介遗传算法简介遗传算法简介 l遗传学基本概念与术语遗传学基本概念与术语变异(变异(mutation):在细胞进行复制时可能以很小):在细胞进行复制时可能以很小的概率产生某些复制差错,从而使的概率产生某些复制差错,从而使DNA发生某种变发生某种变异,产生出新的染色体,这些新的染色体表现出新异,产生出新
14、的染色体,这些新的染色体表现出新的性状的性状;编码(编码(coding):表现型到基因型的映射;):表现型到基因型的映射;解码(解码(decoding):从基因型到表现型的映射。):从基因型到表现型的映射。生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识 第12页/共97页遗传算法基本概念与术语个体(individual):GA所处理的基本对象、结构。群体(population):个体的集合。位串(bitString):个体的表示形式。对应于遗传学中的染色体(Chromosome)基因(gene):位串中的元素,表示不同的
15、特征。对应于生物学中的遗传物质单位,以DNA序列形式把遗传信息译成编码。第13页/共97页l遗传算法基本概念与术语l位串结构空间(bit String Space):等位基因任意组合构成的位串集合,基因操作在位串结构空间进行,对应于遗传学中的基因型的集合。l参数空间(Parameters Space):是位串空间在物理系统中的映射。对应于遗传学中的表现型的集合。l适应值(fitness):某一个体对于环境的适应程度,或者在环境压力下的生存能力,取决于遗传特性。l复制、选择(reproduction or selection):在有限资源空间上的排他性竞争。l逆转或倒位(inversion):反
16、转位串上的一段基因的排列顺序。对应于染色体上的一部分,在脱离之后反转 180o再连接起来。第14页/共97页遗传算法简介遗传算法简介遗传算法简介遗传算法简介 l进化论与遗传学的融合进化论与遗传学的融合 19301947年,达尔文进化论与遗传学走向融合,年,达尔文进化论与遗传学走向融合,Th.Dobzhansky1937年发表的年发表的遗传学与物种起源遗传学与物种起源是融合进化论与遗传学的代表作。是融合进化论与遗传学的代表作。l生物进化与智能学的关系生物进化与智能学的关系 生物物种作为复杂系统,具有奇妙的自适应、自组生物物种作为复杂系统,具有奇妙的自适应、自组织和自优化能力,这是一种生物在进化过
17、程中体现织和自优化能力,这是一种生物在进化过程中体现的智能,也是人工系统梦寐以求的功能。的智能,也是人工系统梦寐以求的功能。生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识 第15页/共97页遗传算法简介遗传算法简介遗传算法简介遗传算法简介 l遗传算法的基本思路遗传算法的基本思路3 3 遗传算法的思路与特点遗传算法的思路与特点遗传算法的思路与特点遗传算法的思路与特点 第16页/共97页遗传算法简介遗传算法简介遗传算法简介遗传算法简介 l自组织、自适应和自学习性自组织、自适应和自学习性 在编码方案、适应度函数及遗传算子确定后
18、,算法在编码方案、适应度函数及遗传算子确定后,算法将利用进化过程中获得的信息自行组织搜索。将利用进化过程中获得的信息自行组织搜索。l本质并行性本质并行性 内在并行性与内含并行性内在并行性与内含并行性l不需求导不需求导 只需目标函数和适应度函数只需目标函数和适应度函数l概率转换规则概率转换规则 强调概率转换规则,而不是确定的转换规则强调概率转换规则,而不是确定的转换规则遗传算法的特点遗传算法的特点遗传算法的特点遗传算法的特点 第17页/共97页遗传算法简介遗传算法简介遗传算法简介遗传算法简介 l选择选择 适应度计算适应度计算:计算结果非负计算结果非负 选择算法选择算法:两类两类基于适应度比例的基
19、于适应度比例的基于适应度排序的基于适应度排序的4 4 遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 第18页/共97页遗传算法简介遗传算法简介遗传算法简介遗传算法简介 l选择选择 选择算法选择算法:轮盘赌选择(轮盘赌选择(roulette wheel selection)随机遍历抽样(随机遍历抽样(stochastic universal selection)局部选择(局部选择(local selection)截断选择(截断选择(truncation selection)锦标赛选择(锦标赛选择(tournament selection)遗传算法的基本操作遗传算法的基
20、本操作遗传算法的基本操作遗传算法的基本操作 第19页/共97页遗传算法简介遗传算法简介遗传算法简介遗传算法简介 l交叉或基因重组交叉或基因重组 实值重组(实值重组(real valued recombination):离散重组(离散重组(discrete recombination)中间重组(中间重组(intermediate recombination)线性重组(线性重组(linear recombination)扩展线性重组(扩展线性重组(extended linear recombination)遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 第20页/共97页
21、遗传算法简介遗传算法简介遗传算法简介遗传算法简介 l交叉或基因重组交叉或基因重组 二进制交叉(二进制交叉(binary valued crossover):单点交叉(单点交叉(single-point crossover)多点交叉(多点交叉(multiple-point crossover)均匀交叉(均匀交叉(uniform crossover)洗牌交叉(洗牌交叉(shuffle crossover)缩小代理交叉(缩小代理交叉(crossover with reduced surrogate)遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 第21页/共97页遗传算法简
22、介遗传算法简介遗传算法简介遗传算法简介 l变异变异 实值变异实值变异 二进制变异二进制变异遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 第22页/共97页遗传算法简介遗传算法简介遗传算法简介遗传算法简介 l简单实例简单实例1.产生初始种群产生初始种群2.计算适应度计算适应度遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 0001100000 0101111001 0000000101 1001110100 10101010101110010110 1001011011 1100000001 1001110100 0001010011(8)(
23、5)(2)(10)(7)(12)(5)(19)(10)(14)第23页/共97页遗传算法简介遗传算法简介遗传算法简介遗传算法简介 l简单实例简单实例3.选择选择遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 个体个体染色体染色体适应度适应度选择概率选择概率累积概率累积概率10001100000820101111001530000000101241001110100105101010101076111001011012710010110115811000000011991001110100101000010100111488521071251910140.0869575
24、8521071251910140.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.152174第24页/共97页遗传算法简介遗传算法简介遗传算法简介遗传算法简介 l简单实例简单实例3.选择选择遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 个体个体染色体染色体适应度适应度选择概率选择概率累积概率累积概率10001100000820101111001530000000101241001110100105101010101076111001011012710010110115811000000
25、01199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.000000第25页/共97页遗传算法简介遗传算法简介遗传算法简介遗传算法简介 l简单实例简单实例3.选择选择在在01之间产生一个之间产生一个随机数:随机数:遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 遗传
限制150内