深度強(qiáng)化學(xué)習(xí)解決動(dòng)態(tài)旅行商問題

陳浩杰，范江亭，劉 勇

（黑龍江大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150006）

0 引言

生活中的運(yùn)輸路線的設(shè)計(jì)、配送快遞等旅行商問題往往會(huì)涉及選擇動(dòng)作的過程，即節(jié)點(diǎn)序列順序的預(yù)測(cè)問題，例如對(duì)于運(yùn)輸路線的設(shè)計(jì)決定以什么順序設(shè)計(jì)運(yùn)輸路線，快遞配送問題是決定在下一個(gè)時(shí)間選擇哪個(gè)客戶節(jié)點(diǎn)作為配送點(diǎn)等，這些決策問題都屬于組合優(yōu)化問題中的旅行商問題，并且很多情況下屬于NP-hard 問題，加入動(dòng)態(tài)網(wǎng)絡(luò)信息后，問題所映射到圖的規(guī)模非常大，解決這些問題的資源消耗隨著圖的節(jié)點(diǎn)增多呈指數(shù)倍數(shù)增長(zhǎng)，所以有必要針對(duì)這些問題研究出更加貼合實(shí)際的求解方法。

近些年，利用強(qiáng)化學(xué)習(xí)自動(dòng)學(xué)習(xí)不斷變化的節(jié)點(diǎn)信息的算法成為機(jī)器學(xué)習(xí)的一大新的探索，本文提出一個(gè)結(jié)合變體Transformer機(jī)制和分布式強(qiáng)化學(xué)習(xí)的統(tǒng)一模型Dy4TSP（Dynamic model for Traveling Salesman Problems），來求解動(dòng)態(tài)旅行商問題中涉及到圖的動(dòng)態(tài)節(jié)點(diǎn)的情況。為了更高效地處理動(dòng)態(tài)圖信息，在輸出節(jié)點(diǎn)序列時(shí)，使用Transformer 的變體通過某種方式得到與每個(gè)輸入序列相關(guān)聯(lián)的權(quán)值，用此權(quán)值來指導(dǎo)模型輸出。整個(gè)模型只需要輸入動(dòng)態(tài)圖信息，選擇要處理的旅行商問題類型，就可以預(yù)測(cè)出對(duì)應(yīng)問題的幾種最優(yōu)決策的節(jié)點(diǎn)解序列。不同于以往貪心產(chǎn)生唯一解的方式，該模型會(huì)預(yù)測(cè)出多個(gè)擁有最優(yōu)獎(jiǎng)勵(lì)值的路線，減少漏掉整條條件概率最大的路線的可能性；并且與大多數(shù)經(jīng)典啟發(fā)式不同，當(dāng)輸入圖的節(jié)點(diǎn)或者邊信息和訓(xùn)練時(shí)的變化不同時(shí)，模型依舊保持魯棒性。為解決圖規(guī)模的動(dòng)態(tài)組合優(yōu)化問題，特別是那些難以設(shè)計(jì)啟發(fā)式的旅行商問題提供了新的方向。

本文的主要工作如下：

1）提出一個(gè)將多頭注意力機(jī)制與分層強(qiáng)化學(xué)習(xí)結(jié)合來求解動(dòng)態(tài)圖上的旅行商問題的輕量級(jí)模型Dy4TSP；

2）本文模型加入了節(jié)點(diǎn)動(dòng)態(tài)變化的元素，隨著配送車輛對(duì)節(jié)點(diǎn)的遍歷，車輛剩余負(fù)載和客戶節(jié)點(diǎn)的需求量發(fā)生變化，更加接近于實(shí)際生活中的旅行商問題；

3）本文模型采用分布式強(qiáng)化學(xué)習(xí)算法融合參數(shù)量更少的圖卷積神經(jīng)網(wǎng)絡(luò)網(wǎng)絡(luò)和預(yù)測(cè)網(wǎng)絡(luò)部分，并行地訓(xùn)練模型，所需的訓(xùn)練時(shí)間更少，在更短的時(shí)間內(nèi)獲得更好的訓(xùn)練效果；

