基于Matlab的蟻群算法求解旅行商問題

河南科技職業大學 嚴玉芳

蟻群算法是一種解決組合優化問題的算法，具有靈活性、穩健性等優勢，而旅行商問題正是一個利用蟻群算法得以解決的經典選擇優化問題。本文首先以蟻群算法為研究對象，闡述了蟻群算法的基本原理、模型的建立以及算法的實現流程，其次討論了蟻群算法在經典的旅行商問題上的應用，最后利用Matlab軟件對旅行商問題進行編程求解并對最終實驗結果進行了分析。

群體智能優化算法來自于對自然界中的有生物種在尋覓食物時所做出的行為的仿真模擬。這種算法是將搜索和優化的所有過程模擬為生物個體進化或者覓物的過程，將搜索范圍中的點看作是自然界中的生物個體，把求解問題的各個目標函數度量為生物個體對自然環境的適應能力，最后將生物個體的適者生存的淘汰過程或者生物個體覓食的過程當作搜索和優化的過程中的較好可行解。群體智能算法也被人們稱為群集算法，比較常見的有：蟻群算法（ACO）、粒子群算法(PSO)、遺傳算法(GA)、菌群算法(BF)等，其中蟻群算法采用的是一種正反饋機制，具有高于一般傳統算法的發現較優解的能力。

1 蟻群算法原理

通過研究蟻群覓食的行為過程，學者們發現螞蟻能在沒接收到任何有關食物源的線索或提示下，靠本能尋找到一條最優路徑（即蟻穴到食物源所在地點間的最短距離）的主要原因在于螞蟻之間的信息傳遞主要是依靠它們在所經過路徑上分泌出的一種具有揮發性的名為“信息素”的物質[1-3]。即螞蟻個體在前進時，若遇到前一個螞蟻分泌出的這種物質，便能根據信息素的強度有選擇的尋找路徑，并且與其他螞蟻選擇到同一路徑的概率與信息素的量以及濃度成正比。正是受螞蟻尋覓食物所做出的行為的啟發，學者們才提出了蟻群算法。

2 蟻群算法

2.1 模型建立

想象蟻群內任一只螞蟻都是簡單的、智能的個體，已知螞蟻選擇節點是依靠某種概率進行的，并且它是每兩個節點之間的距離以及在連接這兩個節點路徑上的信息素的量的函數，螞蟻將會在行走的路徑上分泌適量的信息激素且螞蟻不會二次經過已走過的節點。螞蟻在t時刻選擇t+1時刻要到達的節點，在此時間間隔內，對m只螞蟻調用迭代算法一次，每只螞蟻完成對所有城市的一遍旅行且一次旅行進行n次迭代算法。當螞蟻k完成一次完整閉合路徑且計算其長度Lk后，得有關信息強度公式：且

其中i,j(i,j= 1,2,3...,n)表示節點，bi(t)表在t時刻時節點i內的螞蟻數目；τij(t)表t時刻(i,j)上的信息素強度；ρ(0 ≤ρ≤1)表信息素揮發后的剩余度[1]；Q為常數；1 -ρ表在時間t到t+n內的信息素揮發；為路徑(i,j)的能見度，為蟻群(t,t+n)時間內在路徑(i,j)上留下的單位長度的路徑的信息素數量。

利用禁忌表tabuk(s)禁止螞蟻對已訪問過的節點重復訪問，得到從節點i到j的轉移概率：

其中allowedk= {N-tabuk}，α和β是控制路徑及能見度的重要參數。如果(i,j)之間的距離短，則ηij較大ρij較大，即距離近的節點被選擇的概率大于距離遠的節點被選擇的概率[2]。

2.2 算法實現

蟻群算法的實現可由以下流程圖簡單展示，如圖1所示：

圖1 蟻群算法流程圖[4]Fig.1 Ant colony algorithm flowchart

3 蟻群算法的應用—基于蟻群算法求解旅行商問題

3.1 旅行商問題（Traveling Salesman Problem）

旅行商問題（Traveling Salesman Problem，簡稱TSP）是最為基本的選擇最優路徑的問題[5]。此問題具體來說就是一個推銷商想要到n個城市推銷產品，在已知各城市間的距離的前提下，希望找出最短回路，即選擇一條最短的路徑且這條路徑能使得商人從起點出發并將每個城市都正好走過一遍之后又回到原點處。

3.2 旅行商問題（TSP）的數學規劃模型

假設ijd為每兩個城市i與j之間的距離，即弧長(i,j)的長度為。歸結在圖論意義下，則其圖論可描述為：給定圖G，記為賦權圖G= (V,E)，其中V為頂點集，表示n個城市的集合，E為邊集，表示連接兩城市的路的集合，各頂點間的距離是ijd。引入決策變量，則旅行商問題的目標函數為：，約束條件為

