基于城市權(quán)重的蟻群算法及其在TSP中的應(yīng)用*

馬清鑫，張達(dá)敏，張 斌，阿明翰

（貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院，貴州 貴陽550025）

基于城市權(quán)重的蟻群算法及其在TSP中的應(yīng)用*

馬清鑫，張達(dá)敏，張 斌，阿明翰

（貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院，貴州 貴陽550025）

蟻群算法在解決NP-C問題時展現(xiàn)出了較強(qiáng)的適用性，但收斂速度慢，容易陷入局部最優(yōu)解的缺陷卻沒有得到較好解決。于是，提出了一種基于城市權(quán)重的蟻群算法ACAWC（Ant Colony Algorithm based on the W eight of City）。改進(jìn)后的算法通過利用城市距離在整個城市網(wǎng)中所占比重來協(xié)調(diào)啟發(fā)信息作用，同時應(yīng)用雙重賭盤算法和雙重隨機(jī)性的思想，增強(qiáng)了跳出局部最優(yōu)解的概率，并改進(jìn)了依據(jù)路徑貢獻(xiàn)度的信息素更新機(jī)制，加快了算法的收斂速度。仿真實(shí)驗(yàn)表明，ACAWC算法求得的最優(yōu)解比基本蟻群算法提高了10%～15%，同時也一定程度地提高了收斂速度。

城市權(quán)重；蟻群算法；TSP；信息素

0 引 言

TSP（Traveling Salesman Problem）問題又稱旅行商問題或最短路徑問題。通?？梢悦枋鰹椋阂阎狽個城市及相互間的距離，旅行商從某城市出發(fā)訪問各城市且僅訪問一次后再回到原點(diǎn)的一條最短巡回路徑。作為典型的NP-C問題，旅行商問題已被廣泛應(yīng)用于車間作業(yè)調(diào)度﹑網(wǎng)絡(luò)路由布設(shè)等方面。為了有效解決TSP問題，許多啟發(fā)式搜索算法被用來解決這一問題，如遺傳算法（GA）﹑蟻群算法（ACA）﹑模擬退火算法（SAA）﹑人工免疫算法（AIA）等[1]。其中，因蟻群算法類似一個增強(qiáng)型學(xué)習(xí)系統(tǒng)，具有正反饋﹑分布式﹑并行式﹑自組織等優(yōu)點(diǎn)，使得在解決NPC問題時具有獨(dú)特的優(yōu)勢。然而，信息素反饋機(jī)制有其明顯的缺陷。信息素反饋機(jī)制過強(qiáng)，會使算法出現(xiàn)停滯甚至陷入局部最優(yōu)解；相反，要找出最佳路徑則需要較長的時間[2]。

Dorigo M等[3]提出利用自適應(yīng)蟻群算法調(diào)控信道資源配置，降低通信過程中的負(fù)擔(dān)，以達(dá)到系統(tǒng)能耗最優(yōu)化；丁建立等[4]提出了將蟻群和遺傳算法結(jié)合的融合算法，基于遺傳算法調(diào)控信息素分布，再應(yīng)用蟻群尋優(yōu)解決路徑優(yōu)化問題，較好地解決了TSP求解精度的問題；黃國銳等[5]提出一種基于信息素擴(kuò)散的蟻群算法（PDACO），通過信息素擴(kuò)散機(jī)制，使相鄰或近距離的螞蟻更加協(xié)調(diào)地工作；田富鵬[6]提出了一種改進(jìn)的蟻群算法，引入信息素?fù)]發(fā)系數(shù)的自適應(yīng)控制策略以及將信息素濃度控制在[min-max]中，有效避免了蟻群算法陷入停滯的狀態(tài)；袁東輝等[7]通過優(yōu)化信息素蒸發(fā)機(jī)制，并引入貪婪策略來改進(jìn)蟻群算法，并將改進(jìn)的蟻群算法應(yīng)用于網(wǎng)絡(luò)節(jié)點(diǎn)部署，取得了較好的效果。

