经典算法之遗传算法.ppt

1、遗传算法,遗传算法简介,产生 早在50年代，一些生物学家开始研究运用数字计算机模拟生物的自然遗传与自然进化过程； 1963年，德国柏林技术大学的I. Rechenberg和H. P. Schwefel，做风洞实验时，产生了进化策略的初步思想； 60年代， L. J. Fogel在设计有限态自动机时提出进化规划的思想。1966年Fogel等出版了基于模拟进化的人工智能，系统阐述了进化规划的思想。,1.遗传算法的产生与发展,遗传算法简介,产生 60年代中期，美国Michigan大学的J. H. Holland教授提出借鉴生物自然遗传的基本原理用于自然 和人工系统的自适应行为研究和串编码技术； 19

2、67年，他的学生J. D. Bagley在博士论文中首次提出“遗传算法(Genetic Algorithms)”一词； 1975年，Holland出版了著名的“Adaptation in Natural and Artificial Systems”，标志遗传算法的诞生。,遗传算法的产生与发展,遗传算法简介,发展 70年代初，Holland提出了“模式定理”（Schema Theorem），一般认为是“遗传算法的基本定理”，从而奠定了遗传算法研究的理论基础； 1985年，在美国召开了第一届遗传算法国际会议，并且成立了国际遗传算法学会(ISGA，International Society of

3、Genetic Algorithms)；,遗传算法的产生与发展,遗传算法简介,发展 1989年，Holland的学生D. J. Goldherg出版了“Genetic Algorithms in Search, Optimization, and Machine Learning”，对遗传算法及其应用作了全面而系统的论述； 1991年，L. Davis编辑出版了遗传算法手册，其中包括了遗传算法在工程技术和社会生活中大量的应用实例。,遗传算法的产生与发展,遗传算法简介,几个名词概念 进化计算：,遗传算法的产生与发展,由于遗传算法、进化规划和进化策略是不同领域的研究人员分别独立提出的，在相当长的时

4、期里相互之间没有正式沟通。直到90年代，才有所交流。 他们发现彼此的基本思想具有惊人的相似之处，于是提出将这类方法统称为“进化计算” ( Evolutionary Computation ) 。,遗传算法简介,达尔文的自然选择说 遗传（heredity）：子代和父代具有相 同或相似的性状，保证物种的稳定性； 变异（variation）：子代与父代，子代不同个体之间总有差异，是生命多样性的根源； 生存斗争和适者生存：具有适应性变异的个体被保留，不具适应性变异的个体被淘汰。 自然选择过程是长期的、缓慢的、连续的过程。,2.生物进化理论和遗传学的基本知识,遗传算法简介,遗传学基本概念与术语 染色体（

5、chromosome）：遗传物质的载体； 脱氧核糖核酸（DNA）：大分子有机聚合物，双螺旋结构； 遗传因子（gene）：DNA或RNA长链结构中占有一定位置的基本遗传单位；,生物进化理论和遗传学的基本知识,遗传算法简介,遗传学基本概念与术语 基因型（genotype）：遗传因子组合的模型； 表现型（phenotype）：由染色体决定性状的外部表现；,生物进化理论和遗传学的基本知识,遗传算法简介,遗传学基本概念与术语 基因座（locus）：遗传基因在染色体中所占据的位置，同一基因座可能有的全部基因称为等位基因（allele）； 个体（individual）：指带有染色体特征的实体； 种群（pop

6、ulation）：个体的集合，该集合内个体数称为种群的大小；,生物进化理论和遗传学的基本知识,遗传算法简介,遗传学基本概念与术语 进化（evolution）：生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化； 适应度（fitness）：度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝;,生物进化理论和遗传学的基本知识,遗传算法简介,遗传学基本概念与术语 选择（selection）：指决定以一定的概率从种群中选择若干个体的操作 ； 复制（reprod

7、uction）：细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因; 交叉（crossover）：在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合形成两个新的染色体。又称基因重组，俗称“杂交”;,生物进化理论和遗传学的基本知识,遗传算法简介,遗传学基本概念与术语 变异（mutation）：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状; 编码（coding）：表现型到基因型的映射； 解码（decoding）：从基因型到表现型的映射。,生物进化理论和遗传学的基本知识,

