摘要：旅行商问题，简称TSP(Traveling Salesman Problem)，是一个测试算法优劣性的标准问题，在现实中有很多实际问题都可归结或转化为TSP问题。近年来，研究者们陆续采用了一些新的算法来解决旅行商问题，更是在利用启发式搜索算法解决旅行商问题方面取得了不错的成果。旅行商问题的目标是在一个加权完全无向图中找到一条总距离最短的汉密尔通路，而启发式搜索算法近年来是计算机科学领域中的一个研究热点。故对启发式搜索算法应用在旅行商问题之中的方法和策略进行了研究，特别是对启发式搜索中的遗传算法和蚁群算法做了详细介绍，并对这两种算法在旅行商问题中的运行效果做了分析和评价。实验结果验证了启发式搜索算法在解决旅行商问题上的有效性。

关键词：启发式搜索算法；旅行商问题；遗传算法；蚁群算法 

目录

摘要

Abstract

1 绪论-1

1.1 课题研究的目的与意义-1

1.2 研究现状及存在的问题-1

1.3本文的主要内容-1

2 启发式搜索算法及旅行商问题概述-3

2.1启发式搜索算法-3

2.1.1 背景-3

2.1.2 定义-3

2.1.3 举例-3

2.2旅行商问题-4

2.2.1旅行商问题的定义-4

2.2.2旅行商问题与组合优化问题-4

2.2.3旅行商问题求解算法评价标准-4

2.2.4目前旅行商问题的解法-5

3 遗传算法在旅行商问题中的应用-8

3.1 遗传算法起源和发展-8

3.2 遗传算法特点-9

3.3 遗传算法基本流程及要素-9

3.3.1 遗传算法基本流程-9

3.3.2 遗传算法的具体步骤：-10

3.3.3 遗传算法涉及的五个主要因素-10

3.4 遗传算法解决旅行商问题的算法实现-13

4 蚁群算法在旅行商问题中的应用-15

4.1 蚁群算法思想来源及研究进展-15

4.2 蚁群算法特点-16

4.3 蚁群算法基本原理-16

4.4 基本蚁群算法及流程-17

4.5 基本蚁群算法解决旅行商问题的算法实现-19

5 遗传算法与蚁群算法的对比分析-22

5.1 遗传算法解决TSP问题的结果分析-22

5.2 蚁群算法解决TSP问题的结果分析-24

5.3分析评价两种算法的执行效果-26

总结与展望-28

参 考 文 献-29

致 谢-30