《生物第7章[1].遗传算法》由会员分享，可在线阅读，更多相关《生物第7章[1].遗传算法（27页珍藏版）》请在金锄头文库上搜索。
1、遗传算法 模拟生物在自然环境中的遗传 和化过程而形成的一种自适应全 局优化概率搜索算法。什么是遗传算法 遗传算法是模仿生物遗传学和自然选择机 理，通过人工方式所构造的一类优化搜索 算法，是对生物化过程行的一种数学 仿真，是化计算的最重要的形式。 遗传算法为那些难以找到传统数学模型的 难题指出了一个解决方法。 遗传算法借鉴了生物科学中的某些知识， 这也体现了人工智能这一交叉学科的特点 。遗传算法的起源 遗传算法最早由美国密歇根大学的Holland 教授提出，起源于上世纪60年代对自然和 人工自适应系统的研究。 上世纪70年代，De Jong基于遗传算法的 思想在计算机上行了大量的纯数值函数 优化
2、计算实验。 在一系列研究工作的基础上，上世纪80年 代由Goldberg行归纳总结，形成了遗传 算法的基本框架。遗传算法的应用 函数优化。函数优化是遗传算法的经典应 用领域，也是对遗传算法行性能测试评 价的常用算例。对于一些非线性、多模型 、多目标的函数优化问题，用其他优化方 法较难求解，而遗传算法却可以方便地得 到较好的结果。遗传算法的应用 组合优化。遗传算法是寻求组合优化问题 满意解的最佳工具之一，实践证明，遗传 算法对于组合优化问题中的NP完全问题非 常有效。遗传算法的应用 生产调度问题。生产调度问题在很多情况 下所建立起来的数学模型难以精确求解， 即使经过一些简化之后可以行求解也会 因
3、简化得太多而使求解结果与实际相差太 远。现在遗传算法已经成为解决复杂调度 问题的有效工具。遗传算法的应用 自动控制。遗传算法已经在自动控制领域 中得到了很好的应用，例如基于遗传算法 的模糊控制器的优化设计、基于遗传算法 的参数辨识、基于遗传算法的模糊控制规 则的学习、利用遗传算法行人工神经网 络的结构优化设计和权值学习等。遗传算法的应用 机器人学。机器人是一类复杂的难以精确 建模的人工系统，而遗传算法的起源就来 自于对人工自适应系统的研究，所以机器 人学自然成为遗传算法的一个重要应用领 域。 遗传算法的应用 图象处理。图像处理是计算机视觉中的一 个重要研究领域。在图像处理过程中，如 扫描、特征
4、提取、图像分割等不可避免地 存在一些误差，这些误差会影响图像处理 的效果。如何使这些误差最小是使计算机 视觉达到实用化的重要要求，遗传算法在 这些图像处理中的优化计算方面得到了很 好的应用。 遗传算法的应用 人工生命。人工生命是用计算机、机械等 人工媒体模拟或构造出的具有自然生物系 统特有行为的人造系统。自组织能力和 自学习能力是人工生命的两大重要特征。 人工生命与遗传算法有着密切的关系，基 于遗传算法的化模型是研究人工生命现 象的重要理论基础。基本遗传算法的基本步骤 基本遗传算法（Simple Genetic Algorithms,简称SGA）是一种统一的最基 本的遗传算法，它只使用选择、交
5、叉、变 异这三种基本遗传算子，其遗传化操作 过程简单，容易理解，是其他一些遗传算 法的雏形和基础，它不仅给各种遗传算法 提供了一个基本框架，同时也具有一定的 应用价值。 基本遗传算法的框图初始化种群(t=0)计算适应度的值选择操作t=t+1遗传操作(交叉、变异）结束终止条件SGA的步骤：1.初代种群的生成 根据算法规模，选择N个具有随机染色体的个体。在二 制情况下，即生成规定长度的位串形式编码。 例如，设某数的取值范围是A，B，用t位长的二制码 来表示该数，可将B-A分成2t-1等份，即000000000000=0 A000000000001=1 A+111111111111=2t-1 B 其
6、中， 假设某一个个体的编码是：x：xtxt-1xt-2x2x1则它对应的实数为：2. 适应度的计算 按照预先确定的适应函数对各个个体，计 算其相应的适应函数的值f()。3. 终止条件的测试满足算法停止的最简单的两个条件： 完成了预先给定的化代数则停止； 群体中的最优个体在连续若干代没有改或 平均适应度在连续若干代基本没有改时停 止。4. 选择操作 从第t代中选择N个入t+1代的个体。选择 按比例选择方式行，即“转轮盘”。比例选择的具体执行过程： 先计算出群体中所有个体的适应度之和； 其次计算出每个个体的相对适应度的大小 ，此值即为各个个体被遗传到下一代群体 中的概率；比例选择的具体执行过程：
7、最后再根据个体总数N，来决定各个个体 入下一代的个数。其中，Ni是个体入下一代的期望个数，是平均适应度。 例如，某种群有四个个体X1-X4， 其适应度如下表所 示： 个体 适应度 f()选择概率 p()入下一 代的Ni数实际被选 择的个数 X11500.4051.622 X2800.210.841 X3400.110.440 X41000.271.0815. 遗传操作 交叉操作的简单方式是将被选择出的两个个体P1 和P2作为父母个体，将两者的部分码值行交换 。 例如，有两个8位的二制码个体：1 0 0 0 1 1 1 0 1 1 0 1 1 0 0 1根据随机产生的交叉位数，如3，行低3位的交
8、 换。得到1 0 0 0 1 0 0 1 和1 1 0 1 1 1 1 0 这就是它们的后代。变异操作 变异操作的简单方式是改变数码串的某个 位置上的数码。二制编码表示的简单变 异操作是将0与1互换：0变异为1，1变异为 0。 例如，某个码长为8位二制的个体，1 0 1 0 0 1 1 0根据随机产生的变异位数，如5，改变第5 位的值，由0变1。得到1 0 1 1 0 1 1 0基本遗传算法的运行参数 基本遗传算法有下述4个运行参数需要提前 设定：种群大小N，即群体中所含个体数目 ，一般取为20100；遗传运算的终止化 代数T，一般取为100500； 交叉概率Pc， 一般取为0.40.99；
9、变异概率Pm，一般取 为0.00010.1。 简单函数最优化举例 利用SGA算法，在区间-6.4, 6.3上求下 列函数的最大值。各参数的设定 设定种群的规模N=10，交叉率pc=0.6，变 异率pm=0.006。 用二制编码表示种群中的每一个染色体， 来代表变量x的实数值。矢量的长度取决于 本题所要求的精度，取小数点后1位。 这样-6.4，6.3的区间将被均匀分为个等长的区间。由于27=128，所以码长7位 。 假设某一个个体的编码是：x：x7x6x5x2x1则它对应的实数为：遗传操作的过程 首先，随机地生成初始种群；然后按f(x)分 别计算各个个体的适应度的值；再行终止 条件的测试；最后按pc、pm等参数行“选 择交叉变异”等遗传操作。 经过8次迭代，得到了最优解x=1000000， 它对应的实数值为：
