求解TSP問題的自適應(yīng)模擬退火蟻群算法

袁汪凰　游曉明*　劉　升　朱　艷

1(上海工程技術(shù)大學(xué)電子電氣學(xué)院　上海 201620) 2(上海工程技術(shù)大學(xué)管理學(xué)院　上海 201620)

0　引　言

旅行商問題TSP(Traveling Salesman Problem)是一個(gè)屬于NP-Hard的組合優(yōu)化問題。旅行商從所有城市列表中任選一個(gè)城市作為起點(diǎn)，不重復(fù)地遍歷完所有城市，最后回到原起始點(diǎn)，從而形成一個(gè)最短路徑的Hamilton回路。目前解決TSP問題的算法有最近鄰點(diǎn)[1]、貪心算法[2]、遺傳算法[3]、模擬退火算法[2]、粒子群優(yōu)化算法[4]、蟻群算法[5]等。而蟻群算法是一個(gè)全局搜索策略的群智能算法，具有很好的自組織性、魯棒性、正反饋性、并行性和易與其他算法結(jié)合解決實(shí)際問題等優(yōu)點(diǎn)。但是蟻群算法同時(shí)也存在收斂速度慢、易陷入局部最優(yōu)、容易陷入早熟、停滯的缺點(diǎn)。

蟻群算法最早由意大利學(xué)者M(jìn).Dorigo受到自然界中螞蟻群體的覓食行為的啟發(fā)首次提出，并將其應(yīng)用于經(jīng)典的TSP問題。其后專家學(xué)者對(duì)蟻群算法進(jìn)行了改進(jìn)：1996年M.Dorigo等在此基礎(chǔ)上，提出了螞蟻系統(tǒng)AS(Ant System)[5]，該算法采用隨機(jī)比例規(guī)則構(gòu)建路徑，當(dāng)所有螞蟻路徑構(gòu)建結(jié)束之后，進(jìn)行信息素更新；1997年M.Dorigo和M.Gambardella將蟻群算法中加入Q-Learning算法，提出了一種具有全新機(jī)制的蟻群系統(tǒng)ACS (Ant Colony System)[6];此后T.Stutzle等在AS基礎(chǔ)上進(jìn)行改進(jìn)，提出了最大-最小蟻群算法MMAS (Max-Min Ant System)[7]。在這些改進(jìn)算法中，MMAS是對(duì)AS完善的典型代表之一，在解決TSP問題上具有的良好性能。

MMAS在一定程度上有效地避免了算法的停滯，但仍存在解質(zhì)量不高、收斂速度較慢等不足，因此專家學(xué)者在此基礎(chǔ)上進(jìn)行了改進(jìn)。文獻(xiàn)[8]提出一種動(dòng)態(tài)的最大最小蟻群算法DMAS,通過構(gòu)造與當(dāng)前迭代過程中信息素最大值相關(guān)的函數(shù)，動(dòng)態(tài)更新信息素的下限閾值，增大螞蟻的探索能力，使得多樣性增加；同時(shí)在DMAS中加入2-opt改善了解的質(zhì)量。文獻(xiàn)[9]在MMAS基礎(chǔ)上運(yùn)用混沌Tent映射全局遍歷，尋找初始較優(yōu)的候選路徑，初始化信息素；當(dāng)檢測(cè)到算法陷入停滯時(shí)，采用混沌擾動(dòng)，增加算法跳出局部最優(yōu)的能力，具有較優(yōu)的全局搜索能力。文獻(xiàn)[10]提出一種NMMAS，該算法在兩個(gè)階段更新信息素，第一階段為了使算法的探索能力增強(qiáng)，按順序等級(jí)更新，第二階段更新當(dāng)前迭代最優(yōu)路徑，加快了收斂速度。文獻(xiàn)[11]提出了基于MMAS的雙種群最大最小蟻群算法，該算法采用雙種群并行搜索機(jī)制，一定條件后在種群間進(jìn)行信息素通信，直到信息素達(dá)到平衡，提高了解的質(zhì)量。文獻(xiàn)[12]根據(jù)K鄰域候選集，前期采用局部搜索產(chǎn)生的解進(jìn)行初始化信息素矩陣，再根據(jù)解的分布情況，動(dòng)態(tài)地更新信息素，后期用3opt對(duì)解進(jìn)行優(yōu)化，并采用metropoil準(zhǔn)則在一定概率內(nèi)接受較優(yōu)解，在較大規(guī)模的TSP問題上得到了較好的應(yīng)用。上述文獻(xiàn)雖然在一定程度上改善了解的質(zhì)量但還存在收斂速度方面的問題。文獻(xiàn)[13]提出了模擬退火蟻群算法，一次迭代后對(duì)所有螞蟻求得的解采用更新策略，然后選取較優(yōu)的幾只螞蟻更新信息素。同時(shí)引入Boltzmann機(jī)制，對(duì)每代螞蟻生成的解進(jìn)行處理，避免陷入局部最優(yōu)，在解決Jop-Shop問題上有效地提高了算法的收斂速度。本文借鑒文獻(xiàn)[13]在Jop-Shop問題上將模擬退火機(jī)制引入蟻群算法，提高了收斂速度的優(yōu)勢(shì)，提出自適應(yīng)的模擬退火蟻群算法以用于解決TSP問題。

