基于深度強化學習的旅行商問題研究

鄒 鐵

（雅安開放大學，四川 雅安 625000）

0 引言

旅行商問題（TSP）一般是指找到一條經過給定城市的路線，這條路線長度最短。很多相似的問題都可以用此問題進行建模，同時由NP 完全性理論可知，如果可以用計算機有效地解決此問題，將有助于解決其他NP 完全問題，但經過幾十年的努力，還沒有發現一種有效解決此類問題的精確算法。

用近似算法解決此類問題，是當前應對此類問題的有效方式，但由于近似算法的設計與問題的形式相關，需要對某一類問題進行深入研究，而根據相關領域知識設計啟發式算法，其算法設計難度較大。

機器學習是利用已知經驗和數據求解問題的一類算法，使用機器學習方法（特別是神經網絡）設計解決組合優化問題的算法已成為當前的研究熱點，Bello I 等使用指向性網絡（PointerNetwork）和強化學習方法設計了組合優化問題的神經網絡求解方法[1]；Bengio Y 等對用神經網絡求解組合優化問題進行了綜述[2]；Kool W 等使用注意力機制（Attention）對路徑問題進行了算法設計[3]；Joshi C K 等使用圖神經網絡（GNN）對路徑問題進行了建模并使用與Kool W 相似的強化學習方法進行了求解[4]。

上述研究指出了設計神經網絡求解組合優化問題的方法主要分為三個部分，即設計求解問題的神經網絡結構、設計訓練該網絡的算法以及使用訓練算法對神經網絡進行訓練。本文將基于Transformer 架構[5]（一種基于序列的神經網絡架構，適合用作序列建模），配合強化學習算法，設計求解旅行商問題的神經網絡。

1 問題描述

旅行商問題（Travel Salesman Problem）：給定一個圖G=（V，E），其中，V 是G 的節點集，E 是G的邊集，給定一個從E 到R+的代價函數cost，求該圖的一條環游C，使得該環游的總代價最小，即使得∑e∈Ccost（e）最小。

如果限制該代價函數，使其滿足：當任意三邊e1、e2、e3構成一條回路時，有cost（e1）≤cost（e2）+cost（e3）成立，則該問題被稱為歐氏旅行商問題。

由NP 完全性理論可知，如果能找到一種有效算法解決歐氏旅行商問題，也就能找到解決一般旅行商問題的有效算法。故以下討論均限制在歐氏旅行商問題的范圍內。

2 注意力模型

2.1 注意力模型的概要描述

在序列到序列的模型中，從源序列生成目標序列時，不僅要考慮當前狀態和源序列中的元素，還要考慮當前序列中元素與上下文元素關系的這種方法被稱為注意力機制。

注意力機制，即對齊機制，最早出現在神經機器翻譯[6]中，這項技術能讓解碼器在每個時間步長中專注于某些被編碼器編碼的單詞，使得輸入單詞到翻譯結果的路徑變短，從而實現減少短期記憶限制影響的目的。

在文獻[5]中，研究人員通過Transformer 神經網絡架構，顯著改善了神經機器翻譯的水平；另外，當前最流行的生成語言模型chatGPT 其內部架構GPT-3[7]也是基于此神經網絡架構設計的。由于Transformer 架構除了自注意力機制（指當表示序列中某一時刻狀態時，可以通過計算該狀態與其他時刻狀態的相關性，從而生成目標序列中的元素的方法）和一些必要的連接層（如嵌入層、歸一化、線性層等）外，不包含卷積層和循環層，故其訓練速度比其他完成相似功能的網絡有明顯提高。

2.2 Transformer 架構

一般情況下，我們將從序列映射到序列的神經網絡模型歸結為編碼器－解碼器模型，其含義為將輸入I 用神經網絡變換為中間表示M，然后將中間表示M 再通過神經網絡變換為O。在這一過程中將I 變換為M 的階段稱為編碼，由編碼器完成；而將M 變換為O 的階段稱為解碼，由解碼器完成。Transformer 模型中的編碼器和解碼器均使用了自注意力層和線性層，并以殘差方式連接，并進行歸一化操作，即每一層的輸出xo均為：

其中，Sublayer 函數可以看作自注意力層（多頭注意力層）和線性層，LayerNorm 表示歸一化函數。Transformer 的核心結構如圖1 所示，其中虛線框中的層作為一個整體可根據需求重復多次。值得注意的是，圖1 與文獻[5]中描述的Transformer結構稍有差別，其表現為圖1 去掉了原始的位置編碼部分。

圖1 Transformer 網絡主體架構[5]

在圖1 中，嵌入操作是一個線性變換，將輸入變為多個特征，可由一個線性層表示；多頭注意力（Multi-head Attention）的具體結構在文獻[5]中有相關描述，這里總結如下：

計算注意力的方式，可用以下公式表示：

計算多頭注意力的方式，用如下公式表示：

其中，headi通過以下公式計算：

以上公式中WQ、WV、WK分別表示以Q、V、K為輸入的線性層表示矩陣，Concat 函數表示將headi（i=1...h）合并為一個h×dv維的行向量，該行向量輸入以WO表示的線性層將得到多頭注意力。

