改進蟻群算法在TSP 問題中的應用

徐書揚，王海江

（浙江科技學院，杭州310023）

0 引言

蟻群算法是一種于1992 年由文獻[1]用于尋找最優路徑的經典概率型算法。與其他啟發式算法相比，蟻群算法具有良好的魯棒性（可改進方向多，適用于多種問題的解決）以及優越的全局搜索能力（蟻群算法往往以全局最優為目標解決問題）。因此，蟻群算法在多個領域中得以應用，例如：區域建設[2]、路徑規劃[3-6]、影像測量[7]、調度管理[8-9]等。然而，蟻群算法也同樣存在一些不足之處，例如：在處理信息量較大的問題時迭代速度過慢，算法易陷入局部最優而錯過最優解，對參數的設置有很高的要求，錯誤的參數設置容易導致結果誤差過大等[10-11]。

針對傳統蟻群算法存在的問題，不少學者提出蟻群算法的改進方案來解決蟻群算法本身的缺陷。例如，在TSP（Traveling Salesman Problem）問題的解決中，黃澤斌[12]曾提出利用K-近鄰分區方法對大規模TSP問題進行聚類分區，然后利用蟻群算法對每個子區域進行最優化求解，最后再將連接這些子區域之間距離最近的點連接起來實現TSP 問題的求解，該算法相較于傳統算法有更快的收斂速度，并且在處理信息量較大的圖中有更小的算法復雜度，節約了解決問題的時間成本。但是，連接兩個子區域的方式為尋找子區域之間距離最近的點將其相連，意味著連接兩個子區域之間的路徑有且僅有一條，從而降低了算法探尋更優路徑的可能性，使得結果易產生較大的偏差。在點與點的路徑規劃問題中俞燁[13]曾提出啟發式因子的改進方案，該方案令啟發式因子既考慮到下一步距離最近的結點，也考慮到下一步所到結點距離終點的距離，從而在圖像信息量較小時一定程度上避免了算法陷入局部最優，也加快了算法初期的收斂速度。但是這樣的改進策略僅適用于信息量較小的圖，當圖中信息量較大時，對下一結點到終點距離的考慮反而會是干擾算法收斂的因素。Stützle T[14]曾提出最大-最小蟻群系統的概念，在每次迭代中僅更新最優路徑上的信息素，此方法加快了算法收斂的速度，但是同時也增大了算法陷入局部最優的可能。

上述算法一定程度上解決了蟻群算法的種種弊端，在某一特定場合下比起傳統蟻群算法有著更好的適用性。但是在非特定情況下或多或少存在一些弊端。本文以TSP 問題的討論為基，對蟻群算法做出改進，以全局最優為目標，降低結果陷入局部最優的概率，提高蟻群算法求解結果的精確度。在本問題的討論中，蘇曉琴[15]曾提出根據時間的推進改進信息迭代方案，使得算法能更快的收斂，這樣的改進一定程度上能提高算法的求解精度，但是依舊未能解決算法易陷入局部最優的情況。黃澤斌[12]曾提出用近鄰分區的方法來提高算法的求解精度，但是這樣的方法僅適用于大規模求解TSP 問題。在TSP 問題的解決中上述算法相較于傳統蟻群算法有著明顯的優勢，但是，仍未解決蟻群算法的一大弊端：易陷入局部最優。本文提出一種蟻群算法的改進方案，使得算法能一定程度上避免陷入局部最優的情況，提高算法整體的求解精度。

1 TSP問題和蟻群算法

1.1 TSP問題的描述

TSP 問題又譯為旅行推銷員問題、貨郎擔問題，是數學領域中著名問題之一。它描述了以下場景：有一名旅行商人要拜訪各個城市，城市的數量為n，限制條件為每個城市僅拜訪一次且所有城市必須都需要拜訪，優化目標為使得在拜訪完所有城市并最終回到起點的情況下旅行商人走過的總路徑長度最短。經典的TSP 問題中點與點之間的路徑長度為點與點之間的直線距離。本文將改進后的蟻群算法應用于TSP 問題的解決中，減少蟻群算法易陷入局部最優的情況，使得TSP 問題的求解有更高的精確度。

