基于分布均匀度的改进蚁群算法

摘要

作为一种新型的群集智能算法，蚁群算法从20世纪90年代提出至今，被广泛应用于求解复杂的组合优化问题，如调度问题、TSP问题等，取得了比较好的效果。然而蚁群算法自身也存在着不足之处：蚁群搜索的随机性容易导致全局搜索效率低、收敛速度慢；信息素的正反馈性容易导致在搜索后期，所有个体寻找到的解完全一致，算法不能对解空间进一步地搜索，不利于发现全局最优解甚至更好解等等。
　　 针对以上这些缺陷，为了解决蚁群算法加速收敛和早熟停滞现象这对矛盾，本文在基于分布均匀度的蚁群算法[1]提出的“聚度”思想的基础上进行了改进，提出了基于分布均匀度的改进蚁群算法，主要进行了两方面的改进：
　　 (1)、自适应选择策略。在选择策略中，在基于分布均匀度的蚁群算法[1]的基础上重新定义了“城市聚度”、“选择窗口”等概念，构造了一种具有自适应功能的状态转移策略。
　　 (2)、自适应信息素更新策略。在信息素更新策略中，采用全局更新(基于蚁周模型)和局部更新(基于蚁密模型)相结合的方式，并在局部更新时提出信息素影响因子递减的思想，既结合了TSP问题自身的特点，又能够根据解的分布均匀程度自适应地调整信息素更新策略，保证了算法在搜索后期的高质量。首先，将“城市聚度”引入信息素影响因子的计算中，使得算法能够根据解的实际分布状况动态地调整信息素更新策略；其次，通过控制信息素影响因子，相对地减少后程搜索的信息素增加量，从而减少非优路径对后继搜索的影响，使得算法在搜索后期能有更大的可能跳出局部最优，达到提高算法整体的搜索性能的目的。
　　 论文的实验部分利用多种不同规模的对称TSP问题(Traveling SalesmanProblem)进行验证。实验结果表明，改进后的蚁群算法在整个算法运行期间能够在有效提高搜索效率，加快收敛速度的同时较好地防止早熟、停滞现象，使算法不易陷入局部最优解，且算法所求解具有较好的稳定性，能够固定在一个较小的好的区间内，保证了所求解的质量。

目录

文摘

英文文摘

声明

第一章 引言

1.1研究背景

1.2研究现状分析

1.3研究的目标与意义

1.4本文章节安排

第二章 相关理论技术

2.1蚁群算法的生物学基础与机制原理

2.2经典蚁群算法的基本思想

第三章 基于分布均匀度的改进蚁群算法

3.1 TSP问题

3.2基于TSP问题的蚁群算法数学模型

3.3算法的改进策略

3.4改进的蚁群算法系统分析

第四章 算法的实验验证

4.1实验目的

4.2实验运行环境

4.3实验流程

4.4实验数据分析

4.5实验结论

第五章 总结与展望

5.1本文的研究与贡献

5.2进一步的研究工作

参考文献

致谢