一種基于K-means聚類及分組策略的TSP問題啟發(fā)式算法

時慧琨

一種基于K-means聚類及分組策略的TSP問題啟發(fā)式算法

時慧琨

（淮南師范學院 計算機學院，安徽 淮南 232038）

提出了一種基于分組策略的TSP啟發(fā)式算法。采用二分均值聚類方法對頂點進行遞歸分組，當組內(nèi)頂點數(shù)降到給定閾值之下時進行精確求解，對求解結(jié)果合并從而得到原問題的解。實驗結(jié)果及分析表明，求解結(jié)果和精確解/當前最優(yōu)解差距很小，可以作為精確解的近似。該方法具有(2)的復(fù)雜度，并可以進一步簡化到(log)。

TSP；啟發(fā)式算法；K-means聚類

TSP問題又稱旅行商問題，定義為：給定圖=(,,)，其中為頂點集，為邊集，為邊的權(quán)重信息，求一條經(jīng)過所有頂點的封閉路徑(包含所有頂點的排列)，使得該回路權(quán)重之和最小。按照問題的不同特性可以分為對稱TSP(STSP)、非對稱TSP(ATSP)、單人TSP、多人TSP(MTSP)、單目標TSP、多目標TSP(moTSP)等各種不同類型。TSP問題在交通運輸、線路設(shè)計及物流配送等領(lǐng)域內(nèi)有著廣泛的應(yīng)用，國內(nèi)外學者對其進行了大量的研究。

1 TSP問題描述及研究現(xiàn)狀

TSP問題是典型的NP完全問題，假設(shè)=||，則其完全的解組合共有！種。當比較小時，可以利用動態(tài)規(guī)劃、回溯，甚至蠻力法求得問題的精確解；當比較大時，利用前述解法求出精確解從時間方面考慮是不可能的，這時可以采用的以下的求解方法。

(1)近似解法。近似解法是指在解的最優(yōu)性方面進行了放寬，從而滿足求解復(fù)雜性和使用范圍方面要求而得到的算法。這類算法通常用近似比來衡量算法得到的解和最優(yōu)解之間的接近程度。目前最優(yōu)的近似解法的近似比為3/2。該方法首先找出圖的最小生成樹(MST)，對MST中度為奇數(shù)的頂點求解其最小值完美匹配(MCPM)，將匹配中的邊加入到MST中以保證每個頂點的度均為偶數(shù)，這樣得到了一個歐拉圖，對其進行遍歷+剪枝即得到問題的解，該方法求得的回路長度不會超過最優(yōu)解的3/2倍[1]。

(2)智能算法。TSP問題可以看成是一個組合優(yōu)化問題，傳統(tǒng)的搜索方法受到“組合爆炸”的影響，很難在短時間內(nèi)遍歷整個搜索空間。智能算法是指受到人類智能、社會性生物群體或自然現(xiàn)象啟發(fā)產(chǎn)生的算法，通過模擬某種現(xiàn)象、過程或群體行為來進行搜索，具有簡單、通用、便于并行處理、不易陷入局部最優(yōu)等優(yōu)點，但是對解的質(zhì)量無法保證。這一類算法包括進化類的算法(遺傳算法、差分進化算法、免疫算法)、群智能算法(蟻群算法、粒子群算法)、模擬退火、禁忌搜索等，利用其進行TSP問題求解的實現(xiàn)層出不窮[2]。

(3)啟發(fā)式算法。啟發(fā)式算法是指在求解過程中，利用經(jīng)驗或根據(jù)問題的特殊結(jié)構(gòu)及性質(zhì)尋求一種面向問題的求解策略，期望在給定時間內(nèi)尋找一種相對較好的解。但是和智能算法一樣，啟發(fā)式算法對解的質(zhì)量無法保證。貪心算法可以看成啟發(fā)式算法的一種特殊形式。