4）本文模型是可擴(kuò)展的，針對(duì)不同的維度都可以選擇相應(yīng)的旅行商問題并輸入到模型中進(jìn)行預(yù)測(cè)與訓(xùn)練，為不同維度的旅行商問題提供了統(tǒng)一的模型。

本文模型可以在沒有標(biāo)簽的情況下，經(jīng)過分布式強(qiáng)化學(xué)習(xí)算法的訓(xùn)練為動(dòng)態(tài)旅行商問題的學(xué)習(xí)提供比以往模型準(zhǔn)確率更高的方法。

1 相關(guān)工作

最近人們對(duì)用深度學(xué)習(xí)和強(qiáng)化學(xué)習(xí)來解決圖的組合優(yōu)化問題產(chǎn)生了興趣。最初將深度強(qiáng)化學(xué)習(xí)用于組合優(yōu)化問題是Vinyals 等引入了指針網(wǎng)絡(luò)（Point Network，PN），對(duì)輸入序列按照注意力機(jī)制得到的概率值重新排列作為模型的輸出，缺陷是該模型基于有監(jiān)督學(xué)習(xí)，嚴(yán)重依賴于標(biāo)簽數(shù)據(jù)。

Bello 等第一次嘗試用強(qiáng)化學(xué)習(xí)算法解決組合優(yōu)化問題，解決了強(qiáng)化學(xué)習(xí)需要標(biāo)簽的問題，但模型的設(shè)計(jì)過程沒有針對(duì)處理圖結(jié)構(gòu)的輸入問題，沒有得到很好的擴(kuò)展應(yīng)用。

Sutskever 等通過將圖變換為一個(gè)序列，然后再基于序列到序列模型來生成節(jié)點(diǎn)決策順序。這種方法存在的問題非常明顯，在將圖變換為序列的過程中會(huì)丟失大量的結(jié)構(gòu)信息。

Khalil 等使用基于圖網(wǎng)絡(luò)表征的單一模型，通過擬合Q-learning訓(xùn)練模型輸出節(jié)點(diǎn)插入到局部路線中的順序，每一步為智能體提供增量獎(jiǎng)勵(lì)有效地學(xué)習(xí)貪心算法來依次構(gòu)造最優(yōu)解。缺點(diǎn)是模型需要人為的設(shè)計(jì)輔助函數(shù)，泛化能力差。

Kulkarni 等介紹了一個(gè)分層強(qiáng)化學(xué)習(xí)模型，這是強(qiáng)化學(xué)習(xí)領(lǐng)域最經(jīng)典的并行分布式工作，可以結(jié)合不同層次的動(dòng)作價(jià)值函數(shù)，多個(gè)時(shí)間尺度的抽象來幫助智能體的優(yōu)化策略，為本模型的訓(xùn)練模型的分布式學(xué)習(xí)提供了新的思路。

Nazari 等將指針網(wǎng)絡(luò)的編碼器替換為一維卷積層直接進(jìn)行節(jié)點(diǎn)序列的表征過程，從而可以有效更新狀態(tài)變化后節(jié)點(diǎn)表征向量，他們將該模型應(yīng)用于車輛路徑問題中，減少了很多動(dòng)態(tài)節(jié)點(diǎn)變化上的不必要的計(jì)算。

Gao 等利用圖注意力神經(jīng)網(wǎng)絡(luò)以及循環(huán)神經(jīng)網(wǎng)絡(luò)對(duì)組合優(yōu)化問題的排序策略進(jìn)行學(xué)習(xí)，采用PPO（Proximal Policy Optimization）強(qiáng)化學(xué)習(xí)算法對(duì)模型進(jìn)行訓(xùn)練，但是在優(yōu)化能力上未達(dá)到或極度靠近最優(yōu)解。

