基于蟻群算法的TPS問題求解策略研究

徐 暢 張浩漩

(重慶郵電大學 重慶市 400000)

一、TSP問題是什么

(一)問題概述

TSP問題是一個典型的組合優化問題。比如，一位商人從自己的家鄉出發，希望能找到一個最短的道路，這一條道路要經過給定的所有城市，最后一個城市回到自己的家鄉。并且路過每個城市一次，且僅一次。如果構造一個圖：圖中的頂點為城市，頂點間的邊表示城市間的交通線，邊上的權為沿該交通線旅行的費用。那么，TSP問題就抽象為在這個圖中尋找最短哈密爾頓回路。

(二)數學模型

TSP問題表示為一個有N個城市的有向圖G=(N,A)。其中N={1,2,3,…，n}，城市之間的距離為(不一定是對稱矩陣，實際問題決定)。目標函數為(即總路徑長度)。

二、利用蟻群算法求解TSP問題

(一)蟻群算法概述以及基本原理

蟻群算法最初是通過對螞蟻的觀察，受蟻群行為特征啟發，而得出的一種算法。螞蟻是一種群居昆蟲，他們在日常生活中彼此協調，相互依賴，共同完成任務。單個螞蟻做不到的事情，整群螞蟻卻可以完成。[1]

螞蟻在運動過程中，能夠在它所經過的路徑上，留下一種稱之為信息素的物質。信息素是螞蟻個體之間信息傳遞交流的載體。螞蟻在運動時，能夠感知這種物質，并且習慣于追蹤此物質，追蹤過程中，繼續釋放信息素。一條路上的信息素蹤跡越濃，其它螞蟻將以越高的概率，跟隨此路徑，從而該路徑上的信息素蹤跡會被加強。因此，由大量螞蟻組成的蟻群的集體行為，便表現出一種信息，正反饋現象。某一路徑上走過的螞蟻越多，則后來者選擇該路徑的可能性就越大。螞蟻個體之間，就是通過這種間接的通信機制，實現協同搜索最短路徑的目標。蟻群算法這種啟發式算法的出現，解決了組合爆炸的問題，其可以在合理的時間范圍內找到可接受的最優解。

(二)TSP問題求解過程

基于以上所述的自然界中的蟻群行為，我們可以將TSP問題抽象為求解最短的螞蟻覓食路徑。我們人工構建的蟻群具有一定的記憶能力，能夠記下已經訪問的城市。同時，信息素衡量標準可以改變，螞蟻每次選擇的下一個城市是確定的，而不是盲目的，通過概率計算下一個所要經過的城市。[2]

同時，我們將TSP問題中所給的城市畫為一無向圖，在蟻群算法中，旅行商，即模型中的螞蟻，在圖的鄰接點之間不斷移動，從而找到最短路徑。而從某一點選擇另外一點的轉移概率，由圖的每條邊的權值決定，這里的權值即蟻群散發的信息素濃度。每次選擇一條路，該路上的信息素濃度都會更新，而其更新的形式有兩種，一是揮發，即該路信息素由于無人經過，而以比例減少；二是增強，即有螞蟻走過時，該條路的信息素濃度會相應變大。

人工螞蟻和旅行商走到下一個城市的概率，是通過一個隨機規則實現的，即運用當前信息素和可見度所儲存的信息，計算出下一步可達點的概率，并按概率可能實現下一步的移動。從此往復運算，越來越接近最優解，即最短路徑。螞蟻在尋找過程中，尋找到其中一個解后，會記錄下來和其他解比較，直至找出最短路徑最優解。

1.路徑構建。核心步驟之一為構建合理的路徑供螞蟻選擇。我們可以令TSP問題中的螞蟻隨機選擇一個城市作為出發城市，初始時刻，各條路徑上的信息素量相等。

2.信息素更新。核心步驟之二是信息素的更新，通過信息素的更新才能實現螞蟻對路徑的選擇。當螞蟻選擇到一條路徑之后，就對信息素進行更新，算法開始的時候會有一個固定的信息素值C，每次走過相應路徑，信息素會揮發或增加，并經過多次迭代。初始值的C不能過高，也不能過低。如果C過低，算法容易早熟，過早找到的路徑不一定是最短的，C太大就會影響效率。每經過一輪后，其釋放的信息素公式如下：

3.實際問題求解。實際問題中，我們假定了30個城市的坐標，30×30的地圖，對蟻群算法進行應用，即三個城市的TSP問題求解。隨機設定了30個城市的坐標，定義蟻群數量也為30個，為了精確最小路徑的數值，我們將迭代次數盡量放大，設定為1000次。同時，為了保持城市坐標的隨機性，我們引入了time(0)函數來獲取隨機秒數。同時，在螞蟻選擇下一個城市時，計算標準除了利用概率，還利用輪盤賭法進行選擇，并且螞蟻可以進行城市之間的移動和搜索城市。更新環境信息素時，當前每條路上的信息素，等于過去保留的加上每個螞蟻這次走過這條路留下來的信息素。接下來最重要的一步，就是尋找最短路徑的部分，遍歷所有的螞蟻經過他們的城市道路后，將最好的螞蟻路徑保存下來，只要有螞蟻路徑比其他的完好就保存下來，經過1000次迭代，就可以很大程度的趨近于最近的一條道路。

最終結果大致如下：

?