改進的蟻群算法在ＴＳＰ中的應用

禹旺明　熊紅云

摘要：介紹了蟻群算法的特點，提出了基于蟻群算法的TSP問題的求解方法，并分別建立基本蟻群算法及MAX—MIN蟻群算法模型，并引入“三步走”法確定模型參數的最優組合，還結合了交叉局部優化相關的求凸殼頂點的算法進行預處理，進行仿真分析比較。實驗結果表明基于MMAS模型相對于基本蟻群算法模型，有比較好最短路徑選擇能力及良好的可擴展性能，能夠較好地適應物流配送系統的要求。

關鍵詞：TSP；MMAS；信息素；三步走法

中圖分類號：F224文獻標識碼：A文章編號：1002-3100(2009)01-0027-03

Abstract: Introduces the features of ant colony optimization, puts forward solving method of TSP based on ant colony optimization, establishes these models of basic ant colony optimization and max-min ant colony optimization respectively, ascertains optimum combination of model parametric by three-step method and carries out reprocessing combining algorithm of convex hull peak related to cross-regional optimization to carry on simulation analysis and comparison. The result indicates that MMAS is superior to basic ant colony optimization because it chooses the shortest path and better meets the demand of logistics distribution system.

Key words: TSP; MMAS; pheromone; three-step method

0引言

蟻群算法，是一種用來在圖中尋找優化路徑的機率型技術，由Marco Dorigo于1992年在他的博士論文中引入，其靈感來源于螞蟻在尋找食物過程中發現路徑的行為。蟻群算法是一種模擬進化算法，經過各種數值仿真結果表明該算法具有許多優良的性質，具有一種新的模擬進化優化方法的有效性和應用價值，是一種求解組合最優化問題的新型通用啟發式方法，具有正反饋、分布式計算和富于建設性的貪婪啟發式搜索的特點，通過建立適當的數學模型，可以解決一維靜態優化問題甚至多維動態組合優化問題。

本文采用蟻群算法對TSP問題進行研究，設計一個基本的蟻群算法解決最短路徑問題的模型，并提出一種最大——最小螞蟻系統（MMAS）模型，通過引入“三步走”法確定模型參數的最優組合，使所選參數讓性能達到最優；改進信息素更新規律及動態調整參數；并且引進去交叉局部優化相關的求凸殼頂點的算法，改進算法的局部搜索能力，對MMAS模型加以改進，最終使收斂速度和收斂效果達到令人滿意的結果。

1基本蟻群算法及MMAS在TSP中的應用

1.1問題描述

旅行商問題（traveling salesman problem，TSP）是著名NP 完全問題之一，常被用于測試和評價算法的性能。該問題可以簡單描述如下：有一個商人需要選擇一條最短的哈密頓回路拜訪各城市，即所有城市必須經過且只經過一次，而最后要回到原來出發的城市。如果用窮舉的辦法解決該問題，時間復雜度顯然是很大。當比較大的時候，現有的計算機是無法在可接受的時間內求解該問題的。因此很多高效的算法被用于嘗試求解TSP。本文采用蟻群算法對TSP問題進行研究，并通過基本蟻群算法、MMAS、改進的MMAS三者直接的比較得出最優解。

1.2算法設計

（1）蟻群算法構造TSP問題的基本數學模型

設bt表示t時刻位于元素i城市的螞蟻數目，m表示螞蟻的總數目，n表示城市的規模：

t+n=p?t+△t（1）

t為t時刻路徑i,j上的信息量，則m=bt在初始時刻各路徑上的信息量相等，并設0＝const。

螞蟻kk＝1,2,…,m在運動過程中，根據各路徑上的信息量決定其轉移方向。這里用禁忌表tabu（k＝1,2,3,…,m）來記錄螞蟻k當前所走過的城市，集合隨著tabu進化過程做動態調整。在搜索過程中，螞蟻根據各條路徑上的信息量及路徑的啟發信息來計算狀態轉移概率：pt表示在t時刻螞蟻k由城市i轉移到城市j的狀態轉移概率：

pt=，若j∈allowed0，否則 （2）

上式中，allowed＝C-tabu表示螞蟻下一步允許選擇的城市，C表示所有城市的集合；表示路徑i,j距離d的倒數即

=1/d；α、β分別表示信息素和路徑信息對轉移概率的影響程度。隨著時間的推移，以前留下來的信息素會逐漸揮發，用參數p表示信息素的揮發程度。經過n個時刻，每個螞蟻都完成一次循環，各條路徑上的信息素須做調整：

t+n=1-p?t+△ （3）

其中0＜p＜1，△表示本次循環中所有經歷過的路徑ij的螞蟻留在該路徑上的信息量的增量，局部調整用ant-cycle system調整信息素的方法：

△=Q/L，ant經過i,j0，否則 （4）

其中，Q為常數，表示螞蟻循環一周所釋放的總信息量，L表示ant在這次循環中所走的路徑的長度。

（2）最大最小信息素算法（MMAS）