本文不同于以上模型，本文結(jié)合多頭注意力機(jī)制和分布式強(qiáng)化學(xué)習(xí)方法，以一種自動(dòng)學(xué)習(xí)的方式，實(shí)時(shí)地生成問題的解，不但擁有高效的收斂性，而且得到的結(jié)果更加接近最優(yōu)解。

2 問題定義

經(jīng)典旅行商問題（Traveling Salesman Problem，TSP）：配送車輛從圖中配送中心節(jié)點(diǎn)出發(fā)，經(jīng)過所有城市一次且僅一次并回到配送中心，目標(biāo)是配送客戶節(jié)點(diǎn)需求數(shù)多，且配送路徑最短。

配送收集旅行商問題（Distribution Collection Traveling Salesman Problem，DCTSP）：配送車輛從圖中配送中心節(jié)點(diǎn)出發(fā)，由一限定負(fù)載容量的配送車輛負(fù)責(zé)配送需求大于零的客戶，目標(biāo)是配送客戶節(jié)點(diǎn)需求數(shù)多，且配送路徑最短。

拆分交付旅行商問題（Split Delivery Traveling Salesman Problem，SDTSP）：在配送收集旅行商問題的基礎(chǔ)上，將每個(gè)客戶的需求量拆分成多部分，允許配送車輛對(duì)客戶節(jié)點(diǎn)的需求量大于車輛剩余負(fù)載的客戶節(jié)點(diǎn)進(jìn)行配送，該解決方案可以將給定客戶節(jié)點(diǎn)的需求量分配到多條路線以減少空載率。

3 神經(jīng)網(wǎng)絡(luò)構(gòu)建

將對(duì)動(dòng)態(tài)旅行商問題求取最優(yōu)解的過程看成序列決策問題，整體用馬爾可夫決策過程建模，通過設(shè)計(jì)一個(gè)最優(yōu)策略的概率分布函數(shù)，來達(dá)到建立實(shí)時(shí)輸出可行解序列的參數(shù)化模型的目標(biāo)，模型的訓(xùn)練通過分布式強(qiáng)化學(xué)習(xí)訓(xùn)練產(chǎn)生近似最優(yōu)解來修正預(yù)測(cè)模型輸出的節(jié)點(diǎn)序列順序。

神經(jīng)網(wǎng)絡(luò)構(gòu)建階段包括網(wǎng)絡(luò)模型創(chuàng)建和模型訓(xùn)練兩階段，主要分為3 個(gè)步驟，如圖1 所示。

1）Graph2Vec 圖卷積神經(jīng)網(wǎng)絡(luò)，以整個(gè)

T

時(shí)刻的圖

G

和到目前為止輸出的節(jié)點(diǎn)集

S

依次作為輸入，由前饋網(wǎng)絡(luò)結(jié)合鄰居及節(jié)點(diǎn)信息進(jìn)行聚合操作，輸出某個(gè)時(shí)刻每個(gè)節(jié)點(diǎn)的向量序列，如圖1（a）所示；2）Vec2Seq 預(yù)測(cè)網(wǎng)絡(luò)，將Graph2Vec 網(wǎng)絡(luò)的輸出中取

t

時(shí)刻預(yù)測(cè)網(wǎng)絡(luò)未輸出節(jié)點(diǎn)的表征向量，連接上一時(shí)刻預(yù)測(cè)網(wǎng)絡(luò)已輸出的節(jié)點(diǎn)，依次輸入到多頭上下文注意力機(jī)制和Softmax 層，得到

t

時(shí)刻節(jié)點(diǎn)的概率分布，依據(jù)概率分布等信息輸出前

b

個(gè)節(jié)點(diǎn)作為Vec2Seq 預(yù)測(cè)網(wǎng)絡(luò)預(yù)測(cè)得到的

t

