蚁群算法研究及其应用

论文摘要

在诸多启发式算法中,蚁群算法因具有较强的鲁棒性、分布式计算、易于与其优化算法结合等优点越来越受到人们的关注,已应用到诸多领域;但蚁群算法存在不足,如:易出现局部最优、运行时间长和参数选择难等等。针对蚁群算法的不足,本文开展了关于改进蚁群算法的研究;针对蚁群算法参数选择难的问题,本文开展了关于蚁群算法参数组合优化的研究,提出了基于粒子群的蚁群算法参数组合优化方案,设计了参数最佳组合训练系统;针对国内蚁群算法求解TSP问题仿真系统的空白,设计并实现了基于多线程的蚁群算法TSP问题仿真系统。本文主要研究工作如下:1.阐述论文的研究背景、意义及国内外研究进展,总结常见的改进蚁群算法,分析蚁群算法优缺点。2.分析蚁群算法不足之原因;针对不足,提出改进蚁群算法。该算法借鉴奖惩蚁群算法思想对信息素进行更新;借鉴最大最小蚁群算法思想对各路径信息素的大小进行限制;借鉴自然蚂蚁无法感知距离之行为,对蚁群路径的选择策略进行改进。仿真证明,该算法在一定程度上提高了算法的性能,尤其是降低了算法的运行时间。3.针对蚁群算法参数空间大,参数选择难的问题;采用实例仿真法确定各参数的合理范围;采用粒子群算法,首次讨论了蚁群算法的五个重要参数的组合优化问题,提出了基于粒子群的蚁群算法参数组合优化方案,该方案采用“三步走”策略来确定参数的最佳组合。4.在深入理解蚁群算法的基础上,采用多线程技术,实现了针对TSP问题的蚁群算法仿真系统及蚁群算法参数组合优化训练系统,具有较强的实践意义。5.使用设计的参数最佳组合训练系统,求得参数最佳组合,采用本文改进蚁群算法,求解典型TSP问题,验证改进算法及参数最佳组合方案的可行性和有效性。总之,本文提出的改进蚁群算法是一种切实有效的算法;提出的基于粒子群的蚁群算法参数组合优化方案能够突破传统的参数选择方法的局限;设计的TSP问题仿真系统和参数训练系统能够在一定程度上推广蚁群算法的实用性。为日后的进一步研究提供了一定的参考和借鉴。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究的背景及意义
• 1.2 蚁群算法研究进展及存在的问题
• 1.3 论文主要工作和内容
• 第二章 蚁群算法
• 2.1 基本蚁群算法
• 2.2 蚁群算法优缺点
• 2.2.1 蚁群算法的优点
• 2.2.2 蚁群算法的缺点
• 2.3 现有改进蚁群算法介绍
• 2.3.1 带精英策略的蚁群系统
• 2.3.2 基于排序的蚂蚁系统
• 2.3.3 蚁群系统
• 2.3.4 最大最小蚂蚁系统
• 2.3.5 最优最差蚂蚁系统
• 2.4 本章小结
• 第三章 一种改进的蚁群算法
• 3.1 改进蚁群算法的思想
• 3.2 改进策略
• 3.2.1 初始信息素的改进
• 3.2.2 路径选择策略的改进
• 3.2.3 信息素更新策略改进
• 3.2.4 引入Max-Min 思想
• 3.3 改进蚁群算法实现
• 3.4 本章小结
• 第四章 基于粒子群的蚁群算法参数组合优化
• 4.1 蚁群算法参数对性能的影响
• 4.1.1 信息素挥发度的分析
• 4.1.2 启发式因子α的分析
• 4.1.3 启发式因子β的分析
• 4.1.4 蚁群数量m 的分析
• 4.1.5 信息素量的分析
• 4.2 参数组合优化方案
• 4.3 粒子群算法介绍
• 4.3.1 粒子群算法原理
• 4.3.2 粒子群算法模型
• 4.3.3 粒子群算法参数选择
• 4.4 基于粒子群的蚁群算法参数组合优化实现
• 4.4.1 蚁群算法的实现
• 4.4.2 粒子群算法的实现
• 4.5 本章小结
• 第五章 蚁群算法仿真系统设计及数值试验
• 5.1 蚁群算法仿真系统设计
• 5.1.1 系统模块设计框架图
• 5.1.2 系统界面图
• 5.2 数据仿真
• 5.2.1 本文改进算法有效性验证
• 5.2.2 本文改进算法性能验证
• 5.2.3 参数组合优化训练
• 5.2.4 参数组合优化性能验证
• 5.3 算法分析
• 5.4 本章小结
• 第六章 总结与展望
• 6.1 结论
• 6.2 未来展望
• 参考文献
• 附录A 基本蚁群算法 C++代码
• 附录B 粒子群算法 C++代码
• 个人简历 在读期间发表的学术论文
• 致谢