熊文瑞，陶繼平

1.廈門大學 航空航天學院，福建 廈門 361005

2.廈門大學 大數(shù)據(jù)智能分析與決策重點實驗室，福建 廈門 361005

在一般意義下，優(yōu)化指的是按照某些確定的約束條件進行策略的選擇，在滿足約束條件的情況下，尋求在某個優(yōu)化準則下的極值。組合優(yōu)化問題是一類在離散狀態(tài)下求極值的優(yōu)化問題。在日常生活中，特別是運作管理中，有許多組合優(yōu)化問題。典型的組合優(yōu)化問題有背包問題、指派問題、旅行商問題等。這些類問題與實際生產(chǎn)聯(lián)系緊密，具有重要的研究意義。傳統(tǒng)求解該類問題的方法可以分為精確算法和近似算法兩大類。

常用的精確算法有動態(tài)規(guī)劃、分支定界、枚舉等。精確算法只適用于求解小規(guī)模問題，一旦問題規(guī)模擴大，該種方法難以在較短時間得到最優(yōu)解，不適用于實際的生產(chǎn)。

近似算法是指在合理的計算時間找到盡可能接近最優(yōu)解的方法。近似算法可以分為三類：第一類是基于數(shù)學規(guī)劃的近似算法，該種方法以數(shù)學模型為基礎(chǔ)，采用列生成、拉格朗日松弛等方法求解問題，該類方法的優(yōu)點是可以通過松弛問題的最優(yōu)解為原問題提供一個下界，通過算法運行給出的問題的近似解為原問題提供上界，上下界進行比較，可以衡量算法性能；第二類是常規(guī)啟發(fā)式算法，即根據(jù)問題的特點，按照經(jīng)驗或者某種規(guī)則設(shè)計的，該種方法的優(yōu)點是直觀快速，但解的質(zhì)量不一定好；第三類是基于智能優(yōu)化的近似算法，智能算法是一種通用的算法框架，需要根據(jù)問題的特點對算法框架進行修改就可以直接應(yīng)用于不同的問題。

基于數(shù)學規(guī)劃的近似算法不具有通用性且設(shè)計較為復雜。啟發(fā)式算法雖然簡單，但也存在遷移性不強的問題，一旦問題結(jié)構(gòu)發(fā)生變化，原始方法將不再具有優(yōu)勢，必須重新設(shè)計新的模型來進行求解。智能優(yōu)化算法雖然更具通用性，但是和啟發(fā)式算法都依賴于初始解的質(zhì)量。傳統(tǒng)方法對于每個實例的求解過程都是獨立進行，兩個算例的求解過程沒有任何聯(lián)系，算法沒有充分挖掘并利用在對不同算例求解過程中所積累的經(jīng)驗。深度學習的出現(xiàn)，彌補了傳統(tǒng)方法的不足，深度學習以數(shù)據(jù)為驅(qū)動力，挖掘潛在的數(shù)據(jù)特征[1]，可以自動地學習出有效的“啟發(fā)式方法”，而不需要獲取先驗知識來進行啟發(fā)式規(guī)則的設(shè)計。現(xiàn)有研究工作主要關(guān)注于對模型的改進，缺乏從實例的生成來解決訓練模型的泛化性。

本文以TSP 問題為例，在端到端的學習模型框架下引入對抗的思想，提出生成器加判別器的對抗訓練框架[2]來增強學習模型對于問題的泛化性。本文的貢獻如下：

（1）由隨機數(shù)據(jù)作為數(shù)據(jù)集訓練所得到的模型魯棒性較差，本文借鑒對抗攻擊與對抗防御思想，基于對抗生成模型的框架，設(shè)計神經(jīng)網(wǎng)絡(luò)模型，使用求解器生成標簽，并使用監(jiān)督學習的方式來得到對抗樣本。通過對預訓練模型的攻擊來驗證對抗樣本的效果，最終能夠產(chǎn)生高質(zhì)量的對抗樣本。將生成器與判別器結(jié)合形成生成對抗框架，通過對抗訓練最終得到在隨機樣本和對抗樣本上都表現(xiàn)良好的判別器模型，實驗成功驗證了該思路的可行性。

