GBAS算法在TSP问题中的应用研究

王晨琳 黄世恩 李天涯 向宏志

摘   要：本文使用基于图的蚁群优化算法（GBAS）进行旅行商问题（TSP）的求解。首先，对GBAS算法分别进行串行、并行编程实现。其次，在串行编程情况下，通过对不同循环控制参数条件下TSP问题计算结果的比较评价，选择了合适的循环控制计算参数。最后，使用TSPLIB工具生成一系列对称TSP实例，基于所确定的计算参数，分别用上述两种算法进行计算，并对计算结果进行分析与总结。

关键词：蚁群优化  GBAS算法  TSP  串行算法  并行算法

中图分类号：TP301                                 文献标识码：A                        文章编号：1674-098X（2019）05（c）-0004-05

Abstract： This article chose a graph-based ant system （GBAS） optimization algorithm for serial & parallel coding achievements. Via the comparison among different results under various parameter conditions， the appropriate computing parameters were chosen. Subsequently， a series of TSP instances were produced by use of TSPLIB tool， and then computed with the above-mentioned two algorithms. Finally some summarizations & analyses of the results were given.

Key Words： Ant colony optimization; GBAS algorithm; TSP; Serial algorithm; Parallel algorithm

1  GBAS算法介紹

1992年，Berkeley国际计算机科学研究院（ICSI）的客座研究员意大利人Marco Dorigo提出了一种基于蚁群系统的全新启发式算法。蚁群优化算法（ant colony optimization algorithms）的基本思想是模拟蚁群社会依赖信息素进行通信的生物行为，用随机试探的方法求解组合优化问题。

受Dorigo的启发，W.J. Gutjahr提出了一种基于图的蚁群系统[1-2]（graph-based ant system），也就是GBAS算法。该GBAS算法可以简单描述如下[3]。

STEP 0：对于n个城市的TSP问题，N={1，2，…，n}， A={（i，j）|i，j∈N}，城市间的距离矩阵D=（dij）nxn，为TSP图中的每一条弧（i，j）赋信息素痕迹初值，假设有m只蚂蚁在工作，所以蚂蚁从同一个城市i0出发。k：=1，当前最好解W=（1，2，…，n）。

STEP 1：（外循环）如果满足算法停止规则，停止计算并且输出最好解。否则，让蚂蚁s从起点i0出发，用L（s）表示蚂蚁s行走的城市集合，初始L（s）为空集，1≤s≤m。

STEP 2：（内循环）按蚂蚁1≤s≤m的顺序分别计算。当蚂蚁在城市i，若L（s）=N或{l|（i，l）∈A， lL（s）}=，完成第s只蚂蚁的计算。否则，若L（s）≠N且T={l|（i，l）∈A，lL（s）}-{i0}≠，则以概率到达j，L（s）=L（s）∪{j}，i=j;若L（s）≠N且T={l|（i，l）∈A，lL（s）}-{i0}=，则到达i0，L（s）=L（s）∪{i0}，i=i0;重复STEP 2。

STEP 3：对1≤s≤m，若L（s）=N，按L（s）中城市的顺序计算路径长度;若L（s）≠N，路径长度是一个充分大的数。比较m只蚂蚁中的路径长度，取走最短路径的蚂蚁为t。若f（L（t））

在STEP 3中，挥发因子ρk对于某固定的K≥1，满足，并且。

2  GBAS算法复杂性分析

TSP问题任何一个实例由城市数n和城市间的距离矩阵D={dij|1≤i，j≤n，i≠j}确定，因此TSP任意实例I的规模（用二进制数表示）为l（I）=2n（n-1）+2+log2|P|，其中为实例中所有非零数的乘积。

TSP问题已经被证明是NP完全[3]，因此除非P∩NPC≠，否则不存在TSP问题的多项式时间算法。因此计算TSP问题的GBAS算法肯定不是其多项式时间算法。下面对GBAS算法的复杂性进行简单分析。

首先为了讨论方便，假设GBAS算法的停止规则是固定外循环次数为k，内循环蚂蚁数为m。对于每只蚂蚁，行进到城市i时，首先要进行1次比较，判断是否满足L（s）=N或{l|（i，l）∈A， lL（s）}=，若否，则进行一次转移概率的计算，若|T|表示该蚂蚁仍未到达的城市总数，则有|T|-1次加法，|T|次除法和|T|次比较。所以每只蚂蚁走完一次全路程的计算量为：

则一次内循环m只蚂蚁总的计算量就是3mn（n+1）/2，完成一次内循环以后，要更新信息素痕迹，这里假设挥发因子为常数，则计算量为n（n-1）次乘法、n次除法和n次加法总计n（n+1）。因此进行k次外循环总的计算量为CGBAS（I）=k（3m/2+1）n（n+1）=O（kmn2），而l（I）=O（n2+log2|P|），当固定k，m时，算法计算量随实例规模的增大是同一个量级。

3  串行算法

3.1 串行算法的编程实现与改进

用FORTRAN90实现上述GBAS算法，以TSPLIB产生的n=44的对称TSP问题为例，该算例实际最优解为4385。但是输出上述算法计算结果时发现，计算结果非常依赖初始城市的顺序，比如在不改变城市分布的前提下，人为打乱初始当前最优解W=（1，2，…，n）中的城市顺序，发现计算结果受W=（1，2，…，n）的影响很大，如表1所示。