1.2 蟻群算法的描述

蟻群算法的思想來源于自然界螞蟻覓食，螞蟻在尋找食物源時，會在路徑上留下螞蟻獨有的路徑標識——信息素，螞蟻會感知其他螞蟻在各條路徑上留下的信息素，并根據各條路徑上的信息素濃度來選擇之后要走的路，路徑上留有的信息濃度越高，則螞蟻更傾向于選擇該路徑。在螞蟻選擇某條路徑后也會在改路徑上留下信息素吸引更多螞蟻選擇該路徑，隨著時間的推移，信息素濃度不斷增大，螞蟻選擇路徑的概率也隨之增高，由此形成了正反饋機制。由于蟻群算法的正反饋性，因此蟻群算法也屬于增強型學習算法的其中一種。

對于TSP 問題，設蟻群中螞蟻的數量為m，結點的數量為n，結點i 與結點j 之間的歐式距離為dij(t)，t 時刻結點i 與結點j 之間相連接的路徑上的信息素濃度為cij。初始時刻，螞蟻放置在不同結點里，且各結點連接路徑上的信息素濃度相同[13]，然后螞蟻按一定的概率選擇路線。不妨將Pk ij(t)設為t 時刻螞蟻k 從結點i 轉移到結點j 的概率。“螞蟻TSP”策略收到兩方面的左右，首先是訪問某結點的概率，這個概率的大小依賴于其他螞蟻釋放的信息素濃度。所以定義：

式中，nkij(t)為啟發函數，表示螞蟻從結點i 轉移到結點j 的概率；allowk為螞蟻k 下一步可轉移結點的集合，隨著時間的推移，allowk儲存的元素數量會減小，最終會變為空集合。a 為信息素重要程度因子。

與實際情況類似的一點是：隨著時間的推移，殘留在路徑上的信息素會逐漸揮發，螞蟻在經過路徑時殘留的信息素量也會逐漸等同于信息素揮發量，最終使信息素殘留量趨于穩定。令α表示信息素揮發程度，那么所有螞蟻遍歷完所有結點之后，各路徑上的信息素殘留量的數學表達式如下：

Δ為所有螞蟻在結點i 與結點k 連接路徑上釋放信息素而增加的信息素濃度，通常情況下：

式中，Q 為路徑信息素常量，l 為第k 只螞蟻所經過路徑的總長度。

2 蟻群算法的改進

2.1 初始信息素濃度的賦值

在傳統蟻群算法中，各條路徑上的初始信息素濃度相等，這意味著在第一次迭代時各個結點對螞蟻有相同的吸引力，這樣會造成以下兩個弊端[13]：

（1）初始信息素的濃度不具有指導性，使得算法收斂速度過慢。

（2）前幾次迭代螞蟻有概率向錯誤的路徑轉移，信息素在錯誤的路徑上殘留，導致算法易陷入局部最優。

為了解決以上兩個問題，本文對信息素濃度賦以合理的初值，確保算法向正確的方向收斂。初始信息素濃度的具體數學表達式如下：

其中，k0為常數，確保各條路徑上初始信息素濃度在合理的范圍內，dij為結點i 與結點j 的歐幾里得距離（直線距離），τij為連接結點i 與結點j 的路徑的初始信息素濃度。dij與τij呈反比關系，意味著初次迭代中距離越短的路徑對螞蟻有越強的吸引力，使各條路徑上的初始信息素濃度在算法收斂的過程中有著合理的導向性，增大了最優路徑被選擇的概率。一定程度上加快了算法的收斂速度并避免陷入局部最優的情況。

2.2 信息素的更新策略