（2）傳統(tǒng)對抗訓練沒有評判判別器訓練好壞程度的指標，只通過生成器模型和判別器模型固定次數(shù)的交替迭代來進行對抗訓練，本文基于判別器的更新方式設(shè)計一種自檢測更新機制，設(shè)置超參數(shù)，通過判別器的連續(xù)更新狀態(tài)來判斷是否進入生成對抗樣本的模式，通過該訓練方式所得到的模型能夠有效地降低對抗樣本的代價，避免每一步迭代過程中對抗樣本訓練欠擬合的狀況。

1 相關(guān)工作

Sequence-to-sequence[3]模型是一類針對變長輸入問題的端到端的學習模型。該模型根據(jù)輸入的序列來得到不同的輸出序列，被廣泛用在機器翻譯、自動應(yīng)答等場景。由于上述模型的輸出字典大小固定，不適用于解決不同輸入長度對應(yīng)的不同輸出長度的問題，Vinyals等人提出新的模型架構(gòu)PointerNetwork[4]解決了該問題，該模型基于sequence-to-sequence 模型，使用LSTM[5]模型作為RNN[6]的基本單元，并在此基礎(chǔ)上改變attention機制[7]使其更適應(yīng)于解決組合優(yōu)化問題。該網(wǎng)絡(luò)的提出首次將深度學習引入到組合優(yōu)化問題的求解，開辟了一條有別于傳統(tǒng)算法的研究思路。

使用監(jiān)督學習在訓練效率上較非監(jiān)督學習有一定的優(yōu)勢，但是，對于大規(guī)模組合優(yōu)化問題來說，獲取標簽的代價是昂貴的，而且所得到的模型質(zhì)量取決于標簽的質(zhì)量。另外，這種監(jiān)督學習模型的本質(zhì)是對獲取標簽算法的一種擬合，因此在求解質(zhì)量上有天然的上限。針對該局限性，Bello等人[8]提出使用強化學習的方法來訓練PointerNetwork，使用類似asynchronous advantage actor-critic（A3C）[9]的強化學習訓練框架，用采樣解的代價（旅行長度）來對策略梯度進行無偏蒙特卡羅估計。該論文將TSP問題求解規(guī)模從50擴大到了100個點，同時避免了獲取高質(zhì)量實例標簽的計算困難。Khalil等人[10]針對圖組合優(yōu)化問題的特點提出使用structure2vec[11]來進行圖的嵌入，使用deep Q-learning[12]來學習一個圖嵌入網(wǎng)絡(luò)的貪婪策略，并在三種圖組合優(yōu)化問題（MVC，MAXCUT，TSP）上進行驗證，取得了較啟發(fā)式算法有競爭力的解。Kool等人[13]提出使用基于transformer[14]作為網(wǎng)絡(luò)架構(gòu)?；诩軜?gòu)優(yōu)勢，使用自注意力機制實現(xiàn)了數(shù)據(jù)的并行輸入，改善了串行輸入帶來的效率低下的問題，同時使用一種類似自評價機制[15]的方法來提供強化學習的基線。該方法使TSP 問題在100 點的規(guī)模上得到了更近似于最優(yōu)解的解，同時通過更改網(wǎng)絡(luò)解碼過程中的掩碼機制和上下文來適配不同的問題，將該網(wǎng)絡(luò)結(jié)構(gòu)應(yīng)用在其他幾個組合優(yōu)化問題上，體現(xiàn)了該方法在解決一些沒有有效啟發(fā)式算法問題上的靈活性。

2 對抗訓練模型

本章基于TSP問題來定義對抗訓練模型，TSP問題是一個NP-hard 的組合優(yōu)化問題[16]。問題可以描述為，在二維平面上有一系列分散的坐標點，要求從某一個點出發(fā)，找到一條經(jīng)過各二維坐標點一次后回到出發(fā)點的最短路徑。定義一個問題實例S包含平面上的n個坐標點{(x1,y1),(x2,y2),…,(xn,yn)}，定義實例的解為π=(π1,π2,…,πn)，該解為坐標點的一個全排列。定義實例對應(yīng)的最優(yōu)路徑長度為。

