GBAS算法在TSP問題中的應(yīng)用研究

1、GBAS算法在TSP問題中的應(yīng)用研究摘  要：本文使用基于圖的蟻群優(yōu)化算法GBAS進行旅行商問題TSP的求解。首先，對GBAS算法分別進行串行、并行編程實現(xiàn)。其次，在串行編程情況下，通過對不同循環(huán)控制參數(shù)條件下TSP問題計算結(jié)果的比較評價，選擇了適宜的循環(huán)控制計算參數(shù)。最后，使用TSPLIB工具生成一系列對稱TSP實例，基于所確定的計算參數(shù)，分別用上述兩種算法進行計算，并對計算結(jié)果進行分析與總結(jié)。關(guān)鍵詞：蟻群優(yōu)化 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國際計算機科學(xué)研究院ICSI的客座研究員意大利人MarcoDorigo提出了一種基于蟻群系統(tǒng)的全新啟發(fā)式算法。蟻群優(yōu)化算法antcolonyoptimizationalgorithms的根本思想是模擬蟻群社會依賴信息素進行通信的生物行為，用隨機試探的方法求解組合優(yōu)化問題。受Dorigo的啟發(fā)，W.J.Gutjahr提出了一種基于圖的蟻群系統(tǒng)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賦信息素痕跡初值，假設(shè)有m只螞蟻在工作，所以螞蟻從同一個城市i0出發(fā)。k：=1，當(dāng)前最好解W=1，2，n。STEP1：外循環(huán)如果滿足算法停止規(guī)那么，停止計算并且輸出最好解。否那么，讓螞蟻s從起點i0出發(fā)，用Ls表示螞蟻s行走的城市集合，初始Ls為空集，1sm。STEP2：內(nèi)循環(huán)按螞蟻1sm的順序分別計算。當(dāng)螞蟻在城市i，假設(shè)Ls=N或l|i，lA，lLs=，完成第s只螞蟻的計算。否那么，假設(shè)LsN且T=l|i，lA，lLs-i0

6、，那么以概率到達j，Ls=Lsj，i=j;假設(shè)LsN且T=l|i，lA，lLs-i0=，那么到達i0，Ls=Lsi0，i=i0;重復(fù)STEP2。STEP3：對1sm，假設(shè)Ls=N，按Ls中城市的順序計算路徑長度;假設(shè)LsN，路徑長度是一個充分大的數(shù)。比較m只螞蟻中的路徑長度，取走最短路徑的螞蟻為t。假設(shè)fLt在STEP3中，揮發(fā)因子k對于某固定的K1，滿足，并且。2 GBAS算法復(fù)雜性分析TSP問題任何一個實例由城市數(shù)n和城市間的距離矩陣D=dij|1i，jn，ij確定，因此TSP任意實例I的規(guī)模用二進制數(shù)表示為lI=2nn-1+2+log2|P|，其中為實例中所有非零數(shù)的乘積。TS

7、P問題已經(jīng)被證明是NP完全【3】，因此除非PNPC，否那么不存在TSP問題的多項式時間算法。因此計算TSP問題的GBAS算法肯定不是其多項式時間算法。下面對GBAS算法的復(fù)雜性進行簡單分析。首先為了討論方便，假設(shè)GBAS算法的停止規(guī)那么是固定外循環(huán)次數(shù)為k，內(nèi)循環(huán)螞蟻數(shù)為m。對于每只螞蟻，行進到城市i時，首先要進行1次比較，判斷是否滿足Ls=N或l|i，lA，lLs=，假設(shè)否，那么進行一次轉(zhuǎn)移概率的計算，假設(shè)|T|表示該螞蟻仍未到達的城市總數(shù)，那么有|T|-1次加法，|T|次除法和|T|次比較。所以每只螞蟻走完一次全路程的計算量為：那么一次內(nèi)循環(huán)m只螞蟻總的計算量就是3mnn+1/2，完成一次

8、內(nèi)循環(huán)以后，要更新信息素痕跡，這里假設(shè)揮發(fā)因子為常數(shù)，那么計算量為nn-1次乘法、n次除法和n次加法總計nn+1。因此進行k次外循環(huán)總的計算量為CGBASI=k3m/2+1nn+1=Okmn2，而lI=On2+log2|P|，當(dāng)固定k，m時，算法計算量隨實例規(guī)模的增大是同一個量級。3 串行算法3.1串行算法的編程實現(xiàn)與改進用FORTRAN90實現(xiàn)上述GBAS算法，以TSPLIB產(chǎn)生的n=44的對稱TSP問題為例，該算例實際最優(yōu)解為4385。但是輸出上述算法計算結(jié)果時發(fā)現(xiàn)，計算結(jié)果非常依賴初始城市的順序，比方在不改變城市分布的前提下，人為打亂初始當(dāng)前最優(yōu)解W=1，2，n中的城市順序，發(fā)

9、現(xiàn)計算結(jié)果受W=1，2，n的影響很大，如表1所示。計算結(jié)果受初始W=1，2，n影響很大，并且與目標值相差很大。改變程序的關(guān)鍵參數(shù)m螞蟻數(shù)、k同一個結(jié)果出現(xiàn)k次那么外循環(huán)結(jié)束、rho即揮發(fā)因子k，在可接受的開銷下增加計算次數(shù)，仍不能使算法很好的跳出局部最優(yōu)解。參考文獻【3】中已經(jīng)證明了GBAS算法的收斂性，因此可以認為，上述情況主要是因為算法收斂太慢，因此需要對上述GBAS算法進行適當(dāng)改進。經(jīng)過分析，作者認為算法依賴初始值且不能足夠快的跳出局部最優(yōu)，主要原因是計算每只螞蟻的下步轉(zhuǎn)移概率完全依賴信息素痕跡ijk，而ijk的計算完全取決于其初始賦值、揮發(fā)因子k以及計算過程中的當(dāng)前最優(yōu)解，這些參量都與

