本 科 毕 业 设 计
毕业设计题目：遗传算法及其在TSP问题的应用 学生姓名： 学 号： 系 别： 专业班级：
指导教师姓名及职称： 起止时间：
I
摘要
遗传算法(Genetic Algorithm, GA)是近年来迅速发展起来的一种全新的随机搜索与优化算法,旅行商问题是一个典型的NP完全问题，而遗传算法是解决这类问题的一个比较理想的算法,它的基本思想来源于Darwin的进化论和Mendel的遗传学。 本文首先对遗传算法和旅行商问题进行了简单的介绍，并用数学的方式描述了TSP问题。然后详细地阐述了遗传算法在编码表示和遗传算子（包括选择算子、交叉算子、变异算子）等其他方面的应用情况，最后通过对初始种群、遗传代数、交叉率、变异率等参数进行修改、测试、对比，来验证这些参数对算法的求解结果和求解效率的影响。 关键词 遗传算法 旅行商问题 编码 轮盘赌算法 最优保存策略 顺序交叉 II
Abstract
Genetic Algorithm (Genetic Algorithm, GA) is a new random search and optimization algorithm，develops rapidly in recent years, TSP (Traveling Salesman Problem) is a typical NP - complete problem and genetic algorithm (GA) is one of the best methods for solving NP - complete problem, the basic idea of the theory is Darwin and Mendel's genetics. Firstly，the article introduces the Genetic Algorithm and Traveling Salesman Problem briefly and mathematically. Then describes the detail of the genetic algorithm，such as coded representation，genetic operators (including selection operator, crossover operator, mutation operator) and the other applications. Finally，we modify the parameters of the initial population，genetic algebra，crossover rate，mutation rate to verify the influence on the result and solving efficiency of the algorithm. Key words genetic algorithm TSP coding Roulette algorithm Elitist strategy Order crossover III
目 录
第一章 引言 .................................................................................................................... 2
1.1 研究背景 .............................................................................................................. 3 1.2 国内外发展现况 .................................................................................................. 3 1.3 主要研究内容 ...................................................................................................... 5 1.4 本文结构 .............................................................................................................. 5
第二章 遗传算法与TSP问题介绍 .......................................................................... 6
2.1 遗传算法介绍 ...................................................................................................... 6
2.1.1 遗传算法的特点 ......................................................................................................... 7 2.1.2 基本遗传算法的应用步骤 ......................................................................................... 7 2.1.3 基本遗传算法的流程图 ............................................................................................. 8 2.1.4 遗传算法应用中的关键问题 ..................................................................................... 9
2.2 TSP问题介绍 ..................................................................................................... 12
第三章 遗传算法在TSP上的应用与实现 .......................................................... 13
3.1 遗传算法解决TSP问题的具体实现 ................................................................ 13
3.1.1 本文用遗传算法解决TSP问题的流程图 ............................................................... 13 3.1.2 编码 ........................................................................................................................... 14 3.1.3 适应度函数 ............................................................................................................... 14 3.1.4 初始化种群 ............................................................................................................... 14 3.1.5 选择操作 ................................................................................................................... 15 3.1.6 交叉操作 ................................................................................................................... 16 3.1.7 变异操作 ................................................................................................................... 16
3.2 不同参数下的计算结果对比 ............................................................................ 17
3.2.1 初始种群10和100的对比 ..................................................................................... 18 3.2.2 不同交叉率和变异率的对比 ................................................................................... 19 3.2.3 不同参数下结果对比结论 ....................................................................................... 21 3.2.4 程序运算过程截图 ................................................................................................... 21
3.3 东莞10个景点坐标和运行结果 ...................................................................... 24
第四章 结 论 .............................................................................................................. 26 参 考 文 献 ..................................................................................................................... 27 附录 相关源代码 ......................................................................................................... 28 致 谢 ................................................................................................................................ 28
1
第一章 引言
在过去,人们往往只能处理一些简单的问题，对于大型复杂系统的优化和自适应问题，仍然无能为力。但是在这方面，自然界中的生物表现出了其优异的能力，它们能够通过优胜劣汰、适者生存的自然进化法则进行生存和繁衍，并能渐渐地进化出对其生存环境适应性越来越高的优良物种。遗传算法就是模拟自然界中生物进化的一种高效的算法，其基本思想就是模拟自然界进化机制和生物进化论而形成的一种机制求解最优值问题的自组织、自适应的智能算法。
遗传算法[1] (Genetic Algorithm, GA)是近年来迅速发展起来的一种全新的随机搜索与优化算法，尽管各种理论、方法都尚未成熟，有待于进一步地完善和发展，但我们从它的身上看到了解决多种复杂问题的希望。虽然在遗传算法的研究和应用过程中出现过各种不同的算法设计，同时也会遇到过许多不同的难题，但是就目前而言，遗传算法的应用过程已经展现出了其突出的性能和巨大的发展前景。近年来，遗传程序设计运用遗传算法的思想自动生成计算机程序解决了许多问题，如预测、分类、符号回归和图像处理等，作为一种新技术，它已经与遗传算法并驾齐驱。我相信，随着研究工作进一步深入地发展，遗传算法将会在智能计算领域中起到非常重要的作用。
旅行商问题(Traveling Salesman Problem, TSP),是一个著名的组合优化问题[2],该类问题具有非常广泛的运用背景。如物流的调度问题、数控机床上的最优钻孔路线的选取、电路板的焊接都属于旅行商问题。因此旅行商问题受到了各方面的关注，有效解决TSP问题在计算理论和实际应用上都有很高的价值。目前解决TSP的主要方法有遗传算法、模拟退火算法、启发式搜索法、Hopfield神经网络算[3] 、二叉树描述算法。本文主要介绍了应用遗传算法来解决TSP问题。
2