遗传算法总结报告.doc

遗传算法 一、遗传算法概述 遗传算法(Genetic Algorithm，简称GA)是在20世纪60年代由美国密歇根大学John H.Holland教授及其学生首先提出来的。它的基本思想是模拟生物和人类进化的方法求解复杂的优化问题，因而也称为模拟进化优化算法。 1遗传算法的生物学基础 生物在自然界中的生存繁衍，显示了其对自然环境的优异自适应能力。遗传算法就是这种生物行为过程的计算机模拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力。遗传算法所借鉴的生物学基础就是生物的遗传和进化。 世间的生物从其亲代继承特性或性状，这种生命现象称为遗传(Heredity)，研究这种生命现象的科学叫做遗传学(Genetics)。按照孟德尔和摩根(G.Mendel,T.Morgan)的遗传学理论，遗传物质是作为一种指令密码封装在每个细胞中，并以基因的形式排列在染色体(Chromosome)上，每个基因有特殊的位置并控制生物的某些特性。不同的基因组合产生的的个体对环境的适应性不一样，通过基因杂交和突变可以产生对环境适应性强的后代。经过优胜劣汰的自然选择，适应值高的基因结构就得以保存下来，从而逐渐形成了经典的遗传学染色体理论，揭示了遗传和变异的基本规律。现代遗传学则对基因的本质、功能、结构、突变和调控进行了深入探讨，开辟了遗传工程研究的新领域。在一定的环境影响下，生物物种通过自然选择、基因交换和变异等过程进行繁殖生长，构成了生物的整个进化过程。 生物的遗传物质的主要载体是染色体，DNA是其中最主要的遗传物质，而基因又是控制生物性状的遗传物质的功能单位和结构单位。复数个基因组成染色体，染色体中基因的位置称为基因座(locus)，而基因所取的值则叫做等位基因(alleles)。基因和基因座决定了染色体的特征，也决定了生物个体的性状。此外，染色体有相应的两种表示模式，即基因型(genotype)和表现型(phenotype)。所谓表现型是指生物个体所表现出来的性状，而基因型是指与表现型密切相关的基因组成。同一种基因型的生物个体在不同的环境条件下可以有不同的表现型，因此表现型是基因型与环境条件下相互作用的结果。 基因组合的特异性决定了生物体的多样性，基因结构的稳定性保证了生物物质的稳定性，而基因的杂交和变异使生物进化成为可能。生物的遗传是通过父代向子代传递基因来实现的，而这种遗传信息的改变决定了生物体的变异。 生物进化过程的发生需要四个基本条件：(1)存在由多个生物个体组成的种群；(2)生物个体之间存在着差异，或群体具有多样性；(3)生物能够自我繁殖；(4)不同个体具有不同的环境生存能力，具有优良基因结构的个体繁殖能力强，反之则弱。 生物群体的进化机制可以分为三种基本形式： (1)自然选择：控制生物体群体行为的发展方向，能够适应环境变化的生物个体具有更高的的生存能力，使得它们在种群中的数量不断增加，同时该生物个体所具有的染色体性状特征在自然选择中得以保留。 (2)杂交：通过杂交随机组合来自父代染色体的遗传物质，产生不同于它们父代的染色体。生物进化过程不需要记忆，它所产生的能很好适应自然环境的信息都包含在当前生物体所携带的染色体的基因库中，并且可很好地由子代个体继承下来。 (3)突变：随机改变父代个体的染色体上的基因结构，产生具有新染色体的子代个体。变异是一种不可逆过程，具有突发性、间断性和不可预测性，对于保证群体的多样性具有不可替代的作用。自然界的生物进化是一个不断循环的过程。在这一过程中，生物群体也就不断直接地完善和发展。可见，生物进化过程本质上是一个优化过程，在计算科学上具有直接的借鉴意义。 2遗传算法的特征 遗传算法是进化计算(evolutionary computation，EC)中的一种。进化算法包括三个部分：(1)遗传算法；(2)进化规则(evolutionary strategy，简称ES)；(3)进化策略(evolutionary programming，简称EP)。这三种方法也统称为进化算法(evolutionary algorithm，简称EA)。 进化算法是一种基于自然选择和遗传变异等生物进化机制的全局性概率有哪些信誉好的足球投注网站算法。与基于导数的解析方法和其他启发式有哪些信誉好的足球投注网站方法(如爬山方法，模拟退火方法)一样，进化算法在形式上也是一种迭代方法。它从选定的初始解出发，通过不断迭代逐步改进当前解，直至最后有哪些信誉好的足球投注网站到最优解或满意解。在进化计算中，迭代计算过程模拟了生物体的进化机制，从一组解(群体)出发，评价当前这组解的性能，根据评价结果从当前解中选择一定数量的解作为基因操作的对象，对所选择的解进行基因操作(杂交或称为交叉、突变或称为变异)，生成更好性能指标的下一代解的群体。 进化算法是一种随机有哪些信誉好的足球投注网站方法，在初始解生成以及选择、交叉以及变异等遗传操作过程中，均采