基于改进蚁群算法的TSP问题研究

许能闯

摘 要：蚁群算法作为解决TSP中组合优化问题方案，其搜索路径能力较其它算法优异，但传统蚁群算法的选取策略较随机，导致进化速度慢。为了优化传统蚁群算法速度较慢、过早收敛以致停滞现象，针对概率选取公式随机搜索下一节点，以延缓其收敛速度。对信息素调节公式进行更新以提高蚁群的搜索能力。实验结果表明，改进算法在最短路径、平均路径和搜索最短路径时间上较蚁群算法提高很大，改进的蚁群算法能有效提高算法的收敛速度和搜索能力。

关键词：蚁群算法；正反馈；信息素；收敛速度；TSP問题

DOIDOI：10.11907/rjdk.173024

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2018）002-0056-04

0 引言

TSP问题[1]即旅行商问题，其含义是某商人要访问n个城市后再回到出发城市，前提是各城市只能访问一遍，从而确定最短路径[2]。

目前，针对该问题的解决方案较多，如动态规划法、遗传算法、模拟退火算法等，但这些算法的实现很复杂，由此蚁群算法应运而生。蚁群算法是一种新型的优化算法，其模拟蚂蚁觅食过程。在食物寻找过程中，蚂蚁会分泌信息素记录所走路径，其它蚂蚁根据信息素的浓密程度，选择其中较短路径去寻觅食物，该算法最早于20世纪90年代初由意大利学者Dorigo M[3]提出。蚁群算法中，当越多的蚂蚁分布在路径上，其信息素释放也越多，此时更多蚂蚁将选择信息素浓度大的路径去寻觅食物，由此体现其算法具备好的鲁棒性和协作性。该算法广泛应用在网络优化和路径寻优问题上，是解决组合优化问题的有效算法之一[4]。

文献[5]中，针对TSP容易陷入局部最优和收敛速度慢的问题，提出了一种博弈论的量子蚁群算法。该算法采用博弈模型产生博弈序列，使产生的效益最大，能有效解决蚁群算法的收敛速度和稳定性问题。文献[6]中，针对路径优化问题，提出一种竞争方式以更改信息素的更新机制，使算法的搜索结果更优，精度更高。文献[7]针对蚁群算法求解聚类特征TSP的收敛速度慢的问题，提出新的蚁群算法，将TSP问题从数据域分解为多个子问题，从而分别求解以提高算法的收敛速度。

作为典型的NP问题，已将TSP用作测试和比较算法性能方法[8]。本文在考虑蚁群算法的搜索能力和收敛速度基础上，依据现有算法特点和不足，提出改进蚁群算法的概率选取方式和信息素的更新方式。引入新的参数，改变概率选取方式以延缓收敛速度。与此同时，在信息素更新过程中采用新的更新机制，使蚂蚁寻优效果更好，以提高算法的搜索能力及搜索结果。

1 算法简介

1.1 蚁群算法工作原理

蚁群算法是由许多蚂蚁组成的集体行为构成的一种信息学习正反馈算法[9]：当某条路径上蚂蚁越多，其释放的信息素就越多，信息浓度随之越高，其后选择该路径的可能性越大，个体间通过交流信息以寻找通向食物的最短路径，正反馈现象如图1所示。蚂蚁刚开始觅食时，假设各路径上初始时刻信息素都相同，40只蚂蚁等概率从A结点出发去寻找食物（D结点），有两条路径可以到达，故蚂蚁平均分配20只到路径A-B-D和A-C-D上。因A-B-D和A-C-D的距离分别为20m和30m，故单位时间内在路径A-B-D上通过的蚂蚁数量较多，其释放的信息素也多，导致该路径被其它蚂蚁选择的概率就大。一段时间过后，A-B-D上的蚂蚁为30只，A-C-D上的蚂蚁只有10只，如图2所示。由此可见，随着蚂蚁正反馈现象的持续，A-B-D上蚂蚁会继续增多，最终蚂蚁觅食可找到最佳路径。

1.2 路径选择概率机制