+1時(shí)刻將要遍歷的節(jié)點(diǎn)，如圖1（b）所示，第1）～2）部分作為本文的主體模型進(jìn)行實(shí)時(shí)輸出可行解序列的工作；3）n2Drl 訓(xùn)練網(wǎng)絡(luò)，對(duì)以上創(chuàng)建的網(wǎng)絡(luò)模型進(jìn)行訓(xùn)練，將Graph2Vec 網(wǎng)絡(luò)的節(jié)點(diǎn)表征向量與Vec2Seq 網(wǎng)絡(luò)的預(yù)測(cè)節(jié)點(diǎn)部分輸入到

n

個(gè)線程的Actor 中，多個(gè)線程分布式探索環(huán)境，積累狀態(tài)過度量（狀態(tài)，動(dòng)作，獎(jiǎng)勵(lì)）等信息，一個(gè)批次結(jié)束后更新狀態(tài)過渡向量的優(yōu)先級(jí)并存入經(jīng)驗(yàn)緩存機(jī)制中，使用多個(gè)線程并行運(yùn)行的方式更加高效地收集大規(guī)模圖數(shù)據(jù)，如圖1（c）所示。

圖1 神經(jīng)網(wǎng)絡(luò)構(gòu)建框架Fig.1 Neural network construction framework

綜上，通過Graph2Vec 生成網(wǎng)絡(luò)表征，將每個(gè)時(shí)刻的節(jié)點(diǎn)表征向量提供給Vec2Seq 預(yù)測(cè)網(wǎng)絡(luò)進(jìn)行節(jié)點(diǎn)序列預(yù)測(cè)，與此同時(shí)Vec2Seq 預(yù)測(cè)網(wǎng)絡(luò)同步更新網(wǎng)絡(luò)參數(shù)，使得對(duì)于圖中的每個(gè)節(jié)點(diǎn)，可以更準(zhǔn)確地判斷出該節(jié)點(diǎn)是否是最優(yōu)解的一部分。

3.1 Graph2Vec圖卷積網(wǎng)絡(luò)

Trivedi 等使用了循環(huán)神經(jīng)網(wǎng)絡(luò)（Recurrent Neural Network，RNN）框架，使得某一時(shí)刻的節(jié)點(diǎn)計(jì)算依賴于上一時(shí)刻的計(jì)算結(jié)果，很難具備高效的并行計(jì)算能力，并且RNN 的網(wǎng)絡(luò)結(jié)構(gòu)對(duì)于長(zhǎng)距離和層級(jí)化的依賴關(guān)系難以建立，尤其是在本文所研究的動(dòng)態(tài)旅行商問題中，這樣導(dǎo)致求解問題隨著輸入順序動(dòng)態(tài)改變，網(wǎng)絡(luò)預(yù)測(cè)的性能有一定的差異。同時(shí)在時(shí)間序列中對(duì)圖神經(jīng)網(wǎng)絡(luò)截取快照是一種粗糙的方法，基于此Graph2Vec 網(wǎng)絡(luò)使用連續(xù)時(shí)間的節(jié)點(diǎn)表征，通過聚合鄰居節(jié)點(diǎn)的信息，直接在圖中進(jìn)行卷積操作，產(chǎn)生整個(gè)時(shí)間序列的向量作為節(jié)點(diǎn)表示。

3.2 Vec2Seq預(yù)測(cè)網(wǎng)絡(luò)

在這部分網(wǎng)絡(luò)中，延用了NLP（Natural Language Processing）中廣為應(yīng)用的成熟技術(shù)Transformer 模型，由于Transformer 使用自注意力機(jī)制和前饋神經(jīng)網(wǎng)絡(luò)等結(jié)構(gòu)搭建網(wǎng)絡(luò)，解決了RNN 模型的長(zhǎng)期依賴問題，并且相對(duì)于卷積神經(jīng)網(wǎng)絡(luò)可以更好地進(jìn)行并行計(jì)算，可以有效地處理動(dòng)態(tài)網(wǎng)絡(luò)結(jié)構(gòu)，所以Vec2Seq 預(yù)測(cè)網(wǎng)絡(luò)僅基于多頭上下文注意力機(jī)制從多個(gè)角度計(jì)算Graph2Vec 的節(jié)點(diǎn)表征序列對(duì)預(yù)測(cè)模型輸出序列的注意力權(quán)重，來指示當(dāng)前輸出的節(jié)點(diǎn)，提高了整個(gè)模型的預(yù)測(cè)準(zhǔn)確度。

