基于Transformer的旅行商問題解法

摘 要：在針對旅行商問題（Travelling Salesman Problem）的近似求解算法中，傳統啟發式算法收斂速度較慢，準確性較低。為解決上述問題，該文提出一種基于Transformer的神經網絡方法。該方法使用神經網絡，可有效提高近似解的求解速度和準確性，并使用Transformer注意力機制全面提高神經網絡的性能。該方法使用強化學習進行訓練，使用束搜索算法進行搜索。使用該方法對隨機50節點的旅行商問題進行測試，試驗結果表明該種基于Transformer的旅行商問題解法，可在較低的復雜度前提下，得到近似于精確解的效果。

關鍵詞：旅行商問題；Transformer；注意力機制；神經網絡；近似求解

中圖分類號：TP18 文獻標志碼：A 文章編號：2095-2945（2024）29-0161-05

Abstract： In approximate solutions to the traveling salesman problem （TSP）， traditional heuristic algorithms are known for their slow convergence speed and low accuracy. To address these issues， this paper proposes a neural network approach based on Transformers. This method utilizes neural networks to effectively improve the speed and accuracy of approximate solutions， while leveraging the Transformer's attention mechanism to enhance the overall performance of the neural network. This method uses reinforcement learning for training and beam search algorithm for search. This method is used to test the random 50-node traveling salesman problem， and the experimental results show that the solution of the traveling salesman problem based on Transformer can get the effect which is similar to the exact solution under the premise of low complexity.

Keywords： traveling salesman problem; Transformer; attention mechanism; neural network; approximate solution

旅行商問題（Travelling Salesman Problem，簡稱TSP）是組合優化問題中一類經典的NP完備問題，具有較高搜索空間和復雜度。它的理論全搜索復雜度為O（n！）。旅行商問題可以被描述為在給定n個城市以及各個城市間距離的條件下，有一個旅行商需要從一個城市開始，逐一訪問每個城市，每個城市僅訪問一次，并在訪問完所有城市后返回出發城市。問題在于如何規劃路徑，以使旅行商所走的總路徑最短。其數學模型：對于城市V={v1，v2，…，vn}的一個訪問順序為T=（t1，t2，…，tn），其中ti∈V（i=1～n），且tn+1=t1， 則問題為求min，其中為這n個城市不重復排列的所有可能的回路。

旅行商問題求解方法及其相關方法具有廣泛的工業應用場景，例如路徑規劃、生產規劃、供應鏈和計算機網絡等領域。因此，該問題引起了多學科研究者的關注，并驅動了一系列重要的優化方法的發展，包括切平面法、分支定界法、局部搜索算法、拉格朗日松弛法和模擬退火算法。

1 研究現狀分析

當前，旅行商問題求解方法主要分為精確求解方法與近似求解方法。精確求解方法可確保得到最優解，但當問題規模增大時，計算成本顯著增大。而近似求解方法犧牲最優性，換取部分計算效率，可在允許的時間內得到較優解。

1.1 傳統方法

1.1.1 精確求解方法

旅行商問題的精確求解方法有窮舉法、動態規劃和整數規劃算法。Held和Karp[1]提出了一種可用于求解旅行商問題的動態規劃算法，復雜度為O（n22n），這種算法在n>40時就難以求解。Gu等[2]給出了一種備有切平面法和分支定界法的通用整數規劃求解器。最后，Cook等[3]設計了一種高度專業化的旅行商問題精確求解方法，稱為Concorde，被廣泛認為是目前對于大規模旅行商問題最快的精確求解方法。

1.1.2 近似求解方法

旅行商問題的近似求解方法主要為元啟發式算法，例如最鄰近搜索算法、遺傳算法、模擬退火算法、禁忌搜索算法、蟻群算法和樹木生理算法等。Halim等[4]通過計算時間、統計數值、收斂性3個維度，對比了以上6種主要的元啟發式算法。于計算時間維度而言，最佳算法為最鄰近搜索算法，其次為樹木生理算法和遺傳算法。于統計數值維度而言，最接近最佳路徑的算法有禁忌搜索算法、樹木生理算法、遺傳算法。于收斂性維度而言，最鄰近搜索算法、禁忌搜索算法、蟻群算法表現較優。

由于以上元啟發式算法各有優劣，一些研究者曾嘗試使用多種元啟發式算法進行改進與融合，例如Lee[5]成功地將遺傳算法與蟻群算法進行結合與優化，同時保有了遺傳算法與蟻群算法的優勢，并取得更佳的效果。其中，具有代表性的是Google OR-Tools[6]，其為一個高度優化的程序，可用于解決旅行商問題和更大規模的車輛路徑規劃問題。該程序采用了不同的元啟發式算法，如模擬退火算法、貪婪下降算法、禁忌搜索算法，在搜索空間中進行搜索，并通過局部搜索技術得出較優解。目前，求解旅行商問題最佳的元啟發式算法為LKH-3算法，作為Lin-Kernighan-Helsgaun TSP求解器的衍生版本。