(4)機器學習方法。早期的機器學習方法主要是利用Hopfield神經(jīng)網(wǎng)絡(luò)和自組織神經(jīng)網(wǎng)絡(luò)求解TSP問題，深度學習技術(shù)出現(xiàn)后，近年來出現(xiàn)了利用深度學習或深度強化學習求解組合優(yōu)化問題。利用深度學習技術(shù)求解將TSP問題看成一個序列輸出問題，例如指針網(wǎng)絡(luò)[3](Pointer Network)，采用具有注意力機制的seq2seq架構(gòu)，其輸出是指向輸入序列的一系列指針，從而對輸入序列進行排序，將排序后的結(jié)果作為TSP問題的解。后續(xù)的改進包括更改層類型、采用強化學習機制[4]、使用圖神經(jīng)網(wǎng)絡(luò)等，但這些方法在求解規(guī)模和魯棒性等方面還需要改進。

2 本文提出的算法思想及其描述

TSP的精確解法要求對TSP路徑上每一個可能的頂點進行枚舉，這造成了指數(shù)時間的復(fù)雜度，啟發(fā)式算法根據(jù)問題最優(yōu)解的特征對所有可能的情形進行了簡化，從而降低了執(zhí)行時間，獲得的解通常是最優(yōu)解的逼近。對已有的TSP研究和計算結(jié)果進行總結(jié)分析，得出如下結(jié)論：(1)TSP算法的運行時間受頂點個數(shù)的影響，頂點個數(shù)越少，運行時間越短。因此，將頂點劃分為頂點個數(shù)較少的分組，組內(nèi)分別進行TSP回路計算，再通過組之間的連接將路徑合并，得到原問題的解是一種可行的途徑。(2)在利用精確解法或者其他方法獲得的TSP問題最優(yōu)解中，TSP路徑一般均是將相近的頂點連接起來，很少甚至沒有長程連接。(3)在TSP問題中，如果度量方式滿足三角不等式性質(zhì)，則最優(yōu)解的回路中不會出現(xiàn)交叉連接，因為交叉連接總可以通過互換交叉連接某一方的2個頂點而獲得更優(yōu)的解。

基于以上的啟發(fā)式結(jié)論，提出了clusterTSP算法，利用K-means(k均值)聚類算法[5]對圖中頂點進行遞歸分組，利用精確求解方法求解組內(nèi)的TSP回路，再通過增加組間連接對回路進行合并得到原問題的解。K-means是一種聚類算法，聚類的目標就是使得聚類后類內(nèi)的節(jié)點盡量接近，類之間的節(jié)點盡量遠離，聚類及聚類結(jié)果特征正好滿足啟發(fā)式結(jié)論要求。因此在K-means算法基礎(chǔ)上提出如下基于分治法的TSP算法構(gòu)想，首先判斷處理對象中包含的頂點個數(shù)，若頂點個數(shù)小于給定的閾值時調(diào)用精確算法直接求解；否則，基于K-means算法對頂點集進行迭代二分聚類，直到類內(nèi)頂點數(shù)小于給定閾值。在合并階段利用2個子類的最近鄰將路徑進行合并從而得到問題的解。

2.1 clusterTSP算法描述

算法的設(shè)計基于分治法思想，利用python語言編程實現(xiàn)。算法中處理的頂點只需給出坐標，頂點間距離通過歐式距離進行計算，這也是TSP問題描述中的一種最常見情況。

功能：對pList對應(yīng)的頂點集求解TSP回路，返回回路長度和回路的頂點序列path

輸入：頂點的列表pList

輸出：路徑長度cost，路徑path

在算法中，如果列表的頂點個數(shù)<3，直接返回0(不構(gòu)成回路，代價為0)和列表本身；如果頂點個數(shù)<10，直接利用DP或者回溯法等精確解法求解回路，返回回路的總長度cost及回路的頂點序列path；否則，先利用K-means算法將所有頂點聚類成兩類，構(gòu)造屬于各自類別的頂點列表subList1和subList2，并對其遞歸求解得到相應(yīng)的路徑，利用mergePath算法合并成一條完整路徑，總長度等于子路徑長度之和+合并代價，最后返回總長度和合并后的完整路徑。

2.2 合并算法mergePath描述

