摘要:旅行商问题(Traveling Salesman Problem，TSP)是组合优化领域中研究最多的问题之一，是一个经典的NP-hard问题，目前常用TSP来验证启发式算法或人工智能算法的性能.

　　　本文在蚁群算法的基础上引入信息熵来求解TSP，主要利用信息熵的性质改变蚁群选择下一个城市的概率，使蚁群更容易探索到新的路径.本算法在一定程度上增加了寻找最短路径的随机性，能更好的克服搜索路径早熟收敛 ，具备有搜索更好解的能力.

　　　本文主要取31个城市的TSP实例将本算法与原蚁群算法进行对比验证，实验结果表明本算法的可行性及有效性更高.

关键词：旅行商问题；蚁群算法；信息熵；启发式算法

目录

摘要

ABSTRACT

第一章 前言-1

第二章 旅行商问题-2

2.1 问题描述-2

2.2 问题模型-2

第三章 蚁群算法-4

3.1 历史背景-4

3.2 蚁群算法-4

第四章 算法设计-8

4.1 信息熵简介-8

4.2 算法设计-9

第五章 实验结果分析-10

5.1 实验数据分析-10

5.2 运行图分析-12

第六章 结论-16

参考文献-17

附录A 本算法源代码-18

致 谢-23