本文提出的自適應(yīng)SA-MMAS算法，在MMAS算法中引入模擬退火機(jī)制，在高溫階段以一定概率接受其他解，增加蟻群的搜索空間；在低溫階段能夠一定程度上提高收斂速度。并在全局信息素更新中引用了模擬退火衰減函數(shù)，采用一種自適應(yīng)的信息素?fù)]發(fā)機(jī)制進(jìn)行信息素更新，使得算法前期的搜索能力增強(qiáng)尋到更多可行解，后期使得算法收斂速度加快，縮短找到最優(yōu)解的時(shí)間。通過雙重作用使得該算法能夠更好地平衡種群多樣性和收斂速度的矛盾，同時(shí)采用3opt局部搜索算法更進(jìn)一步提高了解的質(zhì)量。

1　相關(guān)工作

1.1　基本蟻群算法

螞蟻雖然沒有視覺的，但是卻可以通過合作完成任務(wù)，蟻群中后續(xù)螞蟻根據(jù)前期螞蟻從蟻穴出發(fā)尋找食物再回到蟻穴過程中釋放的一種化學(xué)物質(zhì)—信息素，來尋找路徑。前期螞蟻在尋找路徑時(shí)先會(huì)隨機(jī)選擇一個(gè)路徑前行并釋放出相應(yīng)的信息素，若信息素濃度越高，即選擇該條路徑的螞蟻數(shù)越多；若信息素濃度越低，此時(shí)選擇該路徑上的螞蟻數(shù)目越少，通過這種正反饋?zhàn)饔茫詈笳页鲆粭l最優(yōu)路徑。為了避免局部最優(yōu)，即采用一種揮發(fā)機(jī)制，使得路徑上的信息素不是一味的疊加，通過這種負(fù)反饋?zhàn)饔?，以便螞蟻避免局部最?yōu)，找到全局最優(yōu)路徑。螞蟻在尋找最優(yōu)路徑的同時(shí)，采用輪盤賭以一定概率選擇其他路徑。當(dāng)該路徑比當(dāng)前最優(yōu)路徑短時(shí)，將會(huì)有更多螞蟻?zhàn)咴摋l路徑，就可找到最短路徑。

假設(shè)螞蟻的數(shù)量為m，城市的規(guī)模為n，將m只螞蟻隨機(jī)分配到n個(gè)城市中，τij(t)為t時(shí)刻螞蟻k(1,2,…，m)殘留在(i，j)之間的信息素濃度，初始時(shí)刻各城市間信息素濃度相同，即設(shè)置τij(0)=const。每只螞蟻根據(jù)各個(gè)路徑上的信息素濃度選擇轉(zhuǎn)移路徑的方向，螞蟻k從i城市轉(zhuǎn)到j(luò)城市時(shí)采用狀態(tài)轉(zhuǎn)移概率：

