遗传算法研究与应用论文

毕业设计（论文） 5 月 22 日设计论文题目： 遗传算法研究与应用 学生姓名： 学生学号： 专业班级： 学院名称： 指导老师： 学院院长： 毕业设计 (论文 ) 第 I 页 遗传算法研究与应用 摘要 遗传算法 （ Genetic algorithms, GAs） 是借鉴生物界自然选择和 重组 机制的随机的搜索算法。由于它简单易行、鲁棒性强，应用范围极为广泛，并且已在众多领域得到了实际应用 ， 引起了广大学者和工程人员的关注。 Traveling Salesman Problem（ TSP） 问题是一个典型 NP难题，是衡量近似算法效率的主要标准，因此设计 TSP问题的近似算法具有非常重要的意义。本文讨论遗传算法 及其 对于 TSP问题的解决 方法 。 论文首先介 绍 了遗传算法的基本概念、原理、意义及发展现状。通过对遗传算法基本理论的学习和研究，提出了 解决 TSP问题的算法，并详细给出了算法中的编码方案、适应度函数、选择算子、交叉算子、变异算子。最后用 C+语言设计并实现了该算法，结果表明该算法可以在较短的时间内得到 TSP问题的近似最优解。 关键词 ： 遗传 算法 ； TSP 问题 ； 适应度函数 ； 交叉 ； 变异 毕业设计 (论文 ) 第 II 页 Research and Application of Genetic Algorithms Abstract Genetic algorithms (GAs) are optimization search algorithms based on the mechanics of artificial selection and genetic recombination operators. They are simple, robust and easy to implement. They have been used in many fields. For these reasons now they are the hot research field which has got many scholars attention. Traveling Salesman Problem (TSP) is a classic NP problem, which is the main standard of measuring the efficiency of approximative algorithms. So the solution of the problem has has very important significance. The paper discusses the basic genetic algorithms and their application. The essay first introduces the basic concepts, principle, procedure, significance and characteristics of genetic algorithms. By learning the basic theory of genetic algorithms one solution of TSP is given. The detailed coding scheme, fitness function, selection operator, cross operator and mutation operator of the solution are also given. Finally using C+ implement the solution. The result of the program show that the algorithm can get optimal solution of the problem quickly. Keywords: Genetic Algorithms(G A)； Traveling Salesman Problem( TSP)； fitness function； cross operator； mutation operator； 毕业设计 (论文 ) 第 III 页 目 录 1 绪论 . 1 1.1 课题背景 . 1 1.2 课题研究意义 . 2 1.3 国内外研究现状 . 3 1.4 论文内容 . 5 2 遗传算法简介 . 6 2.1 遗传算法基本概念 . 6 2.2 遗传算法基本原理 . 7 2.3 遗传算法的步骤 . 8 3 遗传算法基本理论 . 11 3.1 模式定理 . 11 3.2 积木块假设与欺骗问题 . 12 3.3 收敛性分析 . 13 4 旅行商问题概述 . 14 4.1 旅行商问题的定义和数学模型 . 14 4.1.1 定义 . 14 4.1.2 数学模型 . 14 4.2 旅行商问题的计算复杂性 . 15 4.3 研究旅行商问题的意义 . 16 5 遗传算法在巡回旅行商问题中的应用 . 18 5.1 旅行商问题的建模 . 18 5.1.1 编码 . 18 5.1.2 适应度函数 . 18 毕业设计 (论文 ) 第 IV 页 5.2 遗传算法中三个算子的设计 . 19 5.2.1 选择算子的设计 . 20 5.2.2 交叉算子的设计 . 21 5.2.3 变异算子的设计 . 25 5.3 遗传算法求解旅行商问题的步骤 . 27 5.4 测试结果 . 27 6 结束语 . 29 致 谢 . 30 参考文献 : . 31 毕业设计 (论文 ) 第 1 页 1 绪论 1.1 课题背景 遗传算法（ Genetic Algorithm， GA），是一 类 以 达尔 文的 自 然进 化 论与遗传 变异 理论为基 础 的 求 解复 杂 全 局 优 化问题 的 仿 生 型 算法。它借 鉴 生 物界自 然 选择 和 自 然遗传机制，以概 率 论为基 础 在解 空 间中进行 随 机 化搜索 ，最 终找到问题 的最优解。 遗传算法的 兴起 是在 80年 代末 90年 代初 期， 但 是它的 历史 可以 追溯到 60年 代初 期。 早期的研究大 多 以对 自 然遗传 系统 的计算机模 拟 为主。 早 期遗传算法的研究特 点 是 侧重 于对一 些 复 杂 的 操 作的研究。其中 像自动博弈 、生 物系统 模 拟 、模式识别和 函数 优 化等给 人 以深刻 的印 象 ， 但总 的说 来 ， 这 是一个 无 明确 目 标的发 展 时期， 缺乏带 有指导性的理论和计算工 具 的 开拓 。 这种 现 象直到 70年 代 中期 由 于 Holland和 DeJong的 创造 性研究成果的发表 才得 到改观 。 1967年， Bagley在他的论文中 首次提出 了遗传算法 1这 一术 语 ，并 讨 论了遗传算法在 自动博弈 中的应用。 1970年， Cavicchio把 遗传算法应用于模式识别中。第一个 把 遗传算法应用于 函数 优 化 的是 Hollstien， 1971年他在论文 计算机 控 制 系统 中的人工遗传 自适 应 方 法 中 阐述 了遗传算法用于 数字反馈控 制的 方 法。 1975年 在遗传算法研究的 历史上是 十 分 重 要的一年， Holland出版 了他的 著 名 专著自 然 系统 和人工 系统 的 适配 ， 该 书 系统 的 阐述 了遗传算法的基本理论和 方 法，并 提出 了对遗传算法理论研究和发 展极 为 重 要的模式理论（ schemata theory）， 该 理论 首次 确 认 了 结 构 重组 遗传 操 作对于获得 隐 并行性的重 要性。 J. Holland教授和他的研究 小组围绕 遗传算法进行研究的 宗旨 有 两 个：一是 抽 取和解 释自 然 系统 的 自适 应过 程 ，二是 设 计 具 有 自 然 系统 机理的人工 系统 。同年， DeJong完成了他的 重 要论文 遗传 自适 应 系统 的行为分 析 ，他 把 Holland的模式理论和他的计算实验结 合 起来 ， 这 可以 看 作遗传算法发 展 过 程 中的一个 里程碑 ，尽 管 DeJong和 Hollstien一 样主要 侧重 于 函数 优 化 的研究， 但 他 将选择 、交 叉 和 变异操 作进一步完 善 和 系统化 ，同时 又提出 了 诸如代沟 （ generation gap） 等新 的遗传 操 作技术，为遗传算法及其应用 打 下了 坚实的基 础 。进 入 80年 代 ，遗传算法 迎来 了 兴盛 发 展 时期，理论研究和应用研究 都 成了 十 分热门 的 话题 。 可以认为， DeJong的研究工作为遗传算法及其应用打下了坚实的基础，他所 毕业设计 (论文 ) 第 2 页 得出的许多结论，迄今仍具有普遍的指导意义。 1.2 课题研究意义 由于遗传算法不受搜索空间的限制性假设的约束 , 因此不必要求诸如连续性、导数存在和单峰等条件，同时遗传算法还具有以下特点： 1、遗传算法是利用决策变量集的某种编码进行运算，而不是直接作用在决策变量集上，通用性强。 2、遗传算法能同时使用多个搜索点的搜索信息。传统的优化算法往往是从解空间中的一个初始解开始最优解的迭代搜索过程。而遗传算法从一个解的种群开始搜索，而不是从单个解开始，就像在解空间撒网一样，可以对不同区域采样，并不断交换信息。这使得它减少了陷入局部优解的风险，能以较大概率找到全局最优解。 3、遗传算 法在寻优过程中仅利用解的适应度函数信息作为寻优的依据。它对目标函数几乎无要求，也不涉及映射空间或函数的连续性，仅使用由目标函数值变换来的适应度函数值，就可确定进一步的搜索方向和搜索范围。而传统搜索算法不仅要利用目标函数值，而且往往需要目标函数的导数值等其他一些辅助信息才能确定搜索方向。 4、遗传算法使用概率搜索技术，以一种概率的方式来进行搜索，从而增加了其搜索过程的灵活性。而很多传统的优化算法使用的是确定性的搜索方法，这种确定性往往可能使得搜索永远达不到最优点，因而也限制了算法的应用范围。 5、遗传算法具有 本质并行性，包括内在并行性和隐并行性。内在并行性说明遗传算法非常适合大规模并行运算，而隐并行性使得遗传算法能以较少的计算获得较大的收益。 遗传算法的这些特点使得它比传统搜索方法具有更大的优越性，适用范围更广并且能够应用于一些到目前为止人们知之甚少的困难问题领域。遗传算法提供了一种求解复杂、困难优化问题的通用框架，它不依赖于问题的具体领域，不要求目标函数有明确的解析表达，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。下面是遗传算法的一些主要应用领域 6 7： 函数优化问题。函数优化是遗传算法的经典 应用领域，也是对遗传算法进行性能评价 毕业设计 (论文 ) 第 3 页 的常用算例。很多人构造出了各种各样的复杂形式的测试函数来评价遗传算法的性能。而且对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，而遗传算法却可以方便地得到较好的结果。 组合优化问题。随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解。对这类复杂问题，人们已意识到应把主要精力放在寻求其满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于求解组合优化问题非常有效。遗传算 法已经在求解旅行商问题、图形划分问题等方面得到成功的应用。 生产调度问题。生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以求解，也会因简化太多而使求解结果与实际相差甚远。由于可以采用字符编码，而且不必使用恰好的目标函数估值，遗传算法也成为解决复杂调度问题的有效工具。在单件生产车间调度、流水线生产车间调度、生产规划、任务分配、虚拟企业中的伙伴选择方面遗传算法都得到了有效的应用。 自动控制。在自动控制领域有很多与优化相关的问题需要求解，而且这些优化问题通常要么是通过积分表达的， 要么是写不出明确而严格的解析表达式。遗传算法在求解这类自动控制问题方面已显示出其独特的优点。例如，用遗传算法进行航空控制系统的优化、用遗传算法优化设计透平机械、设计模糊控制器等，都取得了较好的效果。 机器学习。学习能力是高级自适应系统所应具备的特征之一。基于遗传算法的机器学习在很多方面都得到成功应用。例如，遗传算法被用于学习模糊控制规则、确定模糊集的隶属函数、改进模糊系统的性能；被用来调整人工神经网络的连接权及网络拓扑优化。 此外，遗传算法还被应用到反问题求解、机器人学习、生物计算、图像处理、人工生命以及遗 传编程等领域。 1.3 国内外研究现状 进入 90 年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索 毕业设计 (论文 ) 第 4 页 之中。此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑均给遗传算法增添了新的活力。遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。 随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是基于遗 传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓 21 世纪中新的智能计算技术将具有重要的意义。三是并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。四是遗传算法和另一个称为人工生命的崭新研究领 域正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会发挥一定的作用，五是遗传算法和进化规划（ Evolution Programming ,EP）以及进化策略（ Evolution Strategy ,ES）等进化计算理论日益结合。 EP 和 ES 几乎是和遗传算法同时独立发展起来的，同遗传算法一样，它们也是模拟自然界生物进化机制的只能计算方法，即同遗传算法具有相同之处，也有各自的特点。目前，这三者之间的比较研究和彼此结合 的探讨正形成热点。 1991 年 D.Whitey 在他的论文中提出了基于领域交叉的交叉算子 （ Adjacency based crossover） ， 这个算子是特别针对用序号表示基因的个体的交叉，并将其应用到了 TSP 问题中 ， 通过实验对其进行了验证。 D.H.Ackley 等提出了随即迭代遗传爬山法（ Stochastic Iterated Genetic Hill-climbing， SIGH） 采用了一种复杂的概率选举机制，此机制中由 m 个 “投票者 ”来共同决定新个体的值（ m 表示群体的大小）。实验结果表明， SIGH 与单点交叉、 均匀交叉的神经遗传算法相比，所测试的六个函数中有四个表现出更好的性能，而且总体来讲，SIGH 比现存的许多算法在求解速度方面更有竞争力。 H.Bersini 和 G.Seront 将遗传算法与单一方法（ simplex method）结合起来，形成了一种叫单一操作的多亲交叉算子（ simplex crossover），该算子在根据两个母体以及一个额外的个体产生新个体，事实上他的交叉结果与对三个个体用选举交叉产生的结果一致。同时，文献还将三者交叉算子与点交叉、均匀 毕业设计 (论文 ) 第 5 页 交叉做了比较，结果表明，三者交叉算子比其余两个有更好的性能。 国内也有不少的专家和学者对遗传算法的交叉算子进行改进。 2002 年，戴晓明等应用多种群遗传并行进化的思想，对不同种群基于不同的遗传策略，如变异概率，不同的变异算子等来搜索变量空间，并利用种群间迁移算子来进行遗传信息交流，以解决经典遗传算法的收敛到局部最优值问题 2004 年，赵宏立等针对简单遗传算法在较大规模组合优化问题上搜索效率不高的现象，提出了一种用基因块编码的并行遗传算法（ Building-block Coded Parallel GA， BCPGA）。该方法以粗粒度并行遗传算法为基本框架，在染色体 群体中识别出可能的基因块，然后用基因块作为新的基因单位对染色体重新编码，产生长度较短的染色体，在用重新编码的染色体群体作为下一轮以相同方式演化的初始群体 。 2005 年，江雷等针对并行遗传算法求解 TSP 问题 ,探讨了使用弹性策略来维持群体的多样性 ,使得算法跨过局部收敛的障碍 ,向全局最优解方向进化 。 1.4 论文内容 本文内容安排如下： 第一章：绪论。 介绍本课题的选题背景和研究现状以及文章结构。 第二章：简要介绍了遗传算法的基本概念、原理、实现步骤。 第三章：叙述了遗传算法的主要理论：模式定理、积木块假设，以及遗传算法的收 敛性的简单说明。 第四章：就在旅行推销商问题做了简要介绍，并对旅行推销商问题的数学模型，计算的复杂度和求解该问题的意义进行简单概要。 第五章：提出了遗传算法求解旅行商问题的一种方式， 并详细给出了算法中的编码方案、适应度函数、选择算子、交叉算子、变异算子及部分源码。 第六章：结束语。 文章的最后是参考致谢和参考文献。 毕业设计 (论文 ) 第 6 页 2 遗传算法简介 2.1 遗传算法基本概念 遗传算法的基本 思想 是基于 Darwin进 化 论和 Mendel的遗传学说的。 Darwin进 化 论最 重 要的是 适者 生存原理。它 认 为 每 一 物种 在发 展 中 越 来 越 适 应 环境 。物 种 每 个个 体 的基本特 征由 后 代 所 继 承， 但 后 代又 会 产生一 些异 于 父 代 的 新变化 。在 环境变化 时， 只 有 那 些能适 应 环境 的个 体 特 征才能 保留下 来 。 Mendel遗传学说最 重 要的是基 因 遗传原理。它 认 为遗传以密 码方 式存在 细胞 中，并以基 因 形 式包含在 染色 体 内。 每 个基 因 有特 殊 的位 置 并 控 制 某 种 特 殊 性 质 ；所以， 每 个基 因产生的个 体 对 环境具 有 某 种适 应性。基 因突 变 和基 因 杂 交可产生 更 适 应于 环境 的后 代 。经过存优 去劣 的 自 然 淘汰 ， 适 应性 高 的基 因 结 构得以保存下 来 。 由 于遗传算法是 由 进 化 论和遗传学机理产生的 直 接 搜索 优 化方 法，所以在 这 个算法中要用 到 各 种 进 化 和遗传学的概念。 这些 概念 如 下： 1.串 它是个 体 的 形 式，在算法中为二进制 串 ，并 且 对应于遗传学中的 染色 体 。 2.种群 个 体 的 集 合 称 为 群体 ， 串 是 种群 中的 元素 3.种群 大 小 在 种群 中个 体 的 数量 称 为 种群 的大 小 。 4.基 因 基 因 是 串 中的 元素 ，基 因 用于表示个 体 的特 征 。 例如 有一个 串 S 1011， 则 其中的 1011这 4个 元素 分别 称 为基 因 。 5.基 因 位 置 一个基 因 在 串 中的位 置称 为基 因 位 置 ，有时也简 称 基 因 位。基 因 位 置 在 串 中 由 左向右计算， 例如 在 串 S 1101中， 0的基 因 位 置 是 3。基 因 位 置 对应于遗传学中的 地点 。 毕业设计 (论文 ) 第 7 页 6.基 因 特 征值 在用 串 表示 整 数 时，基 因 的特 征值 与二进制 数 的权一致； 例如 在 串 S=1011中，基 因 位置 3中的 1，它的基 因 特 征值 为 2；基 因 位 置 1中的 1，它的基 因 特 征值 为 8。 7.串 结 构 空 间 在 串 中，基 因 任意 组 合所构成的 串 的 集 合。基 因 操 作是在 结 构 空 间中进行的。 串 结 构空 间对应于遗传学中的基 因 型 的 集 合。 8.参数空 间 sp这 是 串 空 间在 物 理 系统 中的 映射 ，它对应于遗传学中的表现 型 的 集 合。 九 、 适 应 度 表示 某 一个 体 对于 环境 的 适 应 程度 。 遗传算法 还 有一 些 其它的概念， 这些 概念在 介 绍 遗传算法的原理和 执 行过 程 时， 再 进行说明。 2.2 遗传算法基本原理 遗传算法 GA把问题 的解表示成 “ 染色 体 ” ，在算法中也 就 是二进制 编码 的 串 。并 且 ，在 执 行遗传算法之 前 ， 给出 一 群 “ 染色 体 ” ，也 就 是 假 设 解。然后， 把这些 假 设 解 置 于 问题 的 “ 环境 ” 中，并 按 适者 生存的原 则 ， 从 中 选择出较适 应 环境 的 “ 染色 体 ” 进行复制，再通 过交 叉 ， 变异 过 程 产生 更 适 应 环境 的 新 一 代 “ 染色 体 ” 群 。 这样 ，一 代 一 代 的进 化 ，最后 就会 收敛到 最 适 应 环境 的一个 “ 染色 体 ” 上 ，它 就 是 问题 的最优解。 很 明 显 ，遗传算法是一 种 最优 化方 法，它 通 过进 化 和遗传机理， 从 给出 的原 始 解 群 中 ，不 断 进 化 产生 新 的解，最后 收敛到 一个特定的 串 bi处，即 求出 最优解。 长 度 为 L的 n个二进制 串 bi(i 1， 2， ， n)组 成了遗传算法的 初 始 解 群 ，也 称 为 初 始 群体 。在 每 个 串 中， 每 个二进制位 就 是个 体 染色 体 的基 因 。 根据 进 化 术 语 ，对 群体 执 行的 操作有 三种 ： 1 选择 这 是 从 群体 中 选择出较适 应 环境 的个 体 。 这些选 中的个 体 用于 繁殖 下一 代 。 故 有时也称 这 一 操 作为 再 生。 由 于在 选择 用于 繁殖 下一 代 的个 体 时，是 根据 个 体 对 环境 的 适 应 度来 毕业设计 (论文 ) 第 8 页 决 定其 繁殖 量 的， 故 而有时也 称 为 非 均 匀再 生。 2 交 叉 这 是在 选 中用于 繁殖 下一 代 的个 体 中，对 两 个不 同的个 体 的相同位 置 的基 因 进行交 换 ，从 而产生 新 的个 体 。交 叉 算子示意 如 图 1.1。 图 1.1 交 叉 算子示意 图 3 变异 这 是在 选 中的个 体 中，对个 体 中的 某 些 基 因按 变异 概 率 P 执 行 异 向转 化 。在 串 bi中，如 果 某 位基 因 为 1，产生 变异 时 就 是 把 它 变 成 0； 反之亦然 。 2.3 遗传算法的步骤 1 初 始 化 选择 一个 群体 ，即 选择 一个 串 或个 体 的 集 合 bi， i=1， 2， .n。 这 个 初 始 的 群体 也 就 是问题 假 设 解的 集 合。一 般 取 n 30-160。 通 常 以 随 机 方 法产生 串 或个 体 的 集 合 bi,i 1， 2， .n。 问题 的最优解 将 通 过 这些初 始假 设 解 进 化 而 求出 。 毕业设计 (论文 ) 第 9 页 2 选择 根据适者 生存原 则 选择 下一 代 的个 体 。在 选择 时，以 适 应 度 为 选择 原 则 。 适 应 度 准则体 现了 适者 生存，不 适 应 者 淘汰 的 自 然法 则 。 给出目 标 函数 f， 则 f(bi)称 为个 体 bi的 适 应 度 。以公式（ 1-1） P选 中 bin)()(1njbjfbif (1-1) 为 选 中 bi为下一 代 个 体 的 次数 。 显 然 。从 上 式可知： (1)适 应 度较高 的个 体 ， 繁殖 下一 代 的 数目较多 。 (2)适 应 度较小 的个 体 ， 繁殖 下一 代 的 数目较 少 ， 甚至被淘汰 。 这样 ， 就 产生了对 环境适 应 能力较 强 的后 代 。 从 问题求 解 角 度来 讲 ， 就 是 选择出 和最优解 较 接近 的中间解。 3 交 叉 对于 选 中用于 繁殖 下一 代 的个 体 ， 随 机 地选择两 个个 体 的相同位 置 ， 按 交 叉 概 率 P。在 选 中的位 置 实行交 换 。 这 个过 程反 映 了 随 机 信息 交 换 ； 目 的在于产生 新 的基 因 组 合，也即产生 新 的个 体 。交 叉 时，可实行单 点 交 叉 或 多点 交 叉 。 例如 有个 体 S1=100101 S2=010111 选择 它 们 的 左边 3位进行交 叉操 作， 则 有 S1=010101 S2=100111 一 般 而言，交 叉 概 率 P。取 值 为 0.25 0.75。 4 变异 根据 生 物 遗传中基 因 变异 的原理，以 变异 概 率 Pm对 某 些 个 体 的 某 些 位 执 行 变异 。在 变 毕业设计 (论文 ) 第 10 页 异 时，对 执 行 变异 的 串 的对应位 求反 ，即 把 1变 为 0， 把 0变 为 1。 变异 概 率 Pm与生 物变异极小 的 情况 一致，所以， Pm的取 值较小 ，一 般 取 0.01-0.2。 例如 有个 体 S 101011。 对其的第 1， 4位 置 的基 因 进行 变异 ， 则 有 S=001111 单 靠 变异 不 能 在 求 解中得 到好 处。 但 是，它 能 保证算法过 程 不 会 产生 无 法进 化 的单一群体 。 因 为 当 所有的个 体 一 样 时，交 叉 是 无 法产生 新 的个 体 的， 这 时 只 能 靠 变异 产生 新 的个 体 。也 就 是说， 变异 增 加了全 局 优 化 的特 质 。 5 全 局 最优 收敛 当 最优个 体 的 适 应 度达到给 定的 阀 值 ，或 者 最优个 体 的 适 应 度 和 群体适 应 度 不 再 上 升时， 则 算法的 迭 代 过 程收敛 、算法 结束 。 否则 ，用经过 选择 、交 叉 、 变异 所得 到 的 新 一 代群体 取 代上 一 代群体 ，并 返回 到 第 2步即 选择操 作处 继续循 环 执 行。 图 1.2中表示了遗传算法的 执 行过 程 图 1.2 遗传算法原理 毕业设计 (论文 ) 第 11 页 3 遗传算法基本理论 3.1 模式定理 模式定理是由 Holland 在 1971 年提出的，它是 GA 的基本定理。它将 GA的运算过程理解为模式运算过程，并从模式运算的角度解释 GA 的性能特点。模式是 描述字符串集的模板，反映字符串集中串的某些位置上存在的相似性。在本节的叙述中，仅就二进制编码的情况进行讨论。 【定义 2.1】基于三值字符集 0,1,*所产生的能描述具有某些结构相似性的 0、 1 字符串集的字符串称作模式。 例如，模式 S = 01*0*描述了所有在位置 1 和位置 4 上为 0，在位置 2 上为 1的字符串，该模式描述的字符串集合为 01000， 01001， 01100， 01101。 也就是： S = 01*0* = 01000， 01001， 01100， 01101 事实上，模式的概念使得我们可以简明地 描述具有相似结构特点的个体编码字符串。 在引入模式的概念后，遗传算法的本质就是对模式所进行的一系列运算，遗传运算过程中的个体通过模式联系起来。通过这些遗传运算，一些比较差的模式逐渐被淘汰，而一些较好的模式逐步被遗传和进化。 在进行遗传算法的理论分析时，往往需要定量地估计模式运算。因此，有必要引入以下两个概念：模式阶和模式定义距。 【定义 2.2】模式 H 中确定位置的个数称为模式的模式阶 (Schemata Order)，记作 O(H)。模式 H 中第一个确定位置和最后一个确定位置之间的距离称为模式的定义距 (Schemata Defining Length)，记作 (H)。 根据定义 2.2， O(101*0) = 4， (101*0) = 4； O(0*1*) = 2， (0*1*) = 3。而对于 H = *1、 H = *0*之类的模式，由于他们只有一个确定位置，所以我们规定它们的定义距为 0，如 (*0*) = 0。 当字符串的长度确定时，模式的阶数越高，与该模式相匹配的样本数目就越少，该模式的确定性也就越高。而模式的定义距越大，则在遗传运算中，该模式被遗传运算破坏的 毕业设计 (论文 ) 第 12 页 概率越大，生存概率越小。 【定 理 2.1】模式定理在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代中将得以指数级增长。 模式定理可以用数学形式表示为： )()1/()()/)(),()1,( mc pHolHpfHftHmtHm （ 2 1） 其中， H 表示一个模式， m(H,t) 表示在第 t 代种群中存在的模式 H 中串的个数。 f (H) 表示在第 t 代种群中模式 H 串的平均适应度， f 表示第 t 代种群的平均适应度， l 表示串的长度 , pc是串之间发生交叉的概率， pm是一个串发生变异的概率， (H) 表示模式 H 的定义距 , o(H) 表示模式 H 的阶。 模式定理保证了遗传优化过程中较优解的样本呈指数级增长，在一定意义上可以解释基本遗传算法的优化本质，同时也给遗传算法的应用提供了指导作用。 3.2 积木块假设与欺骗问题 模式定理说明，低阶、短定义距、平均适应度高的模式被交叉切断的可能性低，随着世代交替其数量将增加。这种类型的模式称为积木块。 【定义 2.3】具 有低阶、短定义距以及高适应度的模式称作积木块。 【假设 2.1】积木块假设积木块在遗传算子的作用下相互结合，能生成高阶、长定义距、高平均适应度的模式，并最终生成全局最优解。 模式定理说明了积木块的样本数呈指数级增长，亦即说明了用遗传算法寻求最优样本的可能性；而积木块假设说明了用遗传算法求解各种问题的基本思想，即通过积木块之间的相互拼接能够产生出问题更好的解，表明遗传算法具有全局寻优能力，能够寻求到最优样本。到目前为止，上述假设并未得到完整而严密的数学证明，但大量的实践对这一假设提供了强有力的支持。 如果一个问 题的编码满足积木块假设，那么用遗传算法求解的效率较高，否则用遗传算法求解的效率较低。应用实践表明，存在一类用遗传算法难以求解的问题，称为 “GA-难 ”问题。属于 “GA-难 ”的问题一般包括有孤立的最优点，在搜索过程中，低阶积木块错误地引导搜索过程，不能发现高阶积木块，通过欺骗遗传算法，使其进化过程偏离最优解，最 毕业设计 (论文 ) 第 13 页 终使遗传算法发散，这种现象称为欺骗。实际上，目前尚未没有解决这类问题的较好的方法，也无法判断一个问题包含欺骗的多少与问题相对于遗传算法的难易程度。不过，现实中遇到的各种应用问题中，遗传算法大部分是适用的。 3.3 收敛性分析 模式定理虽然指出了具有优良结构的模式在算法的进化过程中的演变趋势，但是，它并未回答了遗传算法最终收敛于最优解的概率为多少。积木块假设虽然指明了遗传算法能够收敛于全局最优解，但是仅仅是通过大量的应用数据来证明其有效性，还没有完整而严密的数学证明。利用马尔可夫链对遗传算法的分析严格论证了遗传算法收敛性方面的一些重要性质，有力地支撑了遗传算法的理论基础。下面是由马尔可夫链推导出来的一些结论，具体证明可以参考文献 8。 【定理 2.3】基本遗传算法收敛于最优解的概率小于 1。 【定理 2.4】使用保留最佳 个体策略的遗传算法够收敛于最优解的概率为 1。 通过上述定理可以看出，基本遗传算法收敛于最优解的概率小于 1，而通过对基本遗传算法进行改进，修正它的选择策略，就能使算法一定收敛于最优解。这两个定理不仅在理论上是模式定理和积木块假设的有力补充，更为实际的应用中的算法收敛提供了保证。 毕业设计 (论文 ) 第 14 页 4 旅行商问题概述 4.1 旅行商问题的定义和数学模型 4.1.1 定义 旅行商问题是组合数学中一个古老而又困难的问题，它易于描述但至今尚未彻底解决，现己归入所谓的 NP完全问题类，经典提法为 : 有一货物推销员要去若干个城市推销货物，从城市 1出发，经其余各 城市一次，然后回到城市 1，问选择怎样的行走路线，才能使总行程最短 (各城市间距离为己知 )。 该问题在图论的意义下就是所谓的最小 Hamilton圈问题，由于在许多领域中都有着广泛的应用，因而寻找其实际而有效的算法就显得颇为重要了。遗憾的是，计算复杂性理论给予我们的结论却是，这种可能性尚属未知。 若设城市数目为 n时，那么组合路径数则为 (n-1)!。很显然，当城市数目不多时要找到最短距离的路线并不难，但随着城市数目的不断增大，组合路线数将呈指数级数规律急剧增长，以至达到无法计算的地步，这就是所谓的“组合爆炸问题 ” 。 假设现在城市的数目增为 20个，组合路径数则为 (20-1)!，如此庞大的组合数目，若计算机以每秒检索 1000万条路线的速度计算，也需要花上 386年的时间。 尽管现在计算机的计算速度大大提高，而且己有一些指数级的算法可精确地求解旅行商问题，但随着它们在大规模问题上的组合爆炸，人们退而求其次，转向寻找近似算法或启发式算法，经过几十年的努力，取得了一定的进展。 4.1.2 数学模型 设 G=(V, E)为赋权图， V=l ,2,. .n为顶点集， E为边集，各顶点间距离为 cij。 已知 (cij 0, cij= ,i,j V )，并设 xij=，其它）在最优路线上，边（0ji1 （ 3 1） 毕业设计 (论文 ) 第 15 页 则旅行商问题的数学模型可写成如下的线性规划形式： MinZ ji ijc xijs.t VjixVKKxVjxVixijSjiijjiijijji,1,0,1,1,1,这里， K 为 V 的所有非空子集， K 为集合 K 中所含图 G 的顶点个数。前两个约束意味着对每个顶点而言，仅有一条边进出，后一约束则保证了没有任何子回路解的产生。于是，满足上述约束的解构成了一条 Hamilton 回路。除此之外，模型还有其它一些等价的书写形式 。 4.2 旅行商问题的计算复杂性 一般的，我们定义一个组合优化问题 : 设 RSf : ，其中 S为一个有限集， f为映射函数，对每个 Sx 产生唯一的实数 f(x)，则最大 (小 )化问题即找一个 Sx ，使得对于任何其它 Sx 有 )()()( xfxf 。 此组合优化问题的一个基本算法是 :对于每个 Sx ，求 f(x)的值，挑选 x ，使对于所有的 Sx ， )()()( xfxf 。 这就是穷举搜索法，它在理论上可以解决任何有限的组合最优化问题。 但对于 n个城市的 TSP，可能的回路数有2 )!1( n条，计算每一条路径需求 n个距离之和，故计算量将正比于2!n。表 4 1显示了运算速度 510 亿次 /秒的 CrayXT3巨型计算机按穷举搜索法计算 TSP所需的时间，这里还未考虑算法所需的巨大存贮空间。由此足见 TSP时空复杂度之高。 毕业设计 (论文 ) 第 16 页 表 4.1 4.3 研究旅行商问题的意义 旅行商问题是 一个 NP完全问题，目前任何 NP完全问题都不能用任何已知的多项式算法求解；若任何一个 NP完全问题有多项式算法，则一切 NP完全问题都有多项式算法。 由此，不少人猜测任何 NP完全问题都没有多项式算法，但至今无人证明。事实上，人们普遍认为，不发展全新的数学技术就证明不了这个猜想。这样一种认识的实际意义就在于许多人相信，难计算是这样一类问题的固有性质，因此它们不可能用有效算法求解，而所有能精确求解 NP完全问题的算法，在最坏情况下都需要指数级的时间。 另外，旅行商问题是一个理想化的问题，大多数对于此问题的研究都不是为了 直接的实际应用，但这些研究可以经转化后用于许多现实的组合优化问题。很自然地可以想到，旅行商问题的成果可以应用于运输和物流问题。旅行商问题最早的应用是在上个世纪的四十年代，应用于校车路线的优化。现在，旅行商问题在越来越多的领域得到应用。 1电路板钻孔进度的安排。在这个应用当中，电路板上的孔代表旅行商问题中的城 市，钻头从一个钻孔移动到另一个钻孔。寻找最短路径变成了寻找最省时的钻头移动时间。尽管目前钻机的工艺技术发展很块，但钻头的移动时间仍然是一个令人头疼的问题。 2基因测序。 Concorde是一种求解旅行 商问题的程序。美国国家卫生机构的研究人 员利用这一程序来进行基因测序。在这一应用中，局部的基区图谱作为城市，城市与城市的距离代表某张图谱与其它图谱相连的可能性。研究人员试图寻找一种可能性最高的连接方城市数 N 回路数2 )!1( n加法量2!n搜索时间 5 12 60 12106 秒 10 5108144.1 6108144.1 7108144.1 秒 20 161008.6 181022.1 51022.1 秒 40 461002.1 471008.4 271032.1 年 100 155106.4 157106.4 1361048.1 年 200 371100.5 374100.1 3561022.3 年 毕业设计 (论文 ) 第 17 页 式把这些局部的图谱合成为整张基因图谱。 3半导体的线路设计。一家半导体生产厂家应用 Concorde程序来优化半导体的线路 设计，这样可以节省刻制半导体的时间，也能减少半导体电路消耗的能量。 4光缆的线路设计。贝尔电话公司利用 Concorde程序来设计光缆的铺设线路，同样 的方法也应用于电话和电力线路的铺设当中 。 5在机器人控制等其它方面，旅行商问题也有许多应用。 毕业设计 (论文 ) 第 18 页 5 遗传算法在巡回旅行商问题中的应用 5.1 旅行商问题的建模 5.1.1 编码 在遗传算法中，染色体通常采用简单的二进制串编码，但这种简单的编码方式不能较好的适用于 TSP和其它组合优化问题。 TSP常用的编码表达方式主要有邻接表达、矩阵表达、边表达、随机键表达和序表达等。其中，序表达和随机键表达不仅适用于 TSP，也适用于其它组合优化问题。 本文使用序表达形式。序表达是 TSP问题的最自然的表达，其中城市是按访问的顺序排列的。例如，对于 9个城市的 TSP:3 2 5 4 7 1 6 9 8可简单表示为向量 3 2 5 4 7 1 6 9 8，表示从城市 3出发依次经过城市 2， 5， 4， 7， 1， 6， 9， 8然后返回城市 3的一条路径。序表达方式满足完全无向图 TSP问题的约束条件。保证了每个城市经过且只经过一次，并且保证在任何一个城市子集中不形成回路 . 5.1.2 适应度函数 适应度是生物学家在研究自然界中生物的遗传与进化现象时用以度量某个物种对其生存环境的适应程度。在遗传算法中适应度用来度量个体作为全局最优解的可接受程度，它是模拟进化算法评价和选择个体的度量依据。适应度的取值与适应度函数成正比。适 应度函数的确定通常反映应用者对个体的评价标准和搜索机理 。 适应度函数是遗传进化操作的基础，它的构造是遗传算法的关键 。 合理的适应度函数能引导搜索朝最优化方向进行 。 本文构造基于序的适应度函数 。 它的特点是个体被选择的概率与目标函数的具体值无关 。 将种群中的所有个体按其目标函数值的大小降序排列，设参数 )1,0( ， 定义基于序的适应度函数 e 1)1()( iiv a l x i 1， 2， 3， psize（ 3 2） 式中： xi 种群排序后第 i个个体； 毕业设计 (论文 ) 第 19 页 psize 种群中个体总数。 程序源码： void CreateFitnessofPop( ) std:vector:iterator iter_router； double alpha = EVAL_BASE； std:vector vecSort； for( iter_router=vecPop.begin()；iter_router!=vecPop.end()；iter_router+ ) vecSort.push_back( iter_router-m_fTotalDistance )； iter_router-m_fFitness = -100.0； std:sort( vecSort.begin(), vecSort.end() )； std:vector:iterator iter_sort； int nIndex = 0； for( iter_sort=vecSort.begin()；iter_sort!=vecSort.end()；iter_sort+ ) for( iter_router=vecPop.begin()； iter_router!=vecPop.end()；iter_router+ ) if( fabs(iter_router-m_fTotalDistance-(*iter_sort) m_fFitness m_fFitness = alpha*pow(1-alpha,(double)nIndex)； nIndex+； 5.2 遗传算法中三个算子的设计 毕业设计 (论文 ) 第 20 页 5.2.1 选择算子的设计 按照某种选择策略从群体中选择出若干个体进入交配池。交配池中的个体通过遗传算子的作用产生新一代群体。选择策略应遵守的基本原则是 :适应度值越大的个体被选中的概率应该越大。即选择策略应遵循自然界 “优胜劣汰、适者生存”的自然选择规律。从群体中选择优胜的个体，淘汰劣质个体的操作叫选择。选择算子有时又称为再生算子。选择的目的是把优化的个体 (或解 )直接遗传到下一代或通过交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。在遗传算法中，目前常用的选择机制有以下几种 :适应度比例方法、最佳个体保存方法、期望值方法、排序选择机制、联赛选择机制。 本文适应度比例方法是目前遗传算法中最基本也是最常用的选择方法。它也叫赌轮或蒙特卡罗 (Monte Carlo)选择。在该方法中，各个个体的选择概 率和其适应度值成比例。 程序源码如下： void SelectPop() /群体竞争 轮盘赌选择 std:vector vecRoll； std:vector vecSelPop； int nRollNumber, nRollRange； int nPopSize = vecPop.size()； int i, j； for( i=0；inPopSize；i+ ) double fsumfitness = 0.0； for( int j=0；j=i；j+ ) fsumfitness += vecPopj.m_fFitness*10000； vecRoll.push_back( fsumfitness )； nRollRange = (int)fsumfitness； 毕业设计 (论文 ) 第 21 页 for( i=0；inPopSize；i+ ) nRollNumber = rand()%nRollRange； for( j=0；jnPopSize；j+ ) if( nRollNumber ncrossoverbegin ) break； else if( ncrossoverend ncrossoverbegin ) std:swap( ncrossoverbegin, ncrossoverend )； 毕业设计 (论文 ) 第 23 页 break； for( int i=ncrossoverbegin；i:iterator iter_father, iter_son； bool hasCity = false； int naddbegin = 0； for( iter_father=vecPopnFatherB.m_CityRout