求解TSP問題的改進蟻群算法研究

盧 曦

（南通理工學院 計算機與信息工程學院，江蘇 南通 226003）

求解TSP問題的改進蟻群算法研究

盧 曦

（南通理工學院 計算機與信息工程學院，江蘇 南通 226003）

文章提出了運用一種改進的蟻群算法，主要用來求解旅行商問題（Travelling Salesman Problem，TSP）。實驗表明，改進的蟻群算法一定程度上彌補了基本的蟻群算法容易陷入收斂停滯的缺點，且更容易發現更好性質的解。

蟻群算法；最優化路徑；旅行商問題

1 旅行商問題（TSP問題）

本文需要解決的旅行商問題，即Travelling Salesman Problem，簡稱TSP問題。假設有一名商人需要去n個城市販賣商品，該商人想要選擇一條最合理的線路，線路需要滿足以下要求：（1）每個城市只能到達一次；（2）線路需要回到商人第一個出發的城市；（3）必須是滿足（1）（2）條件的所有線路中最短的線路。它是組合優化中研究最多的問題之一，是一個經典的非確定性（Nondeterministic Poly-nomial，NP）難題。

2 普通蟻群算法

求解TSP問題此類NP問題的算法有很多，本文選取蟻群算法作為主要研究對象。自然界中螞蟻在尋覓食物時能夠自發的發現最優路徑，Marco Dorigo等人由此受到啟發，于1992年提出的一種新型智能算法即蟻群算法（Ant Colony Algorithm，ACA），又稱螞蟻算法。蟻群算法是一種模擬進化算法，通過模擬螞蟻的行為特性中的內在搜索機制來尋求最優解。經實際研究表明，該算法在求解復雜優化問題例如NP問題方面具有諸多優良的性質。

事實上，在使用普通蟻群算法求解此類問題時經常會遇到一些問題，比如：算法所給出最優解并不理想，可能只是一些局部的最優解，而不是問題所希望的全局最優解。這很大程度上是由普通蟻群算法解的性質造成的。

在使用算法進行迭代求解的時候，一般開始的時候迭代收斂速度還比較理想，但當迭代過程進行到后期，可能在出現一些糟糕的停滯現象。這些我們不希望遇到的停滯現象通常會出現在某個（些）局部最優解的鄰域附近。

普通蟻群算法的搜索時間會比較久一點。首先這和算法的時間復雜度有關。其次這和算法中多個螞蟻運動過程的隨機處理有關。

3 改進蟻群算法求解TSP問題

3.1 算法設計思路

TSP問題屬于NP完全組合問題，通常的解決方法可以分為精確算法（Exact Algorithms）與啟發式算法（Heuristics Algorithms）。

一般來說，精確算法在能夠求解的情況下，獲得的解通常比啟發式智能算法要更優。但是精確算法基于嚴謹的數學方式來求解，必然會遇到指數爆炸問題，這使得此類算法難以求只能有效的求解一些中小規模的確定性NP問題。對于實際生活中會遇到的大規模NP問題精確算法難以解決，而啟發式算法卻總可以在有限時間內找到可行解或者較滿意的次優解。

蟻群算法是啟發式算法中的一種，在本文中已經具體說明了基本蟻群算法的優缺點。那么我們是不是可以針對原有算法的一些不足之處，引進Hybrid思想，將啟發式的蟻群算法和精確計算相結合，從而提高算法的計算效率。

3.2 算法基本原理

以TSP問題為例，首先通過蟻群算法其進行初始的全局計算，這時候我們可以得到一組數據，即每條路徑上的信息量。這組數據很關鍵，螞蟻會通過路徑上留下的信息量來選擇路徑，信息量越大螞蟻選擇的概率則越大，這也是對節點進行分類計算的判斷根據。

我們在所有的節點中找到一些特殊的節點，這些節點與之關聯的信息量均比較大。對這些特殊的節點再次進行蟻群算法，因為大大地降低了計算的規模，所以無論是收斂速度還是計算時間都在一定程度上得到了提高。如圖1所示，這些節點是被篩選出的信息量關聯度大的相關節點，圖中所勾畫的回路是第二次進行蟻群算法所得到的最短路徑。

圖1 特殊節點間的最短路徑

我們可以分別以這些節點為起點/終點，以兩點間的連線為軸，計算出非特殊節點與這些軸之間的距離，從而將其他非特殊節點進行分類。如圖1所示，若某非特殊節點a與軸8～10的距離比相對其他軸線的距離都要短，則可以將節點a劃歸到（8，10）的區間內。如此類推，在圖1中就可以把全部節點完全劃分成20個小的局部空間。

