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

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

摘? ?要：本文使用基于圖的蟻群優(yōu)化算法（GBAS）進(jìn)行旅行商問(wèn)題（TSP）的求解。首先，對(duì)GBAS算法分別進(jìn)行串行、并行編程實(shí)現(xiàn)。其次，在串行編程情況下，通過(guò)對(duì)不同循環(huán)控制參數(shù)條件下TSP問(wèn)題計(jì)算結(jié)果的比較評(píng)價(jià)，選擇了合適的循環(huán)控制計(jì)算參數(shù)。最后，使用TSPLIB工具生成一系列對(duì)稱TSP實(shí)例，基于所確定的計(jì)算參數(shù)，分別用上述兩種算法進(jìn)行計(jì)算，并對(duì)計(jì)算結(jié)果進(jìn)行分析與總結(jié)。

關(guān)鍵詞：蟻群優(yōu)化? GBAS算法? TSP? 串行算法? 并行算法

中圖分類號(hào)：TP301? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? ? ? ? ? ? ? ? ? 文章編號(hào)：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國(guó)際計(jì)算機(jī)科學(xué)研究院（ICSI）的客座研究員意大利人Marco Dorigo提出了一種基于蟻群系統(tǒng)的全新啟發(fā)式算法。蟻群優(yōu)化算法（ant colony optimization algorithms）的基本思想是模擬蟻群社會(huì)依賴信息素進(jìn)行通信的生物行為，用隨機(jī)試探的方法求解組合優(yōu)化問(wèn)題。

受Dorigo的啟發(fā)，W.J. Gutjahr提出了一種基于圖的蟻群系統(tǒng)[1-2]（graph-based ant system），也就是GBAS算法。該GBAS算法可以簡(jiǎn)單描述如下[3]。

STEP 0：對(duì)于n個(gè)城市的TSP問(wèn)題，N={1，2，…，n}， A={（i，j）|i，j∈N}，城市間的距離矩陣D=（dij）nxn，為T(mén)SP圖中的每一條?。╥，j）賦信息素痕跡初值，假設(shè)有m只螞蟻在工作，所以螞蟻從同一個(gè)城市i0出發(fā)。k：=1，當(dāng)前最好解W=（1，2，…，n）。

STEP 1：（外循環(huán)）如果滿足算法停止規(guī)則，停止計(jì)算并且輸出最好解。否則，讓螞蟻s從起點(diǎn)i0出發(fā)，用L（s）表示螞蟻s行走的城市集合，初始L（s）為空集，1≤s≤m。

STEP 2：（內(nèi)循環(huán)）按螞蟻1≤s≤m的順序分別計(jì)算。當(dāng)螞蟻在城市i，若L（s）=N或{l|（i，l）∈A， lL（s）}=，完成第s只螞蟻的計(jì)算。否則，若L（s）≠N且T={l|（i，l）∈A，lL（s）}-{i0}≠，則以概率到達(dá)j，L（s）=L（s）∪{j}，i=j;若L（s）≠N且T={l|（i，l）∈A，lL（s）}-{i0}=，則到達(dá)i0，L（s）=L（s）∪{i0}，i=i0;重復(fù)STEP 2。

STEP 3：對(duì)1≤s≤m，若L（s）=N，按L（s）中城市的順序計(jì)算路徑長(zhǎng)度;若L（s）≠N，路徑長(zhǎng)度是一個(gè)充分大的數(shù)。比較m只螞蟻中的路徑長(zhǎng)度，取走最短路徑的螞蟻為t。若f（L（t））

在STEP 3中，揮發(fā)因子ρk對(duì)于某固定的K≥1，滿足，并且。

2? GBAS算法復(fù)雜性分析

TSP問(wèn)題任何一個(gè)實(shí)例由城市數(shù)n和城市間的距離矩陣D={dij|1≤i，j≤n，i≠j}確定，因此TSP任意實(shí)例I的規(guī)模（用二進(jìn)制數(shù)表示）為l（I）=2n（n-1）+2+log2|P|，其中為實(shí)例中所有非零數(shù)的乘積。