(1)

τij(t+1)=(1-ρ)τij(t)+Δτij(t)

(2)

(3)

(4)

式中：Q為信息素強(qiáng)度；Lk為螞蟻k在當(dāng)前循環(huán)中所走路徑的總長(zhǎng)度。

1.2　MMAS算法

最大-最小蟻群算法(MMAS)通過將信息素限定在某一區(qū)間，避免了某一條路徑上信息素的持續(xù)積累，在一定程度上有效地避免了算法的停滯，該算法在TSP、QAP[14]和VRP[15]等問題有較優(yōu)的解。MMAS與基本蟻群算法相比其改進(jìn)的幾點(diǎn)優(yōu)化之處為:

(1) 為了避免算法早熟、停滯，MMAS算法將各邊的信息素限制在一定范圍[τmin，τmax]，若τij≤τmin，τij=τmin；若τij≥τmax，τij=τmax其中τmax和τmin的計(jì)算公式[6,8]分別為式(5)、式(6)：

(5)

(6)

式中：Tgb是全局最優(yōu)路徑。

(2) 每迭代一次，有且僅有一只螞蟻進(jìn)行信息素更新，即對(duì)當(dāng)前最優(yōu)路徑或者全局最優(yōu)路徑進(jìn)行更新，使最優(yōu)解得到有效的利用，算法的探索能力也會(huì)增強(qiáng)。信息素更新規(guī)則表示為：

(7)

(8)

式中：f(sbest)為當(dāng)前最優(yōu)或者全局最優(yōu)的路徑長(zhǎng)度。

(3) 算法中每條邊的信息素初始化為τmax。增加了算法初始階段的隨機(jī)搜索能力。

1.3　3-opt[16]

局部搜索算法對(duì)蟻群每次迭代過程中產(chǎn)生的解進(jìn)行優(yōu)化，而在局部?jī)?yōu)化算法中3-opt算法效率比較高，其基本流程為：隨機(jī)選擇搜索區(qū)域內(nèi)的某些位置，隨后從當(dāng)前位置移動(dòng)到相鄰位置，將候選解轉(zhuǎn)換成另外一個(gè)，該算法反復(fù)執(zhí)行減少路徑的長(zhǎng)度，直到達(dá)到極優(yōu)解。

設(shè)T為當(dāng)前路徑，在每一步迭代中，算法試圖發(fā)現(xiàn)兩個(gè)不相交的邊集X={x1,x2,…,xk}和Y={y1,y2,…,yk}，其中X、Y初始化是空集，按步驟i添加一對(duì)邊xi和yi。其中xi、yi和yi、xi+1必須分別共享端點(diǎn)，且令t1表示端點(diǎn)x1，在i≥1的情況下有xi=(t2i-1,t2i),yi=(t2i,t2i+1)和xi+1=(t2i+1,t2i+2) 。如圖1所示。

圖1　xi，yi，xi+1,yi+1的制約性選擇

X邊集被從T中刪除由Y替代能找到更好的路徑仍構(gòu)成一個(gè)封閉回路，如圖2所示。

圖2　3opt：x1,x2,x3被y1,y2,y3替換

2　改進(jìn)算法

2.1　模擬退火機(jī)制的引入

模擬退火算法SA(Simulated Annealing)是一種模擬物理中固體退火過程而設(shè)計(jì)的全局搜索優(yōu)化算法，最早在1953年由Metropolis等人提出。采用模擬固體退火的加溫、等溫和冷卻三個(gè)階段，具體如下：先在一個(gè)高溫狀態(tài)下(相當(dāng)于算法隨機(jī)搜索)，然后逐漸退火(Metropolis抽樣過程)，在每個(gè)溫度下(相當(dāng)于算法的每一次狀態(tài)轉(zhuǎn)移)逐漸冷卻(相當(dāng)于算法局部搜索)，最終達(dá)到能量最低態(tài)(相當(dāng)于算法找到最優(yōu)解)。

