蚁群算法及其在TSP中的应用

蚁群算法在解决TSP问题中的应用作者：陈灵佳来源：《电子技术与软件工程》2017年第10期文章首先对蚁群算法与TSP问题进行简要介绍，在此基础上对蚁群算法在解决TSP问题中的应用进行论述。

期望通过本文的研究能够对TSP问题的解决有所帮助。

【关键词】蚁群算法 TSP问题最优解1 蚁群算法与TSP问题简介1.1 蚁群算法蚁群算法是一种随机的、概率搜索算法，它是目前求解复杂组合优化问题较为有效的手段之一，借助信息反馈机制，能够进一步加快算法的进化，从而更加快速地找到最优解。

蚁群算法可在诸多领域中应用，借助该算法能够求得TSP问题的最短路径。

蚁群寻找最短路径的过程如图1所示。

蚁群算法之所以在多个领域获得广泛应用，与其自身所具备的诸多优点有着密不可分的关联，如自组织性、正负反馈性、鲁棒性、分布式计算等等，其最为突出的优点是能够与其它算法结合使用。

但是在应用实践中发现，虽然蚁群算法的优点较多，其也或多或少地存在一定的不足，如搜索时间较长，规模越大时间越长；容易出现停滞现象等等。

1.2 TSP问题TSP是旅行商的英文缩写形式，这一术语最早出现于1932年，在1948年时，美国兰德公司（RAND）引入了TSP，由此使得TSP广为人知。

从数学领域的角度上讲，TSP问题是NP-完备组合优化问题，这是一个看似简单实则需要天文数字计算能力方可获得最优解的过程，其适用于搜索算法解决不了的复杂与非线性问题。

2 蚁群算法在解决TSP问题中的应用2.1 蚁群算法的改进（1）大量的实验结果表明，标准蚁群算法在TSP问题的求解中，很容易陷入局部最优解。

这是因为，蚁群的转移主要是由各条路径上的信息素浓度及城市间的距离来引导的，信息素浓度最强的路径是蚁群的首选目标，该路径与最优路径极为接近。

然而，各个路径上初始信息素的浓度全部相同，因此，蚁群在对第一条路径进行创建时，主要依赖于城市间的距离信息，这样一来很难确保蚁群创建的路径是最优路径，如果以此为基础，那么信息素便会在该局部最优路径上越积累越多，其上的信息素浓度将会超过其它路径，从而造成全部蚂蚁都会集中于该路径之上，由此便会造成停滞现象，不但会使搜索的时间增长，而且所求得的解也无法达到理想中的效果。

还有页眉没有添加，页眉上写章标题，把我给你标注的问题改完就可以打印了摘要根据蚂蚁生态学提出的蚁群算法是一种新颖的用于求解复杂组合优化问题的模拟进化算法,具有典型的群体智能特征,表现出较强的学习能力和适应能力。

本文阐述了该算法的基本原理、算法模型和在TSP( Traveling Salesman Problem，旅行商)问题中的具体应用过程,并对算法进行了总结和展望。

关键词：蚁群算法，旅行商问题，外激素目录摘要Ⅰ目录II第一章引言 (1)第二章蚁群算法的基本原理和模型 (2)2.1 蚁群算法的基本原理 (2)2.2 蚁群算法的模型 (3)第三章基于蚁群算法的TSP求解 (5)3.1 TSP问题的描述 (5)3.2 基于蚁群算法的TSP求解 (5)3.3 蚁群算法的局限性 (6)第四章蚁群算法的改进 (8)4.1 优选参数m (8)4.2 参数 的调整 (8)4.3 信息素的更新 (8)4.4 信息素链表L 和禁忌链表TL 的构建 (9)第五章改进的算法基本流程 (10)第六章结论 (11)参考文献 (12)第一章引言研究群居性昆虫行为的科学家发现，昆虫在群落一级上的合作基本上是自组织的，在许多场合中尽管这些合作可能很简单，但它们却可以解决许多复杂的问题。

蚁群算法就是利用群集智能解决组合优化问题的典型例子。