1.2 神經網絡方法

神經網絡方法是一種機器學習方法，其通過模仿生物神經網絡的結構和功能，在計算機視覺、自然語言處理、語音識別等領域有廣泛的應用。近年來，為求解旅行商問題，許多使用神經網絡方法的新型近似求解方法開始出現。相對于傳統方法，這種新型近似求解方法，可有效提高近似解的準確性。這為求解組合優化問題的發展指明了新的方向。使用神經網絡方法求解旅行商問題的典型算法包括Hopfield神經網絡、指針網絡、強化學習指針網絡等。

隨著神經網絡方法的日益發展，一種類似于人的大腦中注意力機制的神經網絡——注意力網絡應運而生。這種網絡最早出現在計算機視覺領域，后來被廣泛應用于自然語言處理領域。2017年，Google團隊最具代表性地在“Attention is all you need”一文中提出Transformer模型結構和注意力機制，由此注意力機制成為研究熱點。注意力機制全面提高了神經網絡模型的性能，大力推動了神經網絡方法的發展，是機器學習領域的一次歷史性變革。

2 Transformer基本框架及組成

Transformer的基本框架由編碼器和解碼器構成，如圖1所示[7]。編碼器將一個由符號表示組成的輸入序列（x1，…，xn）轉化為連續性表示形式z=（z1，…，zn）。在給定z的情況下，解碼器能逐元素地構造輸出序列，表示為（y1，…，ym）。在每一步中，模型均為自回歸性質，將之前生成的符號作為附加輸入，供下一步的生成使用。

編碼器由N=6個相同的層級構建而成。各層級分為2個子級。首個子級為一個多頭自注意力機制層，隨后的子級則為一個基礎的位置全連接前饋網絡。在每個子級上，實施殘差連接及層標準化。

解碼器同樣由N=6個相同的層級構建而成。相較于在編碼器中的2個子級，解碼器中增添了第三個子級，其主要功能是對編碼器的輸出進行多頭注意力機制層的處理。在每個子級上，同樣實施殘差連接和層標準化。此外，為了阻止對后續位置的關注，解碼器對堆棧中的自注意力子級進行了修正。這種遮蔽操作配合了對輸出嵌入位置的偏移，保證了位于i的預測僅依賴于小于i的已有輸出。

3 基于Transformer的旅行商問題解法框架

給定一個輸入圖，表示為二維空間中的n個城市：s={xi}，其中每個xi∈ 2。路徑定義為所有點的置換？仔。優化目標是使路徑的長度最短，其中路徑的長度定義為

L（|s）=||x（n）-x（1）||2+||x（i）-x？仔（i+1）||2，

式中：2范數記為||·||2。

旅行商問題可視為序列到序列的“翻譯”類問題。其中，“源語言”為二維平面上的點集，“目標語言”是最短長度的路徑，設計類Transformer模型可解此問題。基于Transformer的旅行商問題解法框架如圖2所示。

3.1 編碼器

編碼器是一個標準的Transformer編碼器，有著相同的多頭注意力機制層和殘差連接。Kool等[8]指出，批標準化在路徑規劃問題中，較層標準化有更優效果，此處將層標準化改用為批標準化。其數學表達式（僅考慮單頭注意力機制層以簡化描述）為

Henc=H∈ （n+1）×d，

其中，H=0=Concat（z，X）∈ （n+1）×2，z∈ 2，X∈ n×2，

H+1＝softmax∈ （n+1）×d，

Q=HW∈ （n+1）×d，W∈ d×d，

K=HW∈ （n+1）×d，W∈ d×d，

V=HW∈ （n+1）×d，W∈ d×d，

z為隨機生成的起始點。

3.2 解碼器

解碼器是自回歸的，每次一個城市。假設已確定路徑中的前t個城市，以預測下一個城市。模型使用鏈式分解將路徑概率分解為

p（|s）=p（（i）|（<i），s）。

3.2.1 解碼器的第一部分

解碼器的第一部分是位置編碼。對于已選的城市it為

式中： 為位置編碼，則

PEt，i=sin（2？仔fit） 如果i為偶數，cos（2？仔fit） 如果i為奇數，那么fi=。

3.2.2 解碼器的第二部分

