一種求解旅行商問題的改進(jìn)蟻群算法＊

王沛棟，唐功友，楊熙鑫，李 揚(yáng)

（1.中國海洋大學(xué)信息科學(xué)與工程學(xué)院，山東 青島266100；2.青島市產(chǎn)品質(zhì)量監(jiān)督檢驗(yàn)所，山東 青島266101）

旅 行 商 問 題 （Traveling Salesman Problems，TSPs）是組合優(yōu)化領(lǐng)域中一個(gè)重要的問題之一，也是現(xiàn)實(shí)中許多復(fù)雜問題的集中概括和簡化形式，而且由于TSPs問題的典型性，目前它已成為各種啟發(fā)式搜索以及優(yōu)化算法的參照標(biāo)準(zhǔn)。TSPs的任務(wù)是在已知多個(gè)城市位置的條件下，從某個(gè)城市出發(fā)，依次遍歷所有城市，再返回到出發(fā)城市，為銷售員設(shè)計(jì)遍歷路線，使總路徑長度最小或用時(shí)最少。TSPs屬于NP－h(huán)ard問題，采用常規(guī)方法很難得到問題的最優(yōu)解。

目前求解TSPs問題有許多方法，大體可以分為2類算法，即精確算法和啟發(fā)式算法。精確算法主要指動(dòng)態(tài)規(guī)劃和分支限界法［1］等；啟發(fā)式算法包括：遺傳算法［2－3］、蟻群算法［4－11］等。在蟻群算法中，文獻(xiàn)［4］提出螞蟻系統(tǒng)（Ant System ，AS）算法，算法通過隨機(jī)方式進(jìn)行路徑選擇，而且每次迭代結(jié)束后對(duì)信息素進(jìn)行更新；文獻(xiàn)［5］提出螞蟻群系統(tǒng)（Ant Colony System ，ACS）算法，算法使用最優(yōu)選擇和隨機(jī)選擇結(jié)合的路徑選擇方式，信息素更新采用局部更新和全局更新，提高了算法的全局的收斂能力；文獻(xiàn)［6］提出最大最小螞蟻系統(tǒng)（Max－Min Ant System ，AS）算法，算法在 AS算法基礎(chǔ)上，通過限制信息素的大小范圍，使算法不致于陷入停滯狀態(tài)，性能較AS有較大的提高；文獻(xiàn)［7］提出一種基于信息素?cái)U(kuò)散的蟻群算法（Pheromone Diffusion Ant colony Optimization，PDACO），算法通過建立信息素?cái)U(kuò)散模型，使相距較近的螞蟻之間能更好地進(jìn)行協(xié)作；文獻(xiàn)［8］提出一種基于遺傳算法和螞蟻算法的融合算法，它采用遺傳算法生成信息素分布，再利用螞蟻算法進(jìn)行求解；文獻(xiàn)［9］提出一種帶有變異策略和信息素動(dòng)態(tài)更新的蟻群算法，變異策略增加了搜索的多樣性，信息素動(dòng)態(tài)更新方式加快了最優(yōu)解的收斂速度；文獻(xiàn)［10］提出一種帶有變異過程和局部搜索的蟻群算法求解TSPs問題；文獻(xiàn)［11］提出一種基于信息素增量和路徑散播模型的螞蟻群算法（ACO algorithm based on new pheromone increment and path diffusion models，PIPDMACO），它建立了信息素增量模型和信息素散播模型，并且使用復(fù)雜度更低的變異策略對(duì)每次的迭代結(jié)果進(jìn)行優(yōu)化。

本文在蟻群系統(tǒng)算法的基礎(chǔ)上提出一種求解TSPs問題的改進(jìn)算法。其中，在信息素更新過程，利用信息素局部更新和全局動(dòng)態(tài)更新結(jié)合的方法，使得局部最優(yōu)路徑上的信息素值動(dòng)態(tài)地調(diào)配，避免了算法陷入停滯狀態(tài)；在局部搜索過程中，僅對(duì)部分走出更優(yōu)路徑的售貨員使用2－opt方法，加快了最優(yōu)解的收斂速度。

1 問題描述及數(shù)學(xué)模型

TSPs問題是由1名售貨員對(duì)多個(gè)城市進(jìn)行配送服務(wù)的問題。在已知城市位置的前提下，設(shè)計(jì)售貨員配送路線，每個(gè)城市只能被訪問1次，使運(yùn)輸成本最小化，即總代價(jià)最?。ㄐ凶呖偩嚯x最短或耗費(fèi)時(shí)間最少）。用數(shù)學(xué)模型表達(dá)，根據(jù)TSPs問題中的城市分布，可以建立1個(gè)無向圖G（V，A），包括節(jié)點(diǎn)集