為了有效改善蟻群算法存在的缺陷，本文在借鑒前人研究蟻群算法和TSP問題的基礎(chǔ)上，提出了基于城市權(quán)值的信息素初始化矩陣，有效改善了蟻群因前期信息素缺乏而過度依賴啟發(fā)信息，減少了算法搜索時間；利用狀態(tài)轉(zhuǎn)移概率尋找下一個節(jié)點(diǎn)時，采用了雙重輪盤算法，有效增加了可行解的搜索范圍，并改進(jìn)了自適應(yīng)蟻群信息素更新機(jī)制，避免信息素淹沒啟發(fā)因子，幫助算法跳出局部最優(yōu)解，進(jìn)而找到全局最佳路徑。

1 基本蟻群算法

在覓食過程中，單只螞蟻的行為比較簡單，然而蟻群卻能夠表現(xiàn)出及其復(fù)雜的行為。通過研究發(fā)現(xiàn)，螞蟻在尋找食物的過程中，會留下一種叫做信息素的物質(zhì)。所有的螞蟻均能感知這種物質(zhì)，并通過信息素的量來選擇前進(jìn)的方向。這種信息素具有疊加和揮發(fā)的雙重特性，于是大量螞蟻組成的蟻群集體行為就表現(xiàn)出一種信息正反饋現(xiàn)象，即某路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。經(jīng)過一段時間便會形成一條高濃度信息素路徑，該路徑便是螞蟻搜索到的尋找食物的最短路徑。受此啟發(fā)，Dorigo M于1991年提出了蟻群算法。

基本蟻群算法求解TSP的步驟如下。

（1）信息素初始化

信息素初始化：

其中τij(0)表示初始時刻城市i與城市j之間的信息素濃度；const為常數(shù)，一般取值為0。

（2）狀態(tài)轉(zhuǎn)移

狀態(tài)轉(zhuǎn)移：

（3）信息素的更新

蟻群在轉(zhuǎn)移過程中，要對殘留信息進(jìn)行更新處理。同時，考慮到信息素的揮發(fā)，t+n時刻路徑(i, j)上的信息量可按以下規(guī)則進(jìn)行調(diào)整：

其中，ρ表示信息素?fù)]發(fā)系數(shù)，其取值范圍為ρ? ［0,1］；Δτij(t)表示本次循環(huán)中路徑(i, j)上的信息素增量。

Dorigo M根據(jù)信息素更新策略的不同，提出了三種信息素更新模型，分別稱之為Ant-Cycle模型﹑Ant-Quantity模型及Ant-Density模型?？紤]到更新信息素濃度的全局性，通常使用Ant-Cycle模型：

其中，Q表示信息素強(qiáng)度，Lk表示第k只螞蟻在本次循環(huán)中所走路徑的總長度。

2 基于城市權(quán)重的蟻群算法

針對蟻群算法存在收斂時間長，易陷入局部最優(yōu)解的問題，本文提出了基于城市權(quán)重的蟻群算法（ACAWC）。該算法主要實(shí)現(xiàn)策略包括初始信息素濃度分布﹑狀態(tài)轉(zhuǎn)移概率更新﹑信息素更新機(jī)制調(diào)整三部分。

2.1 初始信息素濃度分布

基本蟻群算法中，初始的信息素矩陣為常矩陣，則轉(zhuǎn)移概率只依賴于城市間距離，會導(dǎo)致螞蟻從開始就放棄最優(yōu)路徑上的較長距離。為了解決這一問題，吳華鋒等[9]提出基于城市間的距離與城市規(guī)模之商作為初始信息素分布矩陣：

但該思想存在較為明顯的缺陷。初始信息素濃度與啟發(fā)信息成反比，雖然在一定程度上削弱了啟發(fā)信息的作用，使選擇最優(yōu)路徑上較長路徑的概率增加，但并不是每一條較長路徑都在最佳路徑上，相反，絕大多數(shù)較長路徑都不在最佳路徑上。因此，尋找平衡時間和空間的初始信息素濃度矩陣尤為重要。

針對這種缺陷，在算法初期首先計算每個城市在城市網(wǎng)中的權(quán)重，即每個城市到其他各個城市距離之和與城市規(guī)模之商，再根據(jù)兩城市權(quán)重的平均值初始化信息素，利用全局信息量，可有效降低放棄最優(yōu)路徑上較長距離的同時，減少蟻群的搜索時間。因此，改進(jìn)后的蟻群算法，信息素初始分布矩陣為：

2.2 狀態(tài)轉(zhuǎn)移概率更新機(jī)制