設(shè)系統(tǒng)溫度為T，初始溫度T(0)=T0，當(dāng)蟻群算法完成一次迭代后，可以得到初始解集S1，其中被3opt優(yōu)化過的最優(yōu)解路徑長(zhǎng)度為L(zhǎng)Route，在初始解集基礎(chǔ)上隨機(jī)擾動(dòng)產(chǎn)生最新集S2，由新解集計(jì)算出的路徑長(zhǎng)度為L(zhǎng)2，目標(biāo)函數(shù)變化的差值為：

ΔL=L2-LRoute

(9)

當(dāng)ΔL<0時(shí)，接受S2作為新的當(dāng)前解，否則新解集的接受概率如下：

(10)

即產(chǎn)生(0,1)區(qū)間上均勻分布的隨機(jī)數(shù)ζ，若P>ζ,則接受S2作為新的當(dāng)前解；否則保留原解，最優(yōu)解仍為L(zhǎng)Route。

完成一輪循環(huán)和信息素更新后進(jìn)行降溫，即T(NC+1)=a×T(NC),若降溫系數(shù)a取值較小，溫度下降越慢，算法的收斂速度會(huì)加快，但可能很容易陷入局部最優(yōu)。所以本文加入了回火機(jī)制(類比于金屬淬火處理的最后階段回火)，即人為設(shè)置升溫過程，適當(dāng)概率接受高能狀態(tài)，以一種隨機(jī)擾動(dòng)的方式，幫助算法跳出局部最優(yōu)，再進(jìn)入模擬退火的過程。回火溫度范圍為[Tmin,Tmax]，回火次數(shù)為Hs，回火最大次數(shù)為Hmax。當(dāng)溫度T降到Tmin時(shí)，算法使得T立即回升到Tmax，以較高的概率接受較差解加入最新集，大大地減少了落入局部最優(yōu)的可能性。

2.2　改進(jìn)的信息素更新算子

信息素?fù)]發(fā)因子ρ的大小在某種水平上影響路徑上的信息素量，同時(shí)其大小影響了算法的全局搜索能力和收斂速度。傳統(tǒng)蟻群算法中，信息素?fù)]發(fā)因子是屬于(0,1)范圍的一個(gè)固定常數(shù)。ρ值越大，路徑上的信息素量殘留越少，螞蟻搜索路徑的隨機(jī)性變大，提高了算法的全局搜索能力，易找到全局最優(yōu)解，但是卻導(dǎo)致算法的收斂速度降低。ρ值越小，路徑上信息素量的殘留越多，螞蟻選擇之前走過的路徑概率越大，加劇了算法的收斂速度，但容易陷入局部最優(yōu)。對(duì)此，本文根據(jù)模擬退火算法中衰減函數(shù)對(duì)尋優(yōu)結(jié)果的影響，提出了一種自適應(yīng)的信息素更新方式。在搜索前期ρ取值較大，增加算法的全局搜索能力，使得螞蟻能夠遍歷到所有路徑；后期取值較小，加快算法的收斂速度，縮短搜索時(shí)間?？梢娛桥c迭代次數(shù)NC有關(guān)的，因此信息素?fù)]發(fā)因子ρ改進(jìn)為:

ρ(NC)=1/log2(1+NC)

(11)

2.3　算法描述

算法步驟如下：

Step1： 參數(shù)初始化；

Step2：NC=0，隨機(jī)分配m只螞蟻起點(diǎn);

Step3： 螞蟻k根據(jù)式(1)和輪盤賭方式選擇下一可行城市;

Step4： 所有螞蟻都完成搜索任務(wù)，蟻群得到初始集S1，初始集中最優(yōu)個(gè)體LRoute;