8、遗传算法基本概念与术语 个体（individual）：GA所处理的基本对象、结构。 群体（population）：个体的集合。 位串（bit String）：个体的表示形式。对应于遗传学中的染色体（Chromosome） 基因（gene）：位串中的元素，表示不同的特征。对应于生物学中的遗传物质单位，以DNA序列形式把遗传信息译成编码。,遗传算法基本概念与术语 位串结构空间（bit String Space）：等位基因任意组合构成的位串集合，基因操作在位串结构空间进行，对应于遗传学中的基因型的集合。 参数空间（Parameters Space）：是位串空间在物理系统中的映射。对应于遗传学中的表现

9、型的集合。 适应值（fitness）：某一个体对于环境的适应程度，或者在环境压力下的生存能力，取决于遗传特性。 复制、选择（reproduction or selection）：在有限资源空间上的排他性竞争。 逆转或倒位（inversion）：反转位串上的一段基因的排列顺序。对应于染色体上的一部分，在脱离之后反转 180o再连接起来。,遗传算法简介,进化论与遗传学的融合 19301947年，达尔文进化论与遗传学走向融合，Th. Dobzhansky1937年发表的遗传学与物种起源是融合进化论与遗传学的代表作。 生物进化与智能学的关系 生物物种作为复杂系统，具有奇妙的自适应、自组织和自优化能力，

10、这是一种生物在进化过程中体现的智能，也是人工系统梦寐以求的功能。,生物进化理论和遗传学的基本知识,遗传算法简介,遗传算法的基本思路,3 遗传算法的思路与特点,遗传算法简介,自组织、自适应和自学习性 在编码方案、适应度函数及遗传算子确定后，算法将利用进化过程中获得的信息自行组织搜索。 本质并行性 内在并行性与内含并行性 不需求导 只需目标函数和适应度函数 概率转换规则 强调概率转换规则，而不是确定的转换规则,遗传算法的特点,遗传算法简介,选择 适应度计算： 计算结果非负 选择算法： 两类 基于适应度比例的 基于适应度排序的,4 遗传算法的基本操作,遗传算法简介,选择 选择算法： 轮盘赌选择（ro

11、ulette wheel selection） 随机遍历抽样（stochastic universal selection） 局部选择（local selection） 截断选择（truncation selection） 锦标赛选择（tournament selection）,遗传算法的基本操作,遗传算法简介,交叉或基因重组 实值重组（real valued recombination）： 离散重组（discrete recombination） 中间重组（intermediate recombination） 线性重组（linear recombination） 扩展线性重组（extend

12、ed linear recombination）,遗传算法的基本操作,遗传算法简介,交叉或基因重组 二进制交叉（binary valued crossover）： 单点交叉（single-point crossover） 多点交叉（multiple-point crossover） 均匀交叉（uniform crossover） 洗牌交叉（shuffle crossover） 缩小代理交叉（crossover with reduced surrogate）,遗传算法的基本操作,遗传算法简介,变异 实值变异 二进制变异,遗传算法的基本操作,遗传算法简介,简单实例 产生初始种群 计算适应度,遗传算

13、法的基本操作,0001100000 0101111001 0000000101 1001110100 1010101010 1110010110 1001011011 1100000001 1001110100 0001010011,（8） （5） （2） （10） （7） （12） （5） （19） （10） （14）,遗传算法简介,简单实例 选择,遗传算法的基本操作,0.086957,0.054348,0.021739 0.108696 0.076087 0.130435 0.054348 0.206522 0.108696 0.152174,遗传算法简介,简单实例 选择,遗传算法的基本操

14、作,0.086957,0.054348,0.021739 0.108696 0.076087 0.130435 0.054348 0.206522 0.108696 0.152174,0.086957,0.141304,0.163043,0.271739 0.347826 0.478261 0.532609 0.739130 0.847826 1.000000,遗传算法简介,简单实例 选择 在01之间产生一个 随机数：,遗传算法的基本操作,0.086957,0.054348,0.021739 0.108696 0.076087 0.130435 0.054348 0.206522 0.1086

15、96 0.152174,0.086957,0.141304,0.163043,0.271739 0.347826 0.478261 0.532609 0.739130 0.847826 1.000000,0.070221,0.545929,0.784567,0.446930,0.507893,0.291198,0.716340,0.270901,0.371435,0.854641,0001100000 1110010110 1100000001 1001110100 1010101010 1110010110 1001011011 1100000001 1001110100 000101001

