王 原 陳 名 邢立寧 吳亞輝 馬武彬 趙 宏

1(國防科技大學(xué)系統(tǒng)工程學(xué)院 長沙 410073) 2(湖南安全技術(shù)職業(yè)學(xué)院 長沙 410151)

組合優(yōu)化問題(combinatorial optimization problem, COP)的求解一直是運籌學(xué)領(lǐng)域的一個重要研究方向.典型組合優(yōu)化問題如旅行商問題(travelling salesman problem, TSP)、車輛路徑問題(vehicle routing problem, VRP)、作業(yè)車間調(diào)度問題(job shop scheduling problem, JSSP)等通常均屬于NP-Hard問題.因此，針對組合優(yōu)化問題設(shè)計高效的求解算法一直是該領(lǐng)域的重要研究方向.

目前針對組合優(yōu)化問題的求解方法一般被分為2種類型：近似算法(approximation algorithm)以及精確算法(exact algorithm).這2類方法面臨2個問題的挑戰(zhàn)[1-2]：1) 精確算法求解的時間消耗隨著問題規(guī)模的擴大急遽上升，針對較大規(guī)模問題無法在可接受時間內(nèi)取得最優(yōu)解；2) 設(shè)計有效的啟發(fā)式算法需要大量針對性的領(lǐng)域知識以及大量的試錯(trial-and-error).因此，如何針對組合優(yōu)化問題設(shè)計有效的求解算法，仍然面臨重重困難.

近年來，一批深度強化學(xué)習(xí)方法在組合優(yōu)化問題的新應(yīng)用的提出給本問題的解決帶來新的思路[3].得益于端到端學(xué)習(xí)(end-to-end learning)模型[4]的提出，深度強化學(xué)習(xí)方法能夠通過在同一問題分布的不同實例上的訓(xùn)練來提取有關(guān)問題實例的深層特征，并基于問題特征對問題實例進行求解.深度強化學(xué)習(xí)方法在求解組合優(yōu)化問題時具有如下2個特征：

1) 深度強化學(xué)習(xí)能夠通過訓(xùn)練的方式搜索問題分布的特征并進行求解模型的自完善，且該過程不需要模型設(shè)計者掌握問題相關(guān)的領(lǐng)域知識；

2) 模型訓(xùn)練結(jié)束后，深度強化學(xué)習(xí)在求解時，能夠以O(shè)(n)的時間復(fù)雜度求解問題實例.

然而，深度強化學(xué)習(xí)在求解組合優(yōu)化問題時，仍面臨一定的不足：

1) 算法求解表現(xiàn)距離state-of-the-art算法仍有差距；

2) 缺乏解空間的搜索能力，且對輸入分布較為敏感.

為解決該問題，本文提出了一種基于蟻群算法和深度學(xué)習(xí)方法的混合啟發(fā)式算法框架.該框架采用深度學(xué)習(xí)方法進行特征提取，然后采用蟻群算法基于問題特征在解空間內(nèi)進行可行解的搜索.該框架能夠有效利用深度學(xué)習(xí)方法的特征提取能力，以及蟻群算法的解空間搜索能力.

本文的主要貢獻有4個方面:

1) 提出了一種基于蟻群算法和深度學(xué)習(xí)方法的組合優(yōu)化問題求解方案，并采用該方法對旅行商問題進行了求解.

2) 提出了一種深度學(xué)習(xí)方法進行旅行商問題特征提取的端到端學(xué)習(xí)方法，該方法能夠?qū)⒉煌?guī)模的旅行商問題實例轉(zhuǎn)化為對應(yīng)的啟發(fā)式信息矩陣.

3) 在啟發(fā)式信息矩陣的基礎(chǔ)上，采用蟻群算法對旅行商問題實例進行了求解.

4) 采用TSPLIB中的標準算例對該方法的求解表現(xiàn)和算法穩(wěn)定性進行了驗證.

1 相關(guān)工作

本文從蟻群算法和深度學(xué)習(xí)方法求解組合優(yōu)化問題2方面分別介紹本文的相關(guān)工作.