最后Vec2Seq 預(yù)測(cè)網(wǎng)絡(luò)通過Softmax 傳遞結(jié)果，如式（6）利用Softmax 函數(shù)使所有未輸出節(jié)點(diǎn)的相似性量歸一化，把相似性

C

映射成0 到1 之間的實(shí)數(shù)，將此數(shù)值作為節(jié)點(diǎn)

u

和鄰居節(jié)點(diǎn)

v

的概率值，此后在預(yù)測(cè)節(jié)點(diǎn)時(shí)可以選取相應(yīng)概率的節(jié)點(diǎn)作為Vec2Seq 預(yù)測(cè)網(wǎng)絡(luò)的目標(biāo)輸出。

輸出節(jié)點(diǎn)前首先判斷目標(biāo)節(jié)點(diǎn)的需求值是否大于0，滿足條件后開始進(jìn)行節(jié)點(diǎn)序列輸出，輸出的過程中使用集束搜索算法取代貪心算法，每次深度擴(kuò)展解時(shí)只保留概率值最大的前

b

個(gè)節(jié)點(diǎn)加入集合

S

，其中

S

表示屬于已輸出的節(jié)點(diǎn)集。

3.3 n2Drl訓(xùn)練網(wǎng)絡(luò)

本文考慮使用一種自我驅(qū)動(dòng)性的深度強(qiáng)化學(xué)習(xí)算法n2Drl 來訓(xùn)練模型，該算法的理論模型基于馬爾可夫決策過程，該理論讓智能體在所給的環(huán)境狀態(tài)中通過獎(jiǎng)勵(lì)值的反饋?zhàn)灾鲗W(xué)習(xí)做動(dòng)作，以使累積獎(jiǎng)勵(lì)最大化。由于動(dòng)態(tài)旅行商問題中模型需要訓(xùn)練的樣本的數(shù)量相較于之前會(huì)有成倍數(shù)增長(zhǎng)的趨勢(shì)，在這種情況下，引入分布式強(qiáng)化學(xué)習(xí)，采用并行智能體策略，把任務(wù)分配到不同的智能體上，復(fù)制

n

個(gè)線程，在每個(gè)線程運(yùn)行一個(gè)智能體同所給的環(huán)境進(jìn)行交互來并行縮短收集數(shù)據(jù)的時(shí)間。在第二部分Vec2Seq 預(yù)測(cè)網(wǎng)絡(luò)輸出可行解序列后，訓(xùn)練過程中需要計(jì)算出輸出這

b

個(gè)節(jié)點(diǎn)后所帶來的獎(jiǎng)勵(lì)值，通過獎(jiǎng)勵(lì)值來衡量當(dāng)前節(jié)點(diǎn)動(dòng)作的優(yōu)劣，更新函數(shù)如式（9）：

其中：

Q

表示

t

時(shí)刻狀態(tài)行為值函數(shù)，表示配送車輛在策略

P

(

a

|

s

，

a

)和當(dāng)前狀態(tài)

s

下，采取動(dòng)作

a

作為解的優(yōu)劣程度，如式（9）所示為當(dāng)前輸出的節(jié)點(diǎn)

v

和其所有鄰居節(jié)點(diǎn)的拼接，

J

表示

t

時(shí)刻的路徑長(zhǎng)度，為遍歷前后客戶節(jié)點(diǎn)的二維坐標(biāo)位置

F

的平方差，其中

θ

是每一個(gè)部分的權(quán)重參數(shù)，決定了每個(gè)部分對(duì)動(dòng)作獎(jiǎng)勵(lì)值的貢獻(xiàn)度。本文將截止到