在clusterTSP算法中使用了mergePath算法用于合并已經(jīng)存在的兩條子路徑，算法描述如下。

功能：合并兩個子路徑成一條完整的路徑

輸入：兩個子路徑path1，path2

輸出：合并后的路徑path

在mergePath算法中，輸入為path1和path2，分別是需要合并的兩條子路徑，這兩條子路徑中包含的頂點最初是通過聚類得到的。由于K-means算法聚類后可能會得到僅包含1個或者2個頂點的子類，所以子路徑中也可能只包含1個或2個頂點。但是由于clusterTSP算法設(shè)定當頂點數(shù)小于10時直接求解，所以最多只有1條子路徑中頂點數(shù)<3。算法先計算子路徑中頂點個數(shù)，并通過必要的交換保證如果存在頂點數(shù)<3的子路徑，只會出現(xiàn)在path2中。然后計算path1和path2中最近的2對頂點，即path1[index1]、path1[index1+1]和path2[index2]、path2[index2+1](當n2=1時僅有path2[0]），將path2[index]、path2[index-1]、…、path2[0]、path2[n2-1]、path2[n2-2]、…、path2[index+1]插入到path1[index]和path1[index1+1]之間從而構(gòu)成了合并之后的路徑(按照最近的兩對頂點的配對情況，path2可能要逆置后再插入到path1中)。

3 實驗結(jié)果與分析

研究TSP問題使用最廣泛的國際數(shù)據(jù)集為TSPLIB95[6]，除了提供規(guī)模大小不同的各種地圖外，還記錄了各地圖使用高性能計算獲得的全局最優(yōu)解。以TSPLIB中的地圖樣本為例，計算并和其他算法獲得的解進行比較分析。

3.1 性能分析

選擇TSPLIB網(wǎng)站提供的大小不同地圖，計算并記錄使用前述算法的運行結(jié)果(回路長度)，并和全局最優(yōu)解，以及和本算法復(fù)雜度接近的最近鄰策略近似算法進行了比較，結(jié)果如表1所示。

表1 算法運行結(jié)果舉例

地圖文件名稱頂點數(shù)全局最優(yōu)解本算法最近鄰算法 eil51.tsp51426445.36508.8 eil76.tsp76538569.6681.7 ts225.tsp225126643135932159045 rat575.tsp57567737753.48575 rat783.tsp783880610126.211455.4 fnl4461.tsp4461182566211027227988 brd14051.tsp14051469385547399.6599452

可以將計算結(jié)果得到的TSP回路繪制出來，圖例如圖1、圖2所示。

由表1可以看出，本算法和最優(yōu)解相比，計算結(jié)果接近，且對所有地圖均優(yōu)于最近鄰近似算法的運算結(jié)果。當圖中的頂點數(shù)較少，例如只有幾十個頂點時，算法和全局最優(yōu)解的差距在5%左右，當頂點數(shù)增加時，差距會逐漸加大，但即使是1萬個以上頂點的圖，差距也小于20%。如果希望能夠在較短的時間內(nèi)獲得問題解時，這個差距可以接受。

圖1 計算的回路示例1（eil51.tsp）

圖2 計算的回路示例2（rat783.tsp）

當頂點的個數(shù)增加時，算法的解和最優(yōu)解差距增大的主要原因是算法較多地考慮了局部因素，并且子問題求解及合并的結(jié)果一旦確定即不變，當頂點數(shù)增加時，局部選擇是全局最優(yōu)選擇的可能性減小，但總體來說，算法計算結(jié)果和全局最優(yōu)解相比差距仍然在可接受范圍內(nèi)。

除此之外，算法的計算結(jié)果具有一定的隨機性，這主要是由于K-means算法決定的，K-means算法聚類結(jié)果會受到初始中心點的影響，容易陷入到局部最優(yōu)，所以在實現(xiàn)時采用K-means++的思想，選擇盡量遠的點作為初始聚類中心，并迭代多次。本算法也可以運行多次，并選擇其中的最小值作為最終結(jié)果。

3.2 時間復(fù)雜度分析

對于個頂點的圖，定義算法時間復(fù)雜度函數(shù)為()。K-means算法的復(fù)雜度為()，其中為頂點個數(shù)，為聚類中心數(shù)，為迭代次數(shù)，為數(shù)據(jù)樣本的維度。在本算法中，=2，=2，=300，即為常數(shù)，因此K-means算法復(fù)雜度可以估計為()。由于K-means算法具有均勻效應(yīng)，傾向于產(chǎn)生均分的聚類結(jié)果，通常情況下可以認為聚類會均分數(shù)據(jù)集，因此子問題的時間復(fù)雜度用(/2)表示。mergePath算法合并兩條子路徑的復(fù)雜度為(2)，綜上可得clusterTSP算法復(fù)雜度遞推關(guān)系式：

計算可得()=(2)，實驗結(jié)果表明其運行時間通常在1 min以內(nèi)，當節(jié)點數(shù)很大時，時間也是分鐘級別，與最近鄰策略近似算法的運行時間接近，略少一些。

如果想進一步降低時間復(fù)雜度，可以在mergePath算法中，配對頂點選擇和對方子類的聚類中心距離最近的頂點，此時mergePath算法的復(fù)雜度可以用()表示，因此clusterTSP算法復(fù)雜度遞推關(guān)系式為：

解得()=(log)，這時即使是頂點數(shù)量萬個以上的TSP問題，也可以在1 min內(nèi)得到答案，但是這樣求得的回路長度最優(yōu)解相對于前者會差一些。

4 結(jié)論

提出了一種基于聚類的分組TSP問題解法，利用K-means聚類算法對數(shù)據(jù)遞歸分組到閾值之下數(shù)量時進行精確求解，對求解結(jié)果層級合并得到原問題的解。實驗表明該方法運行速度很快，計算結(jié)果和最優(yōu)結(jié)果差距很小，可以作為時間要求苛刻情況下問題解的近似，也可以作為其他算法的比較基準。進一步的研究可以考慮對數(shù)據(jù)采用其他聚類方法進行分組，考慮在聚類時采用其他距離度量方式提高解優(yōu)越性的可行性。

[1] Christofides N. Worst-case analysis of a new heuristic for the travelling salesman problem[R]. DTIC Document, 1976.

[2]王劍文, 戴光明, 謝柏橋, 等. 求解TSP問題算法綜述[J]. 計算機工程與科學, 2008, 30(2): 72-74, 155.

[3]陳思遠, 林丕源, 黃沛杰. 指針網(wǎng)絡(luò)改進遺傳算法求解旅行商問題[J]. 計算機工程與應(yīng)用, 2020, 56(19): 231-236.

[4]王若愚, 陳勇全. 基于強化學習的旅行商問題解構(gòu)造方法[J]. 計算機工程, 2019, 46(11): 293-300.

[5]許玲. 改進的K-means算法研究與實現(xiàn)[D]. 合肥: 安徽大學, 2019.

[6] University Heidelberg. TSPLIB[EB/OL]. http://comopt.ifi. uni-heidelberg.de/software/TSPLIB95/, 2013-1-1/2019-9- 30.

Heuristic Algorithm for TSP Problem Based on K-means Clustering and Grouping Strategy

SHI Hui-kun

（School of Computer Science, Huainan Normal University, Huainan 232038, China）

A TSP heuristic algorithm based on grouping strategy is proposed. The binary K-means clustering method is used to group the vertices recursively, when the number of vertices in the group is reduced under a given threshold, the exact solution is carried out, and the solution results are combined to obtain the solution to the original problem. The experimental results and analysis show that the difference between the solution and the exact solution or the current optimal solution is slight, which can be used as the approximation of the exact solution. This method has(2) complexity and can be further simplified to(log).

TSP; heuristic algorithm; K-means clustering

TP311

A

1674-3261(2021)02-0075-04

10.15916/j.issn1674-3261.2021.02.002

2020-09-21

時慧琨(1975-)，男，安徽淮南人，講師，碩士。

責任編校：孫 林