蟻群算法是一種模擬螞蟻的覓食行為的仿生算法，該算法由Dorigo于1992年提出[5].在該文中，作者描述了蟻群算法求解旅行商問題的基本流程：首先將人工螞蟻隨機放置于一個開始城市并遵循基于概率的規(guī)則逐步構(gòu)建解.每次產(chǎn)生可行解后，人工螞蟻會按照解的好壞在路徑上留下對應(yīng)的信息素信息.經(jīng)過多代迭代后，在信息素的影響下蟻群算法會逐漸收斂到具有較高質(zhì)量的解.在該工作的基礎(chǔ)上，研究者針對蟻群算法進行了大量的改進，主要成果包括[6-9]：精英蟻群算法(elitist ant system, EAS)、最大-最小蟻群算法(max-min ant system, MMAS)、多蟻群系統(tǒng)(ant colony system, ACS)、基于排序的蟻群算法(rank-based ant system, RAS)等.

為改進蟻群算法在旅行商問題上的求解效能，一類典型的解決辦法是采用蟻群算法與其他類型啟發(fā)式算法的混合算法.龔本燦等人[10]采用蟻群算法生成旅行商問題的初始解，并采用3種不同的鄰域搜索算子對初始解進行改進.Mavrovouniotis和Yang[11]針對蟻群算法求解旅行商問題中算法收斂速度較慢和容易陷入局部最優(yōu)的問題設(shè)計了多種不同的鄰域搜索算子.另一種改進蟻群算法的求解效能的方案是在蟻群算法的求解結(jié)構(gòu)上做改進.Mahi等人[12]提出了一種基于粒子群算法、蟻群算法和3-opt鄰域搜索算法的混合啟發(fā)式算法框架用于求解旅行商問題.該方法被證明具有比當時已有算法更好的算法效能.Pang等人[13]提出了一種基于鄰域搜索庫的蟻群算法用于求解旅行商問題，計算實驗表明采用鄰域搜索庫能夠有效改善算法的求解效能.Manfrin等人[14]將蟻群中的人工螞蟻分為多個不同的并行運行的蟻群，并采用全局信息素交換的方式在不同的并行蟻群間進行交換，并證明采用并行蟻群的方法能夠有效地加速蟻群算法的收斂并提升解的質(zhì)量.Zhang等人[15]提出了一種改進最大-最小蟻群算法.該算法采用基于最優(yōu)解的隨機采樣的方法確定信息素矩陣的最大及最小值，同時確定每次迭代時信息素殘留的量.Gan等人[16]將蟻群算法中的人工螞蟻分為常規(guī)蟻和搜索蟻2個不同的族群.其中，常規(guī)蟻以傳統(tǒng)蟻群算法構(gòu)建解的方式進行解空間搜索，而搜索蟻則更傾向于在現(xiàn)有最優(yōu)解的鄰域進行可行解的搜索.

近年來，深度強化學(xué)習(xí)方法在路徑規(guī)劃問題中涌現(xiàn)了大量應(yīng)用.Vinyals等人[17]提出了一種基于指針網(wǎng)絡(luò)的旅行商問題求解方式.該方法能夠?qū)⑷我庖?guī)模的旅行商問題轉(zhuǎn)化為對應(yīng)規(guī)模的向量向量輸出，并基于貪婪原則進行求解.Nowak等人[18]提出了一種基于圖神經(jīng)網(wǎng)絡(luò)(graph neural network, GNN)的旅行商問題求解方法.該方法能夠同時接受有監(jiān)督訓(xùn)練和無監(jiān)督訓(xùn)練.Prates等人[19]在Nowak[18]的基礎(chǔ)上設(shè)計了一種基于圖卷積網(wǎng)絡(luò)(graph convolutional network, GCN)的深度學(xué)習(xí)方法，用于求解TSP問題.該網(wǎng)絡(luò)能夠更好地提取TSP問題中的客戶和連邊的深層信息.然而，該方法只能通過有監(jiān)督的方式學(xué)習(xí)，每次訓(xùn)練需要輸入TSP問題實例以及對應(yīng)的最優(yōu)解.其中最優(yōu)解采用Concorde TSP solver產(chǎn)生.Joshi等人[20]則以連邊為中心構(gòu)建了一類新的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu).在該結(jié)構(gòu)中，連邊信息首先輸入一個多層卷積神經(jīng)網(wǎng)絡(luò)，網(wǎng)絡(luò)在經(jīng)過多層卷積后，其輸出再經(jīng)過一個多層感知機(multilayer perceptron, MLP)轉(zhuǎn)化為可能出現(xiàn)在最優(yōu)解中的概率值.為訓(xùn)練該網(wǎng)絡(luò)，需要同時向該網(wǎng)絡(luò)輸入3個不同的向量：一個包含全部客戶節(jié)點位置信息的向量，一個包含全部連邊權(quán)重的向量，以及一個預(yù)期的目標值.其中預(yù)期的目標值采用Concorde TSP solver產(chǎn)生.

