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

求解TSP算法的研究与改进

作　者: 胡银厚
导　师: 王世卿
学　校: 郑州大学
专　业: 计算机软件与理论
关键词: 蚁群优化旅行商问题优质边智能计算最大-最小蚁群算法
分类号: TP301.6
类　型: 硕士论文
年　份: 2012年
下　载: 94次
引　用: 4次
阅　读: 论文下载

内容摘要

旅行商问题(Traveling Salesman Problem,简称TSP)是组合优化问题中的经典问题,也是一个NP完全问题。同时,它也是众多优化问题的简化形式,如基因组制图、行星探索、电路板钻孔、电路板焊接、交通调度、作业调度等。由于TSP问题是一个NP完全问题,求解难度大,它也被用作处理器测试和算法比较的标准。因此,对TSP的研究具有重要的理论和应用价值。蚁群算法是求解TSP的有效方法之一。它是由意大利学者Dorigo M等人提出,是一种基于种群的启发式进化算法,具有较强的鲁棒性、并行性、很好的可扩充性,且易于和其他的方法融合的优点。同时,它是一种结合了分布式计算、正反馈机制和遵循贪心原则的搜索算法。蚁群算法自提出之后,引起了许多学者的关注,并将其应用到各个领域的优化问题中。蚁群算法有多种变种,其中最大—最小蚁群算法求解TSP效果最好。本文深入分析了最大—最小蚁群算法运行过程中的算法数据,发现当算法陷入收敛之后,大部分蚂蚁开始构造相同的路径,这在很大程度上浪费了蚂蚁的探索能力。本文中通过让蚂蚁选择第一条边时不使用信息素,很好改善了这一现象。同时,对比研究TSP的真实最优环路与算法构造环路发现,包含真实最优边的环路一般都较短。环路长度和其包含的真实最优边数成反比,环路包含的真实最优边数越多,环路长度越短。据此,反过来可以认为较短环路中所包含的边为真实最优边的概率也大。受此启发,本文提出了一种基于优质边的求解策略。利用算法运行的历史信息选择优质边,也即为真实最优边可能性大的边。使用修改的选路规则,将蚂蚁的路径尽可能限制在优质边中,以试图降低算法的解空间。本文还通过设置不同算法参数的对比实验,确定了改进算法的最合适参数。通过对改进算法的实验仿真,发现改进的算法加快了蚂蚁构造优质解的过程,同时也使得算法在很大概率上能找到真实最优解,提高了算法的求解性能,证明了算法改进的有效性。

全文目录

摘要  4-5
Abstract  5-10
1 绪论  10-13
  1.1 研究背景与意义  10-11
    1.1.1 本文的主要工作  11
  1.2 本文组织结构  11-12
  1.3 本章小结  12-13
2 旅行商问题  13-29
  2.1 问题定义  13
  2.2 实验数据  13-15
  2.3 求解方法  15-27
    2.3.1 精确算法  15-17
    2.3.2 近似算法  17-25
    2.3.3 智能优化算法  25-27
  2.4 本章小结  27-29
3 蚁群算法  29-44
  3.1 蚁群算法原理  29-31
  3.2 蚁群算法研究现状  31-33
  3.3 蚁群算法求解TSP  33-34
  3.4 几种典型的蚁群算法  34-42
    3.4.1 蚂蚁系统  34-36
    3.4.2 优秀蚂蚁系统  36-37
    3.4.3 等级蚂蚁系统  37
    3.4.4 最大最小蚂蚁系统  37-40
    3.4.5 蚁群系统  40-41
    3.4.6 蚂蚁-Q  41-42
  3.5 实验对比  42
  3.6 本章小结  42-44
4 基于优质边的蚁群算法  44-51
  4.1 MMAS求解TSP  44-46
    4.1.1 解的误差  44-45
    4.1.2 同解构造率  45
    4.1.3 最优边命中率  45-46
  4.2 算法改进思想  46-47
  4.3 优质边和优质边系数  47-48
  4.4 路径选择  48-49
  4.5 信息素平滑机制  49
  4.6 本章小结  49-51
5 实验仿真  51-63
  5.1 期望启发因子的选择  51-53
  5.2 信息素挥发系数的选择  53-54
  5.3 蚂蚁数量的选择  54-56
  5.4 合适的优质边系数  56-57
  5.5 仿真结果  57-60
  5.6 与MMAS的对比  60-61
  5.7 求解大规模数据集  61-62
  5.8 本章小结  62-63
6 结束语  63-64
参考文献  64-67
在学期间发表的学术论文与研究成果  67-68
致谢  68

求解TSP算法的研究与改进

内容摘要

全文目录

相似论文