和邊集

其中：n為城市的數(shù)量；vk表示城市k＜vp，vq＞表示城市p與城市q之間的路徑；設(shè)dij為城市i到城市j的距離，

TSPs問題的目標(biāo)是為售貨員尋找最優(yōu)的遍歷路線，使運(yùn)輸成本J達(dá)到最小值，

且應(yīng)滿足以下約束條件：

式（5）表示售貨員僅有1次機(jī)會(huì)到達(dá)城市j；式（6）表示售貨員僅有1次機(jī)會(huì)離開城市i，式（5）與式（6）共同保證了售貨員對(duì)每個(gè)城市只能訪問1次；式（7）為子回路限制條件，保證在規(guī)劃的路徑中沒有其它的回路。

2 算法設(shè)計(jì)

使用蟻群系統(tǒng)算法求解TSPs問題時(shí)，一般將螞蟻看作售貨員，信息素τij表示售貨員處于城市i時(shí)，城市j對(duì)售貨員的吸引程度。在每次迭代之前，售貨員會(huì)隨機(jī)地選擇1個(gè)初始城市，然后按照路徑選擇規(guī)則來構(gòu)建路徑，售貨員每選擇1個(gè)城市，就對(duì)所走過的路徑進(jìn)行信息素局部更新。當(dāng)所有售貨員的路徑構(gòu)建完畢時(shí)，就對(duì)每條路徑使用2－opt方法進(jìn)行局部搜索，選取當(dāng)前最優(yōu)路徑進(jìn)行信息素全局更新，從而完成1次迭代。經(jīng)過數(shù)次迭代后，算法可以得到一個(gè)優(yōu)化解。

根據(jù)以上算法過程的簡述可知，算法可以分為3個(gè)部分：路徑選擇、信息素更新和局部搜索。本節(jié)將分析蟻群算法求解TSPs問題中信息素更新和局部搜索中的局限性，并提出相應(yīng)的策略對(duì)其進(jìn)行改進(jìn)，最后將總結(jié)改進(jìn)算法的步驟。

2.1 路徑選擇方式

路徑選擇方式采用蟻群系統(tǒng)路徑選擇模型［5］。假設(shè)售貨員k在t時(shí)刻處于城市i時(shí)，下一步可能選擇的城市為j，其路徑選擇公式為：

其中：τij（t）表示t時(shí)刻，路徑（i，j）上的信息素值；啟發(fā)式信息ηij＝1／dij，用來引導(dǎo)售貨員向路徑更短的城市移動(dòng)；allow（i）表示售貨員處于城市i時(shí)，候選城市的集合；β為權(quán)值系數(shù)，用來決定啟發(fā)式信息的重要程度；q表示1個(gè)［0，1）的隨機(jī)值；q0表示設(shè)定的閾值（0.8～0.95）。式（8）能夠使售貨員以較大的概率q0向信息素和啟發(fā)式信息乘積最大的城市移動(dòng)，而以較小的概率（1－q0）使用隨機(jī)比例原則選擇城市。這種方式既保證了售貨員選擇的方向性，又增加了售貨員搜索的多樣性。

2.2 信息素更新方式

目前，求解TSPs問題的蟻群算法使用的信息素更新方式包括螞蟻系統(tǒng)信息素的更新方式［4，6，8］和蟻群系統(tǒng)信息素的更新方式［5，7，9－10］等。然而這些方法都普遍存在同樣的問題，在迭代過程中，當(dāng)新的最優(yōu)路徑還未出現(xiàn)時(shí)，當(dāng)前最優(yōu)路徑上的信息素在更新策略的作用下會(huì)不斷增強(qiáng)，可能會(huì)產(chǎn)生2種消極的結(jié)果：首先，當(dāng)前最優(yōu)路徑上信息素可能會(huì)因過度加強(qiáng)而導(dǎo)致算法停滯；其次，當(dāng)新的最優(yōu)路徑出現(xiàn)時(shí)，其路徑上的信息素強(qiáng)度可能會(huì)遠(yuǎn)低于原最優(yōu)路徑上的信息素強(qiáng)度，有時(shí)經(jīng)過數(shù)次迭代這種情況依然沒有得到緩解?？傊壳暗母路绞绞巩?dāng)前最優(yōu)路徑的變化不能迅速地表現(xiàn)在路徑的信息素分布上，從而降低了搜索的效率。