16、1,遗传算法简介,简单实例 交叉,遗传算法的基本操作,0001100000 1110010110 1100000001 1001110100 1010101010 1110010110 1001011011 1001110100 1100000001 0001010011,0001,1110,100000,010110,111,100,0010110,1011011,110000,100111,0100,0001,1001110100,1100000001,1010101,0001010,010,011,遗传算法简介,简单实例 变异,遗传算法的基本操作,遗传算法简介,简单实例 至下一代，适应度

17、计算选择交叉变异，直至满足终止条件。,遗传算法的基本操作,遗传算法简介,函数优化 是遗传算法的经典应用领域; 组合优化 实践证明，遗传算法对于组合优化中的NP完全问题非常有效; 自动控制 如基于遗传算法的模糊控制器优化设计、基于遗传算法的参数辨识等;,5 遗传算法的应用,遗传算法简介,机器人智能控制 遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行动协调等; 组合图像处理和模式识别 目前已在图像恢复、图像边缘持征提取、几何形状识别等方面得到了应用;,遗传算法的应用,遗传算法简介,人工生命 基于遗传算法的进化模型是研究人工生命现象的重要理论基

18、础，遗传算法已在其进化模型、学习模型、行为模型等方面显示了初步的应用能力； 遗传程序设计 Koza发展了遗传程序设计的慨念，他使用了以LISP语言所表示的编码方法，基于对一种树型结构所进行的遗传操作自动生成计算机程序;,遗传算法的应用,2 基本遗传算法,问题的提出 一元函数求最大值：,1 简单函数优化的实例,基本遗传算法,问题的提出 用微分法求取f(x)的最大值： 解有无穷多个：,简单函数优化的实例,基本遗传算法,问题的提出 当i为奇数时xi对应局部极大值点，i为偶数时xi对应局部极小值。x19即为区间-1,2内的最大值点： 此时，函数最大值f(x19)比f(1.85)=3.85稍大。,简单函

19、数优化的实例,基本遗传算法,编码 表现型：x 基因型：二进制编码（串长取决于求解精度） 串长与精度之间的关系： 若要求求解精度到6位小数，区间长度为2-(-1)3，即需将区间分为3/0.000001=3106等份。 所以编码的二进制串长应为22位。,简单函数优化的实例,基本遗传算法,产生初始种群 产生的方式：随机 产生的结果：长度为22的二进制串 产生的数量：种群的大小（规模），如30，50， 1111010011100001011000 1100110011101010101110 1010100011110010000100 1011110010011100111001 000110010

20、1001100000011 0000011010010000000000 ,简单函数优化的实例,基本遗传算法,计算适应度 不同的问题有不同的适应度计算方法 本例：直接用目标函数作为适应度函数 将某个体转化为-1,2区间的实数： s= x=0.637197 计算x的函数值（适应度）： f(x)=xsin(10 x)+2.0=2.586345,简单函数优化的实例,基本遗传算法,计算适应度（简单函数值替换） 二进制与十进制之间的转换： 第一步，将一个二进制串（b21b20b0）转化为10进制数： 第二步，x对应的区间-1,2内的实数：,简单函数优化的实例,(000000000000000000000

21、0)-1 (1111111111111111111111)2,基本遗传算法,遗传操作 选择：轮盘赌选择法； 交叉：单点交叉； 变异：小概率变异,简单函数优化的实例,基本遗传算法,模拟结果 设置的参数： 种群大小50；交叉概率0.75；变异概率0.05；最大迭代数200。 得到的最佳个体： smax=; xmax=1.8506; f(xmax)=3.8503;,简单函数优化的实例,基本遗传算法,模拟结果 进化的过程：,简单函数优化的实例,基本遗传算法,编码原则 完备性（completeness）：问题空间的所有解都能表示为所设计的基因型； 健全性（soundness）：任何一个基因型都对应于一个

22、可能解； 非冗余性（non-redundancy）：问题空间和表达空间一一对应。,2 遗传基因型,基本遗传算法,多种编码方式 二进制编码； 浮点数编码； 格雷码编码； 符号编码； 复数编码； DNA编码等。,遗传基因型,基本遗传算法,二进制编码与浮点数编码的比较 在交叉操作时，二进制编码比浮点数编码产生新个体的可能性多，而且产生的新个体不受父个体所构成的超体的限制； 在变异操作时，二进制编码的种群稳定性比浮点数编码差。,遗传基因型,基本遗传算法,适应度函数的重要性 适应度函数的选取直接影响遗传算法的收敛速度以及能否找到最优解。 一般而言，适应度函数是由目标函数变换而成的，对目标函数值域的某种映