t

時(shí)刻為止智能體探索環(huán)境所反饋回的總獎(jiǎng)勵(lì)值定義為

R

，如式（10）所示，計(jì)算多步獎(jiǎng)勵(lì)的過程中引入衰減因子

γ

，作為下一時(shí)刻獎(jiǎng)勵(lì)值的系數(shù)，令未來狀態(tài)所反饋回的獎(jiǎng)勵(lì)值以不同程度的衰減度遞歸地指導(dǎo)智能體做決策，來同時(shí)關(guān)注決策后的眼前利益和未來獎(jiǎng)勵(lì)。

之后將這些數(shù)據(jù)，壓入緩存中并隨機(jī)抽取批量數(shù)據(jù)利用式（11）對(duì)帶有模型參數(shù)的損失函數(shù)

L

(

W

)進(jìn)行訓(xùn)練，訓(xùn)練模型的網(wǎng)絡(luò)參數(shù)

W

由Xavier初始化器初始化，來保持各層梯度的比例大致相同，后期使用Adam優(yōu)化器對(duì)損失函數(shù)式（11）進(jìn)行隨機(jī)梯度下降優(yōu)化更新參數(shù)

W

，使得總獎(jiǎng)勵(lì)值

R

與模型輸出的

t

時(shí)刻狀態(tài)行為值函數(shù)

Q

越來越接近，并將優(yōu)化后的網(wǎng)絡(luò)參數(shù)

W

進(jìn)行輸出作為n2Drl 訓(xùn)練網(wǎng)絡(luò)的訓(xùn)練結(jié)果。

4 實(shí)驗(yàn)與結(jié)果分析

4.1 Vec2Seq預(yù)測(cè)網(wǎng)絡(luò)參數(shù)設(shè)置

圖2 多頭注意力機(jī)制Fig.2 Multi-head attention mechanism

圖3 Softmax函數(shù)網(wǎng)絡(luò)結(jié)構(gòu)Fig.3 Softmax function network structure

4.2 實(shí)驗(yàn)參數(shù)設(shè)置

對(duì)于任意時(shí)刻

t

(

t

=0，1，…，

T

(

T

≥0))，考慮到現(xiàn)實(shí)中旅行商問題的節(jié)點(diǎn)分布隨機(jī)性，本文隨機(jī)生成有著不同需求量的客戶節(jié)點(diǎn)來模擬現(xiàn)實(shí)世界，實(shí)驗(yàn)過程中隨機(jī)生成1 000 個(gè)圖，圖中客戶節(jié)點(diǎn)數(shù)目設(shè)置皆為20、50 和100 個(gè)，將這些圖

G

(

V

，

E

)輸入到本文的模型Dy4TSP 中。本文對(duì)所提出的模型進(jìn)行實(shí)驗(yàn)，設(shè)置每個(gè)epoch 處理256 個(gè)批次，迭代次數(shù)皆為30 次，設(shè)置時(shí)間最大為

T

=100，在訓(xùn)練模型的過程中，學(xué)習(xí)率設(shè)為0.000 1，從Replay Memory 中采樣的訓(xùn)練樣例為16，訓(xùn)練模型的網(wǎng)絡(luò)參數(shù)

W

使用Adam優(yōu)化器對(duì)損失函數(shù)式（11）進(jìn)行隨機(jī)梯度下降來更新，其中梯度下降的參數(shù)設(shè)置

β

=0.9，

β

=0.99，

ε

=10。與此同時(shí)，發(fā)現(xiàn)本文模型在配送收集旅行商問題、拆分交付旅行商問題的圖訓(xùn)練時(shí)的超參數(shù)和旅行商問題的超參數(shù)一致，這樣可以在不同的問題上節(jié)省調(diào)整參數(shù)的時(shí)間。為了減少訓(xùn)練時(shí)間，使得模型更快地收斂到預(yù)計(jì)的效果，加入預(yù)訓(xùn)練過程，使用已訓(xùn)練好的模型訓(xùn)練新的網(wǎng)絡(luò)，由經(jīng)過預(yù)訓(xùn)練的模型來解決不同節(jié)點(diǎn)數(shù)目的同類型旅行商問題，本文模型（

