学位论文 > 优秀研究生学位论文题录展示

基于Delaunay三角剖分的TSP问题求解研究

作　者: 任保营
导　师: 蒋波
学　校: 大连海事大学
专　业: 计算机科学与技术
关键词: TSP Voronoi图 Delaunay三角剖分蚁群算法最大最小蚁群算法
分类号: O224
类　型: 硕士论文
年　份: 2010年
下　载: 89次
引　用: 4次
阅　读: 论文下载

内容摘要

TSP问题是一个典型的组合优化问题,也是一个易于描述却难以处理的NP难题。针对TSP问题的研究,长期以来,人们一直在寻求一种高效、快速的近似算法,以便在合理的计算时间范围内准确地求解一个规模较大问题,已经设计出了许多高效、实用的算法,其中,蚁群算法就是性能较好且最具代表性的算法之一。本文主要针对基于Delaunay三角剖分的TSP问题求解算法进行研究,针对求解TSP问题的经典算法所存在的求解速度慢、最优解的精度不高等缺点,提出了利用Delaunay三角剖分的良好特性确定候选集策略,利用最大最小蚁群算法防止搜索陷入局部最优的求解TSP问题的改进算法,并通过利用二路选择法重构求解路径、改进信息素更新方法、优化参数设置等技术,进一步提高算法的性能。为了验证算法性能,本文利用TSPLIB提供的实验数据,对比分析了本文所提出的改进算法与基本蚁群算法、最大最小蚁群算法、动态自适应蚁群算法的运行结果。结果表明,本文所提出的改进算法的性能相对较优,针对某些具体的TSP问题,依据本算法能够求得一个最优解。并通过一个TSP问题实例,利用matlab进行仿真以验证改进算法的有效性。

基于Delaunay三角剖分的TSP问题求解研究

内容摘要

全文目录

相似论文