基本蟻群算法及其之后的改進(jìn)只是把兩城市距離的倒數(shù)作為期望因子，即ηij(t)=1/dij。選擇下一個城市時，只看到目前兩城市之間距離，而忽略了下一個城市與其他城市的關(guān)系?；谏衔奶岢龅某鞘袡?quán)重思想，提出了基于城市權(quán)重的期望啟發(fā)信息：

改進(jìn)后蟻群算法的狀態(tài)轉(zhuǎn)移概率計算公式仍然依據(jù)基本蟻群算法，即：

通常，螞蟻k在選擇下一個要遍歷的城市時，通常采用賭盤算法[8]，即依據(jù)概率并結(jié)合隨機(jī)特性來選擇下一個城市。本文引入雙重賭盤算法，首先根據(jù)賭盤算法產(chǎn)生一系列解，這些解就是在選擇下一個城市時概率比較大的城市的一個集合F；然后，再次利用賭盤算法在集合F中尋找下一個城市。這樣就大大降低了算法陷入局部最優(yōu)解的概率。

2.3 信息素更新機(jī)制調(diào)整

在基本蟻群算法中，信息素濃度的大小將直接影響尋找下一節(jié)點(diǎn)的轉(zhuǎn)移概率。隨著迭代的進(jìn)行，信息素將逐漸集中到較少邊上，導(dǎo)致搜索過程總是在這幾條邊上進(jìn)行，進(jìn)而求得相似解而陷入局部最優(yōu)。吳華鋒等[9]引入了路徑貢獻(xiàn)度（CDSP）的概念，通過對最優(yōu)路徑上較長路徑進(jìn)行信息素二次強(qiáng)化，增大較長路徑被選擇的概率，在一定程度上解決了局部最優(yōu)解的情況。

本文通過引入自適應(yīng)信息素?fù)]發(fā)系數(shù)，從而隨著迭代次數(shù)的增加，信息素?fù)]發(fā)系數(shù)逐漸增大，避免期望信息被信息素淹沒，同時降低螞蟻對信息素的依賴。但是，同時為了防止信息素流失過快，不妨對信息素?fù)]發(fā)系數(shù)設(shè)置最大值（假設(shè)為0.2，依仿真實(shí)驗(yàn)數(shù)據(jù)而定）：

同時，不妨借鑒上文中提到的路徑貢獻(xiàn)度（CDSP）的概念，更新公式如下：

rand是對路徑貢獻(xiàn)度大的路徑的信息素濃度隨機(jī)加強(qiáng)，q0則是路徑貢獻(xiàn)度閾值。

具體算法流程如下：

（1）參數(shù)初始化。蟻群算法中主要參數(shù)有α、β和螞蟻的數(shù)目m等。α的大小表明每個路徑上的信息量的受重視程度；β的大小代表了啟發(fā)式因子的受重視程度。螞蟻數(shù)目越多，算法的全局搜索能力越強(qiáng)；相反，則算法的收斂速度將減慢。

（2）將m只螞蟻隨機(jī)放在n個城市上，根據(jù)雙重賭盤算法選取下一個城市。

（3）修改禁忌表。

（4）重復(fù)（2）和（3），直到所有螞蟻?zhàn)弑樗谐鞘小?/p>

（5）判斷是否滿足迭代結(jié)束條件Nc≥Nmax，滿足則結(jié)束循環(huán)并輸出結(jié)果；若不滿足，更新信息素，并清空禁忌表，進(jìn)行下一次循環(huán)。

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

為了驗(yàn)證ACAWC算法的收斂性和可靠性，本文將從TSPLIB中選取14個使用歐式距離的TSP實(shí)例進(jìn)行測試[10-11]，每個實(shí)例運(yùn)行5次。仿真實(shí)驗(yàn)在CPU為Intel(R) Core(TM)型號為i5-4590@3.30 GHz環(huán)境下使用MATLAB 2010b進(jìn)行編程測試；算法使用各個參數(shù)由經(jīng)驗(yàn)和試算得來，初始值設(shè)置如表1所示，仿真結(jié)果依次如圖1﹑圖2所示。。

表1 算法的參數(shù)設(shè)置

圖1 基本蟻群算法求解st70最優(yōu)路徑

圖2 ACAWC算法求解st70最優(yōu)路徑