針對(duì)以上信息素更新方式局限性的分析，本文提出一種局部更新和全局動(dòng)態(tài)更新相結(jié)合的信息素的更新方式。

（1）局部更新

在路徑構(gòu)建過程中，售貨員每經(jīng)過一條邊（i，j）都會(huì)使用下式來更新該邊上的信息素。

其中：ε為局部更新的蒸發(fā)率；τ0為信息素的初始值。信息素局部更新的作用在于，售貨員每經(jīng)過一條邊（i，j），該邊的信息素將會(huì)減少，從而降低其它售貨員選中該邊的概率，這將增加售貨員探索其它未使用過邊的機(jī)會(huì)。

（2）全局動(dòng)態(tài)更新

當(dāng)1次迭代結(jié)束后，將當(dāng)前最優(yōu)路徑使用下式進(jìn)行信息素全局更新。

其中：ρ為全局更新的蒸發(fā)率；Δτij為全局更新信息素增量；L1為當(dāng)前迭代最優(yōu)路徑長度；Lg為當(dāng)前最優(yōu)路徑長度。更新當(dāng)前最優(yōu)路徑上的信息素在于對(duì)最優(yōu)路徑的繼續(xù)開發(fā)，將當(dāng)前最優(yōu)路徑對(duì)信息素的反饋保留到下一次的迭代中去，直到有更優(yōu)的路徑取代為止。

式（10）和（11）能夠根據(jù)售貨員所構(gòu)建路徑的情況動(dòng)態(tài)地調(diào)整當(dāng)前最優(yōu)路徑上的信息素。在迭代過程中，當(dāng)一條更優(yōu)路徑出現(xiàn)后，L1和Lg的差值開始可能會(huì)比較大，這說明當(dāng)前最優(yōu)路徑與大多數(shù)售貨員走出的路徑存在較大的差異，走出當(dāng)前最優(yōu)路徑的售貨員所占比例很小。此時(shí)，式（11）能夠加大當(dāng)前最優(yōu)路徑上信息素的強(qiáng)度，以吸引更多的售貨員。而隨著迭代的進(jìn)行，當(dāng)前最優(yōu)路徑上的信息素不斷增強(qiáng)，更多的售貨員會(huì)聚集到這條路徑上來，L1和Lg的差值會(huì)逐漸減小，此時(shí)，式 （11）能夠相應(yīng)地減小信息素增量，直至減小到0。當(dāng)式 （11）減小到0時(shí)，當(dāng)前最優(yōu)路徑上只進(jìn)行信息素蒸發(fā)，對(duì)信息素進(jìn)行削弱。該方法能夠使當(dāng)前最優(yōu)路徑上的信息素強(qiáng)度更為突出，但又不會(huì)因過度加強(qiáng)而造成算法的停滯，使當(dāng)前最優(yōu)路徑的變化更快地反映在信息素的分布上。

2.3 局部搜索策略

2－opt方法是求解TSP問題經(jīng)常使用的一種方法。圖1描述了2－opt方法對(duì)路徑的搜索過程，如圖1所示，A為搜索之前城市訪問的路徑，B為使用2－opt方法后城市訪問的路徑。文獻(xiàn)［5－6，9－10］分別將其應(yīng)用到迭代后的每名售貨員所構(gòu)建路徑的路徑中。使用這種方法可以提高解的質(zhì)量，為下一步選取當(dāng)前最優(yōu)路徑進(jìn)行信息素全局更新做準(zhǔn)備。但是，使用2－opt方法非常消耗時(shí)間，如果問題規(guī)模和售貨員的數(shù)量比較大，這種方法會(huì)消耗大量的時(shí)間，這也是以上算法［5－6，9－10］求解時(shí)間過長的原因之一。

圖1 局部搜索2－opt過程Fig.1 Schematic diagram of the 2－opt process

針對(duì)以上對(duì)局部搜索局限性的分析，本文局部搜索方法：

（1）在每次迭代結(jié)束后，將所有售貨員所構(gòu)建的路徑，按照路徑長度升序排列。

（2）從排列中選取路徑長度最短的m／2（m為售貨員的數(shù)量）條路徑使用2－opt方法進(jìn)行局部搜索。

