遗传算法原理及其应用

《遗传算法原理及其应用》由会员分享，可在线阅读，更多相关《遗传算法原理及其应用（35页珍藏版）》请在金锄头文库上搜索。

1、Genial USTC http:/ 遗传算法原理及其应用遗传算法原理及其应用 1207 Chap1 序论序论 一一. 遗传算法的生物学基础遗传算法的生物学基础 1.1 遗传与变异 基本概念 Cell:细胞 Chromosome:染色体 Gene:基因 Locus:基因座 Allele:等位基因 Genotype:基因型 Phenotype:表现型 Genome:基因组 Reproduction:复制 Crossover:交叉 Mutation:变异 1.2 进化 基本术语 Evolution:进化 Population:群体 Individual:个体 Fitness:适应度 1.3 遗传与

2、进化的系统观 特点: 1) 生物的所有遗传信息都包含在其染色体中,染色体决定了生物的性状; 2) 染色体是基因及其有规律的排列所构成,遗传和进化过程发生在染色体上; 3) 生物的繁殖过程是由其基因的复制过程完成的; 4) 通过同源染色体之间的交叉或染色体的变异会产生新的物种,使生物呈现新的性状; 5) 对环境适应性好的基因或者染色体会经常比适应性差的基因或染色体有更多的机会遗 传到下一代。 二二. 遗传算法简介遗传算法简介 遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率Genial USTC http:/ 搜索算法。 2.1 遗传算法概要 对于一个求函数最大值的优

3、化问题（求函数最小值也类同） ，一般可描述为下述数学规划模型：max() . .f X stXRRU 式中，12 ,.,TnXx xx= 为决策变量，f（X）为目标函数目标函数，第 2，3 式为约束条件约束条件，U 是基本空间基本空间，R 是 U 的一个子集。满足约束条件的解 X 称为可行解可行解，集合 R 表示由所有满足 约束条件的解所组成的一个集合，叫做可行解集合可行解集合。 对上述最优化问题，目标函数和约束条件种类繁多，由的是线性的，有的是非线性的； 有的是连续的，有的是离散的；有点是单峰的，有的是多峰的。 求最优解或近似最优解的方法主要有三种：枚举法，启发式算法和搜索算法： 1） 枚举

4、法：枚举法：枚举出可行解集合内的所有的可行解，以求出精确最优解。对于连续函数，首先要求对其进行离散化处理。该法效率较低。 2） 启发式算法：启发式算法：寻求一种能产生可行解的启发式规则，以找到一个最优解或近似 最优解。此法对每个问题都必须找出其特有的启发式规则，不具有通用性。 3） 搜索算法：搜索算法：寻求一种搜索算法，该算法在可行解集合的一个子集内进行搜索操 作，以找到问题的最优或者近似最优解。若适当利用一些启发式知识，可以在 近似解的质量和求解效率上达到一种较好的平衡。 遗传算法中，将 n 维决策向量12 ,.,TnXx xx= 用 n 个记号 Xi (i=1,2,n) 所组成的符号串 X

5、 表示： 1212. ,.,TnnXX XXXx xx=1212. ,.,TnnXX XXXx xx= ,把每一个 Xi 看作一个遗传基因遗传基因，它的所有的可能取值称为等位基因等位基因。这样,X 就可看做 是由 n 个遗传基因组成的一个染色体染色体。一般情况下，染色体的长度 n 是固定的，但对 一些问题你也可以是变化的。根据不同的情况，这里的等位基因可以是一组整数，也 可以是某一范围内的实数值，或者纯粹的一个记号。最简单的等位基因是由 0 和 1 这 两个整数组成的，相应的染色体就可以表示为一个二进制符号串。这种编码形成的排 列形式 X 就是个体的基因型基因型，与之对应的 X 值就是个体的表

6、现型表现型。个体的适应度与其 对应的个体表现型 X 的目标函数值相关联，X 越接近于目标函数的最优点，其适应度 越大；反之，其适应度越小。 遗传算法中，决策变量 X 组成了问题的解空间。对问题最优解的搜索是通过对染色体X 的搜索过程来进行的，从而由所有的染色体 X 就组成了问题的搜索空间。遗传算法的运 算过程也是一个反复迭代过程，第 t 代群体记做 P(t), 经过一代遗传和进化后，得到第 t1 代群体，它们也是由多个个体组成的集合，记做 P(t1)。 1208 遗传算法中最优解的搜索过程也是模仿生物的进化过程， 通过染色体之间的交叉和染色 体的变异来完成。通过所谓的遗传算子（genetic

7、operators）作用于群体 P（t）中，进行遗传Genial USTC http:/ 操作，从而得到新一代群体 P(t1)。 A. 选择（选择（selection） ：） ： 根据各个个体的适应度，按照一定的规则或方法，从第 t 代群体 P(t)中选择出一些优良的个体遗传到下一代群体 P(t1)中。 B. 交叉（交叉（crossover） ：） ：将群体 P（t）内的各个个体随机搭配成对，对每一对个体， 以某个概率（称为交叉概率，crossover rate）交换他们之间的染色体。 C. 变异（变异（mutation） ：） ：对群体 P(t)中的每一个个体，以某一概率（称为变异概率， m

8、utation rate）改变某一个或某一些基因座上的基因值为其他的等位基因。 图 12 所示为遗传算法的运算过程示意图： 由该图可以看出，使用上述三种遗传算子（选择算子，交叉算子，变异算子）的遗传算 法的主要运算过程如下所述： 步骤一：初始化。 设置进化代数计数器 tT，则以进化过程 中得到的具有最大适应度的个体作为最优解输出，终止计算。 Genial USTC http:/ 22 遗传算法的手工模拟计算示例 求下述二元函数的最大值： 现对其主要运算过程作如下解释： 1） 个体编码。 遗传算法的运算对象是表示个体的符号串，所以必须把变量 x1，x2编 码为一种符号串。该例中，x1，x2取 0