對比圖1﹑圖2發(fā)現(xiàn)，在求解st70問題時，ACAWC算法在蟻群迭代到20次左右時，最優(yōu)路徑就已經(jīng)低于800，而基本蟻群算法直到60次左右才達(dá)到上述效果?？梢姡珹CAWC算法與基本蟻群算法相比，效率至少提高了一倍。為了說明ACAWC算法效率的普遍性，另外附上求解eil76和rat99時兩種算法的對比圖，如圖3﹑圖4﹑圖5和圖6所示。在效率明顯提高的同時，又對比幾種算法在尋找最優(yōu)解方面的能力，具體如表2所示。

圖3 基本蟻群算法求解eil76最優(yōu)路徑

圖4 ACAWC算法求解eil76最優(yōu)路徑

圖5 基本蟻群算法求解rat99最優(yōu)路徑

圖6 ACAWC求解rat99最優(yōu)路徑

為了更加形象地說明仿真達(dá)到的效果，挑選路徑長度在400～1 500之間的5個城市節(jié)點(diǎn)庫來對比基本蟻群算法最優(yōu)解﹑文獻(xiàn)[8]改進(jìn)蟻群算法最優(yōu)解﹑本文改進(jìn)蟻群算法最優(yōu)解和國際最優(yōu)解，結(jié)果如圖7所示。

圖7 三種算法與國際最優(yōu)解路徑長度對比

表2 基本蟻群算法與改進(jìn)后蟻群算法路徑長度對比

4 結(jié) 語

本文提出了基于城市權(quán)重的蟻群算法(ACAWC)，并應(yīng)用該算法來解決TSP問題。從仿真結(jié)果可以看出，改進(jìn)的蟻群算法求得的最優(yōu)解比基本蟻群算法提高了10%～15%，比文獻(xiàn)[8]改進(jìn)的蟻群算法提高了6%～8%，同時優(yōu)化效率提高了將近一倍。然而，由于具體城市不確定性及參數(shù)選擇存在差異以及迭代次數(shù)的限制，ACAWC算法優(yōu)化解與國際最優(yōu)解還存在差距，但在可接受范圍之內(nèi)。本文在狀態(tài)轉(zhuǎn)移概率機(jī)制選擇上，采用了雙重賭盤算法，雖然最優(yōu)解得到了很大程度改善，但是雙重賭盤算法需要進(jìn)行兩次狀態(tài)轉(zhuǎn)移概率的計算，這無疑會造成優(yōu)化效率的下降。隨著城市節(jié)點(diǎn)的增多，這種效率下降尤為明顯。因此，未來如何更好地權(quán)衡效率與最優(yōu)解，將成為研究的重點(diǎn)。同時，如何將上述思想應(yīng)用于解決大規(guī)模TSP問題以及更多組合優(yōu)化問題將成為研究的方向。

[1] 朱獻(xiàn)文,李福榮.求解旅行商問題的幾種智能算法[J].計算機(jī)與數(shù)字工程,2010,32(01):32-35.

ZHU Xian-wen,LI Fu-rong.Several Intelligent Algorithms for Solving Traveling Salesman Problem[J].Computer& Digital Engineering,2010,32(01):32-35.

[2] COLORINI A,DORIGO M,MANIEZZO V,et al.Distributed optimization by ant colonies[C].Proceedings of the 1st European Conference on Artificial Life,1991:134-142.

[3] DORIGO M,MANIEZZO V,COLORINI A,et al.Ant System: Optimization by a Colony of Cooperating Agents[J].IEEE Transactions on Systems Man and Cybernetics-Part B,1996,26(01):29-41.

[4] 丁建立,陳增強(qiáng),袁著祉.遺傳算法與螞蟻算法的融合 [J].計算機(jī)研究與發(fā)展,2003,40(09):1351-1356.

DING Jian-li,CHEN Zeng-qiang,YUAN Zhu-zhi.The Combination of Genetic AlgorithMand Ant Algorithm[J]. Journal of Computer Research and Development, 2003,40(09):1351-1356.

[5] 黃國銳,曹先彬,王煦法.基于信息素擴(kuò)散的蟻群算法[J].電子學(xué)報,2004,32(04):865-868.

HUANG Guo-rui,CAO Xian-bin,WANG Xu-fa.Ant Colony Algorithm based on Pheromone Diffusion[J]. ACTA ELECTRONICA SINISC,2004,32(04):865-868.