蚂蚁觅食过程分析可有效帮助TSP问题的求解。在TSP问题中，蚂蚁随机分配到各个节点（即城市），因各节点只能被访问一次，故蚂蚁k（k=1，2，3…，m）在节点i访问下一节点j的概率为：

1.3 信息素更新机制

因蚂蚁在访问节点过程中会在经过的路径上释放信息素，为避免残留的信息素过多掩盖启发信息，故当蚂蚁访问完某个节点或完成对所有节点的访问后，必须更新遗留的信息素，故（i，j）上的信息素τij的更新公式为：

1.4 算法流程

求解TSP问题的蚁群算法步骤如下：①初始化算法所需参数。设置循环次数Nc=0，最大迭代次数NC_Max，路径初始化信息量Δτij（t）=C，C为常数，Δτij（0）=0；②将m只蚂蚁置于n个城市，对每只蚂蚁按路径选择概率pkij访问下一节点j，j∈allowedk；③对各蚂蚁搜索的路径长度进行计算，记录当前搜索的最优解；④依据更新公式修改信息素；⑤将各条路径上的信息素增量Δτij，循环次数Nc分别设置为Δτij=0，Nc=Nc+1；⑥若NC_Max>Nc，则跳转至第②步；⑦若满足条件，则输出当前的最优解。算法流程见图3。

2 蚁群算法改进

2.1 蚁群算法缺点

对TSP问题进行求解时，蚁群算法常有以下不足之处：①在首次循环中，蚂蚁经过的路径上释放的信息素并不全是路径最优的方向；②因算法的全局搜索能力不足，当一段时间搜索后，会发现几乎一致的解，故局部最优解容易产生；③计算时间相对较长，容易产生停滞现象；④搜索时间较长；⑤传统蚁群算法对所有搜索路径都要更新信息素，故搜索最优路径效率降低。

2.2 改进的蚁群算法

蚁群算法依据蚂蚁路径上释放的信息素搜索最优解，其将优先选择信息素浓度大的路径。但当迭代次数一定时，因较优解的频率不断刷新使许多蚂蚁在较少蚁群的路径上聚集，从而出现停滞、早熟现象，导致局部最优解。本文依据算法在优化过程中的路径搜索和收敛速度情况，对路径选择概率和信息素进行更新，避免算法出现上述现象，从而提高算法的收敛速度及精确性。

2.2.1 路径选择概率改进endprint

传统蚁群算法中，各蚂蚁选择路径的概率主要由当前节点i访问下一节点j的信息素浓度τij和启发信息ηij两者共同决定，这在一定程度上误导蚂蚁选择最佳路径的机率，从而陷入局部最优解的窘境。为避免上述情况产生，对路径选择概率公式进行改进。蚂蚁由节点i访问下一节点j的概率为：

其中，q0是给定的参数值，范围为（0，1）之间，q是0～1之间的随机数，引入α/β参数，表示信息启发因子与期望启发因子的比值。通过参数引入影响算法的概率选取，以延缓算法收敛速度。当q>q0时，将采用q0的搜索方式；当q≤q0时，将采用q的搜索方式，其目的是保持概率选取在合理范圍。q0的选取调节了随机搜索和确定性搜索的平衡，且q0的大小决定算法的优劣。q0过大会导致算法陷入局部最优解，q0过小将影响算法的搜索程度，使算法收敛速度过慢。

2.2.2 信息素更新的改进

传统的蚁群算法中，单一的信息素更新导致算法并未充分利用上次循环所得的最短路径，故影响算法的精确搜索。为改善这种情况，将之前的信息素公式加以改进，防止蚂蚁过早经过同路径而产生局部最优解。

其中L′表示当前搜索的总路径长度，Lt表示搜索最长路径的集合。信息素调整公式是避免降低算法的收敛速度，提高蚁群对新发现的最短路径的敏感程度，从而快速对附近新的最短路径进行搜索。改进算法流程如图4所示。

3 实验结果

3.1 仿真环境