TSP問(wèn)題已經(jīng)被證明是NP完全[3]，因此除非P∩NPC≠，否則不存在TSP問(wèn)題的多項(xiàng)式時(shí)間算法。因此計(jì)算TSP問(wèn)題的GBAS算法肯定不是其多項(xiàng)式時(shí)間算法。下面對(duì)GBAS算法的復(fù)雜性進(jìn)行簡(jiǎn)單分析。

首先為了討論方便，假設(shè)GBAS算法的停止規(guī)則是固定外循環(huán)次數(shù)為k，內(nèi)循環(huán)螞蟻數(shù)為m。對(duì)于每只螞蟻，行進(jìn)到城市i時(shí)，首先要進(jìn)行1次比較，判斷是否滿足L（s）=N或{l|（i，l）∈A， lL（s）}=，若否，則進(jìn)行一次轉(zhuǎn)移概率的計(jì)算，若|T|表示該螞蟻仍未到達(dá)的城市總數(shù)，則有|T|-1次加法，|T|次除法和|T|次比較。所以每只螞蟻?zhàn)咄暌淮稳烦痰挠?jì)算量為：

則一次內(nèi)循環(huán)m只螞蟻總的計(jì)算量就是3mn（n+1）/2，完成一次內(nèi)循環(huán)以后，要更新信息素痕跡，這里假設(shè)揮發(fā)因子為常數(shù)，則計(jì)算量為n（n-1）次乘法、n次除法和n次加法總計(jì)n（n+1）。因此進(jìn)行k次外循環(huán)總的計(jì)算量為CGBAS（I）=k（3m/2+1）n（n+1）=O（kmn2），而l（I）=O（n2+log2|P|），當(dāng)固定k，m時(shí)，算法計(jì)算量隨實(shí)例規(guī)模的增大是同一個(gè)量級(jí)。

3? 串行算法

3.1 串行算法的編程實(shí)現(xiàn)與改進(jìn)

用FORTRAN90實(shí)現(xiàn)上述GBAS算法，以TSPLIB產(chǎn)生的n=44的對(duì)稱TSP問(wèn)題為例，該算例實(shí)際最優(yōu)解為4385。但是輸出上述算法計(jì)算結(jié)果時(shí)發(fā)現(xiàn)，計(jì)算結(jié)果非常依賴初始城市的順序，比如在不改變城市分布的前提下，人為打亂初始當(dāng)前最優(yōu)解W=（1，2，…，n）中的城市順序，發(fā)現(xiàn)計(jì)算結(jié)果受W=（1，2，…，n）的影響很大，如表1所示。

計(jì)算結(jié)果受初始W=（1，2，…，n）影響很大，并且與目標(biāo)值相差很大。改變程序的關(guān)鍵參數(shù)m（螞蟻數(shù)）、k（同一個(gè)結(jié)果出現(xiàn)k次則外循環(huán)結(jié)束）、rho（即揮發(fā)因子ρk），在可接受的開(kāi)銷下增加計(jì)算次數(shù)，仍不能使算法很好的跳出局部最優(yōu)解。參考文獻(xiàn)[3]中已經(jīng)證明了GBAS算法的收斂性，因此可以認(rèn)為，上述情況主要是因?yàn)樗惴ㄊ諗刻?，因此需要?duì)上述GBAS算法進(jìn)行適當(dāng)改進(jìn)。

經(jīng)過(guò)分析，作者認(rèn)為算法依賴初始值且不能足夠快的跳出局部最優(yōu)，主要原因是計(jì)算每只螞蟻的下步轉(zhuǎn)移概率完全依賴信息素痕跡τij（k），而τij（k）的計(jì)算完全取決于其初始賦值、揮發(fā)因子ρk以及計(jì)算過(guò)程中的當(dāng)前最優(yōu)解，這些參量都與實(shí)例本身的信息無(wú)太大關(guān)聯(lián)。這顯然是不甚合理的。因此對(duì)上述GBAS算法的改進(jìn)集中在對(duì)一步轉(zhuǎn)移概率pij的處理方面。