10、實例本身的信息無太大關(guān)聯(lián)。這顯然是不甚合理的。因此對上述GBAS算法的改進集中在對一步轉(zhuǎn)移概率pij的處理方面。W.J.Gutjahr設(shè)計了一種計算一步轉(zhuǎn)移概率pij的規(guī)那么【1】：3.2串行算法參數(shù)選擇與結(jié)果分析本文統(tǒng)一使用的計算環(huán)境為：AMD2500+1.83GHzCPU;512MB內(nèi)存。pij的計算使用Dorigo推薦相關(guān)參數(shù)為=1，=5，=0.5。這樣GBAS算法還有兩個關(guān)鍵參數(shù)待定：參與內(nèi)循環(huán)的螞蟻數(shù)m以及控制外循環(huán)的同一最優(yōu)解出現(xiàn)次數(shù)k。下面先討論k的選擇。3.2.1外循環(huán)控制參數(shù)k同一最優(yōu)解出現(xiàn)次數(shù)的選擇以n=212的對稱TSP為例，固定m=30，改變k值得到結(jié)果如表2所示。從上

11、面的計算可以看出，用增加k的方法把計算精度從1.13%提高到0.81%，相對精度提高0.32%，但是計算時間從63.82812s到115.3906s增加了80.78%。k的增加對結(jié)果影響并不大，卻會很大程度地增加計算時間。因此k的選取不宜太大，以后的計算中取k=5。3.2.2內(nèi)循環(huán)控制參數(shù)m螞蟻數(shù)的選擇以n=212的對稱TSP為例，固定k=5，改變m值得到結(jié)果如表3所示。從表3可以看出，m值的選取對計算結(jié)果影響很大，對計算時間的影響也很大。后面的計算中m值取固定值50。通過上面一系列的計算和比較，選取參數(shù)如下：k=5，m=50。以此為根底進行TSP實例的計算與結(jié)果比較。計算規(guī)那么為：對于每個城

12、市數(shù)為n的實例，人為打亂城市分布順序，然后每個實例對3個不同打亂形式的城市分布順序計算，結(jié)果取3次計算的平均值以及其中最好的一個最短路徑值，與實際最優(yōu)解進行比照，計算結(jié)果見表4。從表4可以看出，該GBAS算法計算結(jié)果存在一定的波動，這反映在同樣一個實例，不同初始城市順序的計算結(jié)果存在差異最高到達10%的量級，這可能跟算法中內(nèi)循環(huán)存在隨機概率選擇有關(guān)。但是，只要進行適當(dāng)屢次計算比方本文中計算3次，就可以以很高的概率逼近甚至覆蓋最優(yōu)解。本文中7個實例的計算，有5個實例到達了最優(yōu)解，還有一個實例偏差也僅為0.87%，計算結(jié)果還是比較令人滿意的。針對城市數(shù)較大時GBAS算法平均偏差與最優(yōu)值偏差相差比較

13、大，也就是算法結(jié)果波動比較大的問題，Dorigo和Gambardella提出了一種改進方法【4】，即在內(nèi)循環(huán)里對每個城市i增加一個城市候選集cl，螞蟻s行進到城市i以后，優(yōu)先考慮cl集合中的城市，只有在cl中城市都沒有被選擇時，螞蟻s才考慮T集合中其他城市。他們的計算結(jié)果說明，選擇一個小的cl集合推薦值cl=20，能同時改進計算結(jié)果的平均值和最好值。GBAS算法計算TSP問題的CPU時間隨著城市數(shù)的增加而增長很快，表4中計算428城市實例時平均計算時間就到達了1172.01s，計算量還是相當(dāng)可觀的。這不僅與算法本身的復(fù)雜度有關(guān)，也與本文在重復(fù)計算次數(shù)不多的情況下，為了保證計算結(jié)果的精度，而選取

14、了比較大的螞蟻數(shù)取值m=50有關(guān)。本文第2小節(jié)對GBAS算法進行了簡單的復(fù)雜性分析，算法的計算量為CGBASI=k3m/2+1nn+1=Okmn2。而TSP實例的規(guī)模為lI=On2+log2|P|，如果按照這個分析，實例規(guī)模增大時算法計算時間應(yīng)該只是n2量級的增長，這跟計算結(jié)果不吻合。這是因為實際計算過程為了保證解的精度，并沒有按照復(fù)雜性分析中假定的固定外循環(huán)次數(shù)的規(guī)那么來停止運算，而是采用了同一最短路徑出現(xiàn)k次作為停止規(guī)那么。后一停止規(guī)那么在實例規(guī)模較大的時候，明顯強于前面的停止規(guī)那么，因此計算量的增加要高于預(yù)期。計算結(jié)果與理論上的計算復(fù)雜性分析并不矛盾，特此說明。4 并行算法4.1并行算法的實現(xiàn)并行實現(xiàn)GBAS算法的流程如圖1所示。從蟻群算法的物理本質(zhì)來說，蟻群覓食過程實質(zhì)上是一個并行的過程，因此反映在并行算法上來說，各進程實際上代表了各螞蟻單獨的覓食過程。雖然其它螞蟻對于路徑的選擇會影響該螞蟻的選擇，但是螞蟻的覓食過程是相對獨立的。為了使算法精度足夠高，同時不要浪費太多的開銷在信息傳遞上，需要適中選擇每個進程分配到的螞蟻數(shù)。并