在上述數學規劃模型中，約束條件1和2表明對于任意的點，只有一條邊進入另一條邊出去；約束條件3確保了不會有回路解得產生。故約束條件1、2和3共同保證了所求得的解可構成滿足題目條件的回路。

3.3 利用蟻群算法求解旅行商問題的基本思路

利用蟻群算法在求解組合優化類問題上的先進性，可以將螞蟻看作是旅行商，將各個節點看作旅行商要訪問的城市，將螞蟻放置在不同的城市上，利用多次迭代的方式不斷對數據進行優化，最后求出螞蟻完成周游所行走的最短路線以及距離。

3.4 利用蟻群算法求解旅行商問題的基本步驟

由蟻群算法的實現流程圖，再結合實際的旅行商問題，可以總結出解決旅行商問題的基本步驟，如表1所示：

表1 基于蟻群算法求解旅行商問題Tab.1 To solve TSP based on ant colony algorithm

4 有關算法實現的部分程序展示

初始狀態程序：x=[41 37 54 25 7 2 68 71 54 83 64 18 22 83 91 25 24 58 71 74 87 18 13 82 62 58 45 41 44 4]；

求解程序：function [R_best，L_best，L_ave， Shortest_Route，Shortest_Length]=ACATSP(C，NC_max，m，Alpha，Beta，Rho，Q)；

5 生成數據以及部分圖形顯示

利用Matlab[7]對問題進行編程生成數據的過程中由于有參數的存在，且參數對數據的影響不可忽略，故對參數α，β，ρ在α=1.5，β=2，ρ=0.1，Q=106的基礎上，對參數組進行不斷的改變，NC_max=100為最大迭代次數，且每個數據計算五次并記錄下最優解以及平均解。在本次求解中，規定TSP城市個數為30，并且將運行得出的具體結果以及路徑選擇圖形（僅展示部分圖形）展示如下：

（1）參數組α=1，β=2，ρ=0.1，Q=106下的路徑選擇，如圖2所示：

圖2 路徑選擇Fig.2 Path finding

（2）不同參數組下的最終計算結果，如表2所示：

表2 基于蟻群算法求解旅行商問題的計算結果Tab.2 The calculation results of solving TSP based on ant colony algorithm

（3）數據結果分析

從上面的表格數據可以看出，對于城市數據為30的旅行商問題可以做出以下幾種討論：

在參數α=1.5，ρ=0.1，Q=106，NC-max=100一直穩定的情況下，對β=2，β=1，β=0，β=3四個不同β數據下的平均路徑以及最短路徑長度進行對照可以得出：當β=2時，最大最小迭代以及平均迭代次數均為100，其最小路徑長度為425.5242，平均路徑長度為432.48332，是四個β數據選擇中路徑值達到最小的一個。

在參數β=2，ρ=0.1，Q=106，NC-max=100一直穩定的情況下，對α=1.5，α=1，α=0三個不同α數據下的平均路徑以及最短路徑長度進行比照可以得出：當α=1時，最大最小迭代以及平均迭代次數均為100，其最小路徑長度為425.8201，平均路徑長度為428.56204，是三個α數據選擇中路徑值達到最小的一個。

在參數α=1.5，β=2，Q=106，NC-max=100一直穩定的情況下，對ρ=0.1，ρ=0.3，ρ=0.7，ρ=0.05四個不同ρ數據下的平均路徑及最短路徑長度進行比照可得：當ρ=1時，最大最小迭代及平均迭代次數均為100，其最小路徑長度為425.5242，平均路徑長度為432.48332，是四個ρ數據選擇中路徑值達到最小的一個。

總結上面的分析可得在α＞1時路徑長度遞增，α＜1時路徑長度減??；同理ρ＞0.1時路徑長度逐漸增加，ρ＜0.1路徑長度逐漸減小，β＜2時路徑長度也在減小，β＞2時路徑長度增加，經過比較可以得出在這個算例中，最優參數的選擇應該是α=1，β=2，ρ=0.1。

6 結語

本文主要是向讀者介紹蟻群算法運用到現實生活問題中并對問題進行解決的具體事例，利用蟻群算法來對問題進行求解將會把問題的復雜程度逐漸降低。眾所周知旅行商問題是一種經典的復雜組合求最優解的問題，本章就是以經典問題作為算例，以蟻群算法為基礎，利用Matlab軟件對其進行編程求解，最后對求解結果進行分析并得出最終結論。