(第一讲)GA简介.pdf

遗传算法及其应用研究 The Research of Genetic Algorithms(GA) The Research of Genetic Algorithms(GA) and its Applications and its Applications 陕西师范大学计算机科学学院 雷秀娟 陕师大计算机科学学院雷秀娟 1 主要内容 1 遗传算法的生物学基础 2 遗传算法简介 3 遗传算法的发展 4 遗传算法的特点 5 遗传算法的应用 6 作业 陕师大计算机科学学院雷秀娟 2 遗传算法的生物学基础 Holland教授在20世纪70年代初期首先提出遗传算法(genetic algorithms)这个 概念并使其发展起来, 其所借鉴的生物学基础就是生物的遗传和进化。 “适者生存”揭示了大自然生物进化过程中的一个规律——最适合自然环境的群体 往往产生了更大的后代群体。遗传算法主要借用生物进化中“适者生存”的规律。 遗传物质是细胞核中染色体上的有效基因，其中包含了大量的遗传信息。基因是 决定生物特征的最基本的物质单元，基因在染色体上以一定的顺序和结构排列，每个 基因有特殊的位置并控制生物的某些特性。不同的基因组合产生的个体对环境的适应 性不一样，通过基因杂交和突变可以产生对环境适应性强的后代。经过优胜劣汰的自 然选择，适应值高的基因结构就得以保存下来。生物的进化本质体现在染色体的改变 和改进上，生物体自身形态的改变是染色体结构变化的表现形式。 染色体→→DNA→→基因→→交叉、复制→→新个体 陕师大计算机科学学院雷秀娟 3 生物进化过程的发生需要四个基本条件： 存在由多个生物个体组成的种群； 生物个体之间存在着差异，或群体具有多样性； 生物能够自我繁殖； 不同个体具有不同的环境生存能力，具有优良基因结构的个体繁殖能力强， 反之则弱。 生物群体的进化机制包括三种基本形式： 自然选择：控制生物群体行为的发展方向，使适应能力强的个体在种群中数 量不断增加，且使其具有的染色体性状特征得以保留。 杂交 突变：突变是一种不可逆过程，具有突发性、间断性和不可预测性，对于保 证群体的多样性具有不可替代的作用。 另外，生物进化是一个开放的过程，自然界对进化中的生物群体提供及时的 反馈信息，或称为外界对生物的评价。评价反映了生物的生存价值和机会。 陕师大计算机科学学院雷秀娟 4 生物的遗传方式： 1. 复制 1. 复制 生物的主耍遗传方式是复制。遗传过程中，父代的遗传物质DNA被复制到 子代。即细胞在分裂时，遗传物质DNA通过复制(Reproduction)而转移到新生 的细胞中，新细胞就继承了旧细胞的基因。 2. 交叉 2. 交叉 有性生殖生物在繁殖下一代时，两个同源染色体之间通过交叉(Crossover) 而重组，亦即在两个染色体的某一相同位置处DNA被切断，其前后两串分别交 义组合而形成两个新的染色体。 3. 变异 3. 变异 在进行细胞复制时，虽然概率很小，仅仅有可能产生某些复制差错，从而 使DNA发生某种变异(Mutation)，产生出新的染色体。这些新的染色体表现出 新的性状。 陕师大计算机科学学院雷秀娟 5