一種基于K-近鄰分區(qū)的蟻群算法在TSP問題中的應(yīng)用研究

◆黃澤斌 黃鋼忠 楊志鵠 姜春濤 黃穎欣

（佛山科學(xué)技術(shù)學(xué)院數(shù)學(xué)與大數(shù)據(jù)學(xué)院 廣東 528000）

旅行商（TSP）問題是一種組合優(yōu)化問題，指的是旅行者從一個城市出發(fā)，經(jīng)過剩余城市，且每只經(jīng)過一次，最后返回出發(fā)城市的最短旅程[1]。如今，國內(nèi)外很多學(xué)者從很多不同算法入手來研究此問題，并取得了不錯的成果，如：粒子群算法、蟻群算法、遺傳算法等。

其中，蟻群算法是一種模擬螞蟻群體一起覓食行為的智能算法。該算法于1992年，由米蘭理學(xué)院學(xué)者M.Dorigo首次提出，它具有良好的魯棒性、支持分布式的計算和能夠進行全局搜索的優(yōu)點，并被廣泛應(yīng)用在求解TSP問題、job-shop分配問題、蛋白質(zhì)折疊問題等許多與組合優(yōu)化相關(guān)的問題，而且能夠得到良好的結(jié)果。本文在此算法基礎(chǔ)上，將K-近鄰的思想與其相結(jié)合，編寫新的蟻群算法程序，并通過在TSP問題中的應(yīng)用來驗證新算法的可行性。

1 基本原理

1.1 蟻群算法基本原理

蟻群算法是用于搜索和優(yōu)化路徑的模擬進化算法。蟻群在覓食過程中，每只螞蟻都會留下一種用于信息傳遞yon的物質(zhì)，我們稱之為信息素。研究表示，信息素濃度愈高，螞蟻的選擇意向便會愈強，眾多的螞蟻組成的群體行為形成一種協(xié)同搜索最優(yōu)路徑的正反饋機制：某條路徑的信息素濃度愈高，便表明該路徑更短，而隨著時間的流逝，路徑上的信息素又會一直進行自我衰減[2][3]。最后，基于這種正反饋機制，蟻群可以找到食物和巢穴之間的最短路徑。其過程如圖所示。

圖1 蟻群算法原理圖

在圖1中，當T=1時，圖為蟻群搜尋食物的初始圖，假設(shè)僅有圖中左右兩條路徑可以到達食物源Food，從圖中也可以明顯看出，左邊的路徑長度遠小于右邊的路徑長度；

在圖1中，當T=2時，圖為蟻群搜尋食物的過程圖，在圖中有左右兩條路徑到達食物源Food，所以，兩條路線均有螞蟻爬行；

在圖1中，當T=3時，圖為蟻群尋找到食物源最優(yōu)路線的生成圖，在此過程中，沿路的信息素濃度由于有了多數(shù)的螞蟻通過而升高，路徑的信息素濃度愈高，則說明此路徑愈短，而在蟻群中信息正反饋機制的基礎(chǔ)上，能夠讓所有的個體螞蟻都選擇信息素最高的路徑即是最短路徑。

1.2 蟻群算法模型

假設(shè)在m個城市之間的路徑有n只螞蟻上移動，不同的螞蟻借助信息素達到在運動時的交流目的，以此來決定下一步移動的方向，通過公式（1），可以算出在城市j中的螞蟻k選擇移動到下一個城市i的概率，其概率公式為：

使用禁忌表tabuk記錄螞蟻k已留下信息素的城市，確保螞蟻不會再選擇這些城市。當禁忌表記錄了所有城市節(jié)點時，說明螞蟻k成功完成了一次對所有目標城市的循環(huán)，此時便可得到一個旅行商的可行解，與此同時更新所有路徑上現(xiàn)有的信息素。信息素更新的公式如：

在蟻密系統(tǒng)模型中：

在蟻量系統(tǒng)模型中：

在蟻周系統(tǒng)模型中：

