数学建模基本遗传算法入门ppt课件.ppt

《数学建模基本遗传算法入门ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基本遗传算法GeneticAlgorithm(GA)Introduction生物在自然界中的生存繁衍，显示出了其对自然环境的自适应能力。受其启发，人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计和开发提供了广阔的前景。遗传算法(GeneticAlgorithms，简称GA)就是这种生物行为的计算机模拟中令人瞩目的重要成果。基于对生物遗传和进化过程的计算机模拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力。遗传算法所借鉴的生物学基础就是生物的遗传和进化。遗传与变异遗传(Heredity)——世间的生物从其父代继承特性或性状，这种生命现象就称为遗

2、传(Heredity)，由于遗传的作用，使得人们可以种瓜得瓜、种豆得豆，也使得鸟仍然是在天空中飞翔，鱼仍然是在水中邀游。1遗传算法的生物学基础•构成生物的基本结构和功能的单位是细胞(Ce11)。•细胞中含有的一种微小的丝状化合物称为染色体(Chromosome)，生物的所有遗传信息都包含在这个复杂而又微小的染色体中。•基因经过生物学家的研究，控制并决定生物遗传性状的染色体主要是由一种叫做脱氧核糖核酸(简称DNA)的物质所构成。基因就是DNA长链结构中占有一定位置的基本遗传单位。•遗传信息是由基因(Gene)组成的，生物的各种性状由其相应的基因所控制。•基因是遗传的基本单位。细

3、胞通过分裂具有自我复制的能力，在细胞分裂的过程中，其遗传基因也同时被复制到下一代，从而其性状也被下一代所继承。1遗传算法的生物学基础生物的遗传方式：1.复制生物的主耍遗传方式是复制。遗传过程中，父代的遗传物质DNA被复制到子代。即细胞在分裂时，遗传物质DNA通过复制(Reproduction)而转移到新生的细胞中，新细胞就继承了旧细胞的基因。2.交叉有性生殖生物在繁殖下一代时，两个同源染色体之间通过交叉(Crossover)而重组，亦即在两个染色体的某一相同位置处DNA被切断，其前后两串分别交义组合而形成两个新的染色体。3.变异在进行细胞复制时，虽然概率很小，仅仅有可能产生某

4、些复制差错，从而使DNA发生某种变异(Mutation)，产生出新的染色体。这些新的染色体表现出新的性状。如此这般，遗传基因或染色体在遗传的过程中由于各种各样的原因而发生变化。1遗传算法的生物学基础进化地球上的生物，都是经过长期进化而形成的。根据达尔文的自然选择学说，地球上的生物具有很强的繁殖能力。在繁殖过程中，大多数生物通过遗传，使物种保持相似的后代；部分生物由于变异，后代具有明显差别，甚至形成新物种。正是由于生物的不断繁殖后代，生物数目大量增加，而自然界中生物赖以生存的资源却是有限的。因此，为了生存，生物就需要竞争。生物在生存竞争中，根据对环境的适应能力，适者生存，不适者

5、消亡。自然界中的生物，就是根据这种优胜劣汰的原则，不断地进行进化。•生物的进化是以集团的形式共同进行的，这样的一个团体称为群体(Population)，或称为种群。•组成群体的单个生物称为个体(Individual)，•每一个个体对环境都有不同的适应能力，这种适应能力称为个体的适应度(Fitness)。1遗传算法的生物学基础将n维决策向量X＝[x1,x2,…,xn]T用n个记号Xi(i=1,2,…,n))所组成的符号串X来去示：X＝xlx2…xnX＝[x1，x2，…,xn]T•把每一个xi看作一个遗传基因，这样，X就可看做是由n个遗传基因所组成的一个染色体。•这里的等位基因

6、可以是一组整数。也可以是某一范围内的实数值，或者是纯粹的一个记号。最简单的等位基因是由0和1这两个整数组成的，相应的染色体就可表示为一个二进制符号串。•这种编码所形成的排列形式X是个体的基因型，与它对应的X值是个体的表现型。•对于每一个个体X，要按照一定的规则确定出其适应度，个体的适应度与其对应的个体表现型X的目标函数值相关联，X越接近于目标函数的最优点，其适应度越大；反之，其适应度越小。2遗传算法中的概念遗传算法中，决策变量X组成了问题的解空间。对问题最优解的搜索是通过对染色体X的搜索过程来进行的。从而所有的染色体X就组成了问题的搜索空间。生物的进化是以集团为主体的。与此相

7、对应，遗传算法的运算对象是由M个个体所组成的集合，称为群体（或称种群）。与生物一代一代的自然进化过程相类似，遗传算法的运算过程也是一个反复迭代过程：第t代群体记做P(t)，经过一代遗传和进化后，得到t+1代群体，记做P(t+1),这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应度较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体X，它所对应的表现型X将达到或接近于问题的最优解X*。2遗传算法中的概念(1)染色体编码方法基本遗传算法使用固定长度的二进制符号串来表示群体