MMAS與基本蟻群算法的主要區別在于把信息素數量＝,，較好地避免了搜索面的局部停滯（早熟現象）。每次迭代路徑上增加的最大信息素為1/Ls，其中Ls為對應全局最好解的路徑長度，更新最好解時，同時更新，，與信息素揮發因子p及Ls成反比，而與精英螞蟻的數目成正比。這里可按照以下策略動態的確定t和t。

①在最初信息素還未得到更新時（即產生第一代解前），采用下式確定t和t：

t=g （5）

t= （6）

②一旦信息素更新以后則采用下式才更新t：

t=g+ （7）

（3）去交叉局部優化

在這里引進去交叉局部優化相關的求凸殼頂點的算法對MMAS算法進行改進，凸殼問題（convex hull problem）是幾何學中的基本問題之一，在TSP中主要是對各點進行預處理。設S是平面上的非空點集，z和z是S中的任意兩點，t是0與1之間的任意實數。如果滿足公式8的點Z屬于S，則S為凸集。

z＝tz+1-tz0≤t≤1（8）

凸集S中的凸殼是包含S的周長最小的凸多邊形，凸殼必包含凸集，在TSP的預處理算法中，從某一凸殼的頂點開始，需要判斷與其不相鄰的下一個凸殼頂點是否在同一條直線上，若不是，則消去此線，然后以此類推對其余的凸殼頂點進行同樣處理。

2實例仿真

實例：中國的31個省會城市的坐標C=[1 304 2 312；3 639 1 315；4 177 2 244；3 712 1 399；3 488 1 535；3 326 1 556；3 238 1 229；4 196 1 004；4 312 790；4 386 570；3 007 1 970；2 562 1 756；2 788 1 491；2 381 1 676；1 332 695；3 715

1 678；3 918 2 179；4 061 2 370；3 780 2 212；3 676 2 578；4 029 2 838；4 263 2 931；3 429 1 908；3 507 2 367；3 394

2 643；3 439 3 201；2 935 3 240；3 140 3 550；2 545 2 357；2 778 2 826；2 370 2 975]，下面以31個城市的坐標為參考模型，分別建模仿真。

首先采用“三步走”方法選擇蟻群算法的最優參數組合：

（1）確定螞蟻的數目，當城市規模大致是螞蟻數目的1.5倍時，蟻群算法的全局收斂性和收斂速度都比較好。顯然這里螞蟻數目m選20比較適宜，城市n選31。

（2）參數粗調，調整取值范圍較大的信息啟發因子，期望啟發式因子β以及信息素強度Q等參數以得到較理想的解。經過調整取＝1.0，β＝5.0，Q=100。

（3）參數微調，在較小范圍內調整信息素揮發因子ρ。信息揮發素ρ取值為0.04。

實踐證明運用此方法后在減少計算量、快速搜索、收斂性、收斂速度等方面都有較好的效果。在MMAS模型中σ取5，0＝2。進行仿真后得到以下數據：圖1為運行10次基本蟻群算法模型得到的最優路徑；圖2為運行10次改進的MMAS模型得到的最優路徑；圖3為運行10次未改進的MMAS模型得到的最優路徑；表1中為兩種方法中的最短路徑的距離、平均距離、得到最優最小迭代數及平均迭代數。

上述數據表明改進型的MMAS對于基本蟻群算法及MMAS有一定的優越性，所得的結果在收斂性、穩定性、收斂速度等方面都有很大的改進，并且改進型MMAS不會出現圖3中的那種交叉路徑，能夠起到避免出現過早呆滯和及時糾正交叉的作用。圖4列出改進的MMAS在實驗過程中得到實時路徑數據。

3小結

本文主要是分析了蟻群算法及兩種類型蟻群算法在旅行商問題中的應用，通過MATLAB編程仿真了所建立模型，并把獲得的結果進行了比較分析，由實時路徑圖也可以看到此算法的穩定性能較強，能夠較好的應用來解決旅行商問題。

參考文獻：

[1] 段海濱. 蟻群算法原理及其應用[M]. 北京：科學技術出版社，2005.

[2] 趙霞. MAX-MIN螞蟻系統算法及其收斂性證明[J]. 計算機工程與應用，2006(8):70-72.

[3] 陳寶文，宋申民. 應用于車輛路徑問題的多蟻群算法[C]//第25屆中國控制會議論文集（下冊），2006:1723-1726.

[4] Yang Haiqing, Yang Haihong. An self-organizing neural network with convex-hull expanding property for TSP[C]//Neural Net-works and Brain, ICNN&B;' 05, International Conference on Volume1，2005:379-383.

[5] 蔡之華，彭錦國，高偉,等. 一種改進的求解TSP問題的演化算法[J]. 計算機學報，2005(28):823-828.

[6] 周培德. 求凸包定點的一種算法[J]. 北京理工大學學報，1993(13):69-72.

[7]趙凱，熊紅云. 模糊車輛配送問題的改進算法[J]. 物流科技，2008(2):24-27.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。