[6] 田富鵬.改進(jìn)型蟻群算法及其在TSP中的應(yīng)用[J].蘭州大學(xué)學(xué)報:自然科學(xué)版,2005,41(02):78-80.

TIAN Fu-peng.An Improved Model of Ant Colony AlgorithMand Its App lication in TSP[J].Journal of Lanzhou University(Natural Science),2005,41(02):78-80.

[7] 袁東輝,劉大有,申世群.基于蟻群—遺傳算法的改進(jìn)多目標(biāo)數(shù)據(jù)關(guān)聯(lián)方法[J].通信學(xué)報,2011,32(06):17-23.

YUAN Dong-hui,LIU Da-you,SHEN Shi-qun.An Improved multi objective data association method based on ant colony and genetic algorithm [J].JOURNAL OF CHINA INSTITUTE OF COMMUNICATIONS, 2011,32(06):17-23.

[8] 姜坤霖,李美安,張宏偉.面向旅行商問題的蟻群算法改進(jìn)[J].計算機(jī)應(yīng)用,2015,35(S2):114-117.

JIANG Kun-lin,LI Mei-an,ZHANG Hong-wei.Improved Ant Colony Algorithm for Travelling Salesman Problem[J]. Journal of Computer Applications,2015,35(S2):114-117.

[9] 吳華鋒,陳信強(qiáng),毛奇凰等.基于自然選擇策略的蟻群算法求解TSP問題[J].通信學(xué)報,2013,34(04):165-170.

WU Hua-feng,CHEN Xin-qiang,MAO Qi-huang,et al.Improved Ant Colony Algorithm based on Natural Selection Strategy for Solving TSP Problem [J].Journal on Communications,2013,34(04):165-170.

[10] TSPLIB[EB/OL].http://www.iwr.uni-heidelberg.de/groups/ comopt/software/TSPLIB95/.

[11] WANG L,ZHU Q.An Efficient Approach for Solving TSP:the Rapidly Convergent Ant Colony Algorithm[C]. Fou rth In ternational Con ference on Natu ral Computation,2010:448-452.

Ant Colony A lgorithm based on W eight of City and Its App lication in TSP

MA Qing-xin, ZHANG Da-min, ZHANG Bin, A Ming-han

(College of Data and Information Engineering, Guizhou University, Guiyang Guizhou 550025, China)

Ant colony algorithm usually exhibits strong applicability in solving NP complete problems, but easily falls into the defect of local optical solution for its fairly slow convergence rate. An ant colony algorithm based on the weight of city (ACAWC) is thus proposed. The modified algorithm, by using the proportion of urban distance in the whole city network, coordinates and arouses the information role, and again with double roulette algorithMand double randomness idea, enhances the probability of jumping out from the local optimal solution. By modifying the pheromone update mechanism based on path contribution, the algorithm is improved in its convergence speed. The simulation experiments indicate that the optimal solution froMaCAWC algorithm could acquire an improvement of 10%～15% as compared with the basic ant colony algorithm, and in addition, its convergence speed is also improved to a certain extent.

weight of city; ant colony algorithm; TSP; pheromone

TP393

A

1002-0802(2016)-11-1493-06

10.3969/j.issn.1002-0802.2016.11.015

馬清鑫（1989—），男，碩士，主要研究方向?yàn)槿斯ぶ悄埽?/p>

張達(dá)敏（1967—），男，博士，教授，通訊作者，主要研究方向?yàn)橛嬎銠C(jī)應(yīng)用技術(shù)﹑網(wǎng)絡(luò)擁塞控制；

張 斌（1990—），男，碩士，主要研究方向?yàn)橛嬎銠C(jī)應(yīng)用技術(shù)；

阿明翰（1992—），男，碩士，主要研究方向?yàn)閿?shù)據(jù)挖掘。

2016-07-08；

2016-10-17 Received date:2016-07-08;Revised date:2016-10-17

貴州省合作計劃項目(No.[2014]7002)；貴州大學(xué)研究生創(chuàng)新基金項目(No.2016069)

Foundation Item:Cooperative Project of Guizhou Province(No.[2014]7002);Graduate Student Innovation Foundation of Guizhou University(No.2016069)