旅行商问题的并行蚂蚁算法研究

论文摘要

明是NP难题。其路径数目与城市规模呈指数级数增长，所以对于较大规模的实例，采用传统的精确算法求出其最优解不再适用。因此，一类智能启发式算法应运而生，其中蚂蚁算法是一种求解旅行商问题十分有效的仿生算法。蚂蚁算法自提出以来经过多次改进，但是还是存在收敛速度慢、容易陷入局部最优解的缺陷。本文首先在Max-MinAS的基础上，提出一种改进的蚂蚁算法——Max-Mean-MinAS。通过分析之前蚂蚁算法探索更优解和开发新解的特性，该算法提出五处改进：（1）设定信息素上、下限为固定值；（2）添加一个新的参数：信息素上、下限的几何平均值；（3）引入一种经验保留机制；（4）对三边交换法进行改进；（5）使用分化操作。改进后的蚂蚁算法对TSPLIB中43个不同规模、不同类型的实例进行了测试，同时跟Max-MinAS进行了比较，实验结果表明改进后的蚂蚁算法有更快的收敛速度和抗陷入局部最优解的能力。同时，为了进一步提高蚂蚁算法搜索性能，本文设计了在分布式环境下的并行蚂蚁算法。该并行模式在三种不同的通信拓扑模型下执行，并对易发生长停滞现象和搜索进程慢的两组实例进行测试。实验结果表明并行蚂蚁算法能在给定的时间里搜索到更优的解，和给定一定质量的解，能在更短的时间里搜索到。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.2 研究内容
• 第二章 NP 难题及智能算法
• 2.1 引言
• 2.2 计算复杂性及NP 难题
• 2.2.1 计算复杂性
• 2.2.2 N P 难题
• 2.3 智能优化算法
• 2.3.1 模拟退火法
• 2.3.2 遗传算法
• 2.3.3 禁忌搜索
• 2.3.4 人工神经网络
• 2.3.5 蚂蚁算法
• 2.3.6 粒子群优化
• 2.3.7 D NA 计算
• 2.3.8 量子计算
• 2.4 小结
• 第三章 旅行商问题及其蚂蚁算法
• 3.1 引言
• 3.2 传统算法求解旅行商问题
• 3.2.1 精确型算法
• 3.2.2 启发式算法
• 3.3 蚂蚁算法求解旅行商问题
• 3.3.1 蚂蚁算法思想来源
• 3.3.2 蚂蚁算法求解T SP 的基本设计
• 3.3.3 蚂蚁系统直接后续算法
• 3.4 小结
• 第四章 改进蚂蚁算法求解旅行商问题
• 4.1 引言
• 4.2 改进的蚂蚁算法
• 4.3 实例测试
• 4.4 小结
• 第五章 并行蚂蚁算法求解旅行商问题
• 5.1 引言
• 5.2 蚂蚁算法并行执行
• 5.2.1 并行算法基本概念
• 5.2.2 并行蚂蚁算法
• 5.3 分布式环境下并行蚂蚁算法
• 5.4 实例测试
• 5.5 小结
• 参考文献
• 附录
• 在读期间公开发表的论文和承担科研项目及取得成果
• 致谢