改进的蚂蚁算法在TSP问题中的研究

论文摘要

TSP问题(Traveling Salesman Problem)是一个组合优化方面的问题,己经成为并将继续成为测试组合优化新算法的标准问题。从理论上讲,使用穷举法不但可以求解TSP问题,而且还可以求出该问题的最优解。但是对现有的计算机来说,使用穷举法在如此庞大的搜索空间中寻求最优解,几乎是不可能的。所以,各种求TSP问题近似解的优化算法应运而生了,本文所用到的蚂蚁优化算法也在其中。蚂蚁算法作为一类启发式算法,已经成功地应用于求解TSP问题。蚂蚁通过分泌信息素来加强较好路径上的信息素的强度,同时按照路径上的信息素强度来选择下一步所选择的路径,好的路径将会被越来越多的蚂蚁选择,因此更多的信息素将会覆盖较好的路径,最终所有的蚂蚁都集中到了好的路径上。蚂蚁的这种基于信息素的正反馈原理正是整个算法的关键所在。本文首先介绍了TSP问题并且给出了TSP问题的综述,接着讨论了基本蚂蚁算法数学模型及其关键技术,给出蚂蚁算法实现的具体步骤。在此之后,通过实验分析了算法中各个参数的作用及其对算法性能的影响,给出了蚂蚁算法各参数的经验取值。同时充分分析了基本蚂蚁算法现有问题,表现出的主要现象有:搜索时间长,收敛速度慢,易于陷入局部最优解。通过进一步对蚂蚁算法的分析,得出产生这些问题的主要原因是:a)信息素在更新时,信息素轨迹量不被限制,使得一些路径上的信息量远高于其他边,从而阻止进一步搜索更优解的行为,导致其可能出现搜索停滞。b)全局更新规则对系统中所有蚂蚁都进行,这种方式没有很充分利用上次循环中所得路径信息,不能使其搜索行为很快的集中到最优路径附近,降低了算法的搜索效率。针对以上问题,本文提出了一种改进的蚂蚁算法并将其应用于解决TSP问题,具体改进为:a)提出了一种新的信息素更新方式,对每次循环后产生的最差和最优路径进行信息素更新的同时,对所有路径进行局部更新,并将每条路径的信息素控制在给定区间内。b)根据生物对环境的敏感程度的变化原理,给出了对参数α、β实现自适应调整的函数。通过改进,避免了搜索的停滞,提高了算法解的质量;使蚂蚁以更高的概率选择较好的路径,提升了算法寻优能力;同时使模型中的蚂蚁个体具有了更接近于真实蚂蚁的个性,并更为贴切的对外界环境的变化做出反应。最后总结了全文主要工作及改进点,分析了研究中的不足,展望了未来的研究方向。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 本文选题的背景及意义
• 1.2 蚂蚁算法的起源与发展
• 1.3 TSP 问题的重要应用
• 1.4 本文所做工作
• 第2章 TSP 问题
• 2.1 TSP 问题的简介
• 2.2 TSP 问题的理论意义
• 2.3 求解TSP 问题的方法简介
• 2.4 TSP 算法的综述
• 2.5 本章小结
• 第3章 基本蚂蚁算法
• 3.1 蚂蚁算法的建立机制
• 3.2 蚂蚁算法产生的原理
• 3.3 蚂蚁算法策略及其特点
• 3.4 基本蚂蚁算法的数学模型
• 3.5 蚂蚁算法关键技术
• 3.6 本章小结
• 第4章 蚂蚁算法中参数的设置及其影响
• 4.1 蚂蚁算法中各参数的设置
• 4.2 基本蚂蚁算法的优点与不足之处
• 4.3 本章小结
• 第5章 改进的蚂蚁算法求解TSP 问题
• 5.1 信息素τ的限制
• 5.2 信息素更新方式
• 5.3 权函数的自适应调整
• 5.4 改进后的算法模型
• 5.5 改进算法的实验结果与分析
• 5.6 本章小结
• 第6章 总结与展望
• 参考文献
• 致谢
• 附录A 攻读学位期间所发表的学术论文目录