在所得到的局部范圍內，由于計算規模的大大降低，復合了精確計算的條件，所以我們可以選擇精確計算中的動態規劃算法，以特殊節點為起點/終點，找到兩點間的最短路徑。這樣將所有子空間的最短路徑都求出后相連接，即可得到全局的最短路徑。

在求出全局的最短路徑之后，我們對這條最短路徑上的信息量進行更新，這樣一次迭代完成。如此反復迭代，得到最后的最優解。

3.3 改進蟻群算法求解TSP問題

3.3.1 蟻群系統模型

以TSP問題為例，說明改進后的蟻群系統模型。

假設共有m只螞蟻，n個城市，dij表示城市i和城市j之間距離，τij（t）表示在t時刻城市i和城市j之間的信息量，初始時刻τij（0）=C（C是初始信息量，為常數）。表示在t時刻螞蟻k從城市i移動到城市j的概率，計算公式如下。

allowdk表示螞蟻k下一步允許選擇到達的城市集合，α表示在螞蟻選擇路徑時受信息量的影響大小，ηij表示螞蟻k從城市i移動到城市j的期望值，β表示該期望值ηij的影響大小。經過n個時刻，這只螞蟻能夠走完所有城市，我們認為每只螞蟻所走過的路徑就是一個解。此時需要對路徑上的信息量進行更新：

ρ∈（0，1）表示信息量τi（jt）根據時間產生的衰減度表示螞蟻k從城市i移動到城市j時在路徑ij上留下的信息量。

參照基本蟻群算法求出特殊節點的最短路徑，記錄下特殊節點間的路徑Rij。dRi表示非特殊節點于這些路徑的垂直距離。可以對非特殊節點分類：

可以使用固定的迭代次數停止算法，也可以選擇在收斂趨勢不明顯的時候停止計算。

3.3.2 算法流程圖

改進蟻群算法執行流程圖，如圖2所示。

3.3.3 算法偽代碼實現步驟

Step 1：NC ←0（NC為迭代步數或搜索次數），NA←0（NA記錄），對各τi（jt）和Δ（tt））完成初始化，并將m個螞蟻隨機地放在n個頂點上；

Step 4：如果NA=0，計算出，并且排序選出較大的約1/10的特殊節點，否則，跳至step 7；

Step 5：NA=NA+1；

Step 6：跳轉Step 2；

Step 7：根據公式（1）將節點進行分類；

Step 8：將分好類的節點以特殊節點為始/終點，動態規劃算法得子空間最好解；

Step 9：合并子解，得到全局最優解；

Step 10：按公式（2）更新路徑上的信息量；

Step 12：若NC＜預定的迭代次數或者找到的都是相同解，則轉Step 2，否則輸出最優解。

在求解較大規模TSP問題時，可以簡化計算，將公式（2）修改為公式（3）：

圖2 改進蟻群算法執行流程圖

4 結語

本文首先簡單介紹了TSP問題的產生，以及使用普通蟻群算法求解TSP問題時的優缺點。然后文章主要針對其不足之處，對算法進行了改進，提出了一種新的蟻群算法。改進的蟻群算法主要在局部方面進行改進，根據全局信息素對節點進行分類化，對計算空間進行劃分，在局部采用動態規劃精確計算，而在全局方面仍然保留蟻群算法能夠優化控制的優勢。最后本文針對TSP問題給出改進蟻群算法的實現步驟與計算機偽代碼。

［1］馬良，王龍德.背包問題的螞蟻優化算法［J］.計算機應用，2001（8）：4-5.

［2］吳斌，史忠植.一種基于蟻群算法的TSP問題分段求解算法［J］.計算機學報，2001（12）：1328-1333.

［3］黎鎖平，張秀媛，楊海波.人工蟻群算法理論及其在經典TSP問題中的實現［J］.交通運輸系統工程與信息，2002（3）：25.

［4］項寶衛，應建健.蟻群算法研究綜述［J］.臺州學院學報，2007（6）：20.

Study on the improved Ant Colony Algorithm for solving TSP

Lu Xi

（Computer and Information Engineering School of Nantong Institute of Technology，Nantong 226003，China）

This paper proposes an improved ACA（Ant Colony Algorithm），which is mainly used to solve TSP （Travelling Salesman Problem）.The experiments show the improved ACA makes up the shortcomings of the basic ACA which is easy to fall into the stagnation of convergence，and it is easier to find a better solution.

Ant Colony Algorithm；optimization path；Travelling Salesman Problem

南通理工學院科研項目；項目編號：201410。

盧曦（1984—），女，江蘇南通，碩士，講師；研究方向：軟件技術。