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。