采用圖神經(jīng)網(wǎng)絡(luò)方法求解TSP問題目前存在2個主要限制：1)神經(jīng)網(wǎng)絡(luò)維度需與問題維度一致；2)圖神經(jīng)網(wǎng)絡(luò)通常采用有監(jiān)督學(xué)習(xí)方式，其學(xué)習(xí)結(jié)果依賴于產(chǎn)生訓(xùn)練實例對應(yīng)的最優(yōu)解方法的優(yōu)劣.Dai等人[21]采用Structure2Vec技術(shù)將旅行商問題的圖模型以及當前解的狀態(tài)轉(zhuǎn)換為向量輸入，并基于Q學(xué)習(xí)方法設(shè)計了基于該向量輸入的求解方式.Bello等人[22]針對文獻[17]中訓(xùn)練樣本必須帶標簽(即事先已知最優(yōu)解和路徑)的問題，設(shè)計了能夠基于經(jīng)驗進行求解的指針網(wǎng)絡(luò).Kool等人[23]將深度神經(jīng)網(wǎng)絡(luò)和注意力機制進行結(jié)合，用于求解旅行商問題.Nazari等人[24]在文獻[21]的基礎(chǔ)上，考慮到問題求解的動態(tài)性因素，提出了基于注意力機制的深度學(xué)習(xí)方法.該方法將旅行商問題的向量輸入和當前部分解通過嵌入層(embeddings)轉(zhuǎn)換為高維向量，并基于該向量進行了問題求解.有關(guān)深度學(xué)習(xí)方法求解旅行商問題的其他方法可見綜述文獻[25].

本文提出了一種基于深度學(xué)習(xí)和蟻群算法的組合優(yōu)化算法混合求解策略.該方法首先使用深度學(xué)習(xí)方法挖掘問題實例中的特征，并形成對應(yīng)的特征矩陣.以該矩陣為基礎(chǔ)，采用蟻群算法進行解的搜索.該方法能夠有效求解不同規(guī)模的旅行商問題.

2 旅行商問題模型

旅行商問題是一個經(jīng)典的組合優(yōu)化問題.該問題可描述為存在一系列城市和一個商人，商人要按照順序遍歷全部的城市，每個城市只能訪問一次.問題優(yōu)化目標為游歷的總路徑最短.該問題數(shù)學(xué)模型如下：旅行商問題可以表示為一個無向圖Ts=(S,E)，其中，S為全部城市節(jié)點集合，E為城市節(jié)點間的連邊集合.邊eij∈E(i,j∈N,i≠j)有與其相關(guān)的成本dij.

該問題的決策變量為

(1)

該問題的優(yōu)化目標為

(2)

3 深度智慧型蟻群算法框架

深度智慧型蟻群優(yōu)化算法(deep intelligent ant colony optimization, DIACO)在蟻群算法基礎(chǔ)上，通過將蟻群算法中的啟發(fā)式信息矩陣替換為采用深度強化學(xué)習(xí)方法提取的問題特征矩陣，對算法的求解效能進行了改進.為介紹智慧型蟻群算法，首先介紹經(jīng)典蟻群算法框架.

經(jīng)典蟻群算法在構(gòu)建旅行商問題的解時采用以下步驟：

1) 隨機選擇一個城市，并將人工螞蟻放置于該城市.

2) 人工螞蟻采用輪盤賭原則選擇下一步到達的城市，城市被選擇的概率為

(3)

其中，pij為人工螞蟻從城市i出發(fā)拜訪城市j的可能性.τij為人工螞蟻殘留在邊ij上的信息素信息，ηij為邊ij上的啟發(fā)式信息.α和β為控制啟發(fā)式信息和信息素信息重要性的參數(shù).

3) 每當人工螞蟻訪問一個城市時，就將該城市放入當前解，并將該城市加入當前人工螞蟻的禁止訪問列表.

