基于Transformer的旅行商問(wèn)題解法

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

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

中圖分類(lèi)號(hào)：TP18 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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

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

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