蚁群算法（Ant Colony Algorithm, ACA）是由意大利学者M.Dorigo，V.Mzniezzo，A.Colorni 等人在20世纪90年代初首先提出来的。

它是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等元启发式搜索算法以后的又一种应用于组合优化问题的启发式搜索算法。

蚁群算法不仅能够智能搜索、全局优化，而且具有稳健性A、鲁棒性B、正反馈、分布式计算、易与其它算法结合等特点。

利用正反馈原理，可以加快进化过程；分布式计算使该算法易于并行实现，个体之间不断进行信息交流和传递，有利于找到较好的解，不容易陷入局部最优；该算法易与多种启发式算法结合，可改善算法的性能；由于鲁棒性强，故在基本蚁群算法模型的基础上进行修改，便可用于其它问题。

蚁群算法原理及在TSP 中的应用1 蚁群算法（ACA ）原理1.1 基本蚁群算法的数学模型以求解平面上一个n 阶旅行商问题(Traveling Salesman Problem ，TSP)为例来说明蚁群算法ACA （Ant Colony Algorithm ）的基本原理。

对于其他问题，可以对此模型稍作修改便可应用。

TSP 问题就是给定一组城市，求一条遍历所有城市的最短回路问题。

设()i b t 表示t 时刻位于元素i 的蚂蚁数目，()ij t τ为t 时刻路径(,)i j 上的信息量，n 表示TSP 规模，m 为蚁群的总数目，则1()ni i m b t ==∑；{(),}ij i i t c c C τΓ=⊂是t 时刻集合C 中元素(城市)两两连接ij t 上残留信息量的集合。

在初始时刻各条路径上信息量相等，并设 (0)ij const τ=，基本蚁群算法的寻优是通过有向图(,,)g C L =Γ实现的。

蚂蚁(1,2,...,)k k m =在运动过程中，根据各条路径上的信息量决定其转移方向。

这里用禁忌表(1,2,...,)k tabu k m =来记录蚂蚁k 当前所走过的城市，集合随着k tabu 进化过程作动态调整。

在搜索过程中，蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率。

()kij p t 表示在t 时刻蚂蚁k 由元素(城市)i 转移到元素(城市)j 的状态转移概率。

()*()()*()()0k ij ij k kij ij ij s allowed t t j allowed t t p t αβαβτητη⊂⎧⎡⎤⎡⎤⎣⎦⎣⎦⎪∈⎪⎡⎤⎡⎤=⎨⎣⎦⎣⎦⎪⎪⎩∑若否则(1)式中，{}k k allowed C tabuk =-表示蚂蚁k 下一步允许选择的城市；α为信息启发式因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起作用，其值越大，则该蚂蚁越倾向于选择其他蚂蚁经过的路径，蚂蚁之间协作性越强；β为期望启发式因子，表示能见度的相对重要性，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的重视程度，其值越大，则该状态转移概率越接近于贪心规则；()ij t η为启发函数，其表达式如下：1()ij ijt d η=(2)式中，ij d 表示相邻两个城市之间的距离。

蚁群算法及其在TSP问题中的应用研究摘要：tsp问题是一类典型的np完全问题，蚁群算法是求解该问题的方法之一。

该文在研究蚁群算法的基本优化原理的基础上，建立了求解tsp 问题的数学模型，设计了一个求解tsp问题的蚁群算法程序，并通过仿真实验验证了算法的有效性，分析了蚂蚁规模、周游次数等因素对蚁群算法搜索结果所产生的影响。

关键词：tsp；蚁群算法；np完全问题中图分类号：tp301 文献标识码：a 文章编号：1009-3044（2013）13-3117-03旅行商问题（traveling salesman problem，简称tsp）是一个具有广泛应用背景和重要理论价值的组合优化问题，它已被证明属于np难题[1]。

目前对于求解该类问题的研究主要有两个方向：一是传统的数学规划方法，这种算法可以得到全局最优解，但复杂性往往难以接受，因而不适应于大规模复杂问题的求解。

二是近年来发展起来的各种仿生进化算法如遗传算法、蚁群算法等，此类算法能够在多项式时间内找到全局最优解或近似全局最优解[2]。