由于蟻群算法的正反饋機制，隨著時間的推移，蟻群算法會逐漸收斂，各條路徑上的信息素濃度更多的集中在當前最優路徑上，使得每次螞蟻所選擇各條路徑的概率趨于穩定，此時容易忽略潛在的最優路徑，那么便有了陷入局部最優的可能。為了增強算法的全局搜索能力，減少局部最優發生的概率，需要提出一種更合理的信息更新策略。在迭代次數較小時，需要保證螞蟻在路徑上留下信息素濃度足夠高，以確保迭代初期算法能更快的收斂，而當算法收斂到一定程度時，如果多次迭代中算法所求得最優路徑長度一直未發生變化，那么算法既有可能已經得到了正確結果，也有可能陷入局部最優得到了有一定偏差的結果。此時為了避免算法陷入局部最優，需要適當增加信息素揮發量以及減小螞蟻走過路徑留下的信息素量，避免信息素過于集中，使得螞蟻能有更大概率去探索潛在的最優路徑，提高算法的全局搜索能力。為方便算法的描述，給出如下定義：

定義如果存在某個時間節點T0，在T0之前的固定時長范圍內，算法所探索的最優路徑未發生變化，則稱該時間結點T0為信息素發散點。

每次迭代信息素更新的具體數學表達式如下：

式中，τij為連接結點i 與結點j 的路徑上的信息素濃度，Δτk ij為本次迭代中螞蟻k 在路徑上留下的信息素量，ρ為信息素揮發比率，a,b 為常數，控制當時間t 在過了信息素發散點后信息素的增加量和揮發量。

2.3 信息素矩陣的重置

盡管式（5）和文獻[15]所給出的信息素更新方案能一定程度上避免陷入局部最優，但是并不能完全排除陷入局部最優的可能，為了更大程度上避免陷入局部最優的可能，我們在這里引入了熔斷機制——當時間達到信息素發散點后的一段固定時間內，如果最優路徑并沒有發生變化，則將信息素矩陣按式（4）的方式重新進行賦值。

2.4 改進蟻群算法的具體流程

圖1 改進后蟻群算法流程圖

3 仿真實驗

為對改進后蟻群算法的有效性與合理性進行驗證，在五組結點位置坐標互不相同的平面圖上通過MATALB 2018b 進行編程，用改進后的算法與傳統蟻群算法進行比對。初始參數如下：α=1，β=5，ρ=0.1，Nmax=800，T=70，m=6，a=0.02，b=0.02，k0=100。

按以上參數分別代入改進后蟻群算法與傳統蟻群算法，對每種情況分別求解1000 次求得結果如表1 所示。在得到表1 所示結果后對兩種算法的正確收斂情況和平均路徑長度減少情況進行比對后求得結果如表2 所示。

表1 兩種算法正確收斂率與絕對誤差值表

表2 算法正確收斂增加率與絕對誤差值減少率表

對比五種不同情況下的改進后蟻群算法與傳統蟻群算法的正確收斂率和絕對誤差，我們可以發現在相同的參數設置下改進后的蟻群算法能更好地規避局部收斂的情況，增加算法正確收斂的比率，從而大大減小求解誤差，得到更精確的答案。

4 結語

通過對蟻群算法的改進，使得蟻群算法在解決TSP 問題的過程中能更有效地規避算法陷入局部收斂的情況，提高算法的全局搜索能力，從而提高結果求解的精確度。然而，在本文對算法的改進中要求足夠多的迭代次數以判別算法可能陷入局部收斂的情況，這是采用本文提出的改進方法的局限性。另外，本文對算法引入了新的參量，對這些參量賦以不同的值會對結果產生不同程度的影響，如何這些參數設置不當，會使得算法的全局搜索能力大大下降。因此，合理設置這些參數的值成為了本文算法應用的一個難點。但總體來說，本文提出的改進蟻群算法能很大程度上克服蟻群算法易陷入局部最優的弊端，在求解諸如TSP 問題之類的最短路徑問題中有較好的適用性。