蚁群算法的改进及其应用

论文摘要

意大利学者M.Dorigo,V.Maniezzo和A.Colorni于1992年通过模拟蚁群觅食行为提出了一种基于种群的模拟进化算法——蚁群优化。该算法的提出引起了学者们的极大关注,在过去短短十多年的时间里,已在组合优化、网络路由、函数优化、数据挖掘、机器人路径规划等领域获得了广泛的应用,并取得了较好的效果。本文围绕蚁群算法的改进及其应用,就如何改进蚁群算法、与其它算法混合、以及在组合优化领域的应用进行了深入研究。文章的主要研究工作如下:首先,针对蚁群算法的初始信息素匮乏和容易出现早熟,提出了一种免疫克隆-蚁群算法。首先采用免疫克隆算法生成初始信息素分布,然后利用融入免疫克隆算子的蚁群算法进行搜索。这种方法能有效地抑制了收敛过程中的停滞现象,提高了算法的搜索能力。在求解大规模优化问题时,为了克服了轮盘赌的盲目性,本文引入一种基于对比度增强的路径选择规则,算法的收敛速度有了很大的提高。将改进后的算法应用于TSP问题,仿真结果表明改进后的算法比原有算法具有更优越的性能。其次,通过汲取蚁群算法（ACA）和抗体免疫克隆算法（AICA）的优点,提出了一种新型的求解0-1背包问题的混合算法。蚁群算法的正反馈机制使其具有突出的局部搜索性能,但容易陷入停滞;而抗体克隆算法搜索区域比较大,但收敛较慢。本文算法充分利用了前者的搜索能力和后者的种群多样性。实验结果表明,本算法是一种收敛速度和寻优能力都比较好的优化方法。最后,对全文的研究工作进行了总结,并展望了蚁群优化进一步还要研究的课题。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 引言
• 1.2 蚁群算法原理模型
• 1.2.1 蚁群算法基本原理
• 1.2.2 算法模型
• 1.3 蚁群算法的应用
• 1.3.1 作业调度问题
• 1.3.2 二次分配问题
• 1.3.3 背包问题
• 1.3.4 分类规则的学习问题
• 1.4 蚁群算法的研究现状
• 1.5 本文的主要内容
• 2 改进的蚁群算法
• 2.1 引言
• 2.2 蚁群算法的改进策略
• 2.2.1 路径选择策略的改进
• 2.2.2 信息素的更新策略的改进
• 2.2.3 引入变异策略
• 2.2.4 添加随即扰动策略
• 2.2.5 与其他算法的融合
• 2.3 改进的蚁群算法
• 2.3.1 精英蚂蚁系统
• 2.3.2 基于排序的蚂蚁系统
• 2.3.3 最大-最小蚂蚁系统
• 2.3.4 蚁群系统
• 2.3.5 各种蚁群算法的比较
• 2.4 本章小结
• 3 蚁群算法与免疫克隆算法的融合
• 3.1 引言
• 3.2 基本免疫克隆算法
• 3.3 解TSP 问题的的免疫克隆-蚁群算法
• 3.3.1 混合的基本思想
• 3.3.2 免疫克隆算法的变异算子
• 3.3.3 路径选择规则的改进
• 3.3.4 ACACA 算法描述
• 3.4 实验仿真结果
• 3.5 本章小结
• 4 基于蚁群和抗体免疫克隆算法的0-1 背包问题求解
• 4.1 引言
• 4.2 0-1 背包问题概述
• 4.3 KPAICACA 算法和算法描述
• 4.3.1 KPAICACA 算法
• 4.3.2 KPAICACA 算法描述
• 4.4 实验仿真结果
• 4.4.1 KPAICACA 算法的参数设置和分析
• 4.4.2 仿真实验
• 4.5 本章小结
• 5 结论与展望
• 5.1 结论
• 5.2 展望
• 致谢
• 参考文献
• 附录