9、7 之间的整数，可分别用 3 位无符号二进制整数来 表示， 将它们连接在一起所组成的 6 位无符号二进制整数就形成了个体的基因型， 表示一个 可行解。例如，基因型 X=101110 所对应的表现型是：X=5,6T。个体的表现型 x 和基因型 X 之间可通过编码和解码程序相互转换。 2）初始群体的产生。 遗传算法是对群体进行的进化操作，需要给其准备一些表示其实 搜索点的初始群体数据。本例中，群体规模的大小取为 4，即群体由 4 个个体组成，每个个体可通过随机方法产生。一个随机产生的初始群体如表 11 中第栏所示。 3）适应度计算。 遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决 定

10、其遗传机会的大小。结合本例情况，可直接用目标函数值作为个体的适应度。为计算函数 的目标值，需对个体基因型 X 进行解码。表 12 中第，栏所示为初始群体中各个个体 的解码结果，第栏所示为各个个体所对应的目标函数值，它也示个体的适应度，第栏还 给出了群体中适应度的最大值和平均值。 4）选择运算。 选择运算（或称之为复制运算）把当前群体中适应度较高的个体按某种 规则或模型遗传到下一代群体中。 一般要求适应度较高的个体将有更多的机会遗传到下一代 群体中。本例中，采用与适应度成正比的概率来确定各个个体复制到下一代群体中的数量。其具体操作过程是：先计算出群体中所有个体的适应度的总和if；其次，计算出各个

11、个体的相对适应度的大小/iiff，如表中第栏所示，它即为每个个体被遗传到下一代群体中的概率，每个概率值组成一个区域，全部概率值之和为 1；最后再产生一个 0 到 1 的随机数，依据该随机数落在哪个区域内就选择哪个个体。如表中第，栏所示为一个随机 产生的选择结果。 5） 交叉运算。 交叉运算是遗传算法中产生新个体的主要操作过程，它以某一概率相 互交换某两个个体之间的部分染色体。本例采用单点交叉的方法，其具体操作过程是：先对 群体进行随机配对，如表中第栏所示为一种随机配对情况；其次随机设置的交叉位置，如 表中第栏所示为一随机产生的交叉点位置，其中的数字表示交叉点设置在该基因座之后；最后在相互交换配

12、对染色体之间的部分基因。表中第栏所示为交叉运算的结果。 6） 变异运算。 变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的 概率进行改变，它也是产生新个体的一种操作方法。本例中，采用基本位变异的方法来进行 变异运算，具体操作过程是：首先确定出各个个体的基因变异位置，表中第（12）栏所示为 随机产生的变异点位置， 其中的数字表示变异点在该基因座处； 然后依照某一概率将变异点 的原有基因值取反。表中第（13）栏所示为变异结果。 Genial USTC http:/ 对群体 P(t)进行一轮选择，交叉，变异运算后可得到新一代的群体 P(t1)。 三遗传算法的特点三遗传算法的特点 为了解决

13、各种优化计算问题，人们提出了各种优化算法，如单纯形法，梯度法，动 态规划法，分枝定界法等。而遗传算法是一类可用于复杂系统优化计算的鲁棒搜索算法，其 特点如下： 1 遗传算法以决策变量的编码作为运算对象。 2 遗传算法直接以目标函数值作为搜索信息。 3 遗传算法同时使用多个搜索点的搜索信息。 4 遗传算法使用概率搜索技术。 四遗传算法的发展四遗传算法的发展 1J.H.Holland 遗传算法的基本定理模式定理（Schema Theorem） 2. J.D.Bagley 在遗传算法的不同阶段采用不同的选择率，有利于防止早熟。 3. K.A.De Jong 定义了评价遗传算法性能的在线指标和离线指标

14、。 4. D.J.Goldberg 搜索，优化和机器学习中的遗传算法 5. J. R. Koza 遗传编程（Genetic Programming , 1992） Genial USTC http:/ 五遗传算法的应用五遗传算法的应用 1 函数优化。 2 组合优化。 3 生产调度问题。 4 自动控制。 5 机器人学习。 6 图像处理。 7 人工生命。 8 遗传编程。 9 机器学习。 Chap2 基本遗传算法基本遗传算法 一基本遗传算法描述一基本遗传算法描述 Goldberg 总结出了一种统一的最基本的遗传算法基本遗传算法（Simple Genetic Algorithms，简称 SGA） ，只

15、使用选择算子，交叉算子和变异算子这三种基本遗传算子。 1基本遗传算法的构成要素基本遗传算法的构成要素 1） 染色体编码方法。染色体编码方法。 基本遗传算法使用固定长度的二进制符号串儿来表示群体中 的个体， 其等位基因是由二值符号集0,1所组成的。 初始群体中各个个体的基因 值可用均匀分布的随机数来生成。 2） 个体适应度评价。个体适应度评价。 基本遗传算法按与个体适应度成正比的概率来决定当前群体 中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，这里要求所 有个体的适应度必须为正或零。至于，必须预先确定好由目标函数值到个体适应 度之间的转换规则，特别是要预先确定好当目标函数值为负数时的处理。 3） 遗传算子。遗传算子。 使用下述三种遗传算子： A. 选择运算使用比例选择算子； B. 交叉运算使用单点交叉算子； C变异运算使用基本位变异算子或均匀变异算