使用這種方式的原因在于，作者通過實(shí)驗(yàn)發(fā)現(xiàn)，蟻群算法每次迭代后，在對(duì)每個(gè)售貨員構(gòu)建的路徑使用2－opt方法的過程中，大部分售貨員的結(jié)果對(duì)當(dāng)前最優(yōu)解并沒有貢獻(xiàn)，也就是說，并非所有路徑使用2－opt方法都能夠?qū)Ξ?dāng)前最優(yōu)解的選取有所幫助，而當(dāng)前最優(yōu)的結(jié)果往往來自當(dāng)前迭代中更短的那些路徑。這就造成了在蟻群算法求解過程中，由于對(duì)那些沒有幫助的路徑使用2－opt方法而消耗大量的時(shí)間。在本章改進(jìn)蟻群算法中，算法在每次迭代后，僅對(duì)部分更優(yōu)的路徑使用2－opt方法，這種方式可以節(jié)省部分計(jì)算時(shí)間，又不會(huì)降低搜索效率。

2.4 算法步驟

根據(jù)以上改進(jìn)策略的描述，總結(jié)改進(jìn)算法步驟如下：

Step1參數(shù)初始化。令迭代計(jì)數(shù)器NC＝0，設(shè)置當(dāng)前最優(yōu)路徑長度S、最大的迭代次數(shù)T、城市之間的距離dij（i，j＝1，…，n）、當(dāng)前最優(yōu)路徑表t、啟發(fā)式信息ηij（i，j＝1，2，…，n）、路徑上的信息素τij（i，j＝1，2，…，n）。

Step2售貨員位置初始化。初始化m名售貨員的禁忌表tk（k＝1，2，…，m）、所走路徑長度lk（k＝1，2，…，m）。所有的售貨員隨機(jī)地選擇初始城市，將所選的城市添加到tk中，并更新lk的值。

Step3路徑構(gòu)建。每名售貨員按式（8）進(jìn)行路徑選擇，將所選的城市添加到tk中，并更新lk的值。

Step4信息素局部更新。售貨員每選擇一個(gè)城市，就對(duì)剛剛走過路徑（i，j）根據(jù)公式（9）進(jìn)行信息素局部更新。Step5 2－opt局部搜索。當(dāng)所有售貨員完成對(duì)全部城市的搜索，路徑構(gòu)建完畢時(shí)，將所有售貨員的路徑長度按升序排序，然后選取路徑長度最小的m／2名售貨員的路徑進(jìn)行2－opt局部搜索，并更新lk和tk。

Step6信息素全局動(dòng)態(tài)更新。統(tǒng)計(jì)當(dāng)前最優(yōu)路徑，將lk與S進(jìn)行比較。若lk＜S，則lk替換S，t替換tk。對(duì)當(dāng)前最優(yōu)路徑根據(jù)公式（10）和（11）進(jìn)行信息素全局動(dòng)態(tài)更新。

Step7迭代循環(huán)。若NC≤T，則返回Step2，開始新一次的迭代，否則算法結(jié)束，輸出最優(yōu)路徑S和最優(yōu)路徑表t。

3 仿真實(shí)驗(yàn)

算法將從旅行商問題公共數(shù)據(jù)集中選擇標(biāo)準(zhǔn)算例進(jìn)行測(cè)試，使用BCB＋Matlab進(jìn)行程序編寫，并在CPU 為Intel Celeron 1.0G，內(nèi)存512M 的計(jì)算機(jī)上運(yùn)行，實(shí)驗(yàn)參數(shù)為：ρ＝0.1～0.2，ε＝0.1～04，β＝2～5，m＝15～30，q0＝0.7～0.95。從數(shù)據(jù)集中選擇 Oliver30算例進(jìn)行測(cè)試，該算例包含30個(gè)城市，算法對(duì)其計(jì)算結(jié)果見圖2，從圖中可以看到，算法經(jīng)過3次迭代，就可以得到最優(yōu)路徑，其路徑長度為432.74。圖2（a）描述了算法對(duì)Oliver30算例最后得到的最優(yōu)路徑圖，圖2（b）描述了算法每次迭代的當(dāng)前最優(yōu)路徑長度。

圖2 Oliver30數(shù)據(jù)計(jì)算結(jié)果Fig.2Simulation result of Oliver30

從數(shù)據(jù)集中選取部分算例進(jìn)行測(cè)試，每組算例運(yùn)行10次，其結(jié)果如表1所示，其中，BK表示目前每組算例提供的最優(yōu)參考結(jié)果。Best result表示本文算法獲得的的最優(yōu)結(jié)果。Num of cycles表示算法取得最優(yōu)解時(shí)，使用的最少迭代次數(shù)。由表1可以看到，算法對(duì)10組算例都能夠取得目前最優(yōu)解，而且最優(yōu)解所需的迭代次數(shù)最大為72次。