2.3 基于Transformer 架構構建求解歐式旅行商問題的神經網絡

在2.2 節中描述了Transformer 架構的核心結構，結合歐式旅行商問題的描述（這里取代價函數為圖G 中兩點的歐式距離，在求歐氏距離時以每個結點的坐標作為輸入，神經網絡的輸入為圖G中結點的位置坐標），設計求解問題的神經網絡如圖2、圖3 所示。

圖2 編碼器

圖2 是編碼器部分（虛框中的部分作為整體，重復2 次），即將一個帶歐式距離的無向圖通過多頭注意力層和線性層變換為一個張量（圖G 的編碼），為解碼器提供必要的信息。在編碼器中使用多頭注意力時，其Q、K、V 均為同一張量，在計算多頭注意力時需要依次使用公式（4）、（2）、（3），這里不再重復。

圖3 是解碼器部分，其作用是將編碼器提供的張量與輸入一起生成被選擇路徑上結點的概率分布信息。

圖G 中結點概率分布生成后，使用貪心法選擇最大概率所對應的結點，這樣就完成了一個結點的選擇，重復使用圖3 所示的神經網絡架構，可生成一系列的結點，直到圖G 中的結點全部被訪問一次，這樣就生成了一條回路，計算該回路的總長度，以及生成該回路結點的對數概率分布，作為持續改進回路的激勵方式。

3 訓練算法

深度強化學習是一種通過激勵調整神經網絡參數的學習算法，被廣泛用于解決智能體的行動問題，如智能體玩電子游戲、下棋等一系列問題。深度強化學習，主要分為基于價值函數的學習方法和基于策略梯度的學習方法，以及這兩種學習方法的結合。在這里我們使用帶基線的策略梯度學習方法訓練求解TSP 問題的神經網絡，具體算法可用偽代碼描述，見圖4。

圖4 帶可變基線的策略梯度學習算法

該算法中的t 檢驗是差異顯著性檢驗，在這里通過對比當前參數下計算得到的路徑總長度與基線參數下計算得到的路徑總長度的差異顯著性，來判斷是否應當更新當前基線。

4 實驗

筆者用以下環境（見表1）對問題實例進行了訓練和求解。

表1 訓練與求解環境

訓練中分別使用了包含10 000 個20 結點TSP 問題實例的數據集、包含10 000 個50 結點TSP 問題實例的數據集以及包含10 000 個100 結點的TSP 問題實例的數據集。

對20 個結點的TSP 問題訓練情況如圖5 所示。圖5a 是訓練損失，圖5b 是在訓練時每批次的平均路徑長度，圖5c 是在驗證集上的平均路徑長度（在訓練過程中，對于每一個數據集通過隨機打亂等方式生成1.28×108個實例，每個batch 由512個實例組成，每訓練50 次記錄一次數據，總計50 000 條數據，訓練時間為4 小時47 分39 秒）。

圖5 TSP20 數據集上的訓練與驗證（未平滑）

對50 個結點的TSP 問題訓練情況如圖6 所示。圖6a 是訓練損失，圖6b 是在訓練時每批次的平均路徑長度，圖6c 是在驗證集上的平均路徑長度，為看清數據趨勢我們對數據進行了平滑處理，其平滑度為0.6（由于顯存限制，在50 個結點的TSP 問題訓練時，我們將每個batch 的實例數設置為200，其他參數不變，總計128 000 條數據，訓練時間為15 小時5 分46 秒）。

圖6 TSP50 數據集上的訓練與驗證（平滑度0.6）

對100 個結點的TSP 問題訓練情況如圖7 所示。從圖中可以看出訓練數據與訓練損失的關系（見圖7a），訓練數據與平均路徑長度的關系（見圖7b），驗證數據與平均路徑長度的關系（見圖7c），平滑度仍取0.6（每個batch 的實例數設置為50，訓練時間為53 小時22 分27 秒）。

圖7 TSP100 數據集上的訓練與驗證（平滑度0.6）

從平均路徑長度和驗證時的平均路徑長度來看，以Transformer 架構和圖4 中所示算法構建求解TSP問題的神經網絡模型是可行的，不過訓練時間相對較長，隨著硬件技術的發展，訓練時間會進一步縮短。

5 結語

一旦神經網絡訓練完成，可以得到關于求解某一規模的TSP 的神經網絡，并且可以通過神經網絡得出結點的選擇概率。此操作的復雜度是問題規模的多項式級別，另外通過選擇概率獲得路徑也是問題規模的多項式級別的操作，故可以認為在獲得訓練好的神經網絡后，求解TSP 是多項式時間可近似的。在尋找近似算法的過程中，筆者沒有使用除問題實例外的其他知識，僅使用了較長的計算時間，這種方法為尋找相應問題的近似算法提供了一定的思路。

使用這種方法求解TSP 也有一定的缺點，主要表現在求解問題的神經網絡的訓練時間相對較長。如何縮短訓練時間是后續研究的主要方向，一方面可以從改進訓練算法的角度考慮；另一方面可以從引入量子算法對神經網絡架構和訓練算法的角度進行改進，以便使用量子計算機求解相應問題。