一种基于动态局部搜索的蚁群算法及其对TSP问题的求解

摘要

蚁群算法在求解TSP问题时，有陷入局部最优解、收敛速度太慢和求解质量不高以及稳定性不足等三个缺点。文章针对这三个缺点，提出了一种以基于斥候蚁实现的动态局部搜索为核心策略，城市分类、加大信息素浓度差和继承式的信息素清零策略等3种策略进行辅助改进的蚁群算法。
　　城市分类即在蚂蚁开始搜索时对城市进行分类，不同类别的城市代表不同的等级，会向等级高的城市更多的蚂蚁，而对于等级低的城市则相反;而通过仿生学引入的斥候蚁，是在蚂蚁的寻路过程中，若发生选择困难，蚂蚁很难选择出该走那一条路的时候，则酌情派出斥候蚁帮助进行探索，之后通过对比斥候蚁和蚂蚁的路径长短来决定哪一条路径更优;在每次寻路完毕后，采用新的更新信息素的策略，即获得当次迭代的最短路径，与当次迭代前所得到的最短路径进行求比，若比值越大，信息素更新幅度也就越大;当算法陷入局部最优时，为了不让信息素完全被清除，采用有补偿的信息素清零策略，这样不仅能跳出局部最优，还能提高算法的效率。
　　文章对传统的蚁群算法对TSP求解的原理进行详细的阐述，分析了蚁群算法在求解TSP问题时产生三大缺陷的根本原因，从根本原因入手，设计出改进蚁群算法，并通过Matlab和TSPLIB对两种算法进行了仿真实验。对比仿真结果表明，改进的算法在求解TSP问题时，能够极大的优化求解质量，让求解结果也变得稳定，同时可以有效地跳出局部最优解，并能大幅度加快收敛速度。各方面都显示，它的性能要优于传统蚁群算法。

目录

声明

摘要

第一章 绪论

1．1 前言

1．2 国内外发展现状

1．3 研究意义与目的

1．4 本文研究内容和论文结构

第二章 蚁群算法和TSP问题

2．1 启发式搜索

2．2 蚁群算法

2．2．1 蚁群算法的双要素

2．2．2 蚁群算法的初始化

2．2．3 蚁群算法的执行步骤

2．3 TSP问题

2．4 蚁群算法求解TSP问题

2．4．1 收敛速度慢

2．4．2 局部最优

2．4．3 求解质量不高和稳定性不足

2．5 本章小结

第三章 基于动态局部搜索和城市分类对蚁群算法的改进

3．1 基于动态局部搜索对蚁群算法的改进

3．2 2-Opt算法的详细介绍

3．2．1 2-Opt求解TSP问题的工作原理

3．2．2 2-Opt的缺点

3．3 动态局部搜索策略

3．3．1 斥候蚁

3．3．2 基于动态局部搜索的蚁群算法的实现步骤

3．4 基于斥候蚁矩阵的节点分类对蚁群算法的改进

3．5 基于斥候蚁矩阵的节点分类策略

3．5．1 参数的设定

3．5．2 基于斥候蚁矩阵的节点分类的详细介绍

3．5．3 基于斥候蚁矩阵的节点分类的实现步骤

3．6 本章小结

第四章 基于斥候蚁矩阵的信息素修正对蚁群算法的改进

4．1 基于最优解“优质”程度的动态的信息素更新策略

4．1．1 动态的信息素更新策略的参数设置

4．1．2 动态的信息素更新策略的详细介绍

4．1．3 动态的信息素更新策略的流程图

4．1．4 本策略拟达到的目的

4．2 基于继承式的信息素清零策略

4．2．1 信息素清零策略的参数设置

4．2．2 信息素清零策略的详细介绍

4．2．3 信息素清零策略的实现流程

4．2．4 本策略拟达到的目的

4．3 改进算法的描述

4．4 改进算法的时间与空间复杂度分析

4．4．1 时间复杂度

4．4．2 空间复杂度

4．5 本章小结

第五章 仿真实验

5．1 工作环境

5．2 参数设置

5．3 实验结果对比

5．3．1 小规模TSP问题的实验结果对比

5．3．2 中规模TSP问题的实验结果对比

5．3．3 大规模TSP问题的实验结果对比

5．4 总体实验数据分析

5．5 本章小节

第六章 总结与展望

6．1 主要工作总结

6．2 未来研究工作

参考文献

致谢

攻读硕士学位期间发表的学术论文目录