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

關(guān)鍵詞：旅行商問題；Transformer；注意力機制；神經(jīng)網(wǎng)絡(luò)；近似求解

中圖分類號：TP18 文獻標(biāo)志碼：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）是組合優(yōu)化問題中一類經(jīng)典的NP完備問題，具有較高搜索空間和復(fù)雜度。它的理論全搜索復(fù)雜度為O（n?。Ｂ眯猩虇栴}可以被描述為在給定n個城市以及各個城市間距離的條件下，有一個旅行商需要從一個城市開始，逐一訪問每個城市，每個城市僅訪問一次，并在訪問完所有城市后返回出發(fā)城市。問題在于如何規(guī)劃路徑，以使旅行商所走的總路徑最短。其數(shù)學(xué)模型：對于城市V={v1，v2，…，vn}的一個訪問順序為T=（t1，t2，…，tn），其中ti∈V（i=1～n），且tn+1=t1， 則問題為求min，其中為這n個城市不重復(fù)排列的所有可能的回路。

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

1 研究現(xiàn)狀分析

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

1.1 傳統(tǒng)方法

1.1.1 精確求解方法

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

1.1.2 近似求解方法

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

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

1.2 神經(jīng)網(wǎng)絡(luò)方法

神經(jīng)網(wǎng)絡(luò)方法是一種機器學(xué)習(xí)方法，其通過模仿生物神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)和功能，在計算機視覺、自然語言處理、語音識別等領(lǐng)域有廣泛的應(yīng)用。近年來，為求解旅行商問題，許多使用神經(jīng)網(wǎng)絡(luò)方法的新型近似求解方法開始出現(xiàn)。相對于傳統(tǒng)方法，這種新型近似求解方法，可有效提高近似解的準(zhǔn)確性。這為求解組合優(yōu)化問題的發(fā)展指明了新的方向。使用神經(jīng)網(wǎng)絡(luò)方法求解旅行商問題的典型算法包括Hopfield神經(jīng)網(wǎng)絡(luò)、指針網(wǎng)絡(luò)、強化學(xué)習(xí)指針網(wǎng)絡(luò)等。

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

2 Transformer基本框架及組成

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

編碼器由N=6個相同的層級構(gòu)建而成。各層級分為2個子級。首個子級為一個多頭自注意力機制層，隨后的子級則為一個基礎(chǔ)的位置全連接前饋網(wǎng)絡(luò)。在每個子級上，實施殘差連接及層標(biāo)準(zhǔn)化。

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

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

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

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

式中：2范數(shù)記為||·||2。

旅行商問題可視為序列到序列的“翻譯”類問題。其中，“源語言”為二維平面上的點集，“目標(biāo)語言”是最短長度的路徑，設(shè)計類Transformer模型可解此問題?；赥ransformer的旅行商問題解法框架如圖2所示。

3.1 編碼器

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

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 解碼器

解碼器是自回歸的，每次一個城市。假設(shè)已確定路徑中的前t個城市，以預(yù)測下一個城市。模型使用鏈?zhǔn)椒纸鈱⒙窂礁怕史纸鉃?/p>

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

3.2.1 解碼器的第一部分

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

式中： 為位置編碼，則

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

3.2.2 解碼器的第二部分

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

3.2.3 解碼器的第三部分

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

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

3.2.4 解碼器的第四部分

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

式中：C=10。

3.3 模型訓(xùn)練

使用強化學(xué)習(xí)對模型進行訓(xùn)練。給定模型？茲和s，損失函數(shù)定義為

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

定義圖分布S，訓(xùn)練期間圖從中采樣。整體訓(xùn)練目標(biāo)定義為

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

通過梯度下降方法最小化損失函數(shù)。給定基線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 搜索策略

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

4 算法測試

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

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

5 結(jié)論

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

參考文獻：

[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(xiàn)，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.