對抗網(wǎng)絡(luò)主要由兩部分組成，分別為生成器網(wǎng)絡(luò)和判別器網(wǎng)絡(luò)，生成器和判別器的優(yōu)化目標各不相同。生成器用來生成對抗樣本，生成的實例是對于判別器求解質(zhì)量較差的實例。定義網(wǎng)絡(luò)對實例S輸出解為L(θ|S)，其中θ為網(wǎng)絡(luò)參數(shù)。在評估解的優(yōu)劣時，一般使用近似解和精確解的相對誤差，也就是gap 值作為評判標準，gap值定義如式（1）：

判別器將對抗樣本和隨機樣本混合進行訓練，兩個網(wǎng)絡(luò)交替訓練，判別器和生成器相互博弈，最終得到泛化性增強的判別器網(wǎng)絡(luò)，對抗訓練模型示意圖如圖1所示。

圖1 對抗訓練模型Fig.1 Adversarial training model

2.1 判別器模型

本文使用的判別器模型基于文獻[13]。模型可分為兩部分，編碼器和解碼器模型。編碼器使用自注意力機制進行特征提取。解碼器通過編碼器所提取的信息來構(gòu)造上下文信息，通過注意力機制用于每一步的解碼，最后通過指針機制產(chǎn)生每個點被選擇的概率分布，通過不同的采樣機制來獲得實例的一個解。

編碼器部分基于transformer模型，核心部分采用三層多頭自注意力機制，同時在每一層都加入殘差連接[17]以及批規(guī)范化[18]，最后一層為全連接層網(wǎng)絡(luò)。由于各個點的輸入不存在類似NLP輸入的順序問題，所以相比于傳統(tǒng)的transformer 模型，判別器網(wǎng)絡(luò)省略了位置編碼。編碼器將TSP問題中的每個點進行編碼，最終得到每個點關(guān)于整個實例圖的高維表示，同時將所有的點嵌入加和求平均得到關(guān)于整張圖的高維嵌入，所得到的高維表示稱為圖嵌入，編碼器網(wǎng)絡(luò)如圖2所示。

圖2 編碼器網(wǎng)絡(luò)圖Fig.2 Encoder model

解碼器采用逐步輸出的方式，每一步需要根據(jù)上下文信息和每個點的嵌入信息來進行解碼。解碼過程首先使用多頭自注意力機制來對上下文信息進行編碼，解碼過程中使用的上下文信息為解碼器網(wǎng)絡(luò)選擇的第一個點的點嵌入矩陣、圖嵌入矩陣，以及當前對應(yīng)的前一個點的嵌入矩陣的拼接。在第一步解碼過程中，由于第一個點還未被選擇，所以前一個被選擇的點也不存在，使用可學習的參數(shù)矩陣作為輸入的占位符。得到上下文嵌入矩陣后，進行一次自注意力計算來完成上下文和各點嵌入矩陣的信息交換，然后使用指針機制[4]以及掩碼機制生成每個點被選擇的概率，掩碼機制使得前面每一步被選中的點下次被選中的概率為0，所有點被選擇的概率和為1。直到所有的點被選到形成實例的一個解，完成解碼過程。解碼器根據(jù)采樣方式不同可以分為兩種，一種是貪婪解碼，也就是在解碼過程中，每一步只選擇概率最大的點。另一種方式是概率解碼，也就是依據(jù)每一步解碼過程中所產(chǎn)生的概率分布來進行點的選擇。

2.2 生成器模型

