基于带记忆的蚂蚁的蚁群优化算法在TSP上的应用

论文摘要

研究群居性昆虫行为特征的科学家发现,昆虫每个个体能力十分有限,在群落一级上的合作基本上是自组织的,在许多场合中尽管这些合作可能很简单,但是却可以解决复杂的问题。群居性昆虫行为的研究为计算机科学家提供了设计分布式控制和优化算法的有力方法。蚁群算法就是利用群体智能解决组合优化问题的典型例子。对以蚁群算法为代表的群体智能的研究已经逐渐成为一个研究热点。蚁群算法是一种应用于组合优化问题的启发式搜索算法,具有正反馈、分布计算和启发性搜索等特点。蚁群算法自从其出现以来,先后应用于TSP问题、资源二次分配问题等经典优化问题,得到了较好的效果,吸引了大批学者的兴趣。近年来,其研究领域也拓展到了动态环境、混沌计算、多目标等领域,基于蚁群优化算法的新型技术也陆续的面世并且不断的改进。但蚁群算法的提出才不过十几年时间,还未形成完整的数学体系,算法的性能也有待提高。本文以研究典型的NP问题——旅行商问题入手,对蚁群优化算法的发展背景、内容、实现方法和性能作了详细介绍,对该算法本身进行了深入研究,提出了自己的改进方案。本文在蚁群优化算法的研究中主要作了如下几点工作:1.引入带记忆能力的蚂蚁,并且通过程序实现了这个功能,在程序上完成了新蚂蚁与蚁群算法和最大-最小蚂蚁算法的结合;2.在10个不同规模的对称静态旅行售货员问题上,用改进的蚁群算法和最大-最小蚂蚁算法分别进行仿真。通过对大量的数据结果进行对比分析,发现带记忆能力的蚂蚁能够让已有的蚁群优化算法在解决小型城市的旅行售货员问题时,速度上有较明显的提高,但是在中型规模以上的城市群中速度和结果表现都有所欠缺。3.经过分析,对带记忆的蚂蚁进行优化,根据蚂蚁算法中局部搜索时,蚂蚁确定下一个城市采用的伪随机分配思想,让蚂蚁成为具有高、低两种记忆概率的个体。然后通过程序实现了该模型的功能,在程序上完成新功能蚂蚁与蚁群算法和最大-最小蚂蚁算法的结合。4.在10个不同规模的对称静态旅行售货员问题上,用再次改进的蚁群算法和最大最小蚂蚁算法分别进行仿真。通过对大量的数据结果进行对比分析,发现高概率带记忆能力的蚂蚁在与蚁群算法和最大-最小蚂蚁算法结合后的新算法表现最为突出,在寻找最优解的速度和解上有显著程度的优化。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 选题背景及研究意义
• 1.2 群体智能简介
• 1.3 算法性能的评价方法
• 第2章 组合优化问题与TSP 简介
• 2.1 组合优化问题
• 2.2 算法的复杂性和 NP 问题
• 2.3 TSP 问题
• 2.4 小结
• 第3章 蚁群优化算法
• 3.1 蚁群优化算法的基础原理
• 3.1.1 蚂蚁算法生物学原理
• 3.1.2 人工蚂蚁机理分析
• 3.2 主要的蚁群优化算法
• 3.2.1 蚂蚁算法（AS）
• 3.2.2 最大-最小蚂蚁系统（MMAS）
• 3.2.3 蚁群系统（ACS）
• 3.3 参数分析
• 3.3.1 蚂蚁数目m
• 3.3.2 信息素挥发速度ρ
• 3.3.3 启发式因子α和β
• 3.4 局部优化涉及到的优化算法
• 3.4.1 最近邻居算法
• 3.4.2 3-opt 算法
• 3.5 小结
• 第4章 带记忆的蚂蚁及TSP 上的仿真实验
• 4.1 带记忆的蚂蚁
• 4.2 试验环境及参数设置
• 4.3 带记忆蚂蚁在ACS 和MMAS 上面的应用
• 4.3.1 M-ant 在ACS 上
• 4.3.2 M-ant 在MMAS 上
• 4.4 总结和改进
• 第5章 概率带记忆的蚂蚁及TSP 上的仿真实验
• 5.1 概率带记忆的蚂蚁
• 5.2 概率带记忆蚂蚁在ACS 和MMAS 上面的应用
• 5.2.1 M-antP 在ACS 上
• 5.2.2 M-antP 在MMAS 上
• 5.3 小结
• 第6章 结论和展望
• 参考文献
• 致谢
• 附录A
• 附录B
• 附录C
• 个人简历、在学期间发表的学术论文及研究成果