熊文瑞，陶繼平

1.廈門大學(xué) 航空航天學(xué)院，福建 廈門 361005

2.廈門大學(xué) 大數(shù)據(jù)智能分析與決策重點(diǎn)實(shí)驗(yàn)室，福建 廈門 361005

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

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

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

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

本文以TSP 問題為例，在端到端的學(xué)習(xí)模型框架下引入對(duì)抗的思想，提出生成器加判別器的對(duì)抗訓(xùn)練框架[2]來增強(qiáng)學(xué)習(xí)模型對(duì)于問題的泛化性。本文的貢獻(xiàn)如下：

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

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

1 相關(guān)工作

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

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

2 對(duì)抗訓(xùn)練模型

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

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

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

圖1 對(duì)抗訓(xùn)練模型Fig.1 Adversarial training model

2.1 判別器模型

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

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

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

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

2.2 生成器模型

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

將坐標(biāo)分別在兩個(gè)維度進(jìn)行歸一化以匹配判別器的原始輸入。

2.3 訓(xùn)練方法

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

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

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

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

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

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

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)置

3.1.1 數(shù)據(jù)集及評(píng)價(jià)指標(biāo)

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

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

3.1.2 實(shí)驗(yàn)環(huán)境

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

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

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

3.3 對(duì)抗樣本驗(yàn)證

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

圖3 生成器訓(xùn)練過程圖Fig.3 Training process of generator

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

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

3.4 對(duì)抗訓(xùn)練實(shí)驗(yàn)

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

圖4 20維TSP對(duì)抗訓(xùn)練過程圖Fig.4 Adversarial training process of TSP（N=20）

圖5 50維TSP對(duì)抗訓(xùn)練過程圖Fig.5 Adversarial training process of TSP（N=50）

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

表2 對(duì)抗訓(xùn)練結(jié)果Table 2 Result of adversarial training

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

4 結(jié)語

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

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