王晨琳 黃世恩 李天涯 向宏志
摘? ?要:本文使用基于圖的蟻群優(yōu)化算法(GBAS)進(jìn)行旅行商問題(TSP)的求解。首先,對GBAS算法分別進(jìn)行串行、并行編程實(shí)現(xiàn)。其次,在串行編程情況下,通過對不同循環(huán)控制參數(shù)條件下TSP問題計算結(jié)果的比較評價,選擇了合適的循環(huán)控制計算參數(shù)。最后,使用TSPLIB工具生成一系列對稱TSP實(shí)例,基于所確定的計算參數(shù),分別用上述兩種算法進(jìn)行計算,并對計算結(jié)果進(jìn)行分析與總結(jié)。
關(guān)鍵詞:蟻群優(yōu)化? GBAS算法? TSP? 串行算法? 并行算法
中圖分類號:TP301? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識碼: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國際計算機(jī)科學(xué)研究院(ICSI)的客座研究員意大利人Marco Dorigo提出了一種基于蟻群系統(tǒng)的全新啟發(fā)式算法。蟻群優(yōu)化算法(ant colony optimization algorithms)的基本思想是模擬蟻群社會依賴信息素進(jìn)行通信的生物行為,用隨機(jī)試探的方法求解組合優(yōu)化問題。
受Dorigo的啟發(fā),W.J. Gutjahr提出了一種基于圖的蟻群系統(tǒng)[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圖中的每一條?。╥,j)賦信息素痕跡初值,假設(shè)有m只螞蟻在工作,所以螞蟻從同一個城市i0出發(fā)。k:=1,當(dāng)前最好解W=(1,2,…,n)。
STEP 1:(外循環(huán))如果滿足算法停止規(guī)則,停止計算并且輸出最好解。否則,讓螞蟻s從起點(diǎn)i0出發(fā),用L(s)表示螞蟻s行走的城市集合,初始L(s)為空集,1≤s≤m。
STEP 2:(內(nèi)循環(huán))按螞蟻1≤s≤m的順序分別計算。當(dāng)螞蟻在城市i,若L(s)=N或{l|(i,l)∈A, lL(s)}=,完成第s只螞蟻的計算。否則,若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:對1≤s≤m,若L(s)=N,按L(s)中城市的順序計算路徑長度;若L(s)≠N,路徑長度是一個充分大的數(shù)。比較m只螞蟻中的路徑長度,取走最短路徑的螞蟻為t。若f(L(t)) 在STEP 3中,揮發(fā)因子ρk對于某固定的K≥1,滿足,并且。 2? GBAS算法復(fù)雜性分析 TSP問題任何一個實(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問題已經(jīng)被證明是NP完全[3],因此除非P∩NPC≠,否則不存在TSP問題的多項式時間算法。因此計算TSP問題的GBAS算法肯定不是其多項式時間算法。下面對GBAS算法的復(fù)雜性進(jìn)行簡單分析。 首先為了討論方便,假設(shè)GBAS算法的停止規(guī)則是固定外循環(huán)次數(shù)為k,內(nèi)循環(huán)螞蟻數(shù)為m。對于每只螞蟻,行進(jìn)到城市i時,首先要進(jìn)行1次比較,判斷是否滿足L(s)=N或{l|(i,l)∈A, lL(s)}=,若否,則進(jìn)行一次轉(zhuǎn)移概率的計算,若|T|表示該螞蟻仍未到達(dá)的城市總數(shù),則有|T|-1次加法,|T|次除法和|T|次比較。所以每只螞蟻?zhàn)咄暌淮稳烦痰挠嬎懔繛椋?/p> 則一次內(nèi)循環(huán)m只螞蟻總的計算量就是3mn(n+1)/2,完成一次內(nèi)循環(huán)以后,要更新信息素痕跡,這里假設(shè)揮發(fā)因子為常數(shù),則計算量為n(n-1)次乘法、n次除法和n次加法總計n(n+1)。因此進(jìn)行k次外循環(huán)總的計算量為CGBAS(I)=k(3m/2+1)n(n+1)=O(kmn2),而l(I)=O(n2+log2|P|),當(dāng)固定k,m時,算法計算量隨實(shí)例規(guī)模的增大是同一個量級。 3? 串行算法 3.1 串行算法的編程實(shí)現(xiàn)與改進(jìn) 用FORTRAN90實(shí)現(xiàn)上述GBAS算法,以TSPLIB產(chǎn)生的n=44的對稱TSP問題為例,該算例實(shí)際最優(yōu)解為4385。但是輸出上述算法計算結(jié)果時發(fā)現(xiàn),計算結(jié)果非常依賴初始城市的順序,比如在不改變城市分布的前提下,人為打亂初始當(dāng)前最優(yōu)解W=(1,2,…,n)中的城市順序,發(fā)現(xiàn)計算結(jié)果受W=(1,2,…,n)的影響很大,如表1所示。 計算結(jié)果受初始W=(1,2,…,n)影響很大,并且與目標(biāo)值相差很大。改變程序的關(guān)鍵參數(shù)m(螞蟻數(shù))、k(同一個結(jié)果出現(xiàn)k次則外循環(huán)結(jié)束)、rho(即揮發(fā)因子ρk),在可接受的開銷下增加計算次數(shù),仍不能使算法很好的跳出局部最優(yōu)解。參考文獻(xiàn)[3]中已經(jīng)證明了GBAS算法的收斂性,因此可以認(rèn)為,上述情況主要是因為算法收斂太慢,因此需要對上述GBAS算法進(jìn)行適當(dāng)改進(jìn)。 經(jīng)過分析,作者認(rèn)為算法依賴初始值且不能足夠快的跳出局部最優(yōu),主要原因是計算每只螞蟻的下步轉(zhuǎn)移概率完全依賴信息素痕跡τij(k),而τij(k)的計算完全取決于其初始賦值、揮發(fā)因子ρk以及計算過程中的當(dāng)前最優(yōu)解,這些參量都與實(shí)例本身的信息無太大關(guān)聯(lián)。這顯然是不甚合理的。因此對上述GBAS算法的改進(jìn)集中在對一步轉(zhuǎn)移概率pij的處理方面。 W.J. Gutjahr設(shè)計了一種計算一步轉(zhuǎn)移概率pij的規(guī)則[1]: 3.2 串行算法參數(shù)選擇與結(jié)果分析 本文統(tǒng)一使用的計算環(huán)境為:AMD 2500+ 1.83GHz CPU;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所示。 從上面的計算可以看出,用增加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。以此為基礎(chǔ)進(jìn)行TSP實(shí)例的計算與結(jié)果比較。計算規(guī)則為:對于每個城市數(shù)為n的實(shí)例,人為打亂城市分布順序,然后每個實(shí)例對3個不同打亂形式的城市分布順序計算,結(jié)果取3次計算的平均值以及其中最好的一個最短路徑值,與實(shí)際最優(yōu)解進(jìn)行對比,計算結(jié)果見表4。 從表4可以看出,該GBAS算法計算結(jié)果存在一定的波動,這反映在同樣一個實(shí)例,不同初始城市順序的計算結(jié)果存在差異(最高達(dá)到10%的量級),這可能跟算法中內(nèi)循環(huán)存在隨機(jī)概率選擇有關(guān)。但是,只要進(jìn)行適當(dāng)多次計算(比如本文中計算3次),就可以以很高的概率逼近甚至覆蓋最優(yōu)解。本文中7個實(shí)例的計算,有5個實(shí)例達(dá)到了最優(yōu)解,還有一個實(shí)例偏差也僅為0.87%,計算結(jié)果還是比較令人滿意的。 針對城市數(shù)較大時GBAS算法平均偏差與最優(yōu)值偏差相差比較大,也就是算法結(jié)果波動比較大的問題,Dorigo和Gambardella提出了一種改進(jìn)方法[4],即在內(nèi)循環(huán)里對每個城市i增加一個城市候選集cl,螞蟻s行進(jìn)到城市i以后,優(yōu)先考慮cl集合中的城市,只有在cl中城市都沒有被選擇時,螞蟻s才考慮T集合中其他城市。他們的計算結(jié)果表明,選擇一個小的cl集合(推薦值cl=20),能同時改進(jìn)計算結(jié)果的平均值和最好值。 GBAS算法計算TSP問題的CPU時間隨著城市數(shù)的增加而增長很快,表4中計算428城市實(shí)例時平均計算時間就達(dá)到了1172.01s,計算量還是相當(dāng)可觀的。這不僅與算法本身的復(fù)雜度有關(guān),也與本文在重復(fù)計算次數(shù)不多的情況下,為了保證計算結(jié)果的精度,而選取了比較大的螞蟻數(shù)取值(m=50)有關(guān)。本文第2小節(jié)對GBAS算法進(jìn)行了簡單的復(fù)雜性分析,算法的計算量為CGBAS(I)=k(3m/2+1)n(n+1)=O(kmn2)。而TSP實(shí)例的規(guī)模為l(I)=O(n2+log2|P|),如果按照這個分析,實(shí)例規(guī)模增大時算法計算時間應(yīng)該只是n2量級的增長,這跟計算結(jié)果不吻合。這是因為實(shí)際計算過程為了保證解的精度,并沒有按照復(fù)雜性分析中假定的固定外循環(huán)次數(shù)的規(guī)則來停止運(yùn)算,而是采用了同一最短路徑出現(xiàn)k次作為停止規(guī)則。后一停止規(guī)則在實(shí)例規(guī)模較大的時候,明顯強(qiáng)于前面的停止規(guī)則,因此計算量的增加要高于預(yù)期。計算結(jié)果與理論上的計算復(fù)雜性分析并不矛盾,特此說明。 4? 并行算法 4.1 并行算法的實(shí)現(xiàn) 并行實(shí)現(xiàn)GBAS算法的流程如圖1所示。從蟻群算法的物理本質(zhì)來說,蟻群覓食過程實(shí)質(zhì)上是一個并行的過程,因此反映在并行算法上來說,各進(jìn)程實(shí)際上代表了各螞蟻單獨(dú)的覓食過程。雖然其它螞蟻對于路徑的選擇會影響該螞蟻的選擇,但是螞蟻的覓食過程是相對獨(dú)立的。為了使算法精度足夠高,同時不要浪費(fèi)太多的開銷在信息傳遞上,需要適當(dāng)選擇每個進(jìn)程分配到的螞蟻數(shù)。 并行算法的參數(shù)α=1,β=5,ρ=0.5與串行算法一致。在串行算法的實(shí)現(xiàn)中,我們已經(jīng)對螞蟻數(shù)的選擇進(jìn)行了討論,因此這里以上面討論的結(jié)果為依據(jù),為了保證每個進(jìn)程計算的精度,使它分配到的螞蟻數(shù)不少于min_ants。并行環(huán)境下對各進(jìn)程螞蟻數(shù)進(jìn)行了重新分配,每個進(jìn)程的螞蟻數(shù)為max(min_ants,m/n),其中m是總的螞蟻數(shù),n是進(jìn)程總數(shù)。這樣的螞蟻數(shù)分配既保證了各進(jìn)程計算量的一致,也保證了每個進(jìn)程螞蟻數(shù)不至于太少而影響其計算精度。程序中實(shí)際選取的總螞蟻數(shù)為m=100。