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

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

2、            文献标识码：A            文章编号：1674-098X202105c-0004-05Abstract：Thisarticlechoseagraph-basedantsystemGBASoptimizationalgorithmforserial&parallelcodingachievements.Viatheco

3、mparisonamongdifferentresultsundervariousparameterconditions，theappropriatecomputingparameterswerechosen.Subsequently，aseriesofTSPinstanceswereproducedbyuseofTSPLIBtool，andthencomputedwiththeabove-mentionedtwoalgorithms.Finallysomesummarizations&analysesoftheresultsweregiven.KeyWords：Antcolonyop

4、timization;GBASalgorithm;TSP;Serialalgorithm;Parallelalgorithm1 GBAS算法介紹1992年，Berkeley国际计算机科学研究院ICSI的客座研究员意大利人MarcoDorigo提出了一种基于蚁群系统的全新启发式算法。蚁群优化算法antcolonyoptimizationalgorithms的根本思想是模拟蚁群社会依赖信息素进行通信的生物行为，用随机试探的方法求解组合优化问题。受Dorigo的启发，W.J.Gutjahr提出了一种基于图的蚁群系统1-2graph-basedantsystem，也就是GBAS算法。该GBA

5、S算法可以简单描述如下【3】。STEP0：对于n个城市的TSP问题，N=1，2，n，A=i，j|i，jN，城市间的距离矩阵D=dijnxn，为TSP图中的每一条弧i，j赋信息素痕迹初值，假设有m只蚂蚁在工作，所以蚂蚁从同一个城市i0出发。k：=1，当前最好解W=1，2，n。STEP1：外循环如果满足算法停止规那么，停止计算并且输出最好解。否那么，让蚂蚁s从起点i0出发，用Ls表示蚂蚁s行走的城市集合，初始Ls为空集，1sm。STEP2：内循环按蚂蚁1sm的顺序分别计算。当蚂蚁在城市i，假设Ls=N或l|i，lA，lLs=，完成第s只蚂蚁的计算。否那么，假设LsN且T=l|i，lA，lLs-i0

6、，那么以概率到达j，Ls=Lsj，i=j;假设LsN且T=l|i，lA，lLs-i0=，那么到达i0，Ls=Lsi0，i=i0;重复STEP2。STEP3：对1sm，假设Ls=N，按Ls中城市的顺序计算路径长度;假设LsN，路径长度是一个充分大的数。比较m只蚂蚁中的路径长度，取走最短路径的蚂蚁为t。假设fLt在STEP3中，挥发因子k对于某固定的K1，满足，并且。2 GBAS算法复杂性分析TSP问题任何一个实例由城市数n和城市间的距离矩阵D=dij|1i，jn，ij确定，因此TSP任意实例I的规模用二进制数表示为lI=2nn-1+2+log2|P|，其中为实例中所有非零数的乘积。TS

7、P问题已经被证明是NP完全【3】，因此除非PNPC，否那么不存在TSP问题的多项式时间算法。因此计算TSP问题的GBAS算法肯定不是其多项式时间算法。下面对GBAS算法的复杂性进行简单分析。首先为了讨论方便，假设GBAS算法的停止规那么是固定外循环次数为k，内循环蚂蚁数为m。对于每只蚂蚁，行进到城市i时，首先要进行1次比较，判断是否满足Ls=N或l|i，lA，lLs=，假设否，那么进行一次转移概率的计算，假设|T|表示该蚂蚁仍未到达的城市总数，那么有|T|-1次加法，|T|次除法和|T|次比较。所以每只蚂蚁走完一次全路程的计算量为：那么一次内循环m只蚂蚁总的计算量就是3mnn+1/2，完成一次

8、内循环以后，要更新信息素痕迹，这里假设挥发因子为常数，那么计算量为nn-1次乘法、n次除法和n次加法总计nn+1。因此进行k次外循环总的计算量为CGBASI=k3m/2+1nn+1=Okmn2，而lI=On2+log2|P|，当固定k，m时，算法计算量随实例规模的增大是同一个量级。3 串行算法3.1串行算法的编程实现与改进用FORTRAN90实现上述GBAS算法，以TSPLIB产生的n=44的对称TSP问题为例，该算例实际最优解为4385。但是输出上述算法计算结果时发现，计算结果非常依赖初始城市的顺序，比方在不改变城市分布的前提下，人为打乱初始当前最优解W=1，2，n中的城市顺序，发