式中，Q作為信息素的強度；Lk是第k只螞蟻走過完整一條路徑后所得到的路徑全長。在以上3個模型中，蟻密模型和蟻量模型的原理都是通過考慮螞蟻經(jīng)過路徑的局部信息來對信息素濃度進行更新；而蟻周模型是在螞蟻運動過程中的整體信息的基礎(chǔ)上更新信息素的濃度。所以，對于旅行商問題，蟻周模型因具有更好的優(yōu)越性而被廣泛采納。

1.3 K-近鄰分區(qū)方法

K-近鄰算法是一種監(jiān)督學(xué)習(xí)分類算法，屬于回歸和分類方法中的一種。通過K-近鄰算法來進行分區(qū)操作，可以提高蟻群算法在TSP中路徑規(guī)劃的效率。假設(shè)一個TSP路徑優(yōu)化問題有n個節(jié)點，用N1,N2,...,Nn表示，同時為k-近鄰算法設(shè)定一個分類距離閾值D，然后按照以下步驟進行分區(qū)操作：

（1）從所有節(jié)點中，隨機為第一子區(qū)域的中心選取一節(jié)點NC，且令，然后計算所有剩余節(jié)點NC到K1的距離d1c，將d1c與分類距離閾值D進行比較，若，則可將Nj歸屬到第一子區(qū)域節(jié)點中；若，則將Nj作為到第二子區(qū)域中心K2；

（2）若有Nk到K1,K2的距離d1k,d2k都大于D，則將Nk選為一個新的子區(qū)域中心，接著計算剩下所有節(jié)點Nj到已有子區(qū)域Nk的距離djk，若，則將節(jié)點Nj分類到與它距離最小的子區(qū)域中，否則，將一個新子區(qū)域中心設(shè)定為Nj。

1.4 K-近鄰分區(qū)蟻群算法求解TSP問題的步驟

（1）以橫、縱坐標方式表示待求解TSP問題中的所有節(jié)點數(shù)據(jù)；

（2）用K-近鄰分區(qū)方法對所有節(jié)點數(shù)據(jù)進行聚類分區(qū)；

（3）對每個子區(qū)域用蟻群算法進行最優(yōu)化求解；

（4）連接子區(qū)域之間距離最近的點，并輸出問題的最終解。

2 實驗方法及實驗結(jié)果

為了解決傳統(tǒng)的蟻群算法在求解TSP問題時，遇到巨大優(yōu)化性能和時間消耗的問題，本文在此算法的基礎(chǔ)上，加入K-近鄰分區(qū)算法，實現(xiàn)在TSP問題求解時，先分區(qū)再求解的操作，并對此進行實驗仿真。

實驗中，進行TSP問題仿真求解時，分別選取了60，120個節(jié)點。首先，利用K-近鄰算法對所有節(jié)點進行分區(qū)，接著利用蟻群算法對每個子區(qū)域進行最優(yōu)化求解，最后，連接這些子區(qū)域之間距離最近的點。

圖1是對60個節(jié)點進行優(yōu)化求解之后的路徑示意圖，最終的路徑長度是332.8252，圖2是對120個節(jié)點進行優(yōu)化求解之后的路徑示意圖，最終的路徑長度是433.2763。

圖2 60個節(jié)點的局部優(yōu)化路徑圖

圖3 120個節(jié)點的局部優(yōu)化路徑圖

3 結(jié)束語

通過對基本蟻群算法和K-近鄰分區(qū)方法在TSP問題中的應(yīng)用研究，提出了一種基于K-近鄰分區(qū)的蟻群算法。主要目的是解決蟻群算法在優(yōu)化性能和時間性能上的巨大消耗。實驗結(jié)果表明，在解決小規(guī)模TSP問題時，該方法所得的結(jié)果較好，但當節(jié)點增多到120個時，所得結(jié)果會相對于全局優(yōu)化的結(jié)果差。而在平時進行TSP大規(guī)模求解時，倘若運行設(shè)備不能滿足大規(guī)模運算，則需要進行分區(qū)求解，所以此方法還是比較適用的。