基于并行环境求解TSP问题

论文摘要

TSP问题,即旅行商问题,该问题是组合优化中的一个经典问题。它有着广泛的应用背景,如：运输调度、旅游路线设计等,许多实际生活中的问题都与TSP问题的数学模型有着紧密的联系。本文采用模拟退火算法求解TSP问题,模拟退火算法的典型应用就是研究组合优化问题,它是实现全局优化的一种基本途径。由于物理中固体物质的退火过程与一般组合优化问题之间具有相似性,所以人们提出采用模拟退火算法解决组合优化问题。模拟退火算法在求解组合优化问题时取得了很好的效果,能够解决使用传统的优化方法难于解决的一些问题。与传统的模拟退火法求解TSP问题不同,本文是在并行计算的环境下使用并行模拟退火算法对TSP问题进行求解。并行计算就是指在并行机上,将一个任务分成多个子任务,并把这些任务分配给不同的处理器,各个处理器之间相互协同,并行的共同执行分配的子任务,正是由于有许多处理器共同来完成同一个任务,所以就可以加快问题的求解速度,或者能够提高求解大型问题规模的目的。目前并行计算的研究也已经成为现代计算科学研究的主要方向之一。它适用于人们日常生活中的各个领域,比如工程计算,数值计算等等,研究并行计算可以帮助人们充分的利用计算机资源处理大规模较为复杂的科学计算。本文选用目前较为重要的并行编程工具MPI,同时它也是目前国际上最为流行的并行编程环境之一。它实际上是一个消息传递函数库的标准,主要用于开发基于消息传递的并行程序,具有可移植消息传递平台,具备许多消息传递系统的优点。综上,本论文是基于并行计算的MPI标准,将模拟退火算法按照并行策略将其并行化,并根据其思想编程,实现求解TSP实例的问题。该问题的实现,不仅为TSP问题的研究提供了更为优化的研究方法,而且有助于人们今后利用并行计算的环境求解其它大规模的数学问题以及其它工程问题。

论文目录

• 摘要
• Abstract
• 目录
• 第一章 绪论
• 1.1 TSP问题的研究背景
• 1.2 问题的提出以及研究意义
• 1.3 并行计算的研究背景
• 1.4 本论文章节安排
• 第二章 并行计算
• 2.1 并行计算简介
• 2.2 并行算法的定义、分类及特点
• 2.2.1 并行算法的定义
• 2.2.2 并行算法的分类
• 2.2.3 并行算法的特点
• 2.3 并行算法的设计
• 2.3.1 并行算法设计方法
• 2.3.2 分布存储系统的并行编程
• 2.3.3 并行算法设计时应注意问题
• 2.4 并行程序设计的评价标准
• 2.5 并行算法的评价及复杂性分析
• 2.6 本章小结
• 第三章 可移植消息传递界面标准MPI
• 3.1 可移植消息传递标准MPI的定义及特点
• 3.1.1 MPI的定义
• 3.1.2 MPI的特点及主要目的
• 3.2 MPI的实现版本
• 3.3 MPI并行程序设计
• 3.3.1 MPI消息传递过程
• 3.3.2 MPI并行程序设计模式
• 3.3.3 MPI编程
• 3.4 MPI程序
• 3.4.1 MPI基本函数
• 3.4.2 MPI程序的基本结构
• 3.4.3 MPI程序的执行过程
• 3.5 本章小结
• 第四章 并行模拟退火算法
• 4.1 模拟退火法概述
• 4.2 模拟退火算法的并行策略
• 4.3 并行策略的比较
• 4.4 基于MPI的并行模拟退火算法
• 4.5 退火过程实现算法
• 4.6 本章小结
• 第五章 并行环境下模拟退火算法求解TSP问题
• 5.1 实验平台的构建及测试
• 5.1.1 实验平台
• 5.1.2 软件的安装与配置
• 5.2 TSP问题实例描述
• 5.3 模拟退火算法求解TSP问题的主要步骤
• 5.4 串行模拟退火算法求解TSP问题过程
• 5.5 将算法进行并行程序的编程并分析
• 5.6 结果分析
• 5.7 本章小结
• 第六章 总结与展望
• 致谢
• 参考文献
• 附录A 硕士期间发表的论文