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所示。從蟻群算法的物理本質來說，蟻群覓食過程實質上是一個并行的過程，因此反映在并行算法上來說，各進程實際上代表了各螞蟻單獨的覓食過程。雖然其它螞蟻對于路徑的選擇會影響該螞蟻的選擇，但是螞蟻的覓食過程是相對獨立的。為了使算法精度足夠高，同時不要浪費太多的開銷在信息傳遞上，需要適中選擇每個進程分配到的螞蟻數。并