本站原创
摘要：明是NP难题。其路径数目与城市规模呈指数级数增长，所以对于规模的实例，传统的精确算法求出其最优解不再适用。因此，一类智能启发式算法应运而生，其中蚂蚁算法是一种求解旅行商问题十分的仿生算法。蚂蚁算法自以来经过多次改进，但是还是存在收敛速度慢、容易陷入局部最优解的缺陷。在Max-MinAS的基础上，一种改进的蚂蚁算法——Max-Mean-MinAS。分析之前蚂蚁算法探索更优解和开发新解的特性，该算法五处改进：(1)设定信息素上、下限为固定值；(2)添加一个新的参数：信息素上、下限的几何平均值；(3)引入一种经验保留机制；(4)对三边交换法改进；(5)使用分化操作。改进后的蚂蚁算法对TSPLIB中43个不同规模、不同类型的实例了测试，同时跟Max-MinAS了比较，实验结果改进后的蚂蚁算法有更快的收敛速度和抗陷入局部最优解的能力。同时，为了提高蚂蚁算法搜索性能，设计了在分布式环境下的并行蚂蚁算法。该并行模式在三种不同的通信拓扑模型下执行，并对易发生长停滞现象和搜索进程慢的两组实例测试。实验结果并行蚂蚁算法能在给定的时间里搜索到更优的解，和给定一定质量的解，能在更短的时间里搜索到。关键词：旅行商问题论文组合优化论文NP-难题论文蚂蚁算法论文并行算法论文
摘要4-5
ABSTRACT5-8
章 绪论8-12
1.1 研究背景8-10
1.2 研究内容10-12
章 NP 难题及智能算法12-24
2.1 引言12
2.2 计算复杂性及NP 难题12-15
2.2.1 计算复杂性12-14
2.2.2 N P 难题14-15
2.3 智能优化算法15-23
2.3.1 模拟退火法16
2.3.2 遗传算法16-17
2.3.3 禁忌搜索17-19
2.3.4 人工神经网络19-20
2.3.5 蚂蚁算法20
2.3.6 粒子群优化20-21
2.3.7 D NA 计算21-22
2.3.8 量子计算22-23
2.4 小结23-24
章 旅行商问题及其蚂蚁算法24-34
3.1 引言24-25
3.2 传统算法求解旅行商问题25-27
3.2.1 精确型算法25-26
3.2.2 启发式算法26-27
3.3 蚂蚁算法求解旅行商问题27-33
3.3.1 蚂蚁算法思想来源27-29
3.3.2 蚂蚁算法求解T SP 的基本设计29-32
3.3.3 蚂蚁系统后续算法32-33
3.4 小结33-34
章 改进蚂蚁算法求解旅行商问题34-46
4.1 引言34-35
4.2 改进的蚂蚁算法35-41
4.3 实例测试41-45
4.4 小结45-46
第五章 并行蚂蚁算法求解旅行商问题46-56
5.1 引言46
5.2 蚂蚁算法并行执行46-49
5.2.1 并行算法基本46-47
5.2.2 并行蚂蚁算法47-49
5.3 分布式环境下并行蚂蚁算法49-51
5.4 实例测试51-55
5.5 小结55-56