23、射变换称为适应度的尺度变换（fitness scaling）。,3 适应度函数及其尺度变换,基本遗传算法,几种常见的适应度函数 直接转换 若目标函数为最大化问题：Fit ( f (x) )= f (x) 若目标函数为最小化问题：Fit ( f (x) )= - f (x),适应度函数及其尺度变换,基本遗传算法,几种常见的适应度函数 界限构造法1 若目标函数为最大化问题： 若目标函数为最小化问题：,适应度函数及其尺度变换,基本遗传算法,几种常见的适应度函数 界限构造法2 若目标函数为最大化问题： 若目标函数为最小化问题： c为目标函数的保守估计值。,适应度函数及其尺度变换,基本遗传算法,适应度函

24、数的作用 适应度函数设计不当有可能出现欺骗问题： （1）进化初期，个别超常个体控制选择过程； （2）进化末期，个体差异太小导致进化缓慢。,适应度函数及其尺度变换,基本遗传算法,适应度函数的设计 单值、连续、非负、最大化 合理、一致性 计算量小 通用性强,适应度函数及其尺度变换,基本遗传算法,适应度函数的线性变换法 f=*f+ 系数的确定满足以下条件： favg= favg fmax= cmult favg cmult =1.02.0,适应度函数及其尺度变换,基本遗传算法,适应度函数的幂函数变换法 f= f k k与所求优化相关,适应度函数及其尺度变换,基本遗传算法,适应度函数的指数变换法 f=

25、 e-af a决定了复制的强制性，其值越小，复制的强制性就越趋向于那些具有最大适应性的个体。,适应度函数及其尺度变换,基本遗传算法,几个概念 选择压力（selection pressure）:最佳个体选中的概率与平均个体选中概率的比值； 偏差（bias）：个体正规化适应度与其期望再生概率的绝对差值； 个体扩展（spread）：单个个体子代个数的范围； 多样化损失（loss of diversity）：在选择阶段未选中个体数目占种群的比例；,4 遗传操作选择,基本遗传算法,几个概念 选择强度（selection intensity）:将正规高斯分布应用于选择方法，期望平均适应度； 选择方差（se

26、lection variance）：将正规高斯分布应用于选择方法，期望种群适应度的方差。,遗传操作选择,基本遗传算法,个体选择概率的常用分配方法 按比例的适应度分配（proportional fitness assignment） 某个体i，其适应度为fi，则其被选取的概率Pi为：,遗传操作选择,基本遗传算法,个体选择概率的常用分配方法 基于排序的适应度分配（rank-based fitness assignment） 线性排序（by Baker） 为种群大小，i为个体序号，max代表选择压力。,遗传操作选择,基本遗传算法,个体选择概率的常用分配方法 基于排序的适应度分配（rank-based

27、 fitness assignment） 非线性排序（by Michalewicz） i为个体序号，c为排序第一的个体的选择概率。,遗传操作选择,基本遗传算法,常用选择方法 轮盘赌选择法（roulette wheel selection）,遗传操作选择,基本遗传算法,常用选择方法 随机遍历抽样法（stochastic universal sampling）,遗传操作选择,设定n为需要选择的个体数目，等距离选择个体，选择指针的距离为1n。第一个指针的位置由0，ln区间的均匀随机数决定。如图所示，需要选择6个个体，指针间的距离为l6o.167，第一个指针的随机位置为0.1，按这种选择方法被选中作为

28、交配集个体为：12，34，6，8。,基本遗传算法,常用选择方法 局部选择法（local selection） (1)线形邻集,遗传操作选择,在局部选择法中，每个个体处于一个约束环境中，称为局部邻域(而其他选择方法中视整个种群为个体之邻域)，个体仅与其邻近个体产生交互，该邻域的定义由种群的分布结构给出。邻域可被当作潜在的交配伙伴。 首先均匀随机地选择一半交配种群，选择方法可以是随机遍历方法也可以是截断选择方法，然后对每个被选个体定义其局部邻域，在邻域内部选择交配伙伴。,基本遗传算法,常用选择方法 局部选择法（local selection） (2)两对角邻集,遗传操作选择,基本遗传算法,常用选择