9、现计算结果受W=1，2，n的影响很大，如表1所示。计算结果受初始W=1，2，n影响很大，并且与目标值相差很大。改变程序的关键参数m蚂蚁数、k同一个结果出现k次那么外循环结束、rho即挥发因子k，在可接受的开销下增加计算次数，仍不能使算法很好的跳出局部最优解。参考文献【3】中已经证明了GBAS算法的收敛性，因此可以认为，上述情况主要是因为算法收敛太慢，因此需要对上述GBAS算法进行适当改进。经过分析，作者认为算法依赖初始值且不能足够快的跳出局部最优，主要原因是计算每只蚂蚁的下步转移概率完全依赖信息素痕迹ijk，而ijk的计算完全取决于其初始赋值、挥发因子k以及计算过程中的当前最优解，这些参量都与

10、实例本身的信息无太大关联。这显然是不甚合理的。因此对上述GBAS算法的改进集中在对一步转移概率pij的处理方面。W.J.Gutjahr设计了一种计算一步转移概率pij的规那么【1】：3.2串行算法参数选择与结果分析本文统一使用的计算环境为：AMD2500+1.83GHzCPU;512MB内存。pij的计算使用Dorigo推荐相关参数为=1，=5，=0.5。这样GBAS算法还有两个关键参数待定：参与内循环的蚂蚁数m以及控制外循环的同一最优解出现次数k。下面先讨论k的选择。3.2.1外循环控制参数k同一最优解出现次数的选择以n=212的对称TSP为例，固定m=30，改变k值得到结果如表2所示。从上

11、面的计算可以看出，用增加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实例的计算与结果比较。计算规那么为：对于每个城

12、市数为n的实例，人为打乱城市分布顺序，然后每个实例对3个不同打乱形式的城市分布顺序计算，结果取3次计算的平均值以及其中最好的一个最短路径值，与实际最优解进行比照，计算结果见表4。从表4可以看出，该GBAS算法计算结果存在一定的波动，这反映在同样一个实例，不同初始城市顺序的计算结果存在差异最高到达10%的量级，这可能跟算法中内循环存在随机概率选择有关。但是，只要进行适当屡次计算比方本文中计算3次，就可以以很高的概率逼近甚至覆盖最优解。本文中7个实例的计算，有5个实例到达了最优解，还有一个实例偏差也仅为0.87%，计算结果还是比较令人满意的。针对城市数较大时GBAS算法平均偏差與最优值偏差相差比较

13、大，也就是算法结果波动比较大的问题，Dorigo和Gambardella提出了一种改进方法【4】，即在内循环里对每个城市i增加一个城市候选集cl，蚂蚁s行进到城市i以后，优先考虑cl集合中的城市，只有在cl中城市都没有被选择时，蚂蚁s才考虑T集合中其他城市。他们的计算结果说明，选择一个小的cl集合推荐值cl=20，能同时改进计算结果的平均值和最好值。GBAS算法计算TSP问题的CPU时间随着城市数的增加而增长很快，表4中计算428城市实例时平均计算时间就到达了1172.01s，计算量还是相当可观的。这不仅与算法本身的复杂度有关，也与本文在重复计算次数不多的情况下，为了保证计算结果的精度，而选取

14、了比较大的蚂蚁数取值m=50有关。本文第2小节对GBAS算法进行了简单的复杂性分析，算法的计算量为CGBASI=k3m/2+1nn+1=Okmn2。而TSP实例的规模为lI=On2+log2|P|，如果按照这个分析，实例规模增大时算法计算时间应该只是n2量级的增长，这跟计算结果不吻合。这是因为实际计算过程为了保证解的精度，并没有按照复杂性分析中假定的固定外循环次数的规那么来停止运算，而是采用了同一最短路径出现k次作为停止规那么。后一停止规那么在实例规模较大的时候，明显强于前面的停止规那么，因此计算量的增加要高于预期。计算结果与理论上的计算复杂性分析并不矛盾，特此说明。4 并行算法4.1并行算法的实现并行实现GBAS算法的流程如图1所示。从蚁群算法的物理本质来说，蚁群觅食过程实质上是一个并行的过程，因此反映在并行算法上来说，各进程实际上代表了各蚂蚁单独的觅食过程。虽然其它蚂蚁对于路径的选择会影响该蚂蚁的选择，但是蚂蚁的觅食过程是相对独立的。为了使算法精度足够高，同时不要浪费太多的开销在信息传递上，需要适中选择每个进程分配到的蚂蚁数。并