W.J. Gutjahr設(shè)計(jì)了一種計(jì)算一步轉(zhuǎn)移概率pij的規(guī)則[1]：

3.2 串行算法參數(shù)選擇與結(jié)果分析

本文統(tǒng)一使用的計(jì)算環(huán)境為：AMD 2500+ 1.83GHz CPU;512MB內(nèi)存。

pij的計(jì)算使用Dorigo推薦相關(guān)參數(shù)為α=1，β=5，ρ=0.5。這樣GBAS算法還有兩個(gè)關(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的對(duì)稱TSP為例，固定m=30，改變k值得到結(jié)果如表2所示。

從上面的計(jì)算可以看出，用增加k的方法把計(jì)算精度從1.13%提高到0.81%，相對(duì)精度提高0.32%，但是計(jì)算時(shí)間從63.82812s到115.3906s增加了80.78%。k的增加對(duì)結(jié)果影響并不大，卻會(huì)很大程度地增加計(jì)算時(shí)間。因此k的選取不宜太大，以后的計(jì)算中取k=5。

3.2.2 內(nèi)循環(huán)控制參數(shù)m（螞蟻數(shù)）的選擇

以n=212的對(duì)稱TSP為例，固定k=5，改變m值得到結(jié)果如表3所示。

從表3可以看出，m值的選取對(duì)計(jì)算結(jié)果影響很大，對(duì)計(jì)算時(shí)間的影響也很大。后面的計(jì)算中m值取固定值50。

通過(guò)上面一系列的計(jì)算和比較，選取參數(shù)如下：k=5，m=50。以此為基礎(chǔ)進(jìn)行TSP實(shí)例的計(jì)算與結(jié)果比較。計(jì)算規(guī)則為：對(duì)于每個(gè)城市數(shù)為n的實(shí)例，人為打亂城市分布順序，然后每個(gè)實(shí)例對(duì)3個(gè)不同打亂形式的城市分布順序計(jì)算，結(jié)果取3次計(jì)算的平均值以及其中最好的一個(gè)最短路徑值，與實(shí)際最優(yōu)解進(jìn)行對(duì)比，計(jì)算結(jié)果見(jiàn)表4。

從表4可以看出，該GBAS算法計(jì)算結(jié)果存在一定的波動(dòng)，這反映在同樣一個(gè)實(shí)例，不同初始城市順序的計(jì)算結(jié)果存在差異（最高達(dá)到10%的量級(jí)），這可能跟算法中內(nèi)循環(huán)存在隨機(jī)概率選擇有關(guān)。但是，只要進(jìn)行適當(dāng)多次計(jì)算（比如本文中計(jì)算3次），就可以以很高的概率逼近甚至覆蓋最優(yōu)解。本文中7個(gè)實(shí)例的計(jì)算，有5個(gè)實(shí)例達(dá)到了最優(yōu)解，還有一個(gè)實(shí)例偏差也僅為0.87%，計(jì)算結(jié)果還是比較令人滿意的。

針對(duì)城市數(shù)較大時(shí)GBAS算法平均偏差與最優(yōu)值偏差相差比較大，也就是算法結(jié)果波動(dòng)比較大的問(wèn)題，Dorigo和Gambardella提出了一種改進(jìn)方法[4]，即在內(nèi)循環(huán)里對(duì)每個(gè)城市i增加一個(gè)城市候選集cl，螞蟻s行進(jìn)到城市i以后，優(yōu)先考慮cl集合中的城市，只有在cl中城市都沒(méi)有被選擇時(shí)，螞蟻s才考慮T集合中其他城市。他們的計(jì)算結(jié)果表明，選擇一個(gè)小的cl集合（推薦值cl=20），能同時(shí)改進(jìn)計(jì)算結(jié)果的平均值和最好值。

GBAS算法計(jì)算TSP問(wèn)題的CPU時(shí)間隨著城市數(shù)的增加而增長(zhǎng)很快，表4中計(jì)算428城市實(shí)例時(shí)平均計(jì)算時(shí)間就達(dá)到了1172.01s，計(jì)算量還是相當(dāng)可觀的。這不僅與算法本身的復(fù)雜度有關(guān)，也與本文在重復(fù)計(jì)算次數(shù)不多的情況下，為了保證計(jì)算結(jié)果的精度，而選取了比較大的螞蟻數(shù)取值（m=50）有關(guān)。本文第2小節(jié)對(duì)GBAS算法進(jìn)行了簡(jiǎn)單的復(fù)雜性分析，算法的計(jì)算量為CGBAS（I）=k（3m/2+1）n（n+1）=O（kmn2）。而TSP實(shí)例的規(guī)模為l（I）=O（n2+log2|P|），如果按照這個(gè)分析，實(shí)例規(guī)模增大時(shí)算法計(jì)算時(shí)間應(yīng)該只是n2量級(jí)的增長(zhǎng)，這跟計(jì)算結(jié)果不吻合。這是因?yàn)閷?shí)際計(jì)算過(guò)程為了保證解的精度，并沒(méi)有按照復(fù)雜性分析中假定的固定外循環(huán)次數(shù)的規(guī)則來(lái)停止運(yùn)算，而是采用了同一最短路徑出現(xiàn)k次作為停止規(guī)則。后一停止規(guī)則在實(shí)例規(guī)模較大的時(shí)候，明顯強(qiáng)于前面的停止規(guī)則，因此計(jì)算量的增加要高于預(yù)期。計(jì)算結(jié)果與理論上的計(jì)算復(fù)雜性分析并不矛盾，特此說(shuō)明。