表1 本文算法計(jì)算結(jié)果Table 1 Best results for our algorithm on various instances

此外，將本文算法與其它算法進(jìn)行比較，包括ACS［5］，ACS＋2－opt［11］，PDACO［7］，，PIPDMACO［11］，性能對(duì)比如表2所示，可以看到，在所有的算法中，PIPDMACO算法和本文算法對(duì)所有的算例均能夠獲得最優(yōu)解，其余3種算法除Oliver30算例外，均未能獲得算例的最優(yōu)結(jié)果，而且這3種算法獲得最優(yōu)解所需的迭代次數(shù)較PIPDMACO算法和本文算法略大。此外，本文算法與PIPDMACO算法相比，求解Eil51and Pr107算例最優(yōu)值所需的迭代次數(shù)要大，而求解其余4組算例迭代次數(shù)均略小些。本文方法不但能夠增強(qiáng)信息素，而且在當(dāng)前迭代最優(yōu)路徑長度與當(dāng)前最優(yōu)路徑長度相等時(shí)會(huì)對(duì)信息素進(jìn)行削弱，能夠根據(jù)搜索結(jié)果動(dòng)態(tài)地調(diào)配最優(yōu)路徑上的信息素。與其它方法相比，本文更新方式使最優(yōu)路徑的變化能夠更迅速地反映在信息素的變化上，使售貨員對(duì)最優(yōu)路徑更為敏感。綜合以上實(shí)驗(yàn)結(jié)果可以看出，與其它算法相比，本文算法體現(xiàn)出良好的性能，并且在問題規(guī)模較大的情況下，解的質(zhì)量也顯示了較高的穩(wěn)定性。

表2 算法性能對(duì)比Table 2 Comparison among the algorithm performances

4 結(jié)語

本文提出了一種基于蟻群系統(tǒng)算法的改進(jìn)優(yōu)化方法，并將其應(yīng)用于求解旅行商問題。通過對(duì)標(biāo)準(zhǔn)問題的求解以及與其它方法的比較，本文算法均體現(xiàn)出了良好的性能。此外，該算法也可以用于其它相關(guān)類型的優(yōu)化問題。

［1］ Fischetti M，Salazar J J，Toth P.A branch－and－cut algorithm for the symmetric generalized traveling salesman problem ［J］.Operations Research，1997，45：378－394.

［2］ Snyder L V，Daskin M S.A random－key genetic algorithm for the generalized traveling salesman problem ［J］.Operations Research，2006，173：38－53.

［3］ Darrell W，Doug H，Adele H.A hybrid genetic algorithm for the traveling salesman problem using generalized partition crossover［J］.Lecture Notes in Computer Science，2011，6238：566－575.

［4］ Dorigo M，Maniezzo V，Colorni A.Ant System：Optimization by a colony of cooperating agents［J］.IEEE Transaction on Systems，Man and Cybernetics Part B，1996，26（1）：29－41.

［5］ Dorigo M，Gambardella L M.Ant colony System：A cooperative learning approach for the traveling salesman problem ［J］.IEEE Transaction on Evolutionary Computation，1997，1（1）：53－66.

［6］ Stutzle T，Hoos H H.MAX－MIN ant system and local search for the traveling salesman problem ［C］.Indianapolis：Proceedings of the IEEE International Conference on Evolutionary Computation，1997：309－314.

［7］ 黃國銳，曹先彬，王煦法.基于信息素?cái)U(kuò)散的蟻群算法 ［J］.電子學(xué)報(bào)，2004，32（4）：865－868.

［8］ 丁建立，陳增強(qiáng)，袁著祉.遺傳算法與螞蟻算法的融合 ［J］.計(jì)算機(jī)研究與發(fā)展，2003，40（9）：1351－1356.

［9］ 朱慶保，楊志軍.基于變異和動(dòng)態(tài)信息素更新的蟻群優(yōu)化算法［J］.軟件學(xué)報(bào)，2004，15（2）：185－192.

［10］ Yang J H，Shi X H，Maurizio M，et al.An ant colony method for generalized TSP problem ［J］.Progress in Natural Science，2008，18：1417－1422.

［11］ 冀俊忠，黃振，劉椿年.一種快速求解旅行商問題的蟻群算法［J］.計(jì)算機(jī)研究與發(fā)展，2009，46（6）：968－978.