遗传算法求解tsp问题的计算机仿真本科毕业论文(编辑修改稿)

遗传算法求解tsp问题的计算机仿真本科毕业论文(编辑修改稿)内容摘要：

stems),开创了基于遗传算法的机器学习的新概念。 2 1967 年在其博士论文中首次提出了：“遗传算法”一词，发展了复制、交叉、变异、显性、倒位等遗传算子，创立了自适应遗传算法的概念。 3 Jong 1975 年在其博士论文中结合模式定理进行了大量的纯数值函数优化计算实验，树立了遗传算法的工作框架，定义了评价遗传算法性能的在线指标和离线指标。 4 1989 年出版了专著《搜索、优化和机器学习中的遗传算法 (Geic Algorithms in Search，Optimization and Machine Learning)》，系统总结了遗传算法的主要研究成果，全面而完整的论述了遗传算法的基本原理及其应用。 5 1991 年编辑出版了《遗传算法手册 (Handbook of Geic Algorithms)》书中包括遗传算法在科学计算、工程技术和社会经济中的大量应用实例。 1992 年将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程 (Geic Programming) 的概念，并成功的将其提出的遗传编程应用于人工智能、机器学习符号处理等方面。 5 遗传 算法基本原理 遗传算法是受大自然的启发，模拟生物在自然环境中的遗传和进化过程而形成的一种自适应、具有全局优化能力的随机搜索算法。 遗传算法的思路是通过从给定一个初始群体出发，利用选择算子、交叉算子以及变异算子来模拟自然进化的三种原则，逐步改进种群，越来越逼近最优解，以达到求解最优化问题的目的。 在 遗传算法中，种群中的 每一个 个体是问题的一个 解 ， 称为“染色体”， 染色体是 一串 符号，比如二进制的 01 串。 这些 染色体 在后续的迭代中不断 的进化，称为遗传。 在 每一代 中应用适应度（ fitness） 来 测量染色体的优越性 ， 适应度 高的 更容易在自然的选择中 存活 下来。 生存 下来的 染色体被称为后代 （ offspring）。 后代通常是前一代染色体通过交叉（ crossover） 或者 变异（ mutation ） 形成。 新的下一代再重复 根据 适应度选择部分后代，淘汰一部分后代，这样 即 可以 保证 种群染色体的优越性，也 保持了 种群大小的稳点性。 遗传算法中每一条染色体，对应着遗传算法的一个解决方案，一般我们用适应性函数（ fitness function）来衡量这个解决方案的优劣。 所以也可以把遗传算法的过程看作是一个在多元函数里面求最优解的过程。 在这个多维曲面里面也有数不清的 “山峰 ”，而这些最优解所对应的就 是 这些山峰 ， 这些山峰就是局部最优解。 而其中也会有一个 “山峰 ”的海拔最高的，那么这个就是全局最优解。 而遗传算法的任务就是尽量爬到最高峰，而不是陷落在一些小山峰。 （另外，值得注意的是遗传算法不一定要找 “最高的山峰 ”，如果问题的适应度评价越小越好的话，那么全局最优解就是函数的最小值，对应的，遗传算法所要找的就是 “最深的谷底 ”）。 下面给出生物学的几个基本概念知 识，这对于理解遗传算法很重要： 1）遗传因子（ gene） :DNA 长链结构中占有一定位置的基本遗传单位，也称基因。 生物的基因根据物种的不同而多少不一。 2）个体（ individual） :指染色体带有特征的实体。 3）种群（ population） :染色体带有特征的个体的集合。 4）进化（ evolution）。 生物在其延续生命的过程中，逐渐适应其生存环境使得其品质不断得到改良，这种生命现象称为进化。 生物的进化是以种群的形式进行的。 5）适应度（ fitness） :度量某个物种对于生存环境的适应程度。 6）选择（ selection） :指以一定的概率从种群中选择若干个体的操作。 7）变异（ musation）：复制时很小的概率产生的某些复制差错。 8）编码（ coding） :DNA 中遗传信息在一个长链上按一定的模式排列，也即进行了遗传编码。 遗传编码可以看成是从表现型到遗传子型的映射。 9）串（ String） :它是 个体的 形式 ，在算法 中 为二进制串，并且对应于遗传学 中 的染色体。 10）串 结构 空间 （ ss） ： 在串中，基因任意组合所构成的串集合。 基因 操作是在 结构 空间中进行的。 串 结构空间 对 应用 于遗传学 中的基因 型 的 集合。 11）染色体： 是生物细胞中含有的一种微小的丝状化合物，是遗传物质的主要载体，由多个遗传因子 — 基因组成。 6 遗传 算法基本步骤 步骤一 ： 编码 ： 把 所需要选择的群体进行编号，每一个个体就是 一条 染色体 ，一个 解就是一串基因的组合。 步骤二 ： 初始化 ：随机生成有 N 个 个体的初始群体 ， 这些个体一起组成了一个种群。 遗传算法 就是 以这个初始群体为起点开始迭代。 参数 N 可以根据 具体的情况 而定。 步骤三： 交叉算子：这是遗传算法最重要的操作。 所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。 遗传算法中起核心作用的就是交叉算子。 步骤四 ： 适应度： 确定个体适应度的量化评价方法， 适应度 用于 衡 量种群中个体的优劣性， 是确定 种群中个体留存的关键。 步骤五 ： 选择 算子： 选择 的目的是为了从交换后的群体中 选出 优良 的 染色体携带者，使 它们 有机会作为父 代 繁殖 出 下一代群体。 选择 操作 是建立在适应度之上的，适应度高的被选中的几率就大，选择操作体现出了 生物 适者生存的原 则。 步骤六 ： 变异 算子：变异 是根据 生物 遗传 中基因突变的原理， 以 变异概率 对 群体中的某一些个体 的 某些 “位 ”执行 变异。 变异 操作可以保证 算法 过程中不会产生无法进化的单一群体， 避免 算法 早熟 出现 局部最优。 步骤七 ： 终止。 给定最大的遗传代数，算法在计算到最大的遗传代数时，终止计算。 遗传 算法 算法 流程图 开始编码初始化染色体种群计算每个染色体的适应度满足终止条件根据适应度选择交叉变异输出最优解是否 7 图 24 遗传 算法算法流程图 遗传 算法的特点 遗传算法 属于进化算法 （ Evolutionary Algorithms） 的 一种，它通过模仿自然界的选择与 遗传的原理来求出最优解，遗传算法 有 三个 最 基本的算子：选择、交叉、变异。 数值 方法求解这一问题的主要手段是迭代运算。 一般的 迭代 方法容易陷入局部极小的陷阱而出现“ 死循环 ” 现象 ， 使迭代无法进行。 遗传算法 很好 地克服了这个缺点，是一种全局优化算法。 遗传 算法 与 传统的 优化 方法（ 枚举 ，启发 式 等） 相 比较，以生物进化为原型 ， 具有很多的 优点。 主要有 以 下几点： （ 1） 遗传 算法的本质并行性。 首先 ，遗传算法并行的方式 是 从问题 解 的串 集 开始搜索，而不是从单个解开始。 这是 遗传算法与 传统优化算法的 最 大区别。 传统 优化 算法从单个初始值迭代求最优解，容易 早熟 陷入局部最优解。 遗传算法 从 串集开始搜索，覆盖面大，有利于全局最优。 其次 ，算法内 含 并行性，遗传算法采用种群方式组织搜索，因而可同时搜索解空间的多个区域，并 相互 交流信息，能以较小的计算获得较大收益。 （ 2） 遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序 .仅 用 适应度函数值来评估个体 ，在 此基础上进行遗传操作。 适应度 函数 不仅不受连续可微的约束，而且其定义域可以任意的设定 ， 故几乎可处理任何问题。 （ 3） 遗传算法 不是采用确定性规则，而是采用概率的变迁规则来指导 它 的搜索方向 ，具有 自组织 、自适应和自学习性。 遗传算法 利用 进化过程获得信息自行组织搜索时，适应度高的个体具有较高的生存率，并获得更加适应环境的 染色体。 这种 通过自然选择与进化的机制消除了算法设计过程中的一个最大 障碍，即需要事先描述问题的 全部 特点， 并 要 说明 针对 所求 问题的不同 特点， 我们设计的算法应该采用的具体 措施。 所以 ， 遗传算法有很高的容错能力 ，我 们 可以 利用 遗传算法 解决复杂的 非 结构化问题。 （ 4） 遗传 算法可以直接用于实际应用当中，对于给定的问题，可以产生许多解，最终选择是根据用户自己的需求来选取，通用性 高 ， 实际 应用性强 ， 应用范围 广。 遗传 算法的应用 遗传 算法为求解复杂 系统问题 提供了一种通用的算法框架，它不取决于问题的 具体 领域，有很强的鲁棒性 ， 因而被广泛的 使用 于 组合 优化 、 机械设计、人工智能、数学建模、软件工程等领域。 （ 1） 函数 优化 函数 优化是遗传算法经典的应用领域 ，也是 使用最频繁的 领域。 尤其是 在数学领域，科学家 构造出了 许许多多复杂 的测试函数： 连续 函数、离散函数、凸函数、凹函数 、 单峰函数、多峰函数等等。 对于 这些 非线性、 求 极 值、 多模型或 多目标的 函数 优化 问题，用传统的优化方法很难解决，而用遗传算法可以 方便地 得到 较好的结果。 （ 2） 组合优化 随着 变量 n 的 不断增大，问题的规模增大，组合优化问题的求解空间也急剧增大， 应 8 用 传统的枚举法等就很难求出最优解。 对于 这一类 复杂的 问题 ， 遗传 算法 已经 被证实是十分有效的求解方式。 遗传 算法 已经在求解 TSP 问题、 01 背包 问题、 图形 划分问题等方面得到了成功的应用。 (3)生产调度问题 生产调度问题在很多情况下建立起来的传统数学模难以精确求解，虽然经过一些简化之后可以进行求解 .也会因简化得太多而使得求解结果与实际相差太大。 目前在现实生产中主要是靠一些经验来进行调度。 现在遗传算法已成为解决复杂调度问题的有效措施。 在单件生产车间调度、流水线生产间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。 （ 4）机器人 学 机器人是一类复杂的难以精确建模的人工系统， 而遗传算法的起源就来自于人工自适应系统的研究。 所以，机器人学理所当然地成为遗传算法的一个重要应用领域。 例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方而得到研究和应用。 （ 5）数据 挖掘 数据挖掘是近几年出现的数据库技术，它能够从大型数据库中提取隐含的、先前未知的、有潜在应用价值的知识和规则。 许多数据挖掘问题可看成是搜索问题，数据库看作是搜索空间，挖掘算法看作是搜索策略。 因此，应用遗传算法在数据库中进行搜索，对随机产生的一组规则进行进化 .直 到数据库能被该组规则覆盖，从而挖掘出隐含在数据库中的规则。 Sunil 已成功地开发了一个基于遗传算法的数据挖掘下具。 利用该工具对两个飞机失事的真实数据库进行了数据挖掘实验，结果表明遗传算法是进行数据挖掘的有效方法之一。 （ 6）人工 生命 人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。 自组织能力和自学习能力是人工生命的两大主要特征。 人工生命与遗传算法有着密切的关系。 基于遗传算法的进化模型是研究人工生命现象的重要基础理论。 虽然人工生命的研究尚处于启蒙阶段，但遗传算法已在其进化模 型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力，并且必将得到更为深入的应用和发展。 人工生命与遗传算法相辅相成，遗传算法为人工生命的研究提供一个有效的工具，人工生命的研究也必将促进遗传算法的进一步发展。 9 3 基于 遗传 算法求解 TSP问题 旅行商问题， 即 TSP 问题 又译为旅行推销员问题， 属于 NP 完全问题，是 数学领域中著名的 问题之一。 它可以 大致 描述 为 这样 ： 有一个旅行商人要拜访 n 个城市，他必须要 经过所有的城市 ，而且每个城市只能拜访一次，最后要回到原来出发的城市。 要求得的路径路程为所有可能路径之中的最小值， 即 最优值问题。 可以用如下公式表达 : n1 f(T)= ∑d(ti,ti+1)+d(nt,t1) i=1 本系统是 用遗传算法求解 45 个 城市的旅行商问题， 并对其 进行计算机仿真，做出一个能在计算机 上 运行的软件。 方式 编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键步骤。 因为编码方法将会影响到交叉算子、变异算子等遗传算子的运算方法，很大 的程度上决定了遗传进化的效率。 迄今为止人们已经提出了许多种不同的编码方法。 总的来说，这些编码方法可以分为三大类：二进制编码法、浮点编码法、符号编码法。 下面我们从具体实现角度出发介绍其中的几种主要编码方法。 ： 它由二进制符号 0 和 1 所组成的二值符号集。 它有以下一些优点： (1）编码、解码操作简单易行 (2)交叉、变异等遗传操作便于实现 (3)符合最小字符集编码原则 (4)利用模式定理对算法进行理论分析。 二进制编码的缺点是：对于一些连续函数的优化问题，由于其随机性使得其局部搜索能力较差，如对 于一些高精度的问题（如上题），当解迫近于最优解后，由于其变异后表现型变化很大，不连续，所以会远离最优解，达不到稳定。 而格雷码能有效地防止这类现象。 ： 对于一些多维、高精度。