用遗传算法求解TSP问题

论文摘要

巡回旅行商问题(TSP)是一个组合优化方面的问题,已经成为并将继续成为测试组合优化新算法的标准问题。从理论上讲,使用穷举法不但可以求解TSP问题,而且还可以求出该问题的最优解。但是对现有的计算机来说,使用常规的穷举法在如此庞大的搜索空间中寻求最优解,几乎是不可能的。所以,各种求解TSP问题的优化算法应运而生了,本文所用到的遗传算法也在其中。遗传算法是一种高效智能搜索方法,并行遗传算法是遗传算法研究中的一个重要方向。并行遗传算法能够提供各种大型计算问题的解决方案。Java语言提供了对并发的语言级支持,这个特性是Java的伟大创新之一,同时为并行遗传算法的设计提供了最佳的技术支持。在收集国内外相关资料,阅读了相关文献的基础上,本文系统地阐述了遗传算法的构成原理。介绍了作者借助Java语言实现的一种应用“轮盘赌”选择操作,顺序交叉操作以及启发式变异操作求解TSP问题的遗传算法。在了解和掌握并行遗传算法的基本概念和工作原理后,针对TSP问题,提出了两种基于并行遗传算法的求解方法。第一章介绍了课题的研究背景、研究的可行性和意义,并行遗传算法的基本理论以及所面对的问题。此外还介绍了TSP问题的研究现状,并对论文内容进行了概括性综述。第二章介绍了遗传算法及并行遗传算法模型第三章介绍了遗传算法求解TSP问题的基本理论,提出了一种求解TSP问题的串行遗传算法模型,结合实例分析了该算法的创新之处。第四章介绍了两种求解TSP问题的并行遗传算法模型,详细地论述了采用这两种并行模型求解TSP问题的过程。分别分析了这两种遗传算法的创新之处,并通过实例对它们之间的性能进行了比较。第五章总结了整个研究工作,并对研究的方向进行了展望。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 背景与意义
• 1.2 并行遗传算法
• 1.2.1 并行
• 1.2.2 并行遗传算法
• 1.3 TSP的研究现状
• 1.4 研究内容与创新
• 1.5 本文的结构
• 第二章 遗传算法与并行遗传算法
• 2.1 GA遗传算法
• 2.1.1 编码
• 2.1.2 群体设定
• 2.1.3 适应度函数
• 2.1.4 遗传操作
• 2.2 PGA并行遗传算法
• 2.2.1 全局型——主从式模型（master-slave model）
• 2.2.2 独立型——粗粒度模型（coarse-grained model）
• 2.2.3 分散型——细粒度模型（fine-grained model）
• 第三章 遗传算法求解TSP问题的实现
• 3.1 遗传算法与组合优化
• 3.1.1 基于遗传算法的组合优化方法
• 3.1.2 TSP巡回旅行商问题
• 3.2 遗传算法求解TSP问题的核心代码
• 3.2.1 编码与适应度函数
• 3.2.2 遗传操作设计
• 3.2.3 创新点与实验结果分析
• 第四章 并行遗传算法求解TSP问题的实现
• 4.1 并行遗传算法求解TSP问题模型
• 4.2 并行遗传算法一
• 4.2.1 核心代码
• 4.2.2 创新点与实验结果分析
• 4.3 并行遗传算法二
• 4.3.1 核心代码
• 4.3.2 创新点与实验结果分析
• 4.4 与其它并行遗传算法比较
• 第五章 结束语
• 5.1 研究总结
• 5.2 研究展望
• 附录
• 参考文献
• 致谢
• 学位论文评阅及答辩情况表