生成器使用的是多層感知機網(wǎng)絡(luò)，神經(jīng)網(wǎng)絡(luò)的前兩部分都包含一個全連接層、批規(guī)范化層、ReLU激活函數(shù)層，最后一部分為一個全連接層，生成2 維的坐標點信息。設(shè)置生成器的輸入為100維的隨機噪聲，第一層全連接網(wǎng)絡(luò)的節(jié)點數(shù)設(shè)置為256個，第二層全連接神經(jīng)網(wǎng)絡(luò)的節(jié)點設(shè)置為128 個，最后一層節(jié)點數(shù)設(shè)置為兩個。隨機生成的噪聲信息在經(jīng)過生成器后生成坐標集為{(x1,y1),…,(xi,yi),…,(xn,yn)} ，通過min-max 歸一化生成的新的點坐標集為，新坐標點分別為：

將坐標分別在兩個維度進行歸一化以匹配判別器的原始輸入。

2.3 訓練方法

對抗神經(jīng)網(wǎng)絡(luò)包含兩部分，一部分是判別器網(wǎng)絡(luò)，一部分是生成器網(wǎng)絡(luò)，需要分別進行訓練。對于判別器，使用的是基于策略的強化學習的方法來訓練。給定一個實例S，判別器網(wǎng)絡(luò)在每一步解碼中給出每個點被選擇的概率，依據(jù)概率采樣可以獲得一個有效解π|s，定義損失函數(shù)為L(θ|S)=EPθ(π|s)[L(π)]，L(π)為TSP 問題旅行長度的期望值。在訓練判別器時，訓練樣本為生成器所生成對抗樣本和隨機樣本的混合數(shù)據(jù)。固定生成器的參數(shù)，使用帶有基線的強化學習梯度估計器通過梯度下降的方法更新網(wǎng)絡(luò)參數(shù)，梯度估計如式（4）[19]：

對于基準值的選擇，使用一個評判網(wǎng)絡(luò)，結(jié)構(gòu)與主網(wǎng)絡(luò)相同，這種訓練方法類似于自評判機制。在訓練判別器前需要生成一份評估數(shù)據(jù)集，同時在評判網(wǎng)絡(luò)上通過貪婪解碼的方式生成評估數(shù)據(jù)集的解。重新生成訓練數(shù)據(jù)集，訓練數(shù)據(jù)集為隨機樣本和生成器所產(chǎn)生的對抗樣本，評判網(wǎng)絡(luò)對訓練數(shù)據(jù)使用貪婪解碼的方式為主網(wǎng)絡(luò)提供基準值。主網(wǎng)絡(luò)根據(jù)上述強化學習梯度估計更新網(wǎng)絡(luò)，評判網(wǎng)絡(luò)此時不需要進行更新。更新主網(wǎng)絡(luò)后，需要在主網(wǎng)絡(luò)上采用貪婪解碼的方式來得到評估數(shù)據(jù)集的解，根據(jù)評估數(shù)據(jù)集在主網(wǎng)絡(luò)和評判網(wǎng)絡(luò)的解通過配對T檢驗（α=5%）來判斷主網(wǎng)絡(luò)是否得到一定程度的改善，判定主網(wǎng)絡(luò)得到改善后，則將當前主網(wǎng)絡(luò)參數(shù)復制到評判網(wǎng)絡(luò)。每次參數(shù)復制后都會重新生成評估數(shù)據(jù)集以防止過擬合。

傳統(tǒng)的對抗學習一般在固定次數(shù)的判別器更新后切換到生成器網(wǎng)絡(luò)進行訓練，這種訓練方法不能對判別器的訓練現(xiàn)狀進行一個大概的評估，導致生成器和判別器難以訓練至收斂，訓練過程損失函數(shù)曲線震蕩嚴重?；谧栽u價基線的特殊性，當同一份驗證數(shù)據(jù)在判別器主網(wǎng)絡(luò)上的訓練難以繼續(xù)優(yōu)化，判別器參數(shù)將無法更新到自評價網(wǎng)絡(luò)，可判定判別器網(wǎng)絡(luò)對于對抗樣本有了一定的學習能力，基于是否達到此狀態(tài)來判斷是否應(yīng)該切換至生成器網(wǎng)絡(luò)來進行更新。

