论文部分内容阅读
蚁群算法是一种仿生优化算法，它是受到蚂蚁觅食行为的启发提出的。蚁群算法具有分布式计算机制、易与其他方法相结合和具有很强的鲁棒性等优点。蚁群算法已经应用到很多应用领域，并且取得了较好的成果。TSP问题是NP问题，提高TSP问题的求解效率有很多理论及实际意义，蚁群算法能较好的应用于求解TSP问题。本文首先介绍了蚁群算法和TSP问题的相关知识及研究现状，在现有蚁群算法理论及研究的基础上，我们提出了改进型的蚁群算法，本为主要做了以下工作：(1)对TSP问题相关知识进行概述，给出了TSP问题的数学模型，并且综述了现有求解TSP问题的主要方法。首先概述仿生优化算法的相关内容，对几种经典的仿生优化算法进行比较，引出蚁群算法。从蚁群算法的起源，引出蚁群算法模型的建立，并给出基本蚁群算法的数学模型，介绍蚁群算法的实现步骤，最后详细的介绍几种经典的局部优化算法。(2)基于蚁群算法参数对蚁群算法的影响，重点研究了蚂蚁数目、信息素残留系数、启发式因子、信息素强度等对蚁群算法的影响。蚁群算法的参数较多，参数之间存在着耦合的情况，而当前算法参数的选取都是靠研究者的研究经验去设置的。研究采用TSPLIB测试库中的实验问题作为实验对象，对上面几个比较重要的参数进行分析。设置相关实验，分别对m、、、、Q等进行分析研究，以应用较多的Ant-Cycle模型为例，找到这些参数的最优取值区间。(3)详细研究现有的几种改进蚁群算法，并通过TSPLIB测试库中的实验问题作为实验对象对改进蚁群算法进行实验，从实验结果分析这些改进蚁群算法性能的优劣。其中重点研究了多态蚁群算法、自适应调整信息素挥发因子的蚁群算法、基于去交叉局部优化策略的蚁群算法和基于混合行为的蚁群算法等几种经典的改进蚁群算法。结合这几种改进蚁群算法及对蚁群算法相关参数的研究，这里给出一种主要基于多态蚁群算法的改进蚁群算法，给出改进算法的思想、算法步骤，最终同样通过实验验证算法的性能，证明算法的可行性和有效性。