基于城市權重的蟻群算法及其在TSP中的應用*

馬清鑫，張達敏，張 斌，阿明翰

（貴州大學 大數據與信息工程學院，貴州 貴陽550025）

基于城市權重的蟻群算法及其在TSP中的應用*

馬清鑫，張達敏，張 斌，阿明翰

（貴州大學 大數據與信息工程學院，貴州 貴陽550025）

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

城市權重；蟻群算法；TSP；信息素

0 引 言

TSP（Traveling Salesman Problem）問題又稱旅行商問題或最短路徑問題。通常可以描述為：已知N個城市及相互間的距離，旅行商從某城市出發訪問各城市且僅訪問一次后再回到原點的一條最短巡回路徑。作為典型的NP-C問題，旅行商問題已被廣泛應用于車間作業調度﹑網絡路由布設等方面。為了有效解決TSP問題，許多啟發式搜索算法被用來解決這一問題，如遺傳算法（GA）﹑蟻群算法（ACA）﹑模擬退火算法（SAA）﹑人工免疫算法（AIA）等[1]。其中，因蟻群算法類似一個增強型學習系統，具有正反饋﹑分布式﹑并行式﹑自組織等優點，使得在解決NPC問題時具有獨特的優勢。然而，信息素反饋機制有其明顯的缺陷。信息素反饋機制過強，會使算法出現停滯甚至陷入局部最優解；相反，要找出最佳路徑則需要較長的時間[2]。

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

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

1 基本蟻群算法

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

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

（1）信息素初始化

信息素初始化：

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

（2）狀態轉移

狀態轉移：

（3）信息素的更新

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

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

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

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

2 基于城市權重的蟻群算法

針對蟻群算法存在收斂時間長，易陷入局部最優解的問題，本文提出了基于城市權重的蟻群算法（ACAWC）。該算法主要實現策略包括初始信息素濃度分布﹑狀態轉移概率更新﹑信息素更新機制調整三部分。

2.1 初始信息素濃度分布

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

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

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

2.2 狀態轉移概率更新機制

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

改進后蟻群算法的狀態轉移概率計算公式仍然依據基本蟻群算法，即：

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

2.3 信息素更新機制調整

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

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

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

rand是對路徑貢獻度大的路徑的信息素濃度隨機加強，q0則是路徑貢獻度閾值。

具體算法流程如下：

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

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

（3）修改禁忌表。

（4）重復（2）和（3），直到所有螞蟻走遍所有城市。

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

3 仿真實驗與分析

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

表1 算法的參數設置

圖1 基本蟻群算法求解st70最優路徑

圖2 ACAWC算法求解st70最優路徑

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

圖3 基本蟻群算法求解eil76最優路徑

圖4 ACAWC算法求解eil76最優路徑

圖5 基本蟻群算法求解rat99最優路徑

圖6 ACAWC求解rat99最優路徑

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

圖7 三種算法與國際最優解路徑長度對比

表2 基本蟻群算法與改進后蟻群算法路徑長度對比

4 結 語

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

[1] 朱獻文,李福榮.求解旅行商問題的幾種智能算法[J].計算機與數字工程,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] 丁建立,陳增強,袁著祉.遺傳算法與螞蟻算法的融合 [J].計算機研究與發展,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] 黃國銳,曹先彬,王煦法.基于信息素擴散的蟻群算法[J].電子學報,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] 田富鵬.改進型蟻群算法及其在TSP中的應用[J].蘭州大學學報:自然科學版,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].通信學報,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].計算機應用,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] 吳華鋒,陳信強,毛奇凰等.基于自然選擇策略的蟻群算法求解TSP問題[J].通信學報,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—），男，碩士，主要研究方向為人工智能；

張達敏（1967—），男，博士，教授，通訊作者，主要研究方向為計算機應用技術﹑網絡擁塞控制；

張 斌（1990—），男，碩士，主要研究方向為計算機應用技術；

阿明翰（1992—），男，碩士，主要研究方向為數據挖掘。

2016-07-08；

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

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

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