T

≥0）比沒有在相同實(shí)例大小問題上訓(xùn)練表現(xiàn)好，這表明本文加入預(yù)訓(xùn)練過程的模型可以很好地泛化到不同節(jié)點(diǎn)的實(shí)例問題中。

4.3 對(duì)比實(shí)驗(yàn)

由于旅行商問題亦屬于組合優(yōu)化問題，所以針對(duì)所研究的旅行商系列問題，本文將選取處理組合優(yōu)化問題的模型PN、S2V（Structure2Vector）、注意力模型（Attention Model，AM）、帶有邊嵌入的圖注意網(wǎng)絡(luò)（Graph Attention Network with Edge Embedding，EGATE）和動(dòng)態(tài)強(qiáng)化學(xué)習(xí)網(wǎng)絡(luò)（Dynamic Reinforcement Learning network，DyRL）與本文模型Dy4TSP 作對(duì)比，以啟發(fā)式算法優(yōu)化器LKH3（Lin-Kernighan-Helsgaun3）得到的路徑長(zhǎng)度為最優(yōu)性能基準(zhǔn)。圖4（a）、（b）展示了在固定客戶節(jié)點(diǎn)數(shù)目的TSP、DCTSP 上使用不同的模型，所得到的和開源求解器LKH3 的最優(yōu)性能差距，即最優(yōu)路徑的差距對(duì)比，圖4（c）表示不同的模型對(duì)于不同節(jié)點(diǎn)數(shù)的SDTSP 問題的最優(yōu)路徑長(zhǎng)度。圖4（a）、（b）中的TSP100 表示該旅行商問題由100 個(gè)客戶組成，對(duì)于TSP100而言，本文模型在最優(yōu)路徑上的優(yōu)化性能超越了其他對(duì)比模型大約0.15 到0.37 個(gè)單位，比較接近于EGATE 模型，并且在20 個(gè)節(jié)點(diǎn)時(shí)可以達(dá)到LKH3 的最優(yōu)路徑長(zhǎng)度。

圖4（b）加入動(dòng)態(tài)元素后所有的對(duì)比模型皆與最優(yōu)路徑差距較大，與此同時(shí)本文模型也可以取得比對(duì)比算法較優(yōu)的結(jié)果，尤其是Dy4TSP.b5 時(shí)，本文模型使用集束搜索寬度5，所有情況下，不同的節(jié)點(diǎn)數(shù)目皆可以達(dá)到0.1 到1.05 的最優(yōu)路徑差距；由于SDTSP 沒有網(wǎng)絡(luò)上的算法求解器，本文將圖4（c）的縱坐標(biāo)設(shè)置為最優(yōu)路徑長(zhǎng)度，將DyRL AM 模型和EGATE 模型應(yīng)用于此問題，不同的模型之間有著0.01 到1.01 的差距，Dy4TSP 以不到0.1 的差距優(yōu)于EGATE。基于圖4 實(shí)驗(yàn)結(jié)果，可以發(fā)現(xiàn)本文模型能夠比對(duì)比模型獲得更優(yōu)的結(jié)果，在節(jié)點(diǎn)數(shù)目規(guī)模達(dá)到100 個(gè)后，本文模型在不同的問題上皆明顯優(yōu)于對(duì)比模型，在限制時(shí)間內(nèi)輸出最接近最優(yōu)解決方案的路線。