解碼器的第二部分是對已知路徑的嵌入。此注意力機制層是標準的，使用多頭注意力機制，殘差連接和層標準化。其數學表達（僅考慮單頭注意力機制層以簡化描述）為

3.2.3 解碼器的第三部分

解碼器的第三部分在未訪問的城市中，對下一個可能的城市進行查詢。此處應用了多頭注意力機制，殘差連接和層標準化。其數學表達（僅考慮單頭注意力機制層以簡化描述）為

式中： 為已訪問城市的掩碼； 為哈達瑪積。

3.2.4 解碼器的第四部分

解碼器的第四部分使用單頭注意力機制對未訪問的城市進行最終查詢，以得到概率分布。其數學表達為

式中：C=10。

3.3 模型訓練

使用強化學習對模型進行訓練。給定模型？茲和s，損失函數定義為

J（|s）=E～p（.|S）L（|s）。

定義圖分布S，訓練期間圖從中采樣。整體訓練目標定義為

J（）=Es～S[J（|s）]。

通過梯度下降方法最小化損失函數。給定基線b（s），可使用Williams[9]的REINFORCE梯度估計算法為

J（|s）=E～p（.|s）[（L（|s）-b（s））logp（|s）]。

通過Monte Carlo采樣方法，梯度可估計為

J（）（L（k|sk）-b（sk））log（p（k|sk））。

3.4 搜索策略

在搜索策略中，可找到最優解的窮舉方法的復雜度為O（n！），難以求解。因此，搜索策略的估計是必要的。最簡單的搜索策略估計是貪婪搜索，即在每一個時間點，總選取最高概率的下一個城市為？仔（i）=argp（j|（<i），s）。在此基礎上的另一搜索算法為束搜索算法，與貪婪搜索相比，束搜索在每一步都會保存當前最佳的B個候選序列，以提高搜索準確性。為有效提高搜索準確性，本文采用束搜索算法進行搜索。

4 算法測試

隨機選用50節點的旅行商問題，對上述解法進行測試。由于Concorde算法可得旅行商問題的精確解，文中采用其結果進行可視化對比分析（圖3）。

可視化圖像分別呈現的是4次試驗結果。在第i次試驗Test i中，左子圖為基于Transformer的旅行商問題算法結果的可視化，右子圖為Concorde算法結果的可視化。其得出的路徑長度分別標注于子圖上方。從圖3中可以看出，在第一、第二、第四次試驗中，基于Transformer的旅行商問題算法得出了與Concorde算法相同的解。在第三次試驗中，Transformer的路徑長度為6.105個單位長度，Concorde的路徑長度為6.083個單位長度。結果分析表明，基于Transformer的旅行商問題解法可較好地得出較優解，其結果與Concorde精確解近似。

5 結論

基于Transformer的旅行商問題解法，可在較低的復雜度前提下，得到近似于精確解的效果。Transformer在組合優化領域中具有巨大的應用潛力。傳統精確解法，如Concorde等算法，在求解精確解的應用場景中仍然具有優勢。隨著Transformer在此應用場景研究的深入，后續研究可能將聚焦于超大規模旅行商問題解法的研究中。由于GPU內存限制及Transformer復雜度仍有O（n2）L，使用Transformer方法求解大型旅行商問題仍具挑戰性。

參考文獻：

[1] HELD M， KARP R M. A dynamic programming approach to sequencing problems [J]. Journal of the Society for Industrial and Applied mathematics， 1962，10（1）：196-210.

[2] GU Z， ROTHBERG E， BIXBY R. Gurobi [Z]. 2008

[3] COOK W J， APPLEGATE D L， BIXBY R E， et al. The traveling salesman problem： a computational study [M]. Princeton university press， 2011.

[4] HALIM A H， ISMAIL I. Combinatorial optimization： comparison of heuristic algorithms in travelling salesman problem [J]. Archives of Computational Methods in Engineering， 2019，26：367-380.

[5] LEE Z J. A hybrid algorithm applied to travelling salesman problem[C]//proceedings of the IEEE International Conference on Networking， Sensing and Control， 2004，F，2004.

[6] FURNON V， PERRON L. OR-Tools Routing Library [Z].

[7] VASWANI A， SHAZEER N， PARMAR N， et al. Attention is all you need[C]//Advances in Neural Information Processing Systems，2017：5998-6008.

[8] KOOL W， VAN HOOF H， WELLING M. Attention， learn to solve routing problems！[R]. arXiv preprint arXiv：180308475，2018.

[9] WILLIAMS R J. Simple statistical gradient-following algorithms for connectionist reinforcement learning [J]. Machine learning， 1992，8：229-56.