4) 當全部城市都被訪問完后，人工螞蟻返回開始城市，計算當前解的收益，并根據(jù)式(4)更新信息素矩陣：

(4)

(5)

其中，lk為螞蟻k求得的當前問題的解的路徑長度.

通過以上分析不難看出，蟻群算法求解旅行商問題的效果主要取決于2項信息：信息素信息τij以及啟發(fā)式信息ηij.目前針對蟻群算法的研究，主要集中在如何通過改進信息素信息τij的更新方式以促進蟻群算法的收斂和改進蟻群算法的效果.而啟發(fā)式信息則多采用如下方法確定：

(6)

注意到以上問題，在DIACO中，我們設(shè)計了基于深度學(xué)習(xí)方法的問題特征提取方法，并采用該方法獲得的問題特征矩陣代替經(jīng)典蟻群算法中的ηij矩陣，以改進蟻群算法的求解表現(xiàn).DIACO算法的框架如圖1所示：

Fig. 1 Algorithm structure of DIACO圖1 DIACO算法結(jié)構(gòu)

在DIACO中，我們首先采用基于注意力機制的神經(jīng)網(wǎng)絡(luò)對問題實例進行特征提取，并產(chǎn)生ηij.然后采用蟻群算法對問題實例進行求解.

4 基于注意力機制的神經(jīng)網(wǎng)絡(luò)特征提取方法

本文所采用的基于注意力機制的神經(jīng)網(wǎng)絡(luò)模型是一種基于策略(policy-based)的深度強化學(xué)習(xí)方法.該方法不依賴標簽信息(ground truth)，而能夠通過學(xué)習(xí)過程中獎勵值的反饋進行自完善.以下首先介紹該模型的具體結(jié)構(gòu).

4.1 模型結(jié)構(gòu)

本文提出的基于注意力機制的神經(jīng)網(wǎng)絡(luò)模型(neural networks, NN)由2部分組成:1)編碼器-解碼器結(jié)構(gòu).該結(jié)構(gòu)主要負責建立問題輸入和特征輸出之間的關(guān)聯(lián).在旅行商問題中，問題輸入為全部城市的坐標集合以及當前已構(gòu)建的部分解的信息.2)注意力模型.該結(jié)構(gòu)綜合考慮編碼器-解碼器中問題輸入與輸出參數(shù)之間的相關(guān)性，并給予待訪問城市不同程度的關(guān)注度.

該模型的具體結(jié)構(gòu)有4個：

1) 編碼器.編碼器采用一維卷積嵌入層結(jié)構(gòu)，將問題輸入轉(zhuǎn)化為高維度向量，以充分利用圖Ts中的城市的結(jié)構(gòu)信息.該部分的輸入為各個城市的歐氏坐標.

2) 全局變量G.在編碼器中，每一個任務(wù)對應(yīng)輸出的特征向量是相互獨立的，因此這些變量并不能反映出城市之間邊的集合E的特征.因此，需要針對邊的集合E進行表征.本文采用文獻[23]中的多頭注意力(multi-head attention, MHA)神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)來進行相關(guān)特征的提取，該變量可以被認為是該場景的一個全局變量，它包含了針對邊的集合E的相關(guān)信息.

4) 注意力模型.注意力模型用于預(yù)測下一步可選擇城市中，選擇哪個城市獲得最優(yōu)解的可能性更大.采用注意力模型能夠給予下一步更可能產(chǎn)生最優(yōu)解的城市更高的被選擇概率.

Fig. 2 Attention based neural network structure圖2 基于注意力機制的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

在以上變換的基礎(chǔ)上，本文采用文獻[22]中的glimpse結(jié)構(gòu)，得到狀態(tài)變量Z.具體操作如式(7)所示：

Z=glimpse(G;[hs0,hst]),

(7)

其中，s0為初始訪問城市，st為當前訪問城市，G為全局變量，[hs0,hst]表示對2個向量進行拼接操作.

綜上，NN模型的解碼由全局變量G、狀態(tài)變量Z和距離變量D組成.將其輸入全連接層進行特征計算，得到各個待訪問城市的相關(guān)度，最終通過softmax函數(shù)對相關(guān)度進行歸一化，得到針對下一步可選城市的具體評分.具體的計算為

(8)

(9)

