最短路问题的一个改进蚁群算法

论文摘要

最短路问题在近半个世纪以来一直是人们所关注的一个优化问题。最短路问题（SP）是指在一个赋权图的两个节点之间找出一条具有最小权的路径。目前求解SP问题的精确算法已较为成熟,随着信息技术和人工智能的发展,相关的研究已不再局限于求该问题的精确解,而更多的关注于用启发式算法求问题的近似解和满意解。文章综述了求解SP问题的各种精确算法和启发式算法,阐述了蚁群算法的基本原理,求解步骤和时间复杂性。根据基本蚁群算法缺乏初期信息素、容易陷入局部最优解等缺点,本文提出了一个改进蚁群算法,主要是对基本蚁群算法作了以下几点改进:动态调整参数q0的值、对信息素τij的值标准化、修改信息素的全局更新规则。对改进算法的时间复杂性和收敛性进行了分析,最后讨论了其参数设置对算法的影响。

论文目录

• 摘要
• Abstract
• 目录
• 第一章 绪论
• 1.1 本文研究的背景和意义
• 1.2 相关文献综述
• 1.2.1 精确算法
• 1.2.2 启发式算法
• 1.3 论文所做工作
• 第二章 蚁群算法
• 2.1 蚁群算法的基本原理
• 2.2 基本假设与符号说明
• 2.2.1 符号说明
• 2.2.2 模型假设
• 2.3 基本蚁群算法
• 2.4 蚁群算法的复杂性分析
• 2.5 蚁群算法的优缺点
• 2.5.1 优点
• 2.5.2 缺点
• 第三章 改进蚁群算法
• 3.1 算法的改进
• 3.2 改进蚁群算法的求解步骤
• 3.3 改进蚁群算法的复杂性分析
• 3.4 改进蚁群算法的收敛性分析
• 3.5 算法的参数设置研究
• 第四章 结束语
• 4.1 工作总结
• 4.2 下一步的工作
• 参考文献
• 致谢