29、方法 局部选择法（local selection） (2)两对角邻集,遗传操作选择,基本遗传算法,常用选择方法 截断选择法（truncation selection） 个体按适应度排列，只有优秀个体能够成为父个体，参数为截断阀值（被选作父个体的百分比）。,遗传操作选择,基本遗传算法,常用选择方法 锦标赛选择法（tournament selection） 随机从种群中挑选一定数目个体，其中最好的个体作为父个体，此过程重复进行完成个体的选择。,遗传操作选择,基本遗传算法,实值重组 离散重组 子个体的每个变量可以按等概率随机地挑选父个体。,5 遗传操作交叉/基因重组,父个体1 12 25 5 父个体

30、2 123 4 34,子个体1 123 4 5 子个体2 12 4 34,基本遗传算法,实值重组 中间重组 子个体父个体1（父个体2父个体1） 是比例因子，由-d,1+d上均匀分布地随机数产生。 一般取d=0.25。 子代的每个变量均产生一个 。,遗传操作交叉/基因重组,基本遗传算法,实值重组 中间重组示例,遗传操作交叉/基因重组,父个体1 12 25 5 父个体2 123 4 34,子个体1 子个体2,值样本1 0.5 1.1 -0.1 值样本2 0.1 0.8 0.5,120.5（12312）=67.5,67.5,251.1（425）=1.9,1.9,2.1,120.1（12312）=23

31、.1,23.1,8.2,19.5,基本遗传算法,实值重组 中间重组,遗传操作交叉/基因重组,基本遗传算法,实值重组 线性重组,遗传操作交叉/基因重组,父个体1 12 25 5 父个体2 123 4 34,子个体1 子个体2,值样本1 0.5 值样本2 0.1,120.5（12312）=67.5,67.5,250.5（425）=14.5,14.5,19.5,120.1（12312）=23.1,23.1,22.9,7.9,基本遗传算法,实值重组 线性重组,遗传操作交叉/基因重组,基本遗传算法,二进制交叉 单点交叉,遗传操作交叉/基因重组,基本遗传算法,二进制交叉 多点交叉,遗传操作交叉/基因重组,

32、基本遗传算法,实值变异 一般采用： 二进制变异,6 遗传操作变异,4.2 基本遗传算法,运行程序,4.2.7 算法的设计与实现,基本遗传算法,运行程序,算法的设计与实现,4.2 基本遗传算法,运行程序,4.2.7 算法的设计与实现,4.2 基本遗传算法,运行程序,4.2.7 算法的设计与实现,3 遗传算法的改进,改进的途径 改变遗传算法的组成成分； 采用混合遗传算法； 采用动态自适应技术； 采用非标准的遗传操作算子； 采用并行遗传算法等。,遗传算法的改进,改进思路 1991年Eshelman提出的一种改进遗传算法； C：跨代精英选择（Cross generational elitist sel

33、ection）策略； H：异物种重组（Heterogeneous recombination）； C：大变异（Cataclysmic mutation）。,1. CHC算法,遗传算法的改进,选择 上一代种群与通过新的交叉方法产生的个体群混合起来，从中按一定概率选择较优的个体； 即使交叉操作产生较劣个体偏多，由于原种群大多数个体残留，不会引起个体的评价值降低； 可以更好地保持遗传多样性； 排序方法，克服比例适应度计算的尺度问题。,CHC算法,遗传算法的改进,交叉 均匀交叉的改进：当两个父个体位值相异的位数为m时，从中随机选取m/2个位置，实行父个体位值的交换； 显然，这样的操作对模式具有很强的破

34、坏性。 确定一阈值，当个体间距离低于该阈值时，不进行交叉操作。进化收敛的同时，逐渐地减小该阈值。,CHC算法,遗传算法的改进,变异 在进化前期不采取变异操作，当种群进化到一定收敛时期，从最优个体中选择一部分个体进行初始化； 初始化：选择一定比例（扩散率，一般0.35）的基因座，随机地决定它们的位值。,CHC算法,遗传算法的改进,参数分析 交叉概率Pc和变异概率Pm的选择是影响遗传算法行为和性能的关键，直接影响算法的收敛性； Pc越大，新个体产生的速度就越快，但过大会使优秀个体的结构很快被破坏； Pc过小，搜索过程缓慢，以至停止不前； Pm过小，不易产生新个体结构， Pm过大，变成纯粹的随机搜索；,2 自适应遗传算法,遗传算法的改进,自适应策略 Srinvivas等提出一种自适应遗传算法，Pc和Pm能够随适应度自动改变： 当种群各个体适应度趋于一致或趋于局部最优时，使Pc和