Step5： 采用3-opt對(duì)當(dāng)前初始解中最優(yōu)個(gè)體LRoute進(jìn)行局部?jī)?yōu)化;

Step6： 根據(jù)模擬退火原理產(chǎn)生新的可行解S2,按照式(9)判斷是否接受新解作為當(dāng)前解，生成最新集；

Step7： 根據(jù)式(7)計(jì)算自適應(yīng)揮發(fā)素；

Step8： 根據(jù)式(5)、式(6)計(jì)算最大最小信息素值；

Step9： 根據(jù)最新集里的解以及當(dāng)前最優(yōu)個(gè)體，按照式(4)、式(7)、式(8)對(duì)信息素進(jìn)行更新；

Step10： T←aT,NC←NC+1;

若T≥Tmin,則轉(zhuǎn)Step3;

若T

若T

Step11： 輸出最優(yōu)解。

其中，Step6引入模擬退火機(jī)制，以一定概率接受隨機(jī)擾動(dòng)產(chǎn)生的新解，增強(qiáng)了算法的全局搜索能力；Step9通過自適應(yīng)的信息素更新機(jī)制，前期使螞蟻找到更多可行解，后期加快了收斂速度；Step10通過回火策略，減少了算法陷入局部最優(yōu)的可能性。

3　實(shí)驗(yàn)仿真與結(jié)果分析

為了檢驗(yàn)本文算法的性能，使用MATLAB 2014a對(duì)TSPLIB測(cè)試集中的部分城市進(jìn)行仿真，分別對(duì)DMMAS(MMAS中加入自適應(yīng)信息素算子)與MMAS，SA-MMAS與MMAS進(jìn)行比較，驗(yàn)證了算法的優(yōu)越性。參數(shù)設(shè)置如表1所示，其中MMAS參數(shù)設(shè)置參考文獻(xiàn)[8]的建議值,算法的螞蟻數(shù)目m等于城市數(shù)n。

表1　參數(shù)設(shè)置

本文以O(shè)liver30、eil51、berlin52、st70為對(duì)象分別對(duì)DMMAS與MMAS進(jìn)行了10次實(shí)驗(yàn)，每次迭代3 000次。將DMMAS與MMAS進(jìn)行對(duì)比，DMMAS的優(yōu)化路徑圖以及DMMAS與MMAS最短路徑對(duì)比圖如圖3所示。在圖3的4個(gè)例子可以看出：DMMAS算法的收斂精度以及收斂速度優(yōu)于MMAS算法。從表2中也可以看出DMMAS算法的最優(yōu)解更接近于最優(yōu)解。

圖3　MMAS與MMAS對(duì)比

TSP實(shí)例最優(yōu)解DMMASMMAS最優(yōu)解偏差/%均值最優(yōu)解偏差/%均值Oliver304204200．00420．84200．00420．8eil514264270．23431．34290．70435．6st706756770．29700．86821．04692．1berlin52754275420．007741．075420．007591．7

為了將本文算法SA-MMAS與MMAS進(jìn)行比較，本文選取了6種不同規(guī)模的TSP測(cè)試集進(jìn)行實(shí)驗(yàn)。從表3中可以看出，本文算法無論是從最優(yōu)解、均值還是迭代次數(shù)對(duì)于TSP問題的求解皆優(yōu)于MMAS算法。

表3　SA-MMAS算法與MMAS算法比較結(jié)果

以KROA100為例，圖4為求解KROA100的最優(yōu)路徑圖和迭代圖，本文算法求得KROA100最優(yōu)解為21 282，與TSP最優(yōu)解誤差為0%，比MMAS小了0.37%；本文在迭代第188次時(shí)收斂，比MMAS少了1 573；平均迭代次數(shù)469，比MMAS少了1 338，可以看出收斂速度以及求解精度明顯優(yōu)于MMAS算法。

圖4　KROA100

4　結(jié)　語(yǔ)