蚁群算法（ant colony algorithm，简称aca）是受自然界中蚂蚁集体寻食过程的启发而提出来的一种新的智能优化算法，它具有高度的本质并行性、正反馈选择、分布式计算、鲁棒性等优点，蚁群算法最早成功地应用于解决tsp问题。

本文在研究蚁群算法的基本优化原理的基础上，编写了一个基于vc的求解tsp问题的蚁群算法程序，并且通过多次实验测试，验证了算法的有效性，分析了蚂蚁规模、周游次数等因素对蚁群算法的搜索结果和效率所产生的影响。

1 tsp问题建模2 基于蚁群算法的tsp问题求解2.2蚁群算法的基本原理蚁群算法是一种源于自然生物界的新型仿生优化算法，它于20世纪90年代初由意大利学者m.dorigo，v.maniezzo首次提出[3]，蚁群算法的特点是模拟自然界中蚂蚁寻食的群体行为。

研究表明，蚂蚁会在走过的路上留下信息素，信息素会随时间的推移逐渐挥发消失，蚂蚁就是通过信息素进行信息交流。

１１２长春理工大学学报（自然科学版）２００８正系数，表示负增长量与正增长的比例倍数。

一般来说９不可过大，否则会使部分较优路径上的信息素的含量过小而失去被选择的可能，导致最优解质量下降。

△ｒ－一９ｘ罢（６）（２）在每次发现新的最优解时，适当减／ｂＰ的值．提高算法的随机性能和全局搜索能力；发现新的最差解时适当增加ｐ的值，提高解路径上的信息素残留量，以减少对最差解的选择概率。

变参数Ｐ的作用在于维持解空间的平衡，既不使解空间过大而导致随机性增强．又不使解空间过小而停滞早熟，Ｐ变化量根据公式（７）计算，盯为变化系数，表示Ｐ的变化快慢。

Ｐ：Ｊｐ＋似ｐｐ＜‰（７）。

ｌＰ一盯×ＰＰ＞‰ｈ【，，。

ｄ“一“％’一“∞‘∞２昌昌导曷图４妒与平均最优解的关系Ｆｉｇ．４Ｒｅｌａｔｉｏｎｏｆ叩ａｎｄａｖｅｒａｇｅｏｐｔｉｍｕｍｓｏｌｕｔｉｏｎ图５ｏ与平均最优解的关系Ｆｉｇ．５ＲｅｌａｔｉｏｎｏｆＯａｎｄａｖｅｒａｇｅｏｐｔｉｍｕｍｓｏｌｕｔｉｏｎ负增长系数３与信息素残留度变化系数ｄｒ的取值需要通过实验确定，结果如图４、图５所示。

图４中横坐标为１９值，纵坐标为平均最优解；图５中横坐标为ｄｒ值，纵坐标为平均最优解。

从图中可知，９取值在２的时候，平均最优解的质量最好。

而在８的取值大于２０之后，平均最优解质量突然变差，说明此时负增长已经破坏了信息素的正反馈作用。

盯取值在Ｏ．１２５—０．１７５之间平均最优解的结果比较好而且稳定。

信息素负增长只能保证最差解路径上的信息素含量降低，不能保证全部信息素的降低因此无法达到更好的保证搜索空间的效果；变参数盯则是针对全部解，可以减慢收敛速度却无法更好的保证较差路径的排除。

将两者结合起来，会产生更好的效果。

表ｌ为基本蚁群算法与改进的并行算法的运行结果对比。

可见用改进蚁群算法解决ＴＳＰ问题时，可以在平均时间减少的情况下，得到更好的平均最优解。

表１改进蚁群算法与基本算法实验结果比较Ｔａｂ．１Ｃｏｍｐａｒｅｏｆｉｍｐｒｏｖｅｄａｎｔａｌｇｏｒｉｔｈｍａｎｄｂａｓａｌａｌｇｏｒｉｔｈｍ４结束语蚁群算法是一种本质上并行的算法，通过集群容易实现其并行化。