基于信息熵的加权蚁群算法的研究与应用

论文摘要

蚁群算法是由意大利学者M.Dorigo,V.Maniezzo等人从生物进化的机制中受到启发,通过模拟大自然中的蚁群觅食行为提出的一种新型的进化优化算法。该算法在解决诸如TSP问题、分配问题、网络路由问题、车间调度问题等离散领域的优化问题中具有一定的优势,并取得了较好的效果。目前,蚁群算法己成为国际智能计算领域中备受关注的研究热点和前沿性课题。本文研究的重点在于蚁群算法的改进和应用。针对蚁群算法存在求解时间长、收敛速度较慢、对局部寻优不理想等缺点,分别从路径选择策略、信息素更新策略、算法收敛判断三个方面对算法进行改进：(1)在MMAS算法基础上改进路径搜索策略。通过采用徐精明等人提出轮盘赌方法提高算法的随机性,再利用候选列表使得算法能够更加集中于搜索感兴趣的部分以减小搜索空间的维度,最后引入局部搜索策略进一步优化解的质量。(2)为了更好的利用反馈信息,增强较短路径的导向性,文本引入了加权因子λ来改进算法的信息素更新策略。(3)利用信息熵作为算法的收敛判断,提出一种基于信息熵的加权蚁群算法。实验结果表明该算法有较好的求解能力和执行效率。最后,将基于信息熵的加权蚁群算法应用于智能交通领域,来验证算法的可行性和有效性。文中介绍了实际交通路网的构建过程,地球上任意两点间距离计算的相关算法,及如何结合AHP模型用基于信息熵的加权蚁群算法求解城市交通路网中车辆的最优路径的方法。实验证明,该算法能准确快速地找到最优路径。

论文目录

• 摘要
• Abstract
• 目录
• 第一章 绪论
• 1.1 课题的研究背景和意义
• 1.2 国内外的研究现状和进展
• 1.3 论文的主要工作和研究线路图
• 1.4 论文创新点和内容安排
• 1.5 本章小结
• 第二章 蚁群算法的原理及研究
• 2.1 蚁群算法原理及算法描述
• 2.1.1 蚁群算法的生物基础
• 2.1.2 蚁群算法的基本原理
• 2.2 蚁群算法的抽象模型及其实现
• 2.2.1 TSP问题的描述
• 2.2.2 蚁群算法的模型及其实现
• 2.3 几种经典的ACO算法及性能分析
• 2.4 蚁群算法与其他群智能算法的比较
• 2.4.1 蚁群算法与遗传算法的比较
• 2.4.2 蚁群算法与粒子群算法的比较
• 2.5 本章小结
• 第三章 基于信息熵的加权蚁群算法的研究及其性能分析
• 3.1 改进算法的选择策略
• 3.2 改进算法的信息素更新策略
• 3.3 基于信息熵的算法改进
• 3.4 基于信息熵的加权蚁群算法在TSP上的实现
• 3.4.1 基于信息熵的加权蚁群算法的实现步骤
• 3.4.2 基于信息熵的加权蚁群算法与MMAS的性能比较
• 3.5 基于信息熵的加权蚁群算法中参数的选择及对算法的影响
• 3.5.1 蚂蚁数量m的选择
• 3.5.2 信息素挥发因子ρ的选择
• 3.5.3 启发式因子α、β的选择
• 3.6 本章小结
• 第四章 基于信息熵的加权蚁群算法在智能交通中的应用
• 4.1 交通道路网的表示方式
• 4.1.1 路网拓扑结构的提取
• 4.1.2 路网拓扑结构的效果图
• 4.2 椭球算法计算两点距离
• 4.3 出行者选择路径的不同准则
• 4.4 利用AHP模型选择最优路径
• 4.5 基于信息熵的加权蚁群算法在寻优问题中的实现
• 4.5.1 寻优过程
• 4.5.2 寻优结果展示
• 4.6 本章小结
• 第五章 结论与展望
• 5.1 工作总结
• 5.2 进一步的工作展望
• 致谢
• 参考文献
• 附录A （攻读硕士期间发表的论文及其他成果）
• 附录B （算法核心代码）