其中，Ct和Xt分別表示在第t步已經(jīng)訪問和待訪問的城市集合,vT和w表示待學(xué)習(xí)的神經(jīng)網(wǎng)絡(luò)參數(shù)，P(ct+1|Ct,Xt)為在時刻t已選城市ct∈Ct，待訪問城市Xt的情況下向訪問城市ct+1轉(zhuǎn)移的條件概率.該概率越大，代表神經(jīng)網(wǎng)絡(luò)認為下一步選擇ct+1中的城市可能獲得最優(yōu)解的概率越大.

該模型的具體運行流程如圖3所示.首先通過隨機初始化選擇s3作為初始起點，之后基于當前城市s3采用神經(jīng)網(wǎng)絡(luò)模型計算下一步可選擇的解的特征向量，得到當前狀態(tài)下待選擇城市的匹配度，此時的匹配度s4>s2>s1，因此選擇任務(wù)s4作為下一訪問城市，更新模型各個變量并使用掩碼機制對已訪城市進行屏蔽，重復(fù)上述過程直到模型停止.

Fig. 3 DIACO workflow圖3 DIACO算法工作流程

4.2 訓(xùn)練方法

為說明NN模型的訓(xùn)練方法，首先需要闡明NN模型的求解過程.

本文所采用的NN模型將旅行商問題的求解看做一個Markov過程.具體而言，在求解旅行商問題時，NN模型首先隨機選擇一個城市c0∈X0作為初始起點，然后以構(gòu)建式規(guī)則逐步將待訪問城市加入當前解.在每步迭代時，NN模型在C0={c0,c1,c2,…,ct}的狀態(tài)下，通過參數(shù)為θ的網(wǎng)絡(luò)模型選擇下一個被訪問城市ct+1.采用概率的鏈式法則，最終生成長度為T′的訪問順序規(guī)劃C={ct,t=0,1,…,T′}，其中T′為旅行商問題實例的規(guī)模.該過程可通過式(10)表示：

(10)

其中，P(C|X0;θ)為在NN的參數(shù)組合θ下生成訪問序列C的可能性，P(ct+1|Ct,Xt;θ)為在當前狀態(tài)Ct下基于參數(shù)組合θ選擇ct+1作為下一步訪問城市的概率.因此，存在最優(yōu)路徑集合C*，那么模型的最優(yōu)參數(shù)組合θ*應(yīng)滿足：

(11)

本文用J(θ)表示在參數(shù)組合θ下NN模型批量求解旅行商問題的期望，J(θ)可通過式(12)計算：

(12)

其中，r(C)表示當前路徑的目標值.考慮到在式(2)中，旅行商問題的優(yōu)化目標為最小化總旅行距離，因此NN模型的訓(xùn)練目標可通過式(13)表示：

(13)

其中，π*表示最優(yōu)策略，該策略包括模型參數(shù)及決策策略，π表示NN模型的策略集合.式(13)表示NN模型的訓(xùn)練目標為尋找能夠在訓(xùn)練集上取得最小期望路徑長度的策略.

為達成該訓(xùn)練目標，本文采用基于策略梯度的強化學(xué)習(xí)Actor-Critic方法，其偽代碼如算法1所示.其中，Actor網(wǎng)絡(luò)為本文提出的NN模型，Critic網(wǎng)絡(luò)使用與NN模型相同的特征提取層，而只輸入城市的坐標信息，然后2個全連接層將編碼器輸出的特征信息映射到對應(yīng)的網(wǎng)絡(luò)輸出.

算法1.Actor-Critic算法.

① 初始化Actor的網(wǎng)絡(luò)參數(shù)θ;

② 初始化Critic的網(wǎng)絡(luò)參數(shù)θc;

③ for 每一代 do

④ 重置梯度:dθ←0,dθc←0;

⑤N個調(diào)度場景;

⑥ fork=1,2,…,Ndo

⑦ 計步器t←0;

⑧ while 沒有達到終止條件 do

4.3 啟發(fā)式矩陣處理

對于訓(xùn)練好的NN模型，本文針對場景中的每個城市，逐一設(shè)置為初始起點，并運行一次NN模型，得到剩余城市的特征向量，最終將全部城市的特征向量進行拼接得到啟發(fā)式矩陣M0，NN模型的簡要運行流程如圖4所示:

Fig. 4 Characteristic extraction using NN model圖4 采用NN模型進行特征提取

需要額外指出的是，由于NN模型的訓(xùn)練采用構(gòu)建式規(guī)則(本文中為隨機貪婪規(guī)則)，為了保證求解效能的穩(wěn)定性，其訓(xùn)練時在不同待選城市間的評分差距較大.圖5展示了在29城市規(guī)模的算例上的NN模型輸出的可視化圖像.

Fig. 5 The visualization of the M0 on 29 cities instance圖5 29城市規(guī)模算例M0的可視化

考慮到單個城市的特征值與其他城市特征值的差值過大可能導(dǎo)致蟻群算法過早陷入局部最優(yōu)，從而影響蟻群算法搜索效能的問題，需要對NN模型輸出的M0矩陣進行預(yù)處理.預(yù)處理方法為

(14)

Fig. 6 The visualization of the M0(after pre-processing)圖6 M0的可視化(預(yù)處理后)

另外需要指出，本文求解的旅行商問題均為對稱旅行商問題，即從城市si旅行到城市sj與從城市sj旅行到城市si應(yīng)具有相同評價，因此本文采用以下方法對M0進行處理并得到最終的特征矩陣M：

Fig. 7 The visualization of the M圖7 M的可視化

(15)

5 實驗與結(jié)果

5.1 實驗設(shè)計

1) 實驗參數(shù)

NN模型采用(Actor-Cirtic, AC)算法對模型進行訓(xùn)練，為了保證模型在訓(xùn)練過程中的尋優(yōu)能力以及在測試過程中的穩(wěn)定性，本文分別采取隨機策略和貪婪策略對待訪問城市進行選擇.AC算法中的Actor即NN模型，參數(shù)設(shè)置如下：MHA:Q,K,V-dim=128,Head=8,Layer=3,Inner=512；編碼器:Conv-1D(Dinput_size=2,Filter=128,kernel_size=1,stride=1)；解碼器:Conv-1D(Dinput_size=1,Filter=128,kernel_size=1,stride=1).Critic共包含4層編碼器，具體參數(shù)設(shè)置如下：

編碼器1：Conv-1D(Dinput_size=2,Filter=128,kernel_size=1,stride=1)；

編碼器2：Conv-1D(256,Filter=20,kernel_size=1,stride=1)；

編碼器3：Conv-1D(20,Filter=20,kernel_size=1,stride=1)；

編碼器4：Conv-1D(20,Filter=1,kernel_size=1,stride=1).

本文使用Xavier對網(wǎng)絡(luò)參數(shù)進行初始化[26]，并采用Adam優(yōu)化器[27]對網(wǎng)絡(luò)參數(shù)進行更新，初始學(xué)習(xí)率η=0.0001，訓(xùn)練的問題規(guī)模為20，訓(xùn)練的輪數(shù)epoch=100，批訓(xùn)練量為512.

本研究使用的全部蟻群算法中，最大迭代次數(shù)為1 000，最大螞蟻數(shù)量為25，ρ=0.9，α=1，β=1.

2) 數(shù)據(jù)集

本文訓(xùn)練數(shù)據(jù)[xi,yi]均采用在均勻隨機分布Φ下生成，取值范圍(0,1)，最終分別得到128萬個訓(xùn)練場景，1萬個評價場景.

3) 實驗設(shè)備

模型的訓(xùn)練和測試均運行在一臺配置RTX 2080-Ti, i9- 9900k CPU, 64 GB內(nèi)存的服務(wù)器上.編譯語言采用Python，編譯器采用PyCharm，深度學(xué)習(xí)框架采用Pytorch 1.02.

4) 對比算法

5.2 對比分析

本文選取了任務(wù)規(guī)模為29,30,48,51,70,76和101的TSPLIB標準測試算例進行測試，每個算法運行20次，算法評價指標選用了求解的平均路徑長度(Avg)、解的變異系數(shù)(C.V.)和與最優(yōu)解的差距百分比(Gap)三個指標對全部對比算法的求解效能進行了分析.其中，變異系數(shù)的計算方式為CV=Std/Avg，其中，Std為標準差，Avg為均值.顯然，變異系數(shù)越小代表數(shù)據(jù)離散程度越低.采用變異系數(shù)能夠更好地比較多組不同測量尺度的數(shù)據(jù)間的離散程度的差異.另外需要指出的是，在表1和表2中，理論最優(yōu)解(OPT)及對比算法找到的最優(yōu)解用加粗字體標出.bays29的理論最優(yōu)解用下劃線標出，其原因是該理論最優(yōu)解目前存在一定的爭議(其主要原因是不同方法得出的理論最優(yōu)解在保留不同小數(shù)位數(shù)時有所不同).

Table 1 Results of DIACO on benchmark Instances

續(xù)表1

Table 2 Results of Different Model Scale DIACO on Benchmark Instances

表1總結(jié)了本文使用的全部算法和理論最優(yōu)解的對比結(jié)果.通過表1可知，DIACO在測試的全部算法中，找到了6個算例的最優(yōu)值.因此可以認為，相比于其他對比方法，DIACO在較小規(guī)模的TSP問題求解上具有一定優(yōu)勢.且相比于其他類型的啟發(fā)式算法，DIACO具有更好的解的穩(wěn)定性.另外，在算例bays29中，DIACO取得了比現(xiàn)有的最優(yōu)解更好的求解結(jié)果，其可能原因是在求解過程中距離矩陣的保留位數(shù)不同導(dǎo)致的誤差.圖8總結(jié)了不同算法在7組對比算例上的Gap值.

Fig. 8 The Gap of different algorithms圖8 不同算法平均路徑長度的Gap圖

需要額外指出的是，由于Vinyals等人[17]在較大規(guī)模算例上的Gap值太大(超過30%)，因此在此處不再予以列出.

另外，DIACO相比原始的ACO和僅采用NN模型求解的結(jié)果而言，算法的求解表現(xiàn)均有提升.其中，相比于原始ACO算法，DIACO的最小平均表現(xiàn)提升約為1.2%.而相對于NN模型，DIACO的最小平均表現(xiàn)提升約為1.9%.若考慮全部7組算例的均值，則DIACO相比于原始ACO的解的表現(xiàn)平均提升約3.47%，DIACO相比于NN模型的解的表現(xiàn)平均提升約4.27%.

另外需要指出，DIACO是一個具有良好的求解穩(wěn)定性的算法.在7組計算實驗中DIACO的最大變異系數(shù)約為0.0145.且相比于原始ACO和僅采用NN模型求解的結(jié)果，DIACO的變異系數(shù)有較大幅度的下降，可以認為DIACO提升了NN模型和ACO算法的計算穩(wěn)定性.

最后需要說明的是，由于機器學(xué)習(xí)方法一般采用簡單的搜索機制,如貪婪法或者束搜索(beam search, BS)等，因此DIACO相比于一般的機器學(xué)習(xí)方法具有更大的時間開銷.

5.3 模型有效性驗證

1) 模型訓(xùn)練過程分析

本節(jié)首先給出了NN模型的訓(xùn)練過程分析如圖9所示.該圖展示了NN模型在平均算例規(guī)模為20城市的訓(xùn)練樣本上的訓(xùn)練曲線.從圖9可以看出，NN模型在訓(xùn)練的前20代平均路徑長度快速下降，并在約第60代達到基本穩(wěn)定狀態(tài).從圖9可以總結(jié)得出，本文所采用的NN模型能夠以較快速度達到收斂狀態(tài).

Fig. 9 The training process of NN model at 20 scale instances圖9 NN模型在任務(wù)規(guī)模20下的訓(xùn)練過程

2) 模型泛化能力驗證

為了驗證不同規(guī)模NN模型下DIACO算法的性能，本文以20-NN模型為基礎(chǔ)，采用參數(shù)遷移的方式對50和75規(guī)模的NN模型進行訓(xùn)練，縮短了模型的訓(xùn)練周期，具體訓(xùn)練128萬場景，訓(xùn)練輪次20.模型泛化能力驗證的計算結(jié)果如圖10所示：

Fig. 10 The Gap of different scale DIACO on 7 instances圖10 不同模型規(guī)模DIACO在benchmark算例上的實驗結(jié)果

由圖10可得，在7組測試算例中，50節(jié)點規(guī)模的DIACO算法獲得最好的平均計算表現(xiàn).且不同規(guī)模的DIACO在全部測試場景下的平均Gap均在10%以內(nèi)，可以認為該方法具有較好的規(guī)模泛化性能.

5.4 算法有效性驗證

為研究NN模型輸出的啟發(fā)式矩陣的有效性，本文設(shè)計一種新的ACO形式.在該ACO中，啟發(fā)式信息通過式(16)確定：

(16)

在式(16)中，mij為特征矩陣M中的邊ij的特征值，ε和δ為控制特征值和基于距離的啟發(fā)式信息的重要性的參數(shù)，且ε和δ滿足ε+δ=1.通過調(diào)整公式中ε和δ的值，即可控制啟發(fā)式信息中特征值和基于距離的啟發(fā)式信息的比例.當ε=1時，該ACO即為DIACO，當δ=1時，該ACO即為經(jīng)典ACO.我們選取了ε={0,0.1,0.3,0.5,0.7,0.9,1.0}共7種不同的組合進行了驗證，其結(jié)果如圖11所示:

Fig. 11 Algorithm proficiency of NN model圖11 NN模型有效性驗證

從圖11可知，當ε=1時，即該ACO為DIACO時，該算法能夠得到最好的平均表現(xiàn).因此能夠證明使用NN模型替換基于距離的啟發(fā)式矩陣能夠有效提高ACO的求解性能.

6 總 結(jié)

有效利用組合優(yōu)化問題算例提供的啟發(fā)式信息輔助求解組合優(yōu)化問題，是改善算法求解組合優(yōu)化問題效能的重要手段.本文提出了一種基于深度學(xué)習(xí)和蟻群算法的組合優(yōu)化問題混合求解策略.該方法首先采用深度學(xué)習(xí)方法對組合優(yōu)化問題進行特征提取，在此基礎(chǔ)上采用蟻群算法進行搜索求解.為驗證該方法的有效性，本文采用旅行商問題標準算例對該求解方法的效能進行了驗證.結(jié)果表明該方法在旅行商問題上具有良好表現(xiàn).

本研究可從以下3方面開展后續(xù)工作：

1) 深度學(xué)習(xí)方法對問題的分布具有較強敏感性，問題分布的改變可能導(dǎo)致深度學(xué)習(xí)方法得到的問題特征矩陣出現(xiàn)較大誤差.如何解決問題分布帶來的學(xué)習(xí)誤差的問題，是本文后續(xù)的重要研究方向之一.

2) 如何有效地提取算例的深層信息，是本文需要解決的另一個問題.由于深度學(xué)習(xí)方法訓(xùn)練時采用基于平均隨機貪婪原則的方式構(gòu)建解，因此難以避免訓(xùn)練過程的短視問題.因此，如何提高深度學(xué)習(xí)方法提取特征的深度，是本研究另一個重要的后續(xù)工作方向.

3) 在更大規(guī)模的問題上開展針對性研究.在本文中，我們發(fā)現(xiàn)當問題規(guī)模超過100節(jié)點時，DIACO算法的表現(xiàn)具有一定程度的下降.其可能原因包括：①網(wǎng)絡(luò)規(guī)模不夠?qū)е滦畔⑻崛〔煌晟?；②搜索時間不夠?qū)е聼o法搜索到更好的解.因此，在未來針對DIACO算法的研究中，將著重研究該方法在大規(guī)模算例下的表現(xiàn)，以及針對網(wǎng)絡(luò)在不同規(guī)模算例上的泛化性進行研究.

作者貢獻聲明：王原主要負責論文的思路設(shè)計、算法代碼編寫、實驗思路設(shè)計、實驗數(shù)據(jù)分析和論文撰寫；陳名主要貢獻包括深度學(xué)習(xí)方法設(shè)計、算法代碼編寫、深度學(xué)習(xí)方法訓(xùn)練、實驗數(shù)據(jù)收集及論文撰寫，為本文通信作者；邢立寧主要貢獻包括論文思路指導(dǎo)、實驗數(shù)據(jù)分析指導(dǎo)、論文撰寫及修改；吳亞輝主要貢獻包括優(yōu)化方法設(shè)計、實驗數(shù)據(jù)收集及分析；馬武彬主要貢獻包括算法代碼編寫、實驗數(shù)據(jù)采集及分析；趙宏主要貢獻包括：對比算法設(shè)計、代碼編寫、實驗數(shù)據(jù)采集.王原和陳名為共同一作.