同時(shí)還對(duì)比了不同搜索算法對(duì)于選擇節(jié)點(diǎn)后生成總遍歷長(zhǎng)度的影響，在測(cè)試過程中選取貪心算法和不同集束參數(shù)的集束搜索算法。理論上取樣數(shù)目越多，則更容易得到理想的節(jié)點(diǎn)路線，然而考慮到時(shí)間復(fù)雜度會(huì)隨著選取節(jié)點(diǎn)數(shù)目的增多成指數(shù)增長(zhǎng)這一弊端，如何找到一個(gè)理想的臨界值是加入搜索算法對(duì)比實(shí)驗(yàn)的目標(biāo)。圖4 比較了本文模型在不同搜索算法下與當(dāng)前最優(yōu)的開源求解器LKH3 的距離差距，其中g(shù)r 表示貪心算法，s 表示隨機(jī)取樣，b 表示集束搜索算法，右側(cè)的數(shù)字表示集束寬度參數(shù)。本文發(fā)現(xiàn)，在使用貪心算法時(shí)的最優(yōu)路徑差距普遍比集束搜索算法要更長(zhǎng)，集束寬度為5 時(shí)達(dá)到最優(yōu)路徑差距。

圖4 不同模型的最優(yōu)路徑差距和最優(yōu)路徑長(zhǎng)度比較Fig.4 Comparison of optimal path gap and optimal path length between different models

圖5 比較了不同節(jié)點(diǎn)數(shù)目的SDTSP 在訓(xùn)練過程中隨著epoch 的增加，學(xué)習(xí)網(wǎng)絡(luò)的損失值的變化。由于學(xué)習(xí)網(wǎng)絡(luò)隨著訓(xùn)練時(shí)間的增多，經(jīng)過反向傳播、梯度優(yōu)化等過程對(duì)本模型進(jìn)行學(xué)習(xí)優(yōu)化以及學(xué)習(xí)過程中權(quán)重矩陣的調(diào)整后，控制學(xué)習(xí)網(wǎng)絡(luò)整體的學(xué)習(xí)幅度朝著預(yù)測(cè)更加準(zhǔn)確的方向進(jìn)行，模型的損失值在開始時(shí)快速下降，最后損失值趨于平穩(wěn)，在一定范圍內(nèi)震蕩，所以損失值后期呈現(xiàn)逐漸收斂于0 的狀態(tài)。

圖5 不同節(jié)點(diǎn)數(shù)目訓(xùn)練損失值比較Fig.5 Comparision of training loss values for different numbers of nodes

5 結(jié)語

本文提出了一種基于強(qiáng)化學(xué)習(xí)模型Dy4TSP 來計(jì)算NPhard 問題中的動(dòng)態(tài)旅行商問題。本文模型結(jié)合了深度學(xué)習(xí)技術(shù)和分布式強(qiáng)化學(xué)習(xí)方法從而得到了一種可以自動(dòng)學(xué)習(xí)預(yù)測(cè)節(jié)點(diǎn)序列的模型。核心部分是一個(gè)Vec2Seq 預(yù)測(cè)網(wǎng)絡(luò)，通過后期n2Drl 分布式訓(xùn)練網(wǎng)絡(luò)的訓(xùn)練實(shí)時(shí)地生成解決方案，可以精準(zhǔn)地預(yù)測(cè)組合優(yōu)化問題中涉及序列決策問題中節(jié)點(diǎn)序列預(yù)測(cè)的概率，多頭上下文注意力機(jī)制網(wǎng)絡(luò)的設(shè)計(jì)和分布式強(qiáng)化學(xué)習(xí)訓(xùn)練的目的是盡可能從多個(gè)特征角度探索環(huán)境，也在盡可能少的時(shí)間合成多種解決方案，從而可以通過集束搜索算法對(duì)解決空間進(jìn)行快速探索，通過大量不同節(jié)點(diǎn)數(shù)目的實(shí)驗(yàn)結(jié)果表明，Dy4TSP 顯著地比現(xiàn)有文獻(xiàn)中解決動(dòng)態(tài)旅行商問題的技術(shù)速度更快、質(zhì)量更高，可以很好地處理動(dòng)態(tài)旅行商問題。