一种基于MapReduce模型的并行化TSP算法研究

发布时间：2017-08-13 06:15

  本文关键词：一种基于MapReduce模型的并行化TSP算法研究

  更多相关文章： TSP MapReduce模型 并行化 广义Beta分布

【摘要】：TSP问题(Traveling Salesman Problem),即旅行商问题,是数学领域里面组合优化问题中被广泛研究的著名问题之一。TSP问题在学术研究和实际生产需求中十分重要,同时在物理学、生物学和计算机科学等领域有着广泛的应用。TSP问题是NP-完全问题中很有挑战性的一个问题。目前对于TSP问题的研究多是在单一物理机上使用顺序执行的启发式算法求得近似解,也有少量研究初步在Hadoop平台上基于MapReduce模型实现了一些诸如遗传算法和蚁群算法等新型启发式算法,但都仍然存在不能保证算法的质量、运行不稳定等问题。本论文探索通过并行MapReduce模型高效解决TSP问题。根据以上存在的问题,本文提出基于MapReduce模型的并行化迭代K-OPT算法:首先,本文提出一种基于MapReduce模型并行化求解最小生成树算法,并用于构造TSP初始化路径;该算法充分应用MapReduce模型中可以很容易对数据进行排序的特点对图中的所有边的权重进行排序,结合并行化的克鲁斯卡尔算法求得最小生成树;再将其作为Christofides算法输入求得一条可以用于迭代求解TSP问题算法的初始化路径,其中Christofides算法是目前TSP问题中最好的近似算法之一,其近似比为1.5-opt。其次,以初始路径为基础,提出一种基于MapReduce模型并行化的KOPT算法,算法利用MapReduce模型可以充分并行化运算的特点,将map函数用于路径的分发和图的读取,reduce函数用于问题的求解,从集群中多节点求得的不同迭代解中筛选出最优解,将其作为下一次迭代的输入。然后,通过对节点数规模较小的完全图进行基于MapReduce模型所有路径的穷举和对一些TSPLIB中的实例进行基于MapReduce模型的大规模随机路径生成以及并行化去冗余操作,然后进行一定的统计和特征分析,本文首次提出了截断广义Beta分布Truncated Generalized Beta distribution(TGB)作为TSP问题中最优路径的概率密度函数,并以此证明了迭代KOPT算法的近似比,在不断增加迭代次数的情况下,可获得接近优化的结果。最后,通过大量实例测试验证了本文所提算法的性能。
【关键词】：TSP MapReduce模型 并行化 广义Beta分布
【学位授予单位】：电子科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP338.6
【目录】：

• 摘要5-6
• ABSTRACT6-10
• 第一章 绪论10-15
• 1.1 背景及意义10-11
• 1.1.1 TSP问题背景10
• 1.1.2 研究TSP问题的意义10-11
• 1.2 研究现状11-12
• 1.2.1 TSP问题的发展阶段11-12
• 1.2.2 TSP问题的已有的研究成果12
• 1.3 研究内容12-13
• 1.4 组织结构13-14
• 1.5 本章小结14-15
• 第二章 TSP问题及MapReduce模型介绍15-24
• 2.1 TSP问题定义15-16
• 2.1.1 TSP问题的描述15
• 2.1.2 TSP问题的数学模型15-16
• 2.2 TSP问题已有解决方法概述16-21
• 2.2.1 TSP问题精确解决算法16-17
• 2.2.2 TSP问题近似算法17-21
• 2.3 Hadoop平台及MapReduce模型简介21-23
• 2.3.1 Hadoop平台介绍21-22
• 2.3.2 MapReduce模型简介22-23
• 2.4 本章小节23-24
• 第三章 基于MapReduce模型求解MST算法24-32
• 3.1 最小生成树MST定义及基本算法24-26
• 3.1.1 最小生成树MST定义24
• 3.1.2 求解MST基本算法24-26
• 3.2 基于MapReduce模型的MST算法26-31
• 3.2.1 算法概述26
• 3.2.2 算法设计及流程图26-27
• 3.2.3 算法核心代码及时间复杂度分析27-31
• 3.3 初始环路生成31
• 3.3.1 Christofides算法概述及初始环路的生成31
• 3.4 本章小结31-32
• 第四章 基于MapReduce模型实现K-OPT算法32-38
• 4.1 K-OPT算法及基本应用32-33
• 4.1.1 K-OPT算法概述32
• 4.1.2 K-OPT算法在LKH算法中的应用32-33
• 4.2 基于MapReduce模型实现K-OPT算法33-37
• 4.2.1 算法概述33
• 4.2.2 算法设计及流程图33-35
• 4.2.3 算法核心代码及时间复杂度分析35-37
• 4.3 本章小结37-38
• 第五章 TSP优化路径和模型统计分析38-59
• 5.1 完全图的TSP随机路径38-42
• 5.1.1 完全图的TSP随机路径算法概述38-41
• 5.1.2 基于MapReduce模型生成完全图的TSP随机路径41-42
• 5.2 穷举完全图的所有TSP路径42-46
• 5.3 TSP路径模型的统计分析46-58
• 5.3.1 广义Beta分布作为随机TSP问题的概率密度函数48-49
• 5.3.2 TSPLIB实例服从广义Beta分布的概率密度函数49-50
• 5.3.3 基于Christofides算法的截取广义Beta概率分布（Truncated GeneralizedBeta Distribution）50-58
• 5.4 本章小结58-59
• 第六章 算法性能评估与测试59-73
• 6.1 实验环境及配置59
• 6.1.1 实验硬件环境59
• 6.1.2 实验软件环境59
• 6.2 实验结果展示及分析59-72
• 6.2.1 基于MapReduce模型生成最小生成树算法测试及分析60-64
• 6.2.2 基于MapReduce模型K-OPT算法测试及分析64-67
• 6.2.3 TSP优化路径特征的统计分析测试及分析67-72
• 6.3 本章小结72-73
• 第七章 总结与展望73-75
• 7.1 本文总结73-74
• 7.2 存在的问题与不足74
• 7.3 未来工作展望74-75
• 致谢75-76
• 参考文献76-78
• 攻读硕士期间取得的研究成果78-79

【参考文献】

中国期刊全文数据库 前2条

1 夏卫雷;王立松;;基于MapReduce的并行蚁群算法研究与实现[J];电子科技;2013年02期

2 张煜东;吴乐南;韦耿;;智能算法求解TSP问题的比较[J];计算机工程与应用;2009年11期

，

本文编号：665797