本文实验环境为Win10系统下的仿真软件平台。针对蚁群算法求解TSP问题，将本文提出的改进算法与原算法进行对比分析，从而检测改进的算法性能。以ACO52TSP和CH150TSP问题为例说明算法的可执行性，其数据均来自TSP标准数据库[10]。仿真参数设置为：城市数n=52或150，m=30，α=1，β=5，ρ=0.3，Q=100，q=0.6。对两种算法进行对比试验，算法迭代次数为200次。

3.2 仿真结果对比

在仿真软件平台环境下，选取最短路径和平均路径因素，将改进算法与蚁群算法性能进行对比。针对ACO52TSP问题，仿真效果如图5和图6所示。

图5中，程序刚开始运行时，改进算法和原算法都用较少的循环次数获得不错的解。随着程序的继续执行，原算法在循环17次左右出现停滞现象，而改进算法在18次左右表现很强的搜索能力，不断搜索最短路径。当程序运行到45次左右时就找到了最优解，即最短路径为7 033m。而原算法在循环18次才搜索到最优解，最短路径为7 179m。与原始算法相比，改进算法寻找路径最优。图6为ACO52最短路径线路，图7代表原算法和改进算法的搜索路径平均距离。

从图7可以很明显地看出，在0～15次循环期间，原算法和改进算法都以相同的速度寻找路径。随着算法循环至18次后，两者的平均路径出现差异。经过200次循环后，原算法平均路径最小为9 248m，改进算法为8 704m，改进算法在平均路径上明显优于原算法。改进算法性能得以提升，算法的可靠性和有效性得到了印证。

为进一步论证本文算法性能，再以CH150TSP问题为例，如图8所示。

在图8中，当程序刚开始运行时，改进算法的抖动程度较原算法大，表明改进算法有较大的搜索空间；随着程序的不断运行，在算法经过7次循环后，原算法已陷入停滞状态，而改进算法一直保持稳定的向下不断搜索路径；在程序的最后阶段，改进算法的最优解为6 835m，明显优于原算法的7 152m。这得益于参数的引入以及信息素的更新，改进算法花费更多的时间将信息素分泌在较优路径上，增加了算法的搜索能力，降低了收敛速度，使其演化速度更快、更稳定，结果最优。图9表示CH150最短路径线路。

4 结语

本文采用新的路径概率选取公式及信息素更新方法，提高了蚁群节点的收敛速度及搜索能力。本文提出的改进算法主要体现在节点路径选择概率和信息素的更新上。仿真结果表明，改进算法可有效地提高算法的收敛速度和搜索能力，达到精度更高和结果最优的目的。

参考文献：

[1] 孙文彬，王江.一种基于遗传算法的TSP问题多策略优化求解方法[J].地理与地理信息科学，2016，32（4）：1-4.

[2] 林冬梅，王东，李娅.一种求解多旅行商问题双层降解混合算法[J].计算机应用研究，2011，28（8）：2876-2879.

[3] DORIGO M， MANIEZZO V， COLORNI A. Ant system： optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics A Publication of the IEEE Systems Man & Cybernetics Society，1996，26（1）：29-41.

[4] 徐精明，曹先彬，王煦法.多态蚁群算法[J].中国科学技术大学学报，2005，35（1）：59-65.

[5] 王启明，李玮瑶.基于改进量子蚁群算法的TSP求解问题研究[J].微处理机，2015（3）：31-33.

[6] 张开碧，张洋川，万素波，等.一种改进的竞争型蚁群算法在TSP问题中的应用[J].计算机与数字工程，2016，44（3）：396-399.

[7] GAMBARDELLA L M， DORIGO M Q. A Reinforcement learning approach to the traveling salesman problem-machine learning proceedings 1995-ant[J]. Machine Learning Proceedings，2000，170（3）：252-260.

[8] ROSENKRANTZ D J， STEARNS R E， II P M L. An analysis of several heuristics for thetraveling salesman problem[J]. Siam Journal on Computing，1977，6（3）：563-581.

[9] 冯月华.一种求解TSP问题的改进蚁群算法[J].电子测试，2014（8）：38-40.

[10] YOSHIKAWA M，TERAI H.Architecture for high-speed ant colony optimization[C].IEEE International Conference on Information Reuse and Integration. IEEE，2007：1-5.endprint