计算结果受初始W=（1，2，…，n）影响很大，并且与目标值相差很大。改变程序的关键参数m（蚂蚁数）、k（同一个结果出现k次则外循环结束）、rho（即挥发因子ρk），在可接受的开销下增加计算次数，仍不能使算法很好的跳出局部最优解。参考文献[3]中已经证明了GBAS算法的收敛性，因此可以认为，上述情况主要是因为算法收敛太慢，因此需要对上述GBAS算法进行适当改进。

经过分析，作者认为算法依赖初始值且不能足够快的跳出局部最优，主要原因是计算每只蚂蚁的下步转移概率完全依赖信息素痕迹τij（k），而τij（k）的计算完全取决于其初始赋值、挥发因子ρk以及计算过程中的当前最优解，这些参量都与实例本身的信息无太大关联。这显然是不甚合理的。因此对上述GBAS算法的改进集中在对一步转移概率pij的处理方面。

W.J. Gutjahr设计了一种计算一步转移概率pij的规则[1]：

3.2 串行算法参数选择与结果分析

本文统一使用的计算环境为：AMD 2500+ 1.83GHz CPU;512MB内存。

pij的计算使用Dorigo推荐相关参数为α=1，β=5，ρ=0.5。这样GBAS算法还有两个关键参数待定：参与内循环的蚂蚁数m以及控制外循环的同一最优解出现次数k。下面先讨论k的选择。

3.2.1 外循环控制参数k（同一最优解出现次数）的选择

以n=212的对称TSP为例，固定m=30，改变k值得到结果如表2所示。

从上面的计算可以看出，用增加k的方法把计算精度从1.13%提高到0.81%，相对精度提高0.32%，但是计算时间从63.82812s到115.3906s增加了80.78%。k的增加对结果影响并不大，却会很大程度地增加计算时间。因此k的选取不宜太大，以后的计算中取k=5。

3.2.2 内循环控制参数m（蚂蚁数）的选择

以n=212的对称TSP为例，固定k=5，改变m值得到结果如表3所示。

从表3可以看出，m值的选取对计算结果影响很大，对计算时间的影响也很大。后面的计算中m值取固定值50。

通过上面一系列的计算和比较，选取参数如下：k=5，m=50。以此为基础进行TSP实例的计算与结果比较。计算规则为：对于每个城市数为n的实例，人为打乱城市分布顺序，然后每个实例对3个不同打乱形式的城市分布顺序计算，结果取3次计算的平均值以及其中最好的一个最短路径值，与实际最优解进行对比，计算结果见表4。

从表4可以看出，该GBAS算法计算结果存在一定的波动，这反映在同样一个实例，不同初始城市顺序的计算结果存在差异（最高达到10%的量级），这可能跟算法中内循环存在随机概率选择有关。但是，只要进行适当多次计算（比如本文中计算3次），就可以以很高的概率逼近甚至覆盖最优解。本文中7个实例的计算，有5个实例达到了最优解，还有一个实例偏差也仅为0.87%，计算结果还是比较令人满意的。

针对城市数较大时GBAS算法平均偏差與最优值偏差相差比较大，也就是算法结果波动比较大的问题，Dorigo和Gambardella提出了一种改进方法[4]，即在内循环里对每个城市i增加一个城市候选集cl，蚂蚁s行进到城市i以后，优先考虑cl集合中的城市，只有在cl中城市都没有被选择时，蚂蚁s才考虑T集合中其他城市。他们的计算结果表明，选择一个小的cl集合（推荐值cl=20），能同时改进计算结果的平均值和最好值。

GBAS算法计算TSP问题的CPU时间随着城市数的增加而增长很快，表4中计算428城市实例时平均计算时间就达到了1172.01s，计算量还是相当可观的。这不仅与算法本身的复杂度有关，也与本文在重复计算次数不多的情况下，为了保证计算结果的精度，而选取了比较大的蚂蚁数取值（m=50）有关。本文第2小节对GBAS算法进行了简单的复杂性分析，算法的计算量为CGBAS（I）=k（3m/2+1）n（n+1）=O（kmn2）。而TSP实例的规模为l（I）=O（n2+log2|P|），如果按照这个分析，实例规模增大时算法计算时间应该只是n2量级的增长，这跟计算结果不吻合。这是因为实际计算过程为了保证解的精度，并没有按照复杂性分析中假定的固定外循环次数的规则来停止运算，而是采用了同一最短路径出现k次作为停止规则。后一停止规则在实例规模较大的时候，明显强于前面的停止规则，因此计算量的增加要高于预期。计算结果与理论上的计算复杂性分析并不矛盾，特此说明。

4  并行算法

4.1 并行算法的实现

并行实现GBAS算法的流程如图1所示。从蚁群算法的物理本质来说，蚁群觅食过程实质上是一个并行的过程，因此反映在并行算法上来说，各进程实际上代表了各蚂蚁单独的觅食过程。虽然其它蚂蚁对于路径的选择会影响该蚂蚁的选择，但是蚂蚁的觅食过程是相对独立的。为了使算法精度足够高，同时不要浪费太多的开销在信息传递上，需要适当选择每个进程分配到的蚂蚁数。

并行算法的参数α=1，β=5，ρ=0.5与串行算法一致。在串行算法的实现中，我们已经对蚂蚁数的选择进行了讨论，因此这里以上面讨论的结果为依据，为了保证每个进程计算的精度，使它分配到的蚂蚁数不少于min_ants。并行环境下对各进程蚂蚁数进行了重新分配，每个进程的蚂蚁数为max（min_ants，m/n），其中m是总的蚂蚁数，n是进程总数。这样的蚂蚁数分配既保证了各进程计算量的一致，也保证了每个进程蚂蚁数不至于太少而影响其计算精度。程序中实际选取的总蚂蚁数为m=100。