第二章遗传算法.ppt
- 文档编号:10838514
- 上传时间:2023-05-27
- 格式:PPT
- 页数:111
- 大小:1.99MB
第二章遗传算法.ppt
《第二章遗传算法.ppt》由会员分享,可在线阅读,更多相关《第二章遗传算法.ppt(111页珍藏版)》请在冰点文库上搜索。
第二章遗传算法,智能优化方法,沈阳农业大学信电学院2014年,2.1遗传算法简介2.1.1遗传算法的产生与发展2.1.2生物进化理论和遗传学的基本知识2.1.3遗传算法的思路与特点2.1.4遗传算法的基本操作2.1.5遗传算法的应用2.2基本遗传算法2.1.1简单函数优化的实例2.2.2遗传基因型2.2.3适应度函数及其尺度变换2.2.4遗传操作选择2.2.5遗传操作交叉/基因重组2.2.6遗传操作变异2.2.7算法的设计与实现,智能优化方法,沈阳农业大学信电学院2014年,2.3遗传算法的改进2.3.1CHC算法2.3.2自适应遗传算法2.3.3基于小生境技术的遗传算法,智能优化方法,沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,产生早在50年代,一些生物学家开始研究运用数字计算机模拟生物的自然遗传与自然进化过程;1963年,德国柏林技术大学的I.Rechenberg和H.P.Schwefel,做风洞实验时,产生了进化策略的初步思想;60年代,L.J.Fogel在设计有限态自动机时提出进化规划的思想。
1966年Fogel等出版了基于模拟进化的人工智能,系统阐述了进化规划的思想。
2.1.1遗传算法的产生与发展,沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,产生60年代中期,美国Michigan大学的J.H.Holland教授提出借鉴生物自然遗传的基本原理用于自然和人工系统的自适应行为研究和串编码技术;1967年,他的学生J.D.Bagley在博士论文中首次提出“遗传算法(GeneticAlgorithms)”一词;1975年,Holland出版了著名的“AdaptationinNaturalandArtificialSystems”,标志遗传算法的诞生。
2.1.1遗传算法的产生与发展,沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,发展70年代初,Holland提出了“模式定理”(SchemaTheorem),一般认为是“遗传算法的基本定理”,从而奠定了遗传算法研究的理论基础;1985年,在美国召开了第一届遗传算法国际会议,并且成立了国际遗传算法学会(ISGA,InternationalSocietyofGeneticAlgorithms);,2.1.1遗传算法的产生与发展,沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,发展1989年,Holland的学生D.J.Goldherg出版了“GeneticAlgorithmsinSearch,Optimization,andMachineLearning”,对遗传算法及其应用作了全面而系统的论述;1991年,L.Davis编辑出版了遗传算法手册,其中包括了遗传算法在工程技术和社会生活中大量的应用实例。
2.1.1遗传算法的产生与发展,沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,几个名词概念遗传算法进化计算计算智能人工智能,2.1.1遗传算法的产生与发展,沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,几个名词概念进化计算:
2.1.1遗传算法的产生与发展,由于遗传算法、进化规划和进化策略是不同领域的研究人员分别独立提出的,在相当长的时期里相互之间没有正式沟通。
直到90年代,才有所交流。
他们发现彼此的基本思想具有惊人的相似之处,于是提出将这类方法统称为“进化计算”(EvolutionaryComputation)。
沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,几个名词概念计算智能:
2.1.1遗传算法的产生与发展,计算智能主要包括神经计算、进化计算和模糊计算等。
它们分别从不同的角度模拟人类的智能活动,以使计算机具有智能。
通常将基于符号处理的传统人工智能称为符号智能,以区别于正在兴起的计算智能。
符号智能的特点是以知识为基础,偏重于逻辑推理,而计算智能则是以数据为基础,偏重于数值计算。
沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,达尔文的自然选择说遗传(heredity):
子代和父代具有相同或相似的性状,保证物种的稳定性;变异(variation):
子代与父代,子代不同个体之间总有差异,是生命多样性的根源;生存斗争和适者生存:
具有适应性变异的个体被保留,不具适应性变异的个体被淘汰。
自然选择过程是长期的、缓慢的、连续的过程。
2.1.2生物进化理论和遗传学的基本知识,沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,遗传学基本概念与术语染色体(chromosome):
遗传物质的载体;脱氧核糖核酸(DNA):
大分子有机聚合物,双螺旋结构;遗传因子(gene):
DNA或RNA长链结构中占有一定位置的基本遗传单位;,2.1.2生物进化理论和遗传学的基本知识,沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,遗传学基本概念与术语基因型(genotype):
遗传因子组合的模型;表现型(phenotype):
由染色体决定性状的外部表现;,2.1.2生物进化理论和遗传学的基本知识,沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,遗传学基本概念与术语基因座(locus):
遗传基因在染色体中所占据的位置,同一基因座可能有的全部基因称为等位基因(allele);个体(individual):
指染色体带有特征的实体;种群(population):
个体的集合,该集合内个体数称为种群的大小;,2.1.2生物进化理论和遗传学的基本知识,沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,遗传学基本概念与术语进化(evolution):
生物在其延续生存的过程中,逐渐适应其生存环境,使得其品质不断得到改良,这种生命现象称为进化;适应度(fitness):
度量某个物种对于生存环境的适应程度。
对生存环境适应程度较高的物种将获得更多的繁殖机会,而对生存环境适应程度较低的物种,其繁殖机会就会相对较少,甚至逐渐灭绝;,2.1.2生物进化理论和遗传学的基本知识,沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,遗传学基本概念与术语选择(selection):
指决定以一定的概率从种群中选择若干个体的操作;复制(reproduction):
细胞在分裂时,遗传物质DNA通过复制而转移到新产生的细胞中,新的细胞就继承了旧细胞的基因;交叉(crossover):
在两个染色体的某一相同位置处DNA被切断,其前后两串分别交叉组合形成两个新的染色体。
又称基因重组,俗称“杂交”;,2.1.2生物进化理论和遗传学的基本知识,沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,遗传学基本概念与术语变异(mutation):
在细胞进行复制时可能以很小的概率产生某些复制差错,从而使DNA发生某种变异,产生出新的染色体,这些新的染色体表现出新的性状;编码(coding):
表现型到基因型的映射;解码(decoding):
从基因型到表现型的映射。
2.1.2生物进化理论和遗传学的基本知识,沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,进化论与遗传学的融合19301947年,达尔文进化论与遗传学走向融合,Th.Dobzhansky1937年发表的遗传学与物种起源是融合进化论与遗传学的代表作。
生物进化与智能学的关系生物物种作为复杂系统,具有奇妙的自适应、自组织和自优化能力,这是一种生物在进化过程中体现的智能,也是人工系统梦寐以求的功能。
2.1.2生物进化理论和遗传学的基本知识,沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,遗传算法的基本思路,2.1.3遗传算法的思路与特点,沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,自组织、自适应和自学习性在编码方案、适应度函数及遗传算子确定后,算法将利用进化过程中获得的信息自行组织搜索。
本质并行性内在并行性与内含并行性不需求导只需目标函数和适应度函数,2.1.3遗传算法的思路与特点,沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,选择适应度计算:
按比例的适应度函数(proportionalfitnessassignment)基于排序的适应度计算(Rank-basedfitnessassignment)选择算法:
轮盘赌选择(roulettewheelselection),2.1.4遗传算法的基本操作,沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,选择选择算法:
随机遍历抽样(stochasticuniversalselection)局部选择(localselection)截断选择(truncationselection)锦标赛选择(tournamentselection),2.1.4遗传算法的基本操作,沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,交叉或基因重组实值重组(realvaluedrecombination):
离散重组(discreterecombination)中间重组(intermediaterecombination)线性重组(linearrecombination)扩展线性重组(extendedlinearrecombination),2.1.4遗传算法的基本操作,沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,交叉或基因重组二进制交叉(binaryvaluedcrossover):
单点交叉(single-pointcrossover)多点交叉(multiple-pointcrossover)均匀交叉(uniformcrossover)洗牌交叉(shufflecrossover)缩小代理交叉(crossoverwithreducedsurrogate),2.1.4遗传算法的基本操作,沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,变异实值变异二进制变异,2.1.4遗传算法的基本操作,沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,简单实例产生初始种群计算适应度,2.1.4遗传算法的基本操作,0001100000010111100100000001011001110100101010101011100101101001011011110000000110011101000001010011,(8)(5)
(2)(10)(7)(12)(5)(19)(10)(14),沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,简单实例选择,2.1.4遗传算法的基本操作,0.086957,0.054348,0.0217390.1086960.0760870.1304350.0543480.2065220.1086960.152174,沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,简单实例选择,2.1.4遗传算法的基本操作,0.086957,0.054348,0.0217390.1086960.0760870.1304350.0543480.2065220.1086960.152174,0.086957,0.141304,0.163043,0.2717390.3478260.4782610.5326090.7391300.8478261.000000,沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,简单实例选择在01之间产生一个随机数:
2.1.4遗传算法的基本操作,0.086957,0.054348,0.0217390.1086960.0760870.1304350.0543480.2065220.1086960.152174,0.086957,0.141304,0.163043,0.2717390.3478260.4782610.5326090.7391300.8478261.000000,0.070221,0.545929,0.784567,0.446930,0.507893,0.291198,0.716340,0.270901,0.371435,0.854641,沈阳农业大学信电学院2014年,0001100000111001011011000000011001110100101010101011100101101001011011110000000110011101000001010011,2.1遗传算法简介,智能优化方法,简单实例交叉,2.1.4遗传算法的基本操作,0001100000111001011011000000011001110100101010101011100101101001011011100111010011000000010001010011,0001,1110,100000,010110,111,100,0010110,1011011,110000,100111,0100,0001,1001110100,1100000001,1010101,0001010,010,011,沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,简单实例变异,2.1.4遗传算法的基本操作,沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,简单实例至下一代,适应度计算选择交叉变异,直至满足终止条件。
2.1.4遗传算法的基本操作,沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,函数优化是遗传算法的经典应用领域;组合优化实践证明,遗传算法对于组合优化的问题非常有效;自动控制如基于遗传算法的模糊控制器优化设计、基于遗传算法的参数辨识、利用遗传算法进行人工神经网络的结构优化设计和权值学习等;,2.1.5遗传算法的应用,沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,机器人智能控制遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、细胞机器人的结构优化和行动协调等;组合图像处理和模式识别目前已在图像恢复、图像边缘持征提取、几何形状识别等方面得到了应用;,2.1.5遗传算法的应用,沈阳农业大学信电学院2014年,2.1遗传算法简介,智能优化方法,人工生命基于遗传算法的进化模型是研究人工生命现象的重要理论基础,遗传算法已在其进化模型、学习模型、行为模型等方面显示了初步的应用能力;遗传程序设计Koza发展了遗传程序设计的慨念,他使用了以LISP语言所表示的编码方法,基于对一种树型结构所进行的遗传操作自动生成计算机程序;,2.1.5遗传算法的应用,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,问题的提出一元函数求最大值:
2.2.1简单函数优化的实例,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,问题的提出用微分法求取f(x)的最大值:
解有无穷多个:
2.2.1简单函数优化的实例,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,问题的提出当i为奇数时xi对应局部极大值点,i为偶数时xi对应局部极小值。
x19即为区间-1,2内的最大值点:
此时,函数最大值f(x19)比f(1.85)=3.85稍大。
2.2.1简单函数优化的实例,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,编码表现型:
x基因型:
二进制编码(串长取决于求解精度)串长与精度之间的关系:
若要求求解精度到6位小数,区间长度为2-(-1)3,即需将区间分为3/0.000001=3106等份。
所以编码的二进制串长应为22位。
2.2.1简单函数优化的实例,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,产生初始种群产生的方式:
随机产生的结果:
长度为22的二进制串产生的数量:
种群的大小(规模),如30,50,111101001110000101100011001100111010101011101010100011110010000100101111001001110011100100011001010011000000110000011010010000000000,2.2.1简单函数优化的实例,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,计算适应度不同的问题有不同的适应度计算方法本例:
直接用目标函数作为适应度函数将某个体转化为-1,2区间的实数:
s=x=0.637197计算x的函数值(适应度):
f(x)=xsin(10x)+2.0=2.586345,2.2.1简单函数优化的实例,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,计算适应度二进制与十进制之间的转换:
第一步,将一个二进制串(b21b20b0)转化为10进制数:
第二步,x对应的区间-1,2内的实数:
2.2.1简单函数优化的实例,(0000000000000000000000)-1(1111111111111111111111)2,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,遗传操作选择:
轮盘赌选择法;交叉:
单点交叉;变异:
小概率变异,2.2.1简单函数优化的实例,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,模拟结果设置的参数:
种群大小50;交叉概率0.75;变异概率0.05;最大代数200。
得到的最佳个体:
smax=;xmax=1.8506;f(xmax)=3.8503;,2.2.1简单函数优化的实例,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,模拟结果进化的过程:
2.2.1简单函数优化的实例,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,编码原则完备性(completeness):
问题空间的所有解都能表示为所设计的基因型;健全性(soundness):
任何一个基因型都对应于一个可能解;非冗余性(non-redundancy):
问题空间和表达空间一一对应。
2.2.2遗传基因型,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,多种编码方式二进制编码;浮点数编码;格雷码编码;符号编码;复数编码;DNA编码等。
2.2.2遗传基因型,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,适应度函数的重要性适应度函数的选取直接影响遗传算法的收敛速度以及能否找到最优解。
一般而言,适应度函数是由目标函数变换而成的,对目标函数值域的某种映射变换称为适应度的尺度变换(fitnessscaling)。
2.2.3适应度函数及其尺度变换,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,几种常见的适应度函数直接转换若目标函数为最大化问题:
Fit(f(x)=f(x)若目标函数为最小化问题:
Fit(f(x)=-f(x),2.2.3适应度函数及其尺度变换,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,几种常见的适应度函数界限构造法1若目标函数为最大化问题:
若目标函数为最小化问题:
2.2.3适应度函数及其尺度变换,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,几种常见的适应度函数界限构造法2若目标函数为最大化问题:
若目标函数为最小化问题:
c为目标函数的保守估计值。
2.2.3适应度函数及其尺度变换,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,适应度函数的作用适应度函数设计不当有可能出现欺骗问题:
(1)进化初期,个别超常个体控制选择过程;
(2)进化末期,个体差异太小导致陷入局部极值。
2.2.3适应度函数及其尺度变换,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,适应度函数的设计单值、连续、非负、最大化合理、一致性计算量小通用性强,2.2.3适应度函数及其尺度变换,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,适应度函数的线性变换法f=*f+系数的确定满足以下条件:
favg=favgfmax=cmultfavgcmult=1.02.0,2.2.3适应度函数及其尺度变换,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,适应度函数的幂函数变换法f=fkk与所求优化相关,2.2.3适应度函数及其尺度变换,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,适应度函数的指数变换法f=e-afa决定了复制的强制性,其值越小,复制的强制性就越趋向于那些具有最大适应性的个体。
2.2.3适应度函数及其尺度变换,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,几个概念选择压力(selectionpressure):
最佳个体选中的概率与平均个体选中概率的比值;偏差(bias):
个体正规化适应度与其期望再生概率的绝对差值;个体扩展(spread):
单个个体子代个数的范围;多样化损失(lossofdiversity):
在选择阶段未选中个体数目占种群的比例;,2.2.4遗传操作选择,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,几个概念选择强度(selectionintensity):
将正规高斯分布应用于选择方法,期望平均适应度;选择方差(selectionvariance):
将正规高斯分布应用于选择方法,期望种群适应度的方差。
2.2.4遗传操作选择,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,个体选择概率的常用分配方法按比例的适应度分配(proportionalfitnessassignment)某个体i,其适应度为fi,则其被选取的概率Pi为:
2.2.4遗传操作选择,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,常用选择方法轮盘赌选择法(roulettewheelselection),2.2.4遗传操作选择,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,常用选择方法随机遍历抽样法(stochasticuniversalsampling),2.2.4遗传操作选择,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,常用选择方法局部选择法(localselection)
(1)线形邻集,2.2.4遗传操作选择,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,常用选择方法局部选择法(localselection)
(2)两对角邻集,2.2.4遗传操作选择,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,常用选择方法局部选择法(localselection)
(2)两对角邻集,2.2.4遗传操作选择,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,常用选择方法截断选择法(truncationselection)个体按适应度排列,只有优秀个体能够称为父个体,参数为截断阀值(被选作父个体的百分比)。
2.2.4遗传操作选择,沈阳农业大学信电学院2014年,2.2基本遗传算法,智能优化方法,常用选择方法锦标赛选择法(tournamentselection)随机从种群中挑选一定数目个体,其中最好的个体作为父个体,此过程重复进行完成个体的选择。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二 遗传 算法
![提示](https://static.bingdoc.com/images/bang_tan.gif)