毕业设计（论文）-遗传算法求解TSP问题的计算机仿真.doc

i 题目：题目：遗传算法求解旅行商问题的计算机仿真遗传算法求解旅行商问题的计算机仿真 ii 遗传算法求解遗传算法求解 tsptsp 问题的计算机仿真问题的计算机仿真 摘要摘要 由于遗传算法在整体搜索策略和优化搜索方法上不依赖梯度信息或其他辅助知识， 只需要影响搜索方向的目标函数和相应的适应度函数，所以提供了一种求解复杂系统问 题的通用框架，因此遗传算法广泛应用于数学问题、组合优化、机械设计、人工智能等 领域。 遗传算法（genetic algorithms,简称 ga）是模拟自然界生物自然选择和进化的机制 而发展起来的一种高度并行、自适应的随机搜索算法。特别适合于求解传统的搜索算法 不好处理的复杂的最优解问题。旅行商问题（traveling salesman problem）就是要决 定一条经过路线中所有城市当且仅当一次且距离最短的路线，即距离最短的 hamilton 回 路。旅行商问题是一个具有十分广泛的实用背景和重要理论价值的组合优化问题。目前 求解 tsp 问题的主要方法有模拟退火算法、遗传算法、hopfield 神经网络算法、启发式 搜索法、二叉树描述算法。本文选用遗传算法求解 45 个城市的 tsp 问题，基于 microsoft visual c+环境,采用 grefenstette 等提出的一种新的巡回路线编码方法， 变异算子采用了常规的基本位变异法，通过多组实验和数据近似的求解出了 45 个城市的 最优解，实现了计算机仿真求解 tsp 问题。 关键字：旅行商问题；遗传算法；变异算法；编码方式关键字：旅行商问题；遗传算法；变异算法；编码方式 iii the computer simulation of genetic algorithm to solve tsp problem abstract due to genetic algorithm on the overall search strategy and optimization search method does not depend on the gradient information or other auxiliary knowledge, only need to influence the search direction of the objective function and the corresponding fitness function, and so provides a generic framework for solving complicated system problem, so the genetic algorithm is widely used in mathematical problem, combinatorial optimization, mechanical design, artificial intelligence, etc genetic algorithm (based algorithms, the ga) is mimic natural biological natural selection and evolution mechanism and developed a kind of highly parallel, adaptive random search algorithm. particularly suitable for solving the traditional search algorithm is not good to deal with complex optimal solution of problem. traveling salesman problem (ll salesman problem) is to determine a through route if and only if all cities in time and distance is the shortest route, the shortest distance of hamilton loop. traveling salesman problem is a very wide range of practical background and important theoretical value of the combinatorial optimization problem. at present the main method of solving tsp problem with simulated annealing algorithm, genetic algorithm and hopfield neural network algorithm, the heuristic search method, the binary tree described algorithm. this article chooses 45 cities genetic algorithm to solve the tsp problem, based on microsoft visual c + + environment, use the proposed a new tour routes such as grefenstette coding method, mutation operator adopted conventional basic variation method, through multiple sets of experimental data and the approximate solution of the 45 cities the optimal solution, has realized the computer simulation to solve the tsp problem. key words: traveling salesman problem. genetic algorithm; mutation algorithm; iv 目录目录 遗传算法求解遗传算法求解 tsptsp 问题的计算机仿真问题的计算机仿真.i abstract.ii 1 绪论绪论.1 1.1 研究背景.1 1.2 研究意义.2 1.3 研究内容.2 1.4 本文的结构.3 2 遗传算法理论概述遗传算法理论概述.4 2.1 遗传算法的产生及发展.4 2.2 遗传算法基本原理.5 2.3 遗传算法基本步骤.6 2.4 遗传算法算法流程图.6 2.5 遗传算法的特点.7 2.6 遗传算法的应用.8 3 基于遗传算法求解基于遗传算法求解 tsp 问题问题.10 3.1 旅行商问题的描述与建模10 3.2 编码方式10 3.3 遗传算子的设计（交叉、选择、变异）12 3.3.1 交叉算子.12 3.3.2 选择算子.13 3.3.3 变异算子.14 3.4 适应度函数.15 3.5 遗传算法求解 tsp 问题的具体流程图.16 4 45 个城市旅行商问题的仿真软件的设计个城市旅行商问题的仿真软件的设计17 4.1 系统设计模块.17 v 4.2 系统详细设计.17 4.2.1 演示模块设计18 4.2.2 帮助模块设计21 4.3 测试结果及分析.22 4.3.1 测试一.22 4.3.2 测试二.24 4.3.3 测试三.26 4.3.4 测试四.28 4.3.5 测试五.29 5 结论结论.31 参考文献参考文献.32 谢谢 辞辞.33 附录一程序附录一程序34 附录二外文翻译附录二外文翻译.55 1 1 绪论绪论 自 20 世纪 60 年代以来,一种模拟生物自然遗传与进化过程并将生物进化原理、最优 化技术和计算机技术结合起来的优化方法遗传算法（genetic algorithm,简称 ga）被提 出并得到广泛研究，该算法特别适用于处理传统搜索方法难以解决的复杂和非线性问题， 可以广泛应用于人工智能、机械设计、自适应控制等领域。遗传算法固有的并行性和并 行计算的能力，使在搜索过程中不容易陷入局部最优。即使在所定义的适应度函数中是 不连续的、不规则的情况下，也可以很大概率找到全局最优解。采用自然进化机制来表 现复杂的现象，能够快速可靠地解决求解非常困难的问题，非常适用于本课题涉及的 tsp 问题的求解与研究。 旅行商问题（traveling salesman problem ,tsp）是一个非常经典的组合优化问题的 np 难题，长期以来都没有一个十分有效的算法来解决它，但 tsp 本身在许多领域有着重 要的应用，如连锁店的货物配送路线、计算机网络路由器遍历、印刷电路板的钻孔路线 等问题都可以建模为旅行商问题。tsp 问题其实是“哈密顿回路问题”中的“哈密顿最短 回路问题” 。在本系统就是要应用遗传算法求解 45 个城市的 tsp 问题。因为遗传算法本 身是模拟生物自然选择和遗传的过程的，所以用遗传算法求解 tsp 最先要确定的是问题 的建模，即如何用遗传学的算子来表示旅行商问题中的变量。必需要非常的了解，并熟 悉每一个遗传学中的术语在遗传学中的具体作用，然后应用到求解具体问题当中来。应 用遗传算法求解旅行商问题最关键的是编码方式、交叉、选择、变异算子的设计，直接 关系到算法能否求出最优解或近似最优解。所以要在编码方式的确定上做好足够的功夫， 以确定程序求解的精确度。 本章主要论述本文所研究的主要内容，并对论文的章节结构进行规划。 1.11.1 研究背景研究背景 旅行商问题（traveling salesman problem, tsp）,也称旅行推销员问题，具体的数学 模型可以这样理解：现在给定以下几个城市的位置，旅行商从其中的某一个城市出发， 不重复地访问其余的每一个城市，最后又返回到原出发点城市，要求找出这样一条路线， 使旅行所付出的代价最小。虽然它是一个比较古老的问题，最早可以追溯到 euler 提出的 骑士旅行问题，但同时它也是一个新的问题，因为它的计算复杂度较高，虽然人们一直 在尝试用新的方法来改进求解该问题的复杂度，但是这一类问题距今都没有能找到一个 有效的算法来解决。 2 tsp 问题可以形式化描述为：设 g=（v,a,d）是一个图，其中 v 是 n 个顶点的集合， a 是弧线或边集,d=（）是与 a 关联的距离或费用矩阵。旅行商问题就是要解决一个 ij 最小回路问题，回路中所有顶点有且仅经过一次。对于具有一个城市的旅行商问题，其 可能的路径数目为（n-1）！/2，5 个城市的问题模型就对应 120/10=12 条路线，10 个城市 的问题模型对应 3628800/20=181440 条路线。所以当输入越大，则耗费的时间就是个天文 数字了，因此旅行商问题至今都没有能找到一种有效的求解方法。寻求一种能短时间求 解出高精度解的算法，已成为此问题研究的热门。尽管旅行商问题至今仍然没有找到最 优解，但求解它的算法已经在不断的改进。目前，求解 tsp 问题常用的算法主要有遗传 算法和蚁群算法，另外还有爬山法、模拟退火算法、神经网络方法、贪婪算法、禁忌搜 索算法等。1980crowder 和 padberg 求解了 318 个城市的 tsp 问题；1987 年 padberg 和 rinaldi 成功将城市数量增加到了 2392 个；最大的成功求解的旅行商问题已经增加到 24798 个城市。 1.21.2研究意义研究意义 首先旅行商问题是用于求解 n 个城市存在（n-1）条闭合路径的排列方案，对于这一 类问题很难用全局搜索法精确地求出最优解，这一问题已经困扰众多学者许多年，因此 研究相应的算法寻找其最优或近似最优解是非常必要的。 其次，随着旅游业的快速发展，大量的旅客在旅途中浪费了不必要的时间和金钱， 而这些不必要的浪费完全可以通过对旅行路线的合理规划来避免。而在互联网继续扩大 普及的时代，电子商务也迎来了期待已久的春天，同时物流产业也随之水涨船高。毫无 疑问，高效、低成本、低能耗成了各个物流企业追求的目标，更加合理的配送路线能明 显地为物流公司增大利润。再比如在装配线的流程中，对每个工件为完成装配过程节约 的少许时间意味着一天的产量的相应增加。由于旅行商问题在计算机网络、物流、旅游 业、交通运输等许多领域都有着十分广泛的应用，因此寻找一个求解这类问题的求解方 法有很高的应用价值 因此，对旅行商问题有效算法的研究不仅具有重要的理论意义，而且具有重大的实 际应用价值。 1.31.3研究内容研究内容 本文采用遗传算法求解 45 个城市的旅行商问题，并对其实现计算机仿真。遗传算法 （genetic algorithms,ga）又叫基因进化算法或进化算法，是一种通过模拟自然界生物适 者生存、优胜劣汰的进化过程而形成的一种自适应、具有全局优化能力的随机搜索算法。 应用遗传算法求解旅行商问题，最难得地方在于问题建模，如城市编码方式以及交叉、 变异、选择算子的确定等。 本文采用的是 grefenstette 等提出的一种新的巡回路线编码方法，其可以在一定程度 上克服常规巡回路线编码方法在交异操作时易产生不满足问题约束条件或无实际意义的 巡回路线的缺点。交叉算法采用的是常规的单点交叉，之所以可以用这一常规的交叉法， 是因为在编码方式上使用的是 grefenstette 等提出的一种新的巡回路线编码方法，它可以 3 最大化交叉后后代与其父代的性状差异，有利于算法的全局性。变异算法采用的是基本 位变异法，即只是根据变异概率随机改变染色体中的某一段染色体，具体会在后文中做 详细说明。在遗传算法中，以个体适应度的大小来确定该个体被遗传到下一代群体中的 概率。本课题中以每条路径长度的倒数作为适应度函数值。在求出之后将其按照从大到 小的顺序排列，以便于后面找出路径之和最小的城市序列。 1.41.4 本文的结构本文的结构 本文一共分为 5 章，结构如下： 第一章绪论。这一章主要论述旅行商问题的基本概念，以及本课题主要的研究方法 及其研究意义，并对论文的章节结构加以论述。 第二章遗传算法理论概述。这一章主要论述遗传算法的起源发展及其实际应用，重 点介绍了遗传算法的算法原理及步骤。 第三章基于遗传算法求解 tsp 问题。本章主要介绍了本系统具体使用什么方式实现 求解过程，包括编码方式、选择、交叉、变异算子的具体选取。 第四章 45 个城市旅行商问题的仿真软件的设计。本章主要对系统模块进行了介绍， 而且对应用系统进行了多组试算，最后得出结论。 第五章结论。对本文的内容进行总结。 4 2 遗传算法遗传算法理论概述理论概述 2.12.1 遗传算法的产生及发展遗传算法的产生及发展 最早由美国 michigan(密执安大学)的 hollang 教授提出，起源于 60 年代对自然和人工 自适应系统的研究。1967 年，他的学生 bagley j.d.首次提出“遗传算法”一词，并发展了 复制、交叉、变异、显性、倒位等遗传算子。70 年代 de jong 基于遗传算法的思想在计 算机上进行了大量纯数值函数优化计算实验，建立了著名的 de.jong 五函数测试平台。在 一系列研究工作的基础上 80 年代 goldberg 进行总结归纳，形成了遗传算法的基本框架； smith 将遗传算法应用于机械学习领域；bethke 对函数优化的遗传算法进行了系统的研究。 进入 90 年代，遗传算法进入了兴盛期，无论是理论研究还是实际应用都成了十分热门的 课题。如今遗传算法已经被广泛的应用于计算机科学、人工智能、机械设计、图像处理 等各个领域，不仅如此，利用遗传算法进行理论研究的优化和最优解问题的解决能力也 显著提高。 下面是一些在遗传算法发展进程中做出杰出贡献的人物： 1 j.h.holland 60 年代提出在研究和设计人工自适应系统时,可以借鉴生物遗传的机制； 70 年代初提出了遗传算法的基本定理模式定理(schema theorem)，从而奠定了遗传 算法的理论基础； 80 年代实现了第一个基于遗传算法的机器学系统分类器系统(classifier systems),开 创了基于遗传算法的机器学习的新概念。 2 j.d.bagley 1967 年在其博士论文中首次提出了：“遗传算法”一词，发展了复制、交叉、变异、 显性、倒位等遗传算子，创立了自适应遗传算法的概念。 3 k.a.de jong 1975 年在其博士论文中结合模式定理进行了大量的纯数值函数优化计算实验，树立 了遗传算法的工作框架，定义了评价遗传算法性能的在线指标和离线指标。 4 d.j.golgberg 1989 年出版了专著搜索、优化和机器学习中的遗传算法(genetic algorithms in search，optimization and machine learning) ，系统总结了遗传算法的主要研究成果，全 面而完整的论述了遗传算法的基本原理及其应用。 5 l.davis 1991 年编辑出版了遗传算法手册 (handbook of genetic algorithms)书中包括遗传 算法在科学计算、工程技术和社会经济中的大量应用实例。 6j.r.koza 1992 年将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程 (genetic programming) 的概念，并成功的将其提出的遗传编程应用于人工智能、机器学 33 习符号处理等方面。 6 2.22.2 遗传算法基本原理遗传算法基本原理 遗传算法是受大自然的启发，模拟生物在自然环境中的遗传和进化过程而形成的一 种自适应、具有全局优化能力的随机搜索算法。 遗传算法的思路是通过从给定一个初始群体出发，利用选择算子、交叉算子以及变 异算子来模拟自然进化的三种原则，逐步改进种群，越来越逼近最优解，以达到求解最 优化问题的目的。在遗传算法中，种群中的每一个个体是问题的一个解，称为“染色体” ， 染色体是一串符号，比如二进制的 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）染色体：是生物细胞中含有的一种微小的丝状化合物，是遗传物质的主要载体， 由多个遗传因子基因组成。 7 2.32.3 遗传算法基本步骤遗传算法基本步骤 步骤一：编码：把所需要选择的群体进行编号，每一个个体就是一条染色体，一个 解就是一串基因的组合。 步骤二：初始化：随机生成有 n 个个体的初始群体，这些个体一起组成了一个种群。 遗传算法就是以这个初始群体为起点开始迭代。参数 n 可以根据具体的情况而定。 步骤三：交叉算子：这是遗传算法最重要的操作。所谓交叉是指把两个父代个体的 部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。 步骤四：适应度：确定个体适应度的量化评价方法，适应度用于衡量种群中个体的 优劣性，是确定种群中个体留存的关键。 步骤五：选择算子：选择的目的是为了从交换后的群体中选出优良的染色体携带者， 使它们有机会作为父代繁殖出下一代群体。选择操作是建立在适应度之上的，适应度高 的被选中的几率就大，选择操作体现出了生物适者生存的原则。 步骤六：变异算子：变异是根据生物遗传中基因突变的原理，以变异概率对群体中 的某一些个体的某些“位”执行变异。变异操作可以保证算法过程中不会产生无法进化的单 一群体，避免算法早熟出现局部最优。 步骤七：终止。给定最大的遗传代数，算法在计算到最大的遗传代数时，终止计算。 2.42.4 遗传算法算法流程图遗传算法算法流程图 开始 编码 初始化染色体种群 计算每个染色体的适应 度 满足终止条件 根据适应度选择 交叉 变异 输出最优解 是 否 8 图 2-4 遗传算法算法流程图 2.52.5 遗传算法的特点遗传算法的特点 遗传算法属于进化算法（evolutionary algorithms）的一种，它通过模仿自然界的选 择与遗传的原理来求出最优解，遗传算法有三个最基本的算子：选择、交叉、变异。数 值方法求解这一问题的主要手段是迭代运算。一般的迭代方法容易陷入局部极小的陷阱 而出现“死循环”现象，使迭代无法进行。遗传算法很好地克服了这个缺点，是一种全 局优化算法。 遗传算法与传统的优化方法（枚举，启发式等）相比较，以生物进化为原型，具有 很多的优点。主要有以下几点： （1）遗传算法的本质并行性。首先，遗传算法并行的方式是从问题解的串集开始搜 索，而不是从单个解开始。这是遗传算法与传统优化算法的最大区别。传统优化算法从 单个初始值迭代求最优解，容易早熟陷入局部最优解。遗传算法从串集开始搜索，覆盖 面大，有利于全局最优。其次，算法内含并行性，遗传算法采用种群方式组织搜索，因 而可同时搜索解空间的多个区域，并相互交流信息，能以较小的计算获得较大收益。 （2）遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序.仅用适应度 函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束， 而且其定义域可以任意的设定，故几乎可处理任何问题。 （3）遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导它的搜索方向， 具有自组织、自适应和自学习性。遗传算法利用进化过程获得信息自行组织搜索时，适 应度高的个体具有较高的生存率，并获得更加适应环境的染色体。这种通过自然选择与 进化的机制消除了算法设计过程中的一个最大障碍，即需要事先描述问题的全部特点， 并要说明针对所求问题的不同特点，我们设计的算法应该采用的具体措施。所以，遗传 算法有很高的容错能力，我们可以利用遗传算法解决复杂的非结构化问题。 （4）遗传算法可以直接用于实际应用当中，对于给定的问题，可以产生许多解，最 终选择是根据用户自己的需求来选取，通用性高，实际应用性强，应用范围广。 2.62.6 遗传算法的应用遗传算法的应用 遗传算法为求解复杂系统问题提供了一种通用的算法框架，它不取决于问题的具体 领域，有很强的鲁棒性，因而被广泛的使用于组合优化、机械设计、人工智能、数学建 模、软件工程等领域。 （1）函数优化 函数优化是遗传算法经典的应用领域，也是使用最频繁的领域。尤其是在数学领域， 科学家构造出了许许多多复杂的测试函数：连续函数、离散函数、凸函数、凹函数、单 峰函数、多峰函数等等。对于这些非线性、求极值、多模型或多目标的函数优化问题， 用传统的优化方法很难解决，而用遗传算法可以方便地得到较好的结果。 （2）组合优化 9 随着变量 n 的不断增大，问题的规模增大，组合优化问题的求解空间也急剧增大， 应用传统的枚举法等就很难求出最优解。对于这一类复杂的问题，遗传算法已经被证实 是十分有效的求解方式。遗传算法已经在求解 tsp 问题、01 背包问题、图形划分问题等 方面得到了成功的应用。 (3)生产调度问题 生产调度问题在很多情况下建立起来的传统数学模难以精确求解，虽然经过一些简 化之后可以进行求解.也会因简化得太多而使得求解结果与实际相差太大。目前在现实生 产中主要是靠一些经验来进行调度。现在遗传算法已成为解决复杂调度问题的有效措施。 在单件生产车间调度、流水线生产间调度、生产规划、任务分配等方面遗传算法都得到 了有效的应用。 （4）机器人学 机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于人工自 适应系统的研究。所以，机器人学理所当然地成为遗传算法的一个重要应用领域。例如， 遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、 细胞机器人的结构优化和行为协调等方而得到研究和应用。 （5）数据挖掘 数据挖掘是近几年出现的数据库技术，它能够从大型数据库中提取隐含的、先前未 知的、有潜在应用价值的知识和规则。许多数据挖掘问题可看成是搜索问题，数据库看 作是搜索空间，挖掘算法看作是搜索策略。因此，应用遗传算法在数据库中进行搜索， 对随机产生的一组规则进行进化.直到数据库能被该组规则覆盖，从而挖掘出隐含在数据 库中的规则。sunil 已成功地开发了一个基于遗传算法的数据挖掘下具。利用该工具对两 个飞机失事的真实数据库进行了数据挖掘实验，结果表明遗传算法是进行数据挖掘的有 效方法之一。 （6）人工生命 人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为 的人造系统。自组织能力和自学习能力是人工生命的两大主要特征。人工生命与遗传算 法有着密切的关系。基于遗传算法的进化模型是研究人工生命现象的重要基础理论。虽 然人工生命的研究尚处于启蒙阶段，但遗传算法已在其进化模型、学习模型、行为模型、 自组织模型等方面显示出了初步的应用能力，并且必将得到更为深入的应用和发展。人 工生命与遗传算法相辅相成，遗传算法为人工生命的研究提供一个有效的工具，人工生 命的研究也必将促进遗传算法的进一步发展。 10 3 基于遗传算法求解基于遗传算法求解tsp问题问题 3.13.1旅行商问题的描述与建模旅行商问题的描述与建模 旅行商问题，即 tsp 问题又译为旅行推销员问题，属于 np 完全问题，是数学领域 中著名的问题之一。它可以大致描述为这样：有一个旅行商人要拜访 n 个城市，他必须 要经过所有的城市，而且每个城市只能拜访一次，最后要回到原来出发的城市。要求得 的路径路程为所有可能路径之中的最小值，即最优值问题。 可以用如下公式表达: n-1 f(t)= d(ti,ti+1)+d(nt,t1) i=1 本系统是用遗传算法求解 45 个城市的旅行商问题，并对其进行计算机仿真，做出一 个能在计算机上运行的软件。 3.23.2编码方式编码方式 编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键步骤。 因为编码方法将会影响到交叉算子、变异算子等遗传算子的运算方法，很大的程度上决 定了遗传进化的效率。迄今为止人们已经提出了许多种不同的编码方法。总的来说，这 些编码方法可以分为三大类：二进制编码法、浮点编码法、符号编码法。下面我们从具 体实现角度出发介绍其中的几种主要编码方法。 1.二进制编码方法： 它由二进制符号 0 和 1 所组成的二值符号集。它有以下一些优点： (1）编码、解码操作简单易行 (2)交叉、变异等遗传操作便于实现 (3)符合最小字符集编码原则 (4)利用模式定理对算法进行理论分析。 二进制编码的缺点是：对于一些连续函数的优化问题，由于其随机性使得其局部搜 索能力较差，如对于一些高精度的问题（如上题） ，当解迫近于最优解后，由于其变异后 表现型变化很大，不连续，所以会远离最优解，达不到稳定。而格雷码能有效地防止这 类现象。 2.浮点编码法： 对于一些多维、高精度要求的连续函数优化问题，使用二进制编码来表示个体时将 会有一些不利之处。 二进制编码存在着连续函数离散化时的映射误差。个体长度较知时，可能达不到精 度要求，而个体编码长度较长时，虽然能提高精度，但却使遗传算法的搜索空间急剧扩 大。 11 所谓浮点法，是指个体的每个基因值用某一范围内的一个浮点数来表示。在浮点数 编码方法中，必须保证基因值在给定的区间限制范围内，遗传算法中所使用的交叉、变 异等 12 遗传算子也必须保证其运算结果所产生的新个体的基因值也在这个区间限制范围内。 浮点数编码方法有下面几个优点： （1)适用于在遗传算法中表示范围较大的数 （2)适用于精度要求较高的遗传算法 （3)便于较大空间的遗传搜索 （4)改善了遗传算法的计算复杂性，提高了运算交率 （5)便于遗传算法与经典优化方法的混合使用 （6)便于设计针对问题的专门知识的知识型遗传算子 （7)便于处理复杂的决策变量约束条件 3.符号编码法： 符号编码法是指个体染色体编码串中的基因值取自一个无数值含义、而只有代码含 义的符号集如a,b,c 。 符号编码的主要优点是： （1)符合有意义积术块编码原则 （2)便于在遗传算法中利用所求解问题的专门知识 （3)便于遗传算法与相关近似算法之间的混合使用。 但对于使用符号编码方法的遗传算法，一般需要认真设计交叉、变异等遗传运算的 操作方法，以满足问题的各种约束需求，这样才能提高算法的搜索性能。 使用遗传算法第一件事情就是确定染色编码方式，它根据不同的问题模型使用不同 的编码方式，本系统使用的是 grefenstette 等提出的一种新的巡回路线编码方法，是一种 整数编码的方式。对于每个城市用一个整数来编号，例如有 45 个城市，就用 0 到 45 来 标识每一个城市，然后一个路径就是一条染色体编码，染色体长度为 45，如： 0,1,2,3,4.44 就是一个染色体，它表达的意思就是旅行者从 0 号城市出发，依次访问 1,2,.44 号城市再回到 0 号城市；下面具体具体介绍一下这一种编码方法。 对于给定的旅行商问题，设其城市列表 w，假定对各个城市的访问顺序为 t： t=（t1，t2，t3，tn） 规定每访问完一个城市，就从城市列表 w 中将该城市除去，则用第 i（i=1,2,3n）个所访问的城市 ti 在所有未访问城市列表 w=t1，t2，t3，ti-1中 的对应位置序号 gi（1gin-i+1）就可表示具体访问哪个城市，如此这样直到处理完 w 中所有的城市。将全部 gi 顺序排列在一起所得到的一个列表： g=（g1，g2，g3，gn） 这样就可以表示一条巡回路线，它就是遗传算法中的一个个体基因。例如，假设现 在有这样一个城市序列： w=(a,b,c,d,e,f,g,h,i,j) 有如下两条巡回路线： t1=(a,d,b,h,f,i,j,g,e,c) t2=(b,c,a,d,e,j,h,i,f,g) 则按本系统所用的编码方法，这两条巡回路线可以编码为： 13 g1 =(1,3,1,5,3,4,4,3,2,1) g2 =(2,2,1,1,1,5,3,3,1,1) 这种编码方式的优点在于任意的染色体都对应一条有实际意义的巡回路线，因此可 以使用常规的交叉算子对它进行计算，有利于算法的实现。 3.33.3遗传算子的设计（交叉、选择、变异）遗传算子的设计（交叉、选择、变异） 3.3.13.3.1 交叉算子交叉算子 交叉运算，一般指对两个相互配对的染色体依据交叉概率 pc 按某种方式相互交换 其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要 特征，它在遗传算法中起关键作用，是产生新个体的主要方法。求解旅行商问题的遗传 算法的交叉算法主要有：部分匹配交叉（pmx） 、循环交叉（cx） 、次序交叉（ox） 、线 性次序交叉（lox） 、边重组交叉（ex）等。本系统使用的是常规的单点交叉算子。 由于在确定算法的编码方式的过程中使用的是 grefenstette 等提出的编码方式，用这 种编码方式表示个体时，个体的基因型和表现型之间是一一对应的，它使经过运算之后 得到的每一个基因型都是一条有实际意义的巡回路线。因此，就可以使用常规的单点交 叉算子。使用单点交叉，即在个体的编码串上随机设置一个交叉点，然后在该点相互交 换两个配对个体的部分染色体。产生下一代个体在使用 grefenstette 等提出的编码方式时， 染色体编码串前面的一些基因发生变化时，会对后面的基因值产生巨大的影响，产生的 新的个体与上一代的性状变化就会十分明显，有利于整个算法跳出局部最优解。如下是 具体代码： for(i=0;itemp) parent1=temp; parent2=randomint(0,m_ngroupsize-1); temp=randomint(0,m_ngroupsize-1); if(parent2temp) parent2=temp; /复制用于交叉的基因对 popnode pop1; popnode pop2; 14 pop1.copynode( pop2.copynode( / 基因序列中用于交叉的基因位 npos=randomint(3,maxchrom-3); pop1.crosstwo( /交叉完成,保存结果 newpopm_ngroupsize+2*i.copynode( newpopm_ngroupsize+2*i+1.copynode( 3.3.23.3.2 选择算子选择算子 选择操作是建立在对个体适应度进行评价的基础之上的。选择操作的目的是为了避 免基因缺失、提高全局收敛性和计算效率。本课题采用最常用的选择算子比例选择 算子（又称轮盘赌选择） 。其基本思想是：各个个体被选中的概率与其适应度大小成正比。 适应度越高的个体被选中的概率也越大；反之，适应度越低的个体被选中的概率也越小。 具体操作如下： 计算出群体中每个个体的适应度 f(i=1，2，m)，m 为群体大小； 归一化适应度 f 的值 将适应度 f 的值从大到小排列，查找其中最小费用的个体然后将其作为下一代选择出 来。 具体代码如下： for(int gen=0;genmax) 15 max=oldpopj.fit; maxpos=j; if(i!=maxpos) oldpopi.swapnode( m_curganum=gen; / 查找当前一代中的最小费用个体 m_minicost=oldpop0.cost; m_pop.copynode( m_gafitness=m_pop.fit; /afxmessagebox(“显示数据“); updatedata(false); updatewindow(); if (m_curganum = m_ganum - 1) / 绘制图形 drawnetwork(); /继承所有父代基因 for(i=0;irectangle(workarea); pdc-setbkcolor(0x00ffffff); int px=workarea.left; int py=workarea.bottom+20; pdc-settextcolor(0x00f08080); for(int i=0;iellipse(city);（以城市位置为圆心画圆） 4.2.24.2.2 帮助模块设计帮助模块设计 （1）关于作者：在 vc 工具栏 insent 中插入窗口,窗口 id 为 idd_auth，并对其添 加如下操作： protected: virtual void dodataexchange(cdataexchange* pdx); (执行数据绑定的功能,用于显 示关于作者信息) 再拖入一个按钮，在此处可以对其添加函数声明，该函数执行确定操作： void cauthdlg:onok() / todo: add extra validation here 24 cdialog:onok(); （2）关于软件：在 vc 工具栏 insent 中插入窗口 idd_aboutbox，对其添加如下 操作： enum idd = idd_aboutbox (指定窗口 id) protected: virtual void dodataexchange(cdataexchange* pdx); (数据绑定,显示关于软件的 信息 ) 再拖入一个按钮，在此处可以对其添加响应函数： void caboutdlg:onok() / todo: add extra validation here cdialog:onok(); 4.34.3 测试结果及分析测试结果及分析 4.3.14.3.1 测试一测试一 如下图所示，本次测试的是默认的参数m，t，pc，pm=200，100，0.3，0.03，所取 数值都在系统设置的参考范围之内。经过算法运算之后，结果如下图所示： 图4-2 25 图4-3 图4-4 26 图4-5 通过对图 4-2、4-3、4-4 的分析可知，由于本次试算设置的群体大小、交叉概率、变 异概率、进化代数这几个参数都在规定范围内，通过运行，算法运行到指定的进化代数 之后停止运行，并输出了当前群体中的最小费用路径的大小，即城市路径总长度最短者。 基于本系统使用的所有算法计算出了最短路径的城市序列后，依次将两两城市之间路径 长度累加就得到最小费用路径，也就是城市最短路径。如上图所示，以相同的参数连续 执行三次遗传算法演示，最小费用不同，但相差并不是很大。但是从图 4-5 可以看出此次 运算的结果偏大许多，这就体现了出了遗传算法的特点：是不断搜索出适应度较高的个 体，并在群体中增加其数量，最终求出问题的最优解或近似最优解，所以其最后的求解 结果是有一定的波动的。 4.3.24.3.2 测试二测试二 如图 4-5、4-6、4-7、4-8 所示，本次测试的分别设置了m，t，pc，pm =500，100，0.3，0.03，m，t，pc，pm=1000，100，0.3，0.03。这两种情况分别 进行了两次实验。下实验结果分别如下图所示： 27 图4-6 图4-7 28 图 4-8 通过对图 4-6、7、8 可以看出，算法经过运算之后，其求解的结果有一定的更优的趋 势，但是通过运算的计算时间却大大的增加了，当种群数量小时的计算时间短，但是当 增加到 500 后，时间明显感觉增加；但增加到 1000 后，时间非常长，而且系统会变得十 分不稳定，出现卡死现象，可以看出合理的种群设置，对于算法时间复杂度以及系统稳 定性上有很大的影响。 4.3.34.3.3 测试三测试三 如图 4-9、4-10 所示，本次测试分别设置m，t，pc，pm=200，100，0.3，0， m，t，pc，pm=200，100，0.3，1。这是两个极端情况，群体规模不变而变异概率 变异概率变为 0 时即种群中没有染色体变异；变异概率为 1 时，所有染色体全部变异。 仿真结果见图 4-11，4-12： 29 图 4-9 图 4-10 图 4-11 30 图 4-12 如上图所示，本次测试只改变参数变异概率，其它参数保持不变。当变异概率为 0 时，结果如上图所示，最小费用明显大于测试一许多；当变异概率为 1 时，系统提示， 群体规模交叉变异设置有误。测试表明，变异概率取值太小则变异操作将不能产生新个 体或很少生成新个体，将会导致结果出现早熟现象，即求出的解离最优解有一定距离， 严重影响搜索结果；变异概率太大虽能够产生出较多的新个体，但也有很大的可能破坏 系统的稳定性，可能会破坏较好基因，同样严重影响系统搜索性能。 4.3.44.3.4 测试四测试四 如图 4-13 所示，本次测试分别设置m，t，pc，pm=200，100，0，0.03，交叉概 率为 0，其他参数不变，即交叉个体数目为 0。仿真结果见图 4-14。 31 图 4-13 图 4-14 如图所示，当交叉率设置为 0 时，即群体中的交叉算法不起作用，经过运算后的实 验结果显示与试验一有一定的差距。所以说交叉算法是遗传算法中必不可缺的算子，它 有利于算法跳出局部性，提高了算法求解最优解的几率。 4.3.54.3.5 测试五测试五 如图 4-15 所示，本次测试分别设置m，t，pc，pm=200，100，0，0，交叉、变 异概率均为 0，可知交叉、变异个体数目均为 0，其他参数不变。仿真结果见图 4-16。 32 图 4-15 图 4-16 如上图所示，本次测试设置交叉和变异概率均为 0，只有选择算子起作用，显然遗传 算法搜索结果与实际结果相差巨大。可以看出选择算子是随机操作，误差较大，只有选 择算子起作用对于实验结果没有实际意义。 33 5 结论结论 本课题主要对遗传算法的基本原理进行研究，并针对实例实现基于遗传算法的具体 搜索过程。通过对本课题的研究，我们可以看到，遗传算法可用于旅行商问题近似最优 解的研究。多次测试结果表明，遗传算法在求解过程中能收敛于某一稳定的“最好解” 。 在求解质量上和优化效率上均高于其他算法。 针对求解旅行商问题，本课题在 microsoft visual c+环境下解决了 45 个城市的 tsp 问题，主要包括以下几个方面： （1）基于初期研究，确定算法的基本实现过程。 （2）针对具体问题，设计各个模块，仿真实现遗传算法。 各种遗传算法总是依赖于问题的编码以及遗传操作算子。要发展遗传算法也要以这 几个方面作为突破口。各种求解 tsp 问题的算法里面都包含启发式的信息或者是在编码 过程中包含有边的信息(如矩阵表示和矩阵交叉等)，我认为这是一种趋势。尽管对遗传算 法有很多改进和发展，但是总是可以找到更好的算法。对于遗传算法求解旅行商问题， 我认为最大的一个问题是：很难保证染色体的完