遗传算法综述.doc

1 目目 录录 1 1 遗传算法的定义和起源遗传算法的定义和起源 1 1 2 2 遗传算遗传算法法的的特特点点 3 3 3 3 遗传算法的基本原理遗传算法的基本原理 4 4 4 4 遗传算法的基本流程遗传算法的基本流程 7 7 5 5 遗传算法的步骤和意义遗传算法的步骤和意义 9 9 6 6 遗传算法的收敛性遗传算法的收敛性 1313 7 7 遗传算法的现状遗传算法的现状 1313 8 8 遗传算法的展望遗传算法的展望 1414 9 9 遗传算法的特点遗传算法的特点 1616 1010 遗传算法的适用问题和应用领域遗传算法的适用问题和应用领域 1717 1111 遗传算法在神经网络中的应用遗传算法在神经网络中的应用 1818 1212 遗传算法的相关技术遗传算法的相关技术 2020 参考文献参考文献 2121 1 遗传算法综述遗传算法综述 1 1 遗传算法的定义和起源遗传算法的定义和起源 遗传算法 Genetic Algorithm 是模拟达尔文生物进化论的自然选择 和遗传学机理的生物进化过程的计算模型 是一种通过模拟自然进化过程 搜索最优解的方法 由密歇根大学的约翰 霍兰德和他的同事于二十世纪六 十年代在对细胞自动机 英文 cellular automata 进行研究时率先提出 并于 1975 年出版了颇有影响的专著 Adaptation in Natural and Artificial Systems GA 这个名称才逐渐为人所知 约翰 霍兰德教授所 提出的 GA 通常为简单遗传算法 SGA 在二十世纪八十年代中期之前 对 于遗传算法的研究还仅仅限于理论方面 直到在伊利诺伊大学召开了第一 届世界遗传算法大会 随着计算机计算能力的发展和实际应用需求的增多 遗传算法逐渐进入实际应用阶段 1989 年 纽约时报作者约翰 马科夫写了 一篇文章描述第一个商业用途的遗传算法 进化者 英文 Evolver 之 后 越来越多种类的遗传算法出现并被用于许多领域中 财富杂志 500 强 企业中大多数都用它进行时间表安排 数据分析 未来趋势预测 预算 以及解决很多其他组合优化问题 遗传算法是从代表问题可能潜在的解集的一个种群 population 开 始的 而一个种群则由经过基因 gene 编码的一定数目的个体 individual 组成 每个个体实际上是染色体 chromosome 带有特征的实 体 染色体作为遗传物质的主要载体 即多个基因的集合 其内部表现 即基因型 是某种基因组合 它决定了个体的形状的外部表现 如黑头 1 发的特征是由染色体中控制这一特征的某种基因组合决定的 因此 在一 开始需要实现从表现型到基因型的映射即编码工作 由于仿照基因编码的 工作很复杂 我们往往进行简化 如二进制编码 初代种群产生之后 按 照适者生存和优胜劣汰的原理 逐代 generation 演化产生出越来越好 的近似解 在每一代 根据问题域中个体的适应度 fitness 大小选择 selection 个体 并借助于自然遗传学的遗传算子 genetic operators 进行组合交叉 crossover 和变异 mutation 产生出代表 新的解集的种群 这个过程将导致种群像自然进化一样的后生代种群比前 代更加适应于环境 末代种群中的最优个体经过解码 decoding 可以作 为问题近似最优解 1 遗传算法是借鉴生物界的进化规律 适者生存 优胜劣汰遗传机制 演化而来的 其主要特点是直接对结构对象进行操作 不存在求导和函数 连续性的限定 具有内在的隐并行性和更好的全局寻优能力 采用概率化 的寻优方法 能自动获取和指导优化的搜索空间 自适应地调整搜索方向 不需要确定的规则 遗传算法的这些性质 已被人们广泛地应用于组合优 化 机器学习 信号处理 自适应控制和人工生命等领域 它是现代有关 智能计算中的关键技术 对于一个求函数最大值的优化问题 求函数最小值也类同 一般可以 描述为下列数学规划模型 式中为决策变量 为目标函数式 式 2 2 2 3 为约束条件 U 是基本空 间 R 是 U 的子集 满足约束条件的解 X 称为可行解 集合 R 表示所有满足 2 约束条件的解所组成的集合 称为可行解集合 遗传算法的基本运算过程如下 a 初始化 设置进化代数计数器 t 0 设置最大进化代数 T 随机生成 M 个 个体作为初始群体 P 0 b 个体评价 计算群体 P t 中各个个体的适应度 c 选择运算 将选择算子作用于群体 选择的目的是把优化的个体直接遗 传到下一代或通过配对交叉产生新的个体再遗传到下一代 选择操作是建 立在群体中个体的适应度评估基础上的 d 交叉运算 将交叉算子作用于群体 所谓交叉是指把两个父代个体的部 分结构加以替换重组而生成新个体的操作 遗传算法中起核心作用的就是 交叉算子 e 变异运算 将变异算子作用于群体 即是对群体中的个体串的某些基因 座上的基因值作变动 群体 P t 经过选择 交叉 变异运算之后得到下一代群体 P t 1 f 终止条件判断 若 tT 则以进化过程中所得到的具有最大适应度个体作为 最优解输出 终止计算 2 2 遗传算法的特点遗传算法的特点 由上所述遗传算法是以自然界种群进化为原型的一种智能计算方法 它是 一种基于群体的搜索算法 在具体的搜索过程当中 遗传算法具有以下特点 1 遗传算法从问题解的中集开始嫂索 而不是从单个解开始 这是遗传算法与传统优化算法的极大区别 传统优化算法是从单个初始值 3 迭代求最优解的 容易误入局部最优解 遗传算法从串集开始搜索 复盖面大 利于全局择优 2 遗传算法求解时使用特定问题的信息极少 容易形成通用算法程序 由于遗传算法使用适应值这一信息进行搜索 并不需要问题导数等与问题 直接相关的信息 遗传算法只需适应值和串编码等通用信息 故几乎可处理任 何问题 3 遗传算法有极强的容错能力 遗传算法的初始串集本身就带有大量与最优解甚远的信息 通过选择 交 叉 变异操作能迅速排除与最优解相差极大的串 这是一个强烈的滤波过程 并且是一个并行滤波机制 故而 遗传算法有很高的容错能力 4 遗传算法中的选择 交叉和变异都是随机操作 而不是确定的精确规则 这说明遗传算法是采用随机方法进行最优解搜索 选择体现了向最优解迫 近 交叉体现了最优解的产生 变异体现了全局最优解的复盖 5 遗传算法具有隐含的并行性 4 3 遗传算法的遗传算法的基本原理基本原理 在遗传算法里 优化问题的解被称为个体 它表示为一个参数列表 叫做染色体或者基因串 染色体一般被表达为简单的字符串或数字串 不 过也有其他的表示方法适用 这一过程称为编码 一开始 算法随机生成 一定数量的个体 有时候操作者也可以对这个随机产生过程进行干预 播 下已经部分优化的种子 在每一代中 每一个个体都被评价 并通过计算 4 适应度函数得到一个适应度数值 种群中的个体被按照适应度排序 适应 度高的在前面 这里的 高 是相对于初始的种群的低适应度来说的 下一步是产生下一代个体并组成种群 这个过程是通过选择和繁殖完 成的 其中繁殖包括交配 crossover 和突变 mutation 选择则是根据新 个体的适应度进行的 适应度越高 被选择的机会越高 而适应度低的 被选择的机会就低 初始的数据可以通过这样的选择过程组成一个相对优 化的群体 之后 被选择的个体进入交配过程 一般的遗传算法都有一个 交配概率 范围一般是 0 6 1 这个交配概率反映两个被选中的个体进行交 配的概率 例如 交配概率为 0 8 则 80 的 夫妻 会生育后代 每两个 个体通过交配产生两个新个体 代替原来的 老 个体 而不交配的个体 则保持不变 交配父母的染色体相互交换 从而产生两个新的染色体 第 一个个体前半段是父亲的染色体 后半段是母亲的 第二个个体则正好相 反 不过这里的半段并不是真正的一半 这个位置叫做交配点 也是随机 产生的 可以是染色体的任意位置 再下一步是突变 通过突变产生新的 子 个体 一般遗传算法都有一个固定的突变常数 通常是 0 1 或者更 小 这代表变异发生的概率 根据这个概率 新个体的染色体随机的突变 通常就是改变染色体的一个字节 0 变到 1 或者 1 变到 0 经过这一系列的过程 选择 交配和突变 产生的新一代个体不同于 初始的一代 并一代一代向增加整体适应度的方向发展 因为最好的个体 总是更多的被选择去产生下一代 而适应度低的个体逐渐被淘汰掉 这样 的过程不断的重复 每个个体被评价 计算出适应度 两个个体交配 然 后突变 产生第三代 周而复始 直到终止条件满足为止 一般终止条件 5 有以下几种 进化次数限制 计算耗费的资源限制 例如计算时间 计算占用的内存等 一个个体已经满足最优值的条件 即最优值已经找到 适应度已经达到饱和 继续进化不会产生适应度更好的个体 人为干预 以及以上两种或更多种的组合 3 长度为 L 的 n 个二进制串 bi i 1 2 n 组成了遗传算法的初解 群 也称为初始群体 在每个串中 每个二进制位就是个体染色体的基因 根据进化术语 对群体执行的操作有三种 1 选择 Selection 这是从群体中选择出较适应环境的个体 这些选中的个体用于繁殖下 一代 故有时也称这一操作为再生 Reproduction 由于在选择用于繁殖 下一代的个体时 是根据个体对环境的适应度而决定其繁殖量的 故而有 时也称为非均匀再生 differential reproduction 2 交叉 Crossover 这是在选中用于繁殖下一代的个体中 对两个不同的个体的相同位置 的基因进行交换 从而产生新的个体 3 变异 Mutation 这是在选中的个体中 对个体中的某些基因执行异向转化 在串 bi 中 如果某位基因为 1 产生变异时就是把它变成 0 反亦反之 遗传算法的原理可以简要给出如下 6 choose an intial population determine the fitness of each individual perform selection repeat perform crossover perform mutation determine the fitness of each individual perform selection until some stopping criterion applies 这里所指的某种结束准则一般是指个体的适应度达到给定的阀值 或 者个体的适应度的变化率为零 4 4 遗传算法的基本流程遗传算法的基本流程 1 GA 的流程图 GA 的流程图如下图所示 7 2 编码 遗传算法不能直接处理问题空间的参数 必须把它们转换成遗传空间的由 基因按一定结构组成的染色体或个体 这一转换操作就叫做编码 也可以称作 问题的 表示 representation 评估编码策略常采用以下 3 个规范 a 完备性 completeness 问题空间中的所有点 候选解 都能作为 GA 空间 中的点 染色体 表现 b 健全性 soundness GA 空间中的染色体能对应所有问题空间中的候选 解 c 非冗余性 nonredundancy 染色体和候选解一一对应 目前的几种常用的编码技术有二进制编码 浮点数编码 字符编码 变成 编码等 而二进值编码是目前遗传算法中最常用的编码方法 即是由二进值字符集 0 1 产生通常的 0 1 字符串来表示问题空间的候选解 它具有以下特点 a 简单易行 b 符合最小字符集编码原则 c 便于用模式定理进行分析 因为模式定理就是以基础的 3 适应度函数 进化论中的适应度 是表示某一个体对环境的适应能力 也表示该个体繁 殖后代的能力 遗传算法的适应度函数也叫评价函数 是用来判断群体中的个 体的优劣程度的指标 它是根据所求问题的目标函数来进行评估的 遗传算法在搜索进化过程中一般不需要其他外部信息 仅用评估函数来评 8 估个体或解的优劣 并作为以后遗传操作的依据 由于遗传算法中 适应度函 数要比较排序并在此基础上计算选择概率 所以适应度函数的值要取正值 由此 可见 在不少场合 将目标函数映射成求最大值形式且函数值非负的适应度函 数是必要的 适应度函数的设计主要满足以下条件 a 单值 连续 非负 最大化 b 合理 一致性 c 计算量小 d 通用性强 在具体应用中 适应度函数的设计要结合求解问题本身的要求而定 适应 度函数设计直接影响到遗传算法的性能 4 初始群体的选取 遗传算法中初始群体中的个体是随机产生的 一般来讲 初始群体的设定 可采取如下的策略 a 根据问题固有知识 设法把握最优解所占空间在整个问题空间中的分布 范围 然后 在此分布范围内设定初始群体 b 先随机生成一定数目的个体 然后从中挑出最好的个体加到初始群体中 这种过程不断迭代 直到初始群体中个体数达到了预先确定的规模 2 5 遗遗传传算算法法的的步步骤骤和和意意义义 4 1 初始化 选择一个群体 即选择一个串或个体的集合 bi i 1 2 n 这个初始 9 的群体也就是问题假设解的集合 一般取 n 30 160 通常以随机方法产生串 或个体的集合 bi i 1 2 n 问题的最优解将通过这些初始假设解进化而 求出 2 选择 根据适者生存原则选择下一代的个体 在选择时 以适应度为选择原则 适应度准则体现了适者生存 不适应者淘汰的自然法则 给出目标函数 f 则 f bi 称为个体 bi 的适应度 以 3 86 为选中 bi 为下一代个体的次数 显然 从式 3 86 可知 1 适应度较高的个体 繁殖下一代的数目较多 2 适应度较小的个体 繁殖下一代的数目较少 甚至被淘汰 这样 就产生了对环境适应能力较强的后代 对于问题求解角度来讲 就是选 择出和最优解较接近的中间解 3 交叉 10 对于选中用于繁殖下一代的个体 随机地选择两个个体的相同位置 按交 叉概率 P 在选中的位置实行交换 这个过程反映了随机信息交换 目的在于 产生新的基因组合 也即产生新的个体 交叉时 可实行单点交叉或多点交叉 例如有个体 S1 100101 S2 010111 选择它们的左边 3 位进行交叉操作 则有 S1 010101 S2 100111 一般而言 交叉幌宰 P 取值为 0 25 0 75 4 变异 根据生物遗传中基因变异的原理 以变异概率 Pm 对某些个体的某些位执行 变异 在变异时 对执行变异的串的对应位求反 即把 1 变为 0 把 0 变为 1 11 变异概率 Pm 与生物变异极小的情况一致 所以 Pm 的取值较小 一般取 0 01 0 2 例如有个体 S 101011 对其的第 1 4 位置的基因进行变异 则有 S 001111 单靠变异不能在求解中得到好处 但是 它能保证算法过程不会产生无法 进化的单一群体 因为在所有的个体一样时 交叉是无法产生新的个体的 这 时只能靠变异产生新的个体 也就是说 变异增加了全局优化的特质 5 全局最优收敛 Convergence to the global optimum 当最优个体的适应度达到给定的阀值 或者最优个体的适应度和群体适应 度不再上升时 则算法的迭代过程收敛 算法结束 否则 用经过选择 交叉 变异所得到的新一代群体取代上一代群体 并返回到第 2 步即选择操作处继续 循环执行 12 图 3 7 中表示了遗传算法的执行过程 6 遗传算法的收敛性遗传算法的收敛性 一些研究人员对进化算法的运行机理进行过研究 Radolph 在文献 1 中证明 了一般的遗传算法不一定收敛 只有每代保存了最优个体时才收敛 在实际应 用中 使用了上述结论来保证收敛性 采用优秀个体保护法就是将每代中的最 优个体 直接进入子代 相应淘汰其子代中适应度最差的个体 使种群规模不 变 对保存最优个体时遗传算法是收敛的结论的证明是通过对遗传算法构造马 尔柯夫 markov 链 因为遗传算法的进行过程是一个马尔柯夫过程 当遗传算法收敛时 求到的解通常只是所要解决问题的最优解的一个近似 解 或者叫满意解 从数学分析的角度看 收敛过程是一个无限逼近过程 而 计算过程是一个有限自动机 因此通过遗传算法程序求得的解总是一个近似解 近似解与问题真正的最优解的差是一个统计意义下的量 也就是说每次程序运 13 行得到的解的质量可能是有较大的差别的 7 7 遗传算法的优缺点遗传算法的优缺点 优点 1 与问题领域无关切快速随机的搜索能力 2 搜索从群体出发 具有潜在的并行性 可以进行多个个体的同时比较 robust 3 搜索使用评价函数启发 过程简单 4 使用概率机制进行迭代 具有随机性 5 具有可扩展性 容易与其他算法结合 缺点 1 没有能够及时利用网络的反馈信息 故算法的搜索速度比较慢 要得要较精 确的解需要较多的训练时间 2 算法对初始种群的选择有一定的依赖性 能够结合一些启发算法进行改进 3 算法的并行机制的潜在能力没有得到充分的利用 这也是当前遗传算法的一 个研究热点方向 8 8 遗遗传传算算法法的的现现状状 进入 90 年代 遗传算法迎来了兴盛发展时期 无论是理论研究还是应用研 究都成了十分热门的课题 尤其是遗传算法的应用研究显得格外活跃 不但它 的应用领域扩大 而且利用遗传算法进行优化和规则学习的能力也显著提高 同时产业应用方面的研究也在摸索之中 此外一些新的理论和方法在应用研究 14 中亦得到了迅速的发展 这些无疑均给遗传算法增添了新的活力 遗传算法的 应用研究已从初期的组合优化求解扩展到了许多更新 更工程化的应用方面 随着应用领域的扩展 遗传算法的研究出现了几个引人注目的新动向 一 是基于遗传算法的机器学习 这一新的研究课题把遗传算法从历来离散的搜索 空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法 这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带 来了希望 二是遗传算法正日益和神经网络 模糊推理以及混沌理论等其它智 能计算方法相互渗透和结合 这对开拓 21 世纪中新的智能计算技术将具有重要 的意义 三是并行处理的遗传算法的研究十分活跃 这一研究不仅对遗传算法 本身的发展 而且对于新一代智能计算机体系结构的研究都是十分重要的 四 是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透 所谓人工生命 即是用计算机模拟自然界丰富多彩的生命现象 其中生物的自适应 进化和免 疫等现象是人工生命的重要研究对象 而遗传算法在这方面将会发挥一定的作 用 五是遗传算法和进化规划 Evolution Programming EP 以及进化策略 Evolution Strategy ES 等进化计算理论日益结合 EP 和 ES 几乎是和遗传 算法同时独立发展起来的 同遗传算法一样 它们也是模拟自然界生物进化机 制的智能计算方法 即同遗传算法具有相同之处 也有各自的特点 目前 这 三者之间的比较研究和彼此结合的探讨正形成热点 1991 年 D Whitey 在他的论文中提出了基于领域交叉的交叉算子 Adjacency based crossover 这个算子是特别针对用序号表示基因的个体 的交叉 并将其应用到了 TSP 问题中 通过实验对其进行了验证 D H Ackley 等提出了随即迭代遗传爬山法 Stochastic Iterated 15 Genetic Hill climbing SIGH 采用了一种复杂的概率选举机制 此机制中由 m 个 投票者 来共同决定新个体的值 m 表示群体的大小 实验结果表明 SIGH 与单点交叉 均匀交叉的神经遗传算法相比 所测试的六个函数中有四个 表现出更好的性能 而且总体来讲 SIGH 比现存的许多算法在求解速度方面更 有竞争力 H Bersini 和 G Seront 将遗传算法与单一方法 simplex method 结合起 来 形成了一种叫单一操作的多亲交叉算子 simplex crossover 该算子在 根据两个母体以及一个额外的个体产生新个体 事实上他的交叉结果与对三个 个体用选举交叉产生的结果一致 同时 文献还将三者交叉算子与点交叉 均 匀交叉做了比较 结果表明 三者交叉算子比其余两个有更好的性能 国内也有不少的专家和学者对遗传算法的交叉算子进行改进 2002 年 戴 晓明等应用多种群遗传并行进化的思想 对不同种群基于不同的遗传策略 如 变异概率 不同的变异算子等来搜索变量空间 并利用种群间迁移算子来进行 遗传信息交流 以解决经典遗传算法的收敛到局部最优值问题 2004 年 赵宏立等针对简单遗传算法在较大规模组合优化问题上搜索效率 不高的现象 提出了一种用基因块编码的并行遗传算法 Building block Coded Parallel GA BCPGA 该方法以粗粒度并行遗传算法为基本框架 在染 色体群体中识别出可能的基因块 然后用基因块作为新的基因单位对染色体重 新编码 产生长度较短的染色体 在用重新编码的染色体群体作为下一轮以相 同方式演化的初始群体 2005 年 江雷等针对并行遗传算法求解 TSP 问题 探讨了使用弹性策略来 维持群体的多样性 使得算法跨过局部收敛的障碍 向全局最优解方向进化 1 16 9 遗传算法的展望遗传算法的展望 遗传算法作为一种对生物进化现象进行仿真的程序 取得了人工遗传的模 拟效果 具有自适应性 在遗传算法的结构中遗传操作和选择机制是两个重要 的因素 其联系可用 遗传算法 遗传操作 选择过程 这个逻辑关系来表示 如果一个应用问题不能求得目标函数的全局最优值 而只能或只希望求一定 意义下的 满意解 这时 可供选择的方法之一自然是遗传算法 因为遗传算法 比其他算法有更多的优势 可喜的是 近年来遗传算法在商业应用方面取得了一 系列重要成果 遗传算法的商业应用五花八门 覆盖面甚广 比如通用电器公司 的计算机辅助设计系统 Engeneous 这是一个采用了遗传算法以及其他传统的优 化技术做为寻优手段的混合系统 hybrid system Engeneous 已成功地应用于 汽轮机设计 并改善了新的波音 777 发动机的性能 这是目前正在研究和应用的 一个重要方面 遗传算法具有隐并行性 它可容易改造成为并行 分布式算法 用来解决那 些复杂性问题 到目前 遗传算法的理论机制仍不是很清楚 这可能和生命科学的研究一 样 将是一个永恒的研究课题 10 遗传算法的适用问题和应用领域遗传算法的适用问题和应用领域 适用问题适用问题 遗传算法擅长解决的问题是全局最优化问题 例如 解决时间表安排问题 就是它的一个特长 很多安排时间表的软件都使用遗传算法 遗传算法还经常 被用于解决实际工程问题 17 跟传统的爬山算法相比 遗传算法能够跳出局部最优而找到全局最优点 而且 遗传算法允许使用非常复杂的适应度函数 或者叫做目标函数 并对变量的变 化范围可以加以限制 而如果是传统的爬山算法 对变量范围进行限制意味着 复杂的多的解决过程 这方面的介绍可以参看受限优化问题和非受限优化问题 3 应用领域应用领域 工业工程与运作管理 物流系统设计 生产调度 制造系统控制 系统优化设计 汽车设计 包括材料选择 多目标汽车组件设计 减轻重量等 机电系统设计 分布计算机网络的拓扑结构 电路设计 此类用途的遗传算法叫做进化电路 电子游戏设计 例如计算平衡解决方案 机器智能设计和机器人学习 模糊控制系统的训练 移动通讯优化结构 时间表安排 例如为一个大学安排不冲突的课程时间表 旅行推销员问题 神经网络的训练 也叫做神经进化 3 18 11 遗传算法在神经网络中的应用遗传算法在神经网络中的应用 遗传算法在神经网络中的应用主要反映在 3 个方面 网络的学习 网 络的结构设计 网络的分析 1 遗传算法在网络学习中的应用 在神经网络中 遗传算法可用于网络的学习 这时 它在两个方面起 作用 1 学习规则的优化 用遗传算法对神经网络学习规则实现自动优化 从而提高学习速率 2 网络权系数的优化 用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度 2 遗传算法在网络设计中的应用 用遗传算法设计一个优秀的神经网络结构 首先是要解决网络结构的 编码问题 然后才能以选择 交叉 变异操作得出最优结构 编码方法主 要有下列 3 种 1 直接编码法 这是把神经网络结构直接用二进制串表示 在遗传算法中 染色体 实质上和神经网络是一种映射关系 通过对 染色体 的优化就实现了对 网络的优化 2 参数化编码法 参数化编码采用的编码较为抽象 编码包括网络层数 每层神经元数 各层互连方式等信息 一般对进化后的优化 染色体 进行分析 然后