網(wǎng)絡(luò)首先從判別器開始訓練，根據(jù)以上介紹的強化學習方法進行訓練。設(shè)置超參數(shù)為n，當判別器主網(wǎng)絡(luò)連續(xù)n步?jīng)]有更新參數(shù)到基準網(wǎng)絡(luò)時，跳轉(zhuǎn)到生成器網(wǎng)絡(luò)的訓練階段，開始一個回合的生成器訓練，訓練結(jié)束后繼續(xù)跳轉(zhuǎn)到判別器訓練。

在訓練生成器時，需要固定判別器的參數(shù)。高維噪聲信號輸入生成器后輸出未經(jīng)處理的坐標信息，將生成器生成的數(shù)據(jù)標準化后，使用Gurobi求解器求取對抗樣本實例的解作為訓練生成器的標簽，將得到的對抗樣本混合到隨機樣本中送入判別器網(wǎng)絡(luò)，判別器網(wǎng)絡(luò)此時使用的解碼方式為貪婪解碼，得到的每個實例i的解為Li(π)，每個實例對應(yīng)的求解標簽為y^i，使用監(jiān)督學習的方法來訓練神經(jīng)網(wǎng)絡(luò)。定義損失函數(shù)L(θ|S)，使用梯度下降的方法來優(yōu)化損失函數(shù)。經(jīng)過判別器初始預熱訓練后，求解實例的gap值遠小于1，可以將1作為目標值，因此損失函數(shù)可以定義為式（5）：

在訓練生成器時，判別器的解碼模式為貪婪解碼。當對抗樣本gap 值上升趨于平緩且判別器網(wǎng)絡(luò)對解的質(zhì)量提升也趨于平緩時，結(jié)束對抗訓練。

3 實驗

3.1 實驗設(shè)置

3.1.1 數(shù)據(jù)集及評價指標

本文使用的數(shù)據(jù)用例包含隨機生成的用例和隨機噪聲通過生成器所生成的對抗用例，隨機生成用例是分布在正方形區(qū)域[0，1]2區(qū)間的均勻分布用例，而通過生成器所生成的對抗用例通過數(shù)據(jù)標準化來歸一化到[0，1]2區(qū)間。

本文將實驗分為兩個對照組，一組是通過隨機樣本充分訓練的預訓練模型，一組是初始化后，通過對抗訓練機制訓練的對抗訓練模型。本文將從對抗樣本和隨機樣本分別在對抗模型和預訓練模型的表現(xiàn)來驗證訓練效果。為了驗證生成器可以有效生成對抗樣本，需要通過對抗訓練生成對于預訓練模型gap 值較大的對抗樣本。驗證生成器有效后，再通過對抗訓練機制來訓練初始化的模型，使用預訓練模型上所得到的對抗樣本、隨機樣本以及對抗訓練中產(chǎn)生對抗樣本的gap 值來檢驗對抗訓練模型。

3.1.2 實驗環(huán)境

硬件環(huán)境為NVIDIA GeForce GTX1080 顯卡，16 GB 運行內(nèi)存，英特爾i7-7700 處理器。軟件環(huán)境為Windows10系統(tǒng)，Tensorflow2.0，Pytorch0.4.1開發(fā)環(huán)境。

3.2 實驗參數(shù)設(shè)置

由于求解器求解速度限制，本文對于20規(guī)模的TSP問題，每回合處理5 000個實例，每一批次包含500個實例。對于50 規(guī)模的TSP 問題，每回合處理3 000 個實例，每一批次包含300 個實例，判別器網(wǎng)絡(luò)的學習速率設(shè)置為η1=10-4，生成器的學習速率設(shè)置為η1=10-3，同時生成器學習速率衰減值設(shè)置為0.96。

3.3 對抗樣本驗證

為了驗證生成器網(wǎng)絡(luò)能夠生成有效對抗樣本，分別在20 規(guī)模和50 規(guī)模的TSP 問題上進行驗證，判別器使用的是基于文獻[13]中的預訓練模型。固定判別器參數(shù)，生成器網(wǎng)絡(luò)使用監(jiān)督學習的方式來獲取gap值更大的對抗樣本，訓練每一回合的批次大小和每一批次包含實例數(shù)量與上面設(shè)置相同，生成器采用Adam優(yōu)化器來進行優(yōu)化。訓練完畢后，對生成器進行驗證，驗證規(guī)模為500個對抗例，訓練過程如圖3。