4? 并行算法

4.1 并行算法的實(shí)現(xiàn)

并行實(shí)現(xiàn)GBAS算法的流程如圖1所示。從蟻群算法的物理本質(zhì)來(lái)說(shuō)，蟻群覓食過(guò)程實(shí)質(zhì)上是一個(gè)并行的過(guò)程，因此反映在并行算法上來(lái)說(shuō)，各進(jìn)程實(shí)際上代表了各螞蟻單獨(dú)的覓食過(guò)程。雖然其它螞蟻對(duì)于路徑的選擇會(huì)影響該螞蟻的選擇，但是螞蟻的覓食過(guò)程是相對(duì)獨(dú)立的。為了使算法精度足夠高，同時(shí)不要浪費(fèi)太多的開(kāi)銷在信息傳遞上，需要適當(dāng)選擇每個(gè)進(jìn)程分配到的螞蟻數(shù)。

并行算法的參數(shù)α=1，β=5，ρ=0.5與串行算法一致。在串行算法的實(shí)現(xiàn)中，我們已經(jīng)對(duì)螞蟻數(shù)的選擇進(jìn)行了討論，因此這里以上面討論的結(jié)果為依據(jù)，為了保證每個(gè)進(jìn)程計(jì)算的精度，使它分配到的螞蟻數(shù)不少于min_ants。并行環(huán)境下對(duì)各進(jìn)程螞蟻數(shù)進(jìn)行了重新分配，每個(gè)進(jìn)程的螞蟻數(shù)為max（min_ants，m/n），其中m是總的螞蟻數(shù)，n是進(jìn)程總數(shù)。這樣的螞蟻數(shù)分配既保證了各進(jìn)程計(jì)算量的一致，也保證了每個(gè)進(jìn)程螞蟻數(shù)不至于太少而影響其計(jì)算精度。程序中實(shí)際選取的總螞蟻數(shù)為m=100。