本文針對(duì)TSP問題提出了自適應(yīng)模擬退火蟻群算法。通過對(duì)不同規(guī)模的城市進(jìn)行仿真，結(jié)果表明，在蟻群算法中加入自適應(yīng)信息素更新算子，前期增加了算法的全局搜索能力，后期加快了算法的收斂速度。而在蟻群算法中引入模擬退火機(jī)制，高溫階段提高了算法的全局搜索能力，低溫階段加快了算法的收斂速度且有效地避免陷入局部最優(yōu)。在不同規(guī)模的TSP問題上，本文算法結(jié)合以上兩種機(jī)制，經(jīng)多次實(shí)驗(yàn)表明不僅可以提高解的質(zhì)量，而且可以較好地提升算法的收斂速度，從而使整個(gè)算法的運(yùn)行效率更加優(yōu)化。因此，本文算法比傳統(tǒng)的MMAS算法性能更優(yōu)，在今后的工作中會(huì)進(jìn)一步研究自適應(yīng)信息素模型，使算法具有更好的性能。

[1] 饒衛(wèi)振,金淳,黃英藝,等.求解TSP問題的最近鄰域與插入混合算法[J].系統(tǒng)工程理論與實(shí)踐,2011,31(8):1419-1428.

[2] 李金旭,黃悅悅.求解TSP的貪心模擬退火算法[J].河南工程學(xué)院學(xué)報(bào)(自然科學(xué)版),2015(1):66-69.

[3] 于瑩瑩,陳燕,李桃迎,等.改進(jìn)的遺傳算法求解旅行商問題[J].控制與決策,2014(8):1483-1488.

[4] 李文,伍鐵斌,趙全友,等.改進(jìn)的混沌粒子群算法在TSP中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用研究,2015,32(7):2065-2067.

[5] Dorigo M,Maniezzo V,Colorni A.Ant system: optimization by a colony of cooperating agents[J].IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics A Publication of the IEEE Systems Man & Cybernetics Society,1996,26(1):29.

[6] Dorigo M,Gambardella L M.Ant colony system:a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation,1997,1(1):53-66.

[7] Stutzle T,Hoos H H.MAX-MIN Ant system[J].Future Generation Computer Systems,2000,16(9):889-914.

[8] Bonyadi M R,Shah-Hosseini H.A dynamic max-min ant system for solving the travelling salesman problem[J].International Journal of Bio-Inspired Computation,2010,2(6):422-433.

[9] 耿志強(qiáng),邱大洪,韓永明.基于混沌的MMAS算法及其在旅行商問題中的應(yīng)用[J].計(jì)算機(jī)工程,2016,42(3):192-197.

[10] Zhang Z J,Feng Z R.A novel Max-Min ant system algorithm for traveling salesman problem[C]//IEEE International Conference on Intelligent Computing and Intelligent Systems.IEEE,2009:508-511.

[11] Zhou X,Zhao L,Xia Z,et al.A Max-Min Ant System with two colonies and its application to Traveling Salesman Problem[C]//2012 IEEE Fifth International Conference on Advanced Computational Intelligence (ICACI),2012:319-323.

[12] 陳星宇,全惠云,肖偉.求解旅行商問題的高效自適應(yīng)混合螞蟻算法[J].計(jì)算機(jī)工程與應(yīng)用,2007,43(27):84-87.

[13] 張曉婧,高慧敏.基于模擬退火的蟻群算法求解Job-Shop問題[J].計(jì)算機(jī)應(yīng)用與軟件,2008,25(5):77-79.

[14] 牟廉明,戴錫笠,李坤,等.求解二次指派問題的最優(yōu)迭代最大最小螞蟻算法[J].計(jì)算機(jī)應(yīng)用,2014,34(1):199-203.

[15] 謝驪玲,宋彥斌,楊坦,等.求解車輛路徑問題的改進(jìn)MMAS算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2016,26(3):27-30,35.

[16] Helsgaun K.General k-opt submoves for the Lin-Kernighan TSP heuristic[J].Mathmatical Programming Computation,2009,1(2/3):119-163.