圖3 生成器訓練過程圖Fig.3 Training process of generator

可以觀察到，通過監(jiān)督學習的方式不斷更新生成器網(wǎng)絡(luò)，最終得到了對于原預訓練判別器結(jié)果較差的解的實例，實驗證明生成器網(wǎng)絡(luò)能夠生成有效的對抗樣本，訓練最終結(jié)果如表1所示。

表1 生成器驗證結(jié)果Table 1 Result of generator training

3.4 對抗訓練實驗

對抗訓練階段，不使用預訓練模型，初始化判別器和生成器的參數(shù)，首先進行判別器的訓練，采用的是上述基于策略梯度的強化學習的方法。設(shè)置判別器和生成器的跳轉(zhuǎn)機制：設(shè)置TSP問題規(guī)模為20時，當判別器連續(xù)30個epoch沒有將主網(wǎng)絡(luò)參數(shù)更新到基準網(wǎng)絡(luò)時，將自動切換到生成器網(wǎng)絡(luò)進行訓練；當規(guī)模為50時，則設(shè)置為40個epoch。生成器網(wǎng)絡(luò)的回合數(shù)獨立計數(shù)，生成器的學習速率的衰減依據(jù)生成器的訓練回合數(shù)，不與判別器使用相同的回合計數(shù)。每次生成器更新完成后將生成新的混合評估數(shù)據(jù)，同時在判別器評判網(wǎng)絡(luò)上進行貪婪解碼，為后續(xù)主網(wǎng)絡(luò)更新到評判網(wǎng)絡(luò)提供評判標準，訓練過程如圖4、圖5所示。

圖4 20維TSP對抗訓練過程圖Fig.4 Adversarial training process of TSP（N=20）

圖5 50維TSP對抗訓練過程圖Fig.5 Adversarial training process of TSP（N=50）

對抗訓練后，分別對隨機樣本、生成器所產(chǎn)生的對抗樣本進行測試。可以觀察到，隨機樣本和對抗樣本最終能在對抗訓練模型上取得較好的結(jié)果。同時通過預訓練模型生成的對抗樣本同樣在對抗模型上有較好的結(jié)果，證明通過對抗訓練，判別器在一定范圍上泛化能力增強。對抗訓練后的訓練結(jié)果如表2所示，對抗訓練模型與預訓練模對對抗樣本及隨機樣本的改善程度如表3所示?？梢杂^察到在20規(guī)模和50規(guī)模上對抗模型對對抗樣本有一定改善程度，尤其在20 規(guī)模上改善效果較為明顯，同時對隨機樣本的結(jié)果有一定削弱，改善效果要好于削弱效果，模型在原來的基礎(chǔ)上得到平衡。

表2 對抗訓練結(jié)果Table 2 Result of adversarial training

表3 預訓練模型對抗樣本在對抗模型上的表現(xiàn)Table 3 Performce of adversarial model in adversarial samples of pre-trained model

4 結(jié)語

本文提出針對組合優(yōu)化問題的對抗學習框架，通過加入生成器模型，樣本生成的豐富度得到提升，進一步增強了網(wǎng)絡(luò)的泛化性能。在原預訓練模型上表現(xiàn)較差的對抗樣本，通過對抗訓練后，解的質(zhì)量得到較大的提升。同時針對原判別器模型訓練方式引入一種自適應(yīng)切換判別器和生成器訓練的方式，使對抗樣本能夠得到充分的擬合，同時對抗訓練后的模型對于原分布的gap值影響較小，最終整體上提升了原訓練網(wǎng)絡(luò)的泛化性能。

在未來工作中，將問題擴大到更大規(guī)模具有重要的實際意義。由于生成對抗樣本過程中求解標簽對問題規(guī)模的限制，通過不使用標簽的方法來得到對抗樣本也會是接下來的重點研究方向。