大连海事大学《现代优化技术》第9讲：现代启发式算法之遗传算法PPT课件.ppt

现代优化技术
第9讲:现代启发式算法之遗传算法
在生物细胞中,控制并决定生物遗传特性的物质是脱氧核糖核酸,简称DNA。染色体是其载体。
DNA是由四种碱基按一定规则排列组成的长链。四种碱基不同的排列决定了生物不同的表现性状。例如,改变DNA长链中的特定一段(称为基因),即可改变人体的身高。
细胞在分裂时,DNA通过复制而转移到新产生的细胞中,新的细胞就继承了旧细胞的基因。
生物学中的遗传概念
有性生殖生物在繁殖下一代时,两个同元染色体之间通过交叉而重组,亦即在两个染色体的某一相同位置处DNA被切断,其前后两串分别交叉形成两个新的染色体。
在细胞进行复制时可能以很小的概率产生某些复制差错,从而使DNA发生某种变异,产生新的染色体。
这些新的染色体将决定新的个体(后代)的新的性状。
生物学中的遗传概念
在一个群体中,并不是所有的个体都能得到相同的繁殖机会,对生存环境适应度高的个体将获得更多的繁殖机会;对生存环境适应度较低的个体,其繁殖机会相对较少,即所谓自然选择。而生存下来的个体组成的群体,其品质不断得以改良,称为进化。
遗传算法的基本思想和基本概念
基本思想
遗传算法GA把问题的解表示成“染色体”,在算法中即是以一定方式编码的串。并且,在执行遗传算法之前,给出一群“染色体”,也即假设解。然后,把这些假设解置于问题的“环境”中,并按适者生存的原则,从中选择出较适应环境的“染色体”进行复制,再通过交叉,变异过程产生更适应环境的新一代“染色体”群。这样,一代一代地进化,最后就会收敛到最适应环境的一个“染色体”上,它就是问题的最优解。
现代启发式算法之遗传算法
ic Algorithm(遗传算法)
模仿生物遗传进化过程
同时产生复数的可行解
(即,解集团 population)
新的解集团的生成来自于两种基本操作:
交叉(crossover)
变异(mutation).
现代启发式算法之遗传算法
编码(code, representation)
编码:在特定的数据结构下,
从可行解的状态空间到编码解的状态空间的一个映射。
常规码:{0,1}1:包括该项;0:不包括该项。如背包问题
非常规码:非{0,1}向量的表示。如TSP问题的一个都市排列
针对问题设计编码
编码与解码
GA中的编码方法可分为三大类:二进制编码方法、浮点数编码方法和符号编码方法。
二进制编码方案
是GA中最常用的一种编码方法。它所构成的个体基因型是一个二进制编码符号串。
GA的算法过程简述如下。首先在解空间中取一群点,作为遗传开始的第一代。每个点(基因)用一个二进制数字串表示,其优劣程度用适应度函数(fitness function)来衡量。