南 京 理 工 大 学
毕业设计说明书(论文)
作 者: 学院(系): 专 业: 题 目:
杨敏 学 号： 0606230236
计算机科学与技术学院 计算机科学与技术
基于遗传算法的TSP问题求解方法
的研究与实现
朱保平 副教授 指导者：
(姓 名) (专业技术职务)
评阅者：
(姓 名) (专业技术职务)
2010年 5 月
毕业设计说明书（论文）中文摘要
旅行商问题是一个典型的NP完全问题，遗传算法是解决这类问题一个比较理想的算法。遗传算法是近年来迅速发展起来的一种全新的随机搜索与优化方法。它的基本思想来自于Darwin的进化论和Mendel的遗传学。 论文首先对遗传算法和旅行商问题进行了简单的描述。接着用数学的方式描述了TSP问题。然后，阐述了遗传算法在编码表示和遗传算子（包括选择算子、交叉算子、变异算子）等其他方面的应用情况，最后通过对初始种群、交叉率、变异率、遗传代数等参数进行修改、测试、对比、来验证这些参数对算法的求解结果和求解效率的影响。 关键字 遗传算法 旅行商问题 遗传算子 编码
毕业设计说明书（论文）外文摘要
Title Solving Traveling Salesman Problem by Genetic Algorithm Abstract TSP (Traveling Salesman Problem) is a typical NP - complete problem and genetic algorithm (GA) is the perfect method for solving NP - complete problem. Genetic Algorithm (Genetic Algorithm, GA) is a new random search and optimization algorithm ，develop rapidly in recent years, the basic idea of the theory is Darwin and Mendel's genetics. Paper first introduces genetic algorithm and Tsp. Then paper describes the mathematical approach the problem of TSP，and then paper explains that genetic algorithm coding and genetic operators(including selection operator, crossover operator, mutation operator) and other aspects of the application。 Finally, the initial population, crossover rate, mutation rate, genetic algebra modifies the parameters, testing, comparison, To verify these parameters on the algorithm results and efficiency. Keywords genetic algorithm TSP genetic operator coding 本科毕业设计说明书（论文）
目 次
第 I 页 共 I 页
1 引言 .............................................................................................................................. 1 1.1 研究背景 ...................................................................................................................... 1 1.2 国内外发展现状 .......................................................................................................... 1 1.3 本文研究的内容 .......................................................................................................... 3 1.4 本文结构 ...................................................................................................................... 3 2 遗传算法与TSP问题介绍 .......................................................................................... 5 2．1 遗传算法介绍 .............................................................................................................. 5 2.1.1遗传算法简介 ............................................................................................................. 5 2.1.2 遗传算法应用中的关键问题 .................................................................................... 6 2.1.2 遗传算法特点 ............................................................................................................ 8 2.1.3 遗传算法的应用步骤 ................................................................................................ 9 2.1.4 遗传算法的流程图 .................................................................................................. 10 2.2 TSP问题介绍 ........................................................................................................... 10 3 遗传算法在TSP上的应用与实现 .......................................................................... 12 3.1 算法的实现 .............................................................................................................. 12 3.1.1 遗传算法运用在TSP上的流程图 .......................................................................... 12 3.1.2 编码 .......................................................................................................................... 13 3.1.3 初始化种群 .............................................................................................................. 13 3.1.4 适应度函数 .............................................................................................................. 14 3.1.5 选择操作 .................................................................................................................. 14 3.1.6 交叉操作 .................................................................................................................. 17 3.1.7 变异操作 .................................................................................................................. 21 3．2 不同参数下的计算结果对比 .................................................................................. 21 3.2.1 初始种群10和100的对比 .................................................................................... 21 3.2.2 不同交叉率和变异率的对比 .................................................................................. 24 3．3 程序计算过程截图 .................................................................................................. 25 4 混合遗传算法的展望 .............................................................................................. 28 结 论 .................................................................................................................................. 30 致 谢 .................................................................................................................................. 31 参 考 文 献 ........................................................................................................................ 32
本科毕业设计说明书（论文）
1 引言
第 1 页 共 32 页
在过去,人们往往只能够处理一些简单的问题，对于大型复杂系统的优化和自适应仍然无能为力。但是在自然界中，生物在这方面表现出了其优异的能力，他们能够通过优胜劣汰、适者生存的自然进化规则进行生存和繁衍，并且慢慢的产生对其生存环境适应性越来越高的优良物种。遗传算法就是模拟自然进化的一种高效的算法。其基本思想就是模拟自然界进化机制和生物进化论而形成的一种过程搜索最优解得算法。
遗传算法是一门新的学科，各种理论、方法都尚未成熟，有待于进一步地发展和完善，但它却让我们看到了解决许多复杂问题的希望。尽管在遗传算法的研究和应用过程中出现过许多难题，同时也会产生许多不同的算法设计，但是，目前遗传算法的运用过程中已经展现出了其优异的性能和巨大的发展前景。我们相信，随着研究工作的进一步深入和发展，遗传算法一定能够在智能计算领域中起到关键性作用。
巡回旅行商问题(Traveling Salesman Problem, TSP),是一个著名的组合优化问题[1],该类问题具有很强的运用背景。如数控机床上的最优钻孔路线的选取、电路板的焊接、物流的调度问题都属于旅行商问题。因此旅行商问题受到了各方面的关注。目前解决TSP问题的主要方法有启发式搜索法、模拟退火算法、遗传算法、Hopfield神经网络算法、二叉树描述算法。有效解决TSP问题在计算理论和实际应用上都有很高的价值。本文主要介绍了运用遗传算法来解决TSP问题。
1.1 研究背景
如今的科学技术正在步入多学科相互交叉、互相渗透、互相影响的时代、生命科学与工程科学的交叉、渗透和相互促进是其中一个典型的例子，也是近代科学技术发展的一个显著点。遗传算法从此诞生。
TSP问题，也称为巡回旅行商问题，就是为人们所广泛研究的典型的组合优化为题。而且TSP问题由于其典型性已经成为各种启发式的搜索、优化算法(如遗传算法、神经网络优化法、列表寻优法、模拟退火法等[2][3][4])的间接比较标准。遗传算法在此体现出了不俗的表现[5]。
1.2 国内外发展现状
最早美国Ｍichigan(密执安大学) [6] [7]的Holland教授提出，起源于60年代对自