張宏立，朱家政，董穎超

(新疆大學(xué) 電氣工程學(xué)院，新疆 烏魯木齊 830017)

0 引言

優(yōu)化問題是指在不同的可能性中尋找出最佳方案，根據(jù)求解問題的不同，對應(yīng)的求解問題可分為三大類：連續(xù)、離散、混合整數(shù)規(guī)劃問題.例如，尋找一個凸優(yōu)化問題的解是一個連續(xù)優(yōu)化問題，而從一個圖的所有路徑中找到最短路徑則是一個離散優(yōu)化問題，將此類離散空間的優(yōu)化問題稱為組合優(yōu)化問題，其數(shù)學(xué)模型如下所示：

式中：f(x) 為目標(biāo)函數(shù)，g(x) 為問題的約束條件，D 表示有限的離散決策空間.其中的一個常見問題是旅行商問題，該問題目標(biāo)是尋找到一條能夠訪問所有城市并返回初始城市的最短路線，其本質(zhì)是在一個全連接的加權(quán)圖中找到一個長度最小的哈密頓回路.哈密頓回路中所有的節(jié)點組成了D，回路中每條邊權(quán)值的累加構(gòu)成了f(x).

大多數(shù)組合優(yōu)化問題都是NP 難問題，通常無法在多項式時間內(nèi)找到解決方案.因此，許多近似方法或啟發(fā)式算法被設(shè)計用以解決此類問題，但此類方法往往計算耗時、計算成本過高.而近些年隨著人工智能技術(shù)的不斷發(fā)展，一個新興趨勢是使用訓(xùn)練機器學(xué)習(xí)算法解決此類問題.強化學(xué)習(xí)算法作為機器學(xué)習(xí)算法的一個特殊分支已經(jīng)在旅行商問題中得到應(yīng)用，對于一個組合優(yōu)化問題，它通過定義環(huán)境、訓(xùn)練環(huán)境中的智能體的方式，最終產(chǎn)生一個解決方案.將強化學(xué)習(xí)應(yīng)用到組合優(yōu)化問題中，首先將問題建模為序列決策過程，其中智能體通過執(zhí)行一系列的動作同環(huán)境進行交互，最終找到一個可行的解決方案.馬爾可夫決策過程為此類問題的建模提供了一個廣泛使用的數(shù)學(xué)框架[1].該過程可以被描述為一個五元組：

式中：S 為狀態(tài)空間，以旅行商問題為例，可以通過兩種方式進行狀態(tài)空間的設(shè)計，一種方法是漸進式地構(gòu)建解決方案，將問題中已去過的城市作為狀態(tài)空間，逐步地得到完整的解決方案；另一種方法是從問題的次優(yōu)解出發(fā)，在該解的基礎(chǔ)上不斷進行改進.A 為動作空間，不同時刻的動作會對當(dāng)前的狀態(tài)產(chǎn)生改變.R 為獎勵函數(shù)，是對當(dāng)前狀態(tài)下所產(chǎn)生動作的一種評價，反映了當(dāng)前選擇的動作是否改善了需要解決的問題.T 是轉(zhuǎn)移函數(shù)，其制約著不同時刻狀態(tài)的轉(zhuǎn)移.γ 為折扣因子，0 ＜γ ＜1，折扣因子的大小展示了智能體對未來獎勵的期望程度.

在馬爾可夫決策過程中智能體的目標(biāo)是找到一個策略函數(shù)，使得預(yù)期的累計獎勵最大化：

如果一個組合優(yōu)化問題能夠定義為馬爾可夫決策過程，就需要訓(xùn)練智能體如何尋找到最優(yōu)策略，一般而言，有兩種類型的強化學(xué)習(xí)算法：

第一種為基于價值的方法，智能體不需要制定顯式的策略，它維護一個價值表格或價值函數(shù)，并通過這個價值表格或價值函數(shù)來選取價值最大的動作.

第二種為基于策略的方法，智能體會制定一套動作策略（確定在給定狀態(tài)下需要采取何種動作），并根據(jù)這個策略進行操作.強化學(xué)習(xí)算法直接對策略進行優(yōu)化，使制定的策略能夠獲得最大的獎勵.

可以看出，強化學(xué)習(xí)算法的關(guān)鍵在于將馬爾可夫決策過程的狀態(tài)轉(zhuǎn)化為輸入并輸出行動值或者行動的策略.狀態(tài)包含了關(guān)于問題的一些特征信息，如旅行商問題中給定的圖或者當(dāng)前的行程.而動作值或者策略則為數(shù)字.因此強化學(xué)習(xí)算法中應(yīng)該包含編碼器，能夠?qū)顟B(tài)轉(zhuǎn)化為數(shù)字形式.針對不同的組合優(yōu)化問題，已經(jīng)有許多的編碼器被提出，包括遞歸神經(jīng)網(wǎng)絡(luò)[2]、圖神經(jīng)網(wǎng)絡(luò)[3]、基于注意力的網(wǎng)絡(luò)[4]和多層感知器[5].

本文的組織結(jié)構(gòu)如下：第1 節(jié)對常見的組合優(yōu)化問題、編碼器和強化學(xué)習(xí)算法進行了研究背景概述.第2節(jié)對當(dāng)前主流的將強化學(xué)習(xí)應(yīng)用于各種組合優(yōu)化問題的研究進行了綜述.第3 節(jié)進行了總結(jié)與展望.

1 基礎(chǔ)知識概述

1.1 組合優(yōu)化問題概述

首先介紹混合整數(shù)線性規(guī)劃模型，一種受限的優(yōu)化問題，許多實際的應(yīng)用都可以歸結(jié)為此類問題.已經(jīng)有許多使用分支定界技術(shù)的工業(yè)優(yōu)化器用以求解此類問題的實例[6－10].該問題能夠表現(xiàn)為如下形式[11]：

式中：c ∈Rn為目標(biāo)系數(shù)向量，A ∈Rm×n為約束系數(shù)矩陣，b ∈Rm為約束向量，p ≤n 為整數(shù)變量的個數(shù).

解決混合整數(shù)線性規(guī)劃模型所使用的工業(yè)求解器，往往也可用于求解離散的組合優(yōu)化問題，常見的離散的組合優(yōu)化問題如下所示.

首先，旅行商問題為給定一個完整的加權(quán)圖G=(V,E)，找出其中權(quán)重最小的路線，這是一個典型的組合優(yōu)化問題，已經(jīng)在路徑規(guī)劃、數(shù)據(jù)聚類、基因測序等領(lǐng)域得到了應(yīng)用[12].旅行商問題屬于NP-hard 問題[13]，為了解決該問題，已經(jīng)有許多精確算法、啟發(fā)式算法、近似算法被提出.其中最著名的精確算法為1962 年被提出的霍普克洛夫特-卡普算法[14]，該算法求解的時間復(fù)雜度為O(n22n)，是目前精確算法中理論速度最好的算法，但并不實用，且在此之后一直未得到改進提升.旅行商問題也可以被表述為混合整數(shù)線性規(guī)劃模型[15]，可以通過混合整數(shù)規(guī)劃模型的求解器得到其精確或近似的解決方案.

最大割問題為給定一個完整的加權(quán)圖G=(V,E)，從包含頂點S ?V 的集合中，找出一個子集，使切口，其中ωij∈W 為連接頂點i 和j 的邊的權(quán)重.最大割問題的解決方法已經(jīng)在許多實際問題中得到了應(yīng)用，包括蛋白質(zhì)折疊[16]、金融投資管理[17]、尋找物理學(xué)中的基態(tài)[18]等.最大割是一個完全的NP 難問題[19]，因此沒有一個明確的多項式時間算法.存在近似算法對其求解，包括確定性的近似算法[20]和隨機的近似算法[21].

裝箱問題為給定一個物品集I，每個i ∈I 的尺寸大小為s(i)∈Z+，以及一個正整數(shù)容量的箱子B.要求將這些物品按一定的數(shù)量放入箱子中，使得每個箱子中的物品大小之和不超過箱子容量并使所用的箱子數(shù)目最少.裝箱問題有多種變體，如二維裝箱、三維裝箱、不同表面積的裝箱等[22]，該問題在許多領(lǐng)域都有應(yīng)用，如資源優(yōu)化、物流和電路設(shè)計等[23].其同樣也是一個完全的NP 難問題，許多近似算法被提出以解決該問題.首選遞減和最佳匹配遞減是兩種簡單的近似算法，首先按照成本的遞減順序?qū)椖窟M行排序，然后將每個項目分配到它所適合的第一個或最完整的箱子.這兩種方法的時間復(fù)雜度都為O(nlogn)[24].精確算法中，最早使用的是Martello-Toth 算法，該算法原理為分支定界算法[25].

最大獨立集問題為給定圖G=(V,E)，尋找到一個集合，該集合任意兩點所構(gòu)成的邊都不是圖G 中的邊，且|S| 最小.該問題是一個受關(guān)注的組合優(yōu)化問題，應(yīng)用于分類理論、分子對接、推薦系統(tǒng)等[26－28].很容易發(fā)現(xiàn)，該問題中圖G 中獨立集的補集是圖G 中的頂點的覆蓋以及補圖ˉG 的團.因此，求解該問題的思路在于找出圖G 中的最小頂點覆蓋或者圖ˉG 中的最大團.使用遍歷算法求解該問題的時間復(fù)雜度為O(n22n)，該算法時間復(fù)雜度被Tarjan 等[29]提升至O(2n/3).而Xiao 等找到其最佳邊界為O(1.199 6n)[30].

最小頂點覆蓋問題為給定圖G=(V,E)，需找到使得每條邊都被覆蓋的節(jié)點最少的節(jié)點集S ?V，即(u,v)∈E ?u ∈S，且|S| 最小.該問題是一個應(yīng)用于計算生物化學(xué)[31]和計算機網(wǎng)絡(luò)安全[32]的基本問題.求解該問題的一種方法為近似算法[33]，通過將任意一條邊的兩個端點添加至解中，并將這兩點從圖中刪除.

為了使用強化學(xué)習(xí)來處理上述問題，必須將問題中涉及到的圖表示為向量，并進一步提供給機器學(xué)習(xí)算法作為輸入，即進行編碼操作.

1.2 編碼器概述

強化學(xué)習(xí)中，編碼器主要是為了處理組合優(yōu)化問題中的輸入狀態(tài)S，將目前得到的輸入狀態(tài)S 映射為d 維的實數(shù).編碼器的結(jié)構(gòu)類型會因輸入狀態(tài)的變化而變化，常用的一些架構(gòu)如下所示.

第一個經(jīng)常使用的架構(gòu)為循環(huán)神經(jīng)網(wǎng)絡(luò)，循環(huán)神經(jīng)網(wǎng)絡(luò)可以對序列數(shù)據(jù)進行操作，將序列中的每個元素編碼為一個向量，如圖1 所示.該網(wǎng)絡(luò)由成塊的形式組成，它把序列的當(dāng)前元素和先前的輸出作為一個輸入.序列的當(dāng)前元素和前一個輸出構(gòu)成循環(huán)神經(jīng)網(wǎng)絡(luò)塊，并輸出一個向量，傳遞給序列的下一個元素.例如，在旅行商問題中，可以通過對當(dāng)前節(jié)點使用循環(huán)神經(jīng)網(wǎng)絡(luò)進行編碼，得到其后續(xù)的一個行程.常用的循環(huán)神經(jīng)網(wǎng)絡(luò)有長短時記憶網(wǎng)絡(luò)[34]和門控循環(huán)單元[35].

圖1 循環(huán)神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

循環(huán)神經(jīng)網(wǎng)絡(luò)的一個基本局限性與其長期依賴關(guān)系的建模有關(guān)：當(dāng)模型獲取最后一個時間步的輸出時，它可能會丟失序列中先前保存的元素信息.而注意力模型通過與所有輸入元素形成連接來解決這個問題.因此，注意力模型的輸出取決于序列的當(dāng)前元素和所有先前的元素.特別是，輸入元素和之前的每個元素之間的相似性分數(shù)（例如點積）被計算出來，這些分數(shù)被用來確定之前的每個元素對當(dāng)前元素的重要性權(quán)重.注意力模型在語言處理上能夠取得不錯的表現(xiàn)[36]，并在組合優(yōu)化問題中得到了應(yīng)用，例如為旅行商問題逐步建立解決方案[37].

值得注意的一點是注意力模型依賴于對輸入結(jié)構(gòu)中每一對元素之間的依賴關(guān)系進行建模，如果只有少數(shù)相關(guān)的依賴關(guān)系，則是低效的.另一種對注意力模型簡單的擴展是指針網(wǎng)絡(luò)[38].指針網(wǎng)絡(luò)不使用所有配對中的權(quán)重來計算每個輸入元素的影響，而是使用權(quán)重來選擇一個將被用于編碼的單一輸入元素.如圖2 所示示例中，元素“A”與元素“B”的相似度最高，因此，它被用于計算元素“B”的表示（與注意力模型不同，在這種情況下，元素“C”和“D”也會被使用）.

圖2 指針網(wǎng)絡(luò)結(jié)構(gòu)

盡管上述的模型具有足夠的通用性，可以應(yīng)用在各種輸入狀態(tài)下，但許多的組合優(yōu)化問題都可以通過圖的形式進行表示，使用圖的形式能夠?qū)M合優(yōu)化問題產(chǎn)生更直觀的理解，而傳統(tǒng)的神經(jīng)網(wǎng)絡(luò)只能通過節(jié)點的特征來理解圖中的依賴關(guān)系，并不全面，而圖神經(jīng)網(wǎng)絡(luò)則可以直接學(xué)習(xí)兩個節(jié)點間的依賴關(guān)系.首先，將節(jié)點關(guān)系通過向量進行表示；然后，每個節(jié)點的表示通過該節(jié)點的鄰域結(jié)構(gòu)進行更新.在最常見的消息傳遞范式中，相鄰的節(jié)點交換它們當(dāng)前的表示，以便在下一次迭代中更新它們.這個框架看作是注意力模型的一般化，其中的元素并不需要關(guān)注其它所有的元素，僅需關(guān)注與當(dāng)前圖相關(guān)的元素.常用的圖神經(jīng)網(wǎng)絡(luò)包括圖卷積網(wǎng)絡(luò)[39]、圖注意力網(wǎng)絡(luò)[40]、圖同構(gòu)網(wǎng)絡(luò)[41]和圖嵌入網(wǎng)絡(luò)[42].

1.3 強化學(xué)習(xí)算法

第1 節(jié)對馬爾可夫決策過程進行了定義，其中包括了狀態(tài)、動作、獎勵等.接下來，將深入介紹搜索馬爾可夫決策過程最優(yōu)策略的強化學(xué)習(xí)算法.強化學(xué)習(xí)算法大體上分為基于模型和無模型兩大類.如圖3 所示.

圖3 強化學(xué)習(xí)算法分類

無模型的方法更專注于環(huán)境，其中的轉(zhuǎn)移函數(shù)是已知的或者可以學(xué)習(xí)的，能夠在算法決策時使用的.包括蒙特卡洛樹搜索算法，如AlphaZero[43]和MuZero[44].

基于模型的方法則不依賴環(huán)境的轉(zhuǎn)移函數(shù)的可用性，只使用智能體所收集到的經(jīng)驗進行學(xué)習(xí).基于模型的方法按照得到解決方案的方法又可分為基于策略和基于價值兩大類方法.在基于策略的方法中，得到的為解決該問題所選擇的策略，而基于價值的方法則側(cè)重于得到一個價值函數(shù)，這個價值函數(shù)是對給定環(huán)境中狀態(tài)-動作對的評價.此外，還有對上述兩種方法進行結(jié)合的方法，比較典型的是演員-評論家方法[45].這種方法的基本原理是演員起到產(chǎn)生策略的作用，而評論家近似于價值函數(shù)的作用.通常為了做到這一點，行為者和評論家都會使用上述的基于策略和基于價值的強化學(xué)習(xí).這樣一來，批判者提供了衡量行為者所采取的行動有多好的標(biāo)準(zhǔn)，從而可以適當(dāng)?shù)卣{(diào)整下一個訓(xùn)練步驟的可學(xué)習(xí)參數(shù).

1.3.1 基于價值的方法

正如前面提到的，所有強化學(xué)習(xí)方法的主要目標(biāo)是找到一個策略，該策略將持續(xù)允許智能體獲得大量獎勵.基于價值的強化學(xué)習(xí)方法主要是通過對價值函數(shù)V(s)和行動價值函數(shù)Q(s,a)的近似來尋找這種策略.在本節(jié)中，將定義這兩個函數(shù)，哪些價值和動作-價值函數(shù)可以被稱為最優(yōu)，以及在知道最優(yōu)價值函數(shù)的情況下，如何能得出最優(yōu)策略.

狀態(tài)s 的價值函數(shù)是對未來折現(xiàn)回報的期望，當(dāng)從狀態(tài)s 開始并遵循一些策略π 時，價值函數(shù)如下所示：

式中：Vπ為策略時的價值函數(shù)V，在有限馬爾可夫決策過程中，其最終狀態(tài)的值為0.同時，把價值函數(shù)看作不僅取決于狀態(tài)而且取決于行動的函數(shù)可能更容易理解.

動作價值函數(shù)Q(s,a) 是對未來折現(xiàn)回報的期望，當(dāng)從狀態(tài)s 開始并遵循一些策略π 時，價值函數(shù)如下所示：

式（5）很明顯與式（6）有下列的關(guān)系：

從價值函數(shù)的定義中產(chǎn)生了一個非常重要的遞歸屬性，代表了狀態(tài)s 的價值Vπ(s) 和后面可能的狀態(tài)s′的價值Vπ(s′)之間的關(guān)系，這也是許多基于價值的強化學(xué)習(xí)方法的基礎(chǔ).這一特性可以用一個方程來表示，稱為貝爾曼方程[46]：

貝爾曼方程使用動作價值函數(shù)的表達形式為：

在本節(jié)開始時已經(jīng)指出，所有強化學(xué)習(xí)任務(wù)的目標(biāo)是找到一個策略，它可以積累大量的獎勵.這意味著，如果一個政策的預(yù)期收益大于另一個政策所取得的收益，那么這個政策就可以比（或等于）另一個政策更好.除此以外，根據(jù)價值函數(shù)的定義，我們可以得到策略π′≥π 當(dāng)且僅當(dāng)對于所有的狀態(tài)來講都有Vπ′(s)≥Vπ(s).

得到了策略之間的這種關(guān)系，則可以確定一定有一種策略優(yōu)于或等于所有其它可能的策略.這個策略被稱為最優(yōu)策略π*.顯而易見，行動-價值函數(shù)和價值函數(shù)的最優(yōu)性與它們所遵循的策略的最優(yōu)性是密切相關(guān)的.如果一個價值函數(shù)是所有策略中價值函數(shù)的最大值，則被稱為最優(yōu)價值函數(shù).如下所示：

同樣的，可以得到最佳行動-價值函數(shù)的定義：

根據(jù)貝爾曼方程（8）和（9），如果行動-價值或價值函數(shù)是已知的，可以推導(dǎo)出最佳策略.根據(jù)已有的最佳的價值函數(shù)V*(s)，可以通過做貪婪搜索找到最佳動作：選擇對應(yīng)于貝爾曼方程（8）所計算的狀態(tài)s 中的最大值V*(s) 的動作.在行動-價值函數(shù)的情況下，不需要進行單步式的搜索.對于每個狀態(tài)s，可以很容易地找到這樣的動作a，使動作函數(shù)最大化，只需要計算Q*(s,a)，而不需要知道下一狀態(tài)s′中的獎勵和價值.

因此，在基于價值的方法的情況下，為了找到最佳策略，需要找到最佳價值函數(shù).值得注意的是，當(dāng)轉(zhuǎn)移函數(shù)已知的情況下，有可能明確地解出貝爾曼方程，即找到最佳價值函數(shù).然而在實踐中，這種情況很少發(fā)生，所以需要一些方法來近似貝爾曼方程的解決方案.

基于近似值的方法的代表是Q-learning[47]以及其的一個變體Deep Q-learning（DQN）[48].在Q-learning中，通過學(xué)習(xí)當(dāng)前策略所產(chǎn)生的經(jīng)驗，對動作-價值函數(shù)Q(s,a) 進行迭代更新，由這種規(guī)則更新的函數(shù)收斂于最優(yōu)價值函數(shù)[49].

隨著深度學(xué)習(xí)的發(fā)展，神經(jīng)網(wǎng)絡(luò)已被證明在各種數(shù)據(jù)集上取得了最先進的結(jié)果，它通過高維輸入學(xué)習(xí)有用的函數(shù)近似.強化學(xué)習(xí)發(fā)展出了同深度學(xué)習(xí)相結(jié)合的DQN，可以直接使用端到端強化學(xué)習(xí)來學(xué)習(xí)策略[50].該網(wǎng)絡(luò)根據(jù)當(dāng)前的輸入狀態(tài)為每個動作近似地計算出Q 值.其損失函數(shù)如下所示：

式中：D 為記憶回放機制容量，用來存儲訓(xùn)練中產(chǎn)生的軌跡(s,a,r,s′).其結(jié)果是當(dāng)前Q 函數(shù)的近似值與某個最大化目標(biāo)值之間的均方誤差.DQN 的訓(xùn)練已被證明是比較穩(wěn)定的，因此，DQN 對許多組合優(yōu)化問題都是有效的.

1.3.2 基于策略的方法

基于價值的方法旨在找到最佳狀態(tài)-動作價值函數(shù)Q*(s,a)，并對其進行貪婪的行動以獲得最佳策略π，與之不同的是，基于策略的方法試圖通過對式（3）中的策略參數(shù)進行優(yōu)化，直接找到由一些參數(shù)θ 表示的最佳策略π*θ：該方法收集環(huán)境中使用當(dāng)前策略的經(jīng)驗，并利用這些收集的經(jīng)驗對其進行優(yōu)化.已經(jīng)有許多方法來優(yōu)化策略函數(shù)，接下來討論解決組合優(yōu)化問題的常用方法.

第一種為策略梯度算法，為了對式（3）中的策略參數(shù)θ 進行優(yōu)化，可以應(yīng)用策略梯度定理[51]來估計策略函數(shù)的梯度，其形式如下：

第二種為REINFORCE 算法，基線b(s) 的作用為減少回報估計的方差 ?A(st,at)，由于它是通過運行當(dāng)前的策略πθ計算出來的，初始參數(shù)可能導(dǎo)致訓(xùn)練開始時的性能不佳，基線b(s) 試圖通過減少方差來緩解這種情況.當(dāng)b(s) 被排除在回報估計計算之外時，得到了一個REINFORCE 算法[52].另外，可以通過計算采樣軌跡的平均獎勵來計算基線值b(st)，或者使用參數(shù)化的價值函數(shù)估計器Vφ(st).

第三種為Actor-Critic 算法，該算法通過使用自舉法從后續(xù)狀態(tài)-價值估計的值中更新狀態(tài)值，進一步擴展了REINFORCE 與基線.一個常見的方法是使用參數(shù)值函數(shù)來計算每一步的收益估計值：

雖然這種方法會給梯度估計帶來偏差，但它往往能進一步減少方差.此外，這種方法可以應(yīng)用于在線和持續(xù)學(xué)習(xí)，因為它們不再依賴蒙特卡洛滾動，即把軌跡展開到一個終端狀態(tài).

第四種為近端策略優(yōu)化算法，第三種強化學(xué)習(xí)算法的進一步發(fā)展推出了一些更先進的方法，如近端策略優(yōu)化（PPO）[53]，該算法在策略空間中以約束條件進行策略更新，試圖學(xué)習(xí)一個參數(shù)化的狀態(tài)-行動價值函數(shù)Qφ(s,a)，對應(yīng)于當(dāng)前策略，并使用它來計算引導(dǎo)的回報估計.PPO 算法公式如下：

1.3.3 蒙特卡洛樹搜索

基于價值的方法和基于策略的方法都不使用環(huán)境的模型（無模型的方法），即模型的轉(zhuǎn)移概率，因此，這種方法不通過展開環(huán)境到下一個步驟.然而，為組合優(yōu)化問題定義一個馬爾可夫決策過程是可行的，可以利用環(huán)境的知識，通過提前幾步計劃來提高預(yù)測能力.蒙特卡洛樹搜索算法的一般程序包括選擇、擴展、模擬和回溯[54]，如圖4 所示.其中，不是通過進行遍歷來評估樹中的葉子節(jié)點，而是使用神經(jīng)網(wǎng)絡(luò)fθ來為樹中的新節(jié)點提供策略P(s,*)和狀態(tài)-價值估計V(s).樹中的節(jié)點表示狀態(tài)s，每條邊指代動作a.在選擇階段，從根狀態(tài)s0開始，不斷選擇下一個狀態(tài)，使置信度上限最大化，公式如下所示：

圖4 蒙特卡洛樹搜索操作

當(dāng)遇到搜索樹中以前未見過的節(jié)點時，對該節(jié)點的策略P(s,*)、狀態(tài)價值函數(shù)以及狀態(tài)-價值估計V(s)進行估計.之后，V(s) 的估計值沿著搜索樹向后傳播，更新Q(s,a) 和N(s,a) 的值.經(jīng)過若干次搜索迭代后，根據(jù)改進的策略從根狀態(tài)中選擇下一個動作，公式如下所示：

2 強化學(xué)習(xí)求解組合優(yōu)化問題

本節(jié)對近年來現(xiàn)有的解決組合優(yōu)化問題的強化學(xué)習(xí)方法進行了介紹，這些問題包括旅行商問題、最大剪問題、裝箱問題、最小頂點覆蓋問題和最大獨立集問題.對解決這些問題的算法進行了羅列對比.

2.1 旅行商問題

Bello 等[55]最早將策略梯度算法應(yīng)用于組合優(yōu)化問題.在解決旅行商問題時，其馬爾可夫決策過程的表現(xiàn)形式為：狀態(tài)是一個d 維的圖嵌入向量，代表節(jié)點在時間t 的當(dāng)前行程，而動作是挑選另一個節(jié)點，該節(jié)點在當(dāng)前狀態(tài)下沒有被使用過.初始狀態(tài)s0即為初始節(jié)點的嵌入表示.在這種情況下，轉(zhuǎn)移函數(shù)T(s,a,s′) 會返回所構(gòu)建的旅行的下一個節(jié)點，直到所有的節(jié)點都被訪問過.最后，其獎勵函數(shù)與總的行程進行負相關(guān).指針網(wǎng)絡(luò)被用來對輸入序列進行編碼，而解決方案則是利用解碼器的指針機制從輸入的分布中依次構(gòu)建的，并進行并行異步訓(xùn)練.

Dai 等[56]的工作又對其進行了提升，在狀態(tài)、動作等改變不大的情況下，將獎勵進行了改進.獎勵被定義為從狀態(tài)s 過渡到狀態(tài)s′后，采取某種動作a 時，成本函數(shù)的差異，即r(s,a)=c(h(s′),G)-c(h(s),G)，其中：h為圖嵌入函數(shù)，G 為該問題的圖表示，c 為代價函數(shù).除此以外，在神經(jīng)網(wǎng)絡(luò)中使用了圖嵌入網(wǎng)絡(luò)進行了編碼工作，DQN 作為網(wǎng)絡(luò)參數(shù)更新的強化學(xué)習(xí)算法.

受到Bello 等[55]的啟發(fā)，Nazari 等[57]使用強化學(xué)習(xí)求解了旅行商問題的一種延續(xù)問題――車輛路徑問題.Bello 等[55]提出的方法不能直接應(yīng)用于解決車輛路徑問題，因為它具有動態(tài)性質(zhì)，即一旦節(jié)點被訪問，該節(jié)點的需求就會變成零，因為它嵌入了輸入的順序和靜態(tài)性質(zhì).Nazari 等[57]擴展了以前用于解決TSP 的方法來規(guī)避這個問題，并找到了車輛路徑問題及其隨機變體的解決方案.其狀態(tài)設(shè)置為一個包含兩元素的向量，其中一個值為當(dāng)前時刻的位置坐標(biāo)，另一個值為當(dāng)前時刻的任務(wù)需求.動作設(shè)置為選定下一個將要去的節(jié)點.獎勵則與旅行商問題中使用的獎勵類似，它是負的總路線長度，只有在所有客戶的需求得到滿足后才會給智能體.除此以外，編碼器被簡化，用1-d 卷積嵌入層取代長短時記憶單元，使模型對輸入序列的順序不變，從而能夠處理動態(tài)狀態(tài)變化.然后，通過使用REINFORCE 算法進行策略學(xué)習(xí)，而對于隨機的車輛路徑問題，則使用A3C 算法進行訓(xùn)練.

與Nazari 等[57]的工作類似，Deudon 等[58]采用了相同的方法，但改變了編碼器和解碼器的網(wǎng)絡(luò)結(jié)構(gòu).其圖神經(jīng)網(wǎng)絡(luò)的編碼器架構(gòu)不包括長短時記憶單元，而是完全基于注意力機制，因此輸入被編碼為一個集合而不是一個序列.解碼網(wǎng)絡(luò)仍然使用指針網(wǎng)絡(luò).此外，作者還研究了將強化學(xué)習(xí)智能體提供的解決方案與2-Opt 啟發(fā)式方法相結(jié)合，以進一步改善得到的結(jié)果.帶有批評基線的REINFORCE 算法被用來更新所描述的編碼解碼器的網(wǎng)絡(luò)參數(shù).

Kool 等[59]提出了一種構(gòu)造啟發(fā)式學(xué)習(xí)方法，以解決旅行商問題和車輛路徑問題的兩種變體.其編碼器使用了一種類似于Transformer 的基于注意力的編碼器，而解碼器則與指針網(wǎng)絡(luò)相類似.

Liu 等[60]提出了一種改進的強化突變遺傳算法，命名為RMGA，用于解決TSP.RMGA 的核心在于使用異構(gòu)配對選擇EAX 中的隨機配對選擇和強化突變算子（RLM）的構(gòu)造，方法是修改Q 學(xué)習(xí)算法并將其應(yīng)用于修改后生成的個體EAX.TSP 中對小型和大型TSP 實例的實驗結(jié)果表明，RMGA 幾乎每次都能在合理的時間內(nèi)獲得最佳游覽，在解決方案質(zhì)量和運行時間方面優(yōu)于已知的EAX-GA 和LKH.

Cappart 等[61]的工作結(jié)合了兩種解決帶時間窗口的旅行商問題的方法，即強化學(xué)習(xí)方法和約束編程方法，以便學(xué)習(xí)分支策略.為了對組合優(yōu)化問題進行編碼，作者提出了一個動態(tài)編程公式，作為兩種技術(shù)之間的橋梁.其狀態(tài)s 是由三種元素組成的向量，包括仍需訪問的剩余城市集、已訪問的最后一個城市以及當(dāng)前時間.其動作為選擇一個相應(yīng)的城市.獎勵為兩個城市花費時間的負相關(guān).然后，這個馬爾可夫決策過程可以轉(zhuǎn)化為一個動態(tài)編程模型.通過DQN 和PPO 算法進行訓(xùn)練.

Drori 等[62]的工作與之前的工作不同，他們的方法針對特殊的問題給出解決方案.相比之下，這項工作為無模型強化學(xué)習(xí)提供了一個通用框架，使用圖神經(jīng)網(wǎng)絡(luò)表示，通過改變獎勵來適應(yīng)不同的問題類別.這個框架通過使用邊緣到頂點的線圖來模擬問題，并將其制定為一個單人游戲框架.將策略表示為具有基于注意力的解碼器的圖嵌入網(wǎng)絡(luò)編碼器，在樹形搜索過程中訓(xùn)練學(xué)習(xí).

Xu 等[63]考慮到現(xiàn)有的強化學(xué)習(xí)模型都是簡單地聚合節(jié)點嵌入來生成前后關(guān)聯(lián)的嵌入，而沒有考慮到動態(tài)的網(wǎng)絡(luò)結(jié)構(gòu)，使得它們不能對動態(tài)的狀態(tài)轉(zhuǎn)換和行動選擇進行建模.其開發(fā)了一個新的基于注意力的強化學(xué)習(xí)模型，通過批量歸一化重排和門聚合提供增強的節(jié)點嵌入，以及通過對多個關(guān)系結(jié)構(gòu)的注意力聚合模塊提供動態(tài)感知的嵌入.通過實驗表明，其設(shè)計的模型不僅優(yōu)于基于學(xué)習(xí)的基線，而且解決問題的速度也比傳統(tǒng)基線快很多.此外，在評估大規(guī)模問題以及不同數(shù)據(jù)分布的問題時顯示出更好的通用性.

Zhang 等[64]通過結(jié)合熵正則化最優(yōu)傳輸技術(shù)與強化學(xué)習(xí)算法以解決旅行商問題，其將熵正則化技術(shù)整合為編碼器網(wǎng)絡(luò)的一個層，并構(gòu)建為一個能夠在沒有監(jiān)督和推論的情況下學(xué)習(xí)的模型，其速度明顯快于目前的自回歸方法.通過實驗評估了在深度學(xué)習(xí)模型中包含最優(yōu)傳輸算法的優(yōu)勢.旅行商問題總結(jié)見表1.

表1 強化學(xué)習(xí)求解旅行商問題總結(jié)

2.2 最大剪問題

Dai 等[56]首次將強化學(xué)習(xí)應(yīng)用于求解最大剪問題，提出了通過結(jié)合圖嵌入和Q-learning 來構(gòu)造啟發(fā)式的原則性方法，他們將該問題表述為馬爾可夫決策過程，其中狀態(tài)空間s 被定義為問題的部分解決方案，即添加到圖中的所有節(jié)點的子集，該子集能使最大切口最大化.動作空間為一組不在當(dāng)前狀態(tài)下的節(jié)點.轉(zhuǎn)移函數(shù)T(st+1|st,at) 是確定性的，對應(yīng)于用特征xv=1 標(biāo)記最后選定的節(jié)點.獎勵的計算方式是立即改變減重，當(dāng)減重?zé)o法通過進一步的行動得到改善時，該回合就會終止.圖嵌入網(wǎng)絡(luò)被用作狀態(tài)的編碼器.Q-learning 算法的一個變種被用來學(xué)習(xí)構(gòu)建解決方案，該算法在隨機生成的圖形實例上進行了訓(xùn)練.與常用的啟發(fā)式解決方案相比，這種方法實現(xiàn)了更好的近似率以及泛化能力，這一點已經(jīng)通過在由50～100 個節(jié)點組成的圖上的訓(xùn)練和在多達1 000～1 200 個節(jié)點的圖上的測試得到了證明，實現(xiàn)了與精確解決方案非常好的近似率.

Barrett 等[65]在Dai 等[56]的工作基礎(chǔ)上，提出ECO-DQN 算法，在近似率以及泛化方面進行了改進.該算法保持了原算法的一般框架，但是引入了一些修改.智能體被允許從部分構(gòu)建的解決方案中刪除頂點，以更好地探索解決方案空間.獎勵函數(shù)也作出改進，以提供一個正?；脑隽开剟町?dāng)找到一個比迄今為止的回合中看到的更好的解決方案，以及給予較小的獎勵當(dāng)找到一個在回合中尚未看到的局部最優(yōu)解決方案.此外，對降低切割值沒有添加懲罰措施.狀態(tài)編碼器的輸入被修改以適應(yīng)獎勵函數(shù)的變化.因為在這種情況下，智能體已經(jīng)能夠無限期地探索，所以情節(jié)長度被設(shè)定為2|V|.作者允許算法從一個任意的狀態(tài)開始，這對于將這種方法與其它方法（例如啟發(fā)式方法）結(jié)合起來是很有效的.該方法顯示了比原本算法更好的近似率，以及更好的泛化能力.

Cappart 等[66]通過將強化學(xué)習(xí)納入決策圖框架來學(xué)習(xí)啟發(fā)式，設(shè)計了解決最大切割問題的聯(lián)合方法.強化學(xué)習(xí)的整合允許通過學(xué)習(xí)變量排序的啟發(fā)式方法以向決策圖提供更嚴(yán)格的目標(biāo)函數(shù)界限的解決方案.狀態(tài)空間s 被表示為一組選定變量的有序序列以及部分構(gòu)建的決策圖.動作空間a 由未被選定的變量組成.轉(zhuǎn)移函數(shù)則將已選用的變量加入已用集合與決策圖中.獎勵函數(shù)旨在縮小決策圖的界限，并被編碼為變量加入集合以改進相對上限和下限.實驗表明，他們的方法優(yōu)于幾個排序啟發(fā)式方法，對較大的圖實例有很好的泛化作用，但沒有與其它基于強化學(xué)習(xí)的方法進行比較.

Tang 等[67]將強化學(xué)習(xí)框架同切割面方法進行結(jié)合，其狀態(tài)空間包括了原始的線性約束和迄今為止所添加的切割，動作空間則使用了割平面法，轉(zhuǎn)移函數(shù)將所選擇的切割添加到問題中，從而形成一個新的狀態(tài).獎勵函數(shù)被定義為兩個連續(xù)線性問題解決方案的目標(biāo)函數(shù)之差.策略梯度算法被用來選擇新的割平面，并用基于注意力機制的長短時記憶網(wǎng)絡(luò)對狀態(tài)進行編碼.該算法使用進化策略對生成的圖實例進行了訓(xùn)練，與通常用于選擇割平面的啟發(fā)式方法相比，其已被證明能夠提高切割的效率、完整性差距和概括性.

Gu 等[68]使用了帶有指針網(wǎng)絡(luò)的Actor-Critic 算法迭代構(gòu)建出了解決方案.狀態(tài)空間定義為一個對稱矩陣，其值是節(jié)點之間的邊緣權(quán)重.該矩陣以每列的形式作為輸入進入到指針網(wǎng)絡(luò)，由指針網(wǎng)絡(luò)產(chǎn)生當(dāng)前時刻的動作，以指向輸入向量的指針形式，加上一個特殊的序列結(jié)束符號“EOS”.由此產(chǎn)生的“EOS”符號分隔的節(jié)點序列代表了問題的解決方案，并從中計算出獎勵.作者用多達300 個節(jié)點的模擬圖進行了實驗，并產(chǎn)生了相當(dāng)好的近似率，但并沒有與以前的工作或已知的啟發(fā)式方法進行比較.最大剪問題總結(jié)見表2.

表2 強化學(xué)習(xí)求解最大剪問題總結(jié)

2.3 裝箱問題

Zhao 等[69]解決的是一個具有挑戰(zhàn)性但實際有用的三維垃圾箱包裝問題（3D-BPP）的變體.智能體對要裝入一個倉的物品的信息有限，而且一個物品必須在到達后立即被裝入，不需要緩沖或重新調(diào)整.物品的擺放也受制于順序依賴和物理穩(wěn)定性.其將此在線3D-BPP 表述為一個受限的馬爾可夫決策過程（CMDP）.為了解決這個問題，提出了一個有效的、易于實施的、在行為人批判框架下的約束性深度強化學(xué)習(xí)方法.特別是，引入了一個預(yù)測和投射方案.代理人首先預(yù)測安置行動的可行性掩碼，作為一項輔助任務(wù)，然后使用掩碼來調(diào)節(jié)訓(xùn)練期間演員輸出的行動概率.這樣的監(jiān)督和投射有利于智能體有效地學(xué)習(xí)可行的政策.方法可以很容易地擴展到處理超前物品、多倉包裝和物品重新定位.

Duan 等[70]試圖解決上述中方法的局限性，具體來說，作者提出構(gòu)建一個端到端的通道，通過使用注意力機制來選擇一個物品、方向和位置坐標(biāo).其狀態(tài)空間包括物品是否被包裝的標(biāo)志位、物品的尺寸以及相對箱子的坐標(biāo).動則空間則包括物品的選擇、旋轉(zhuǎn)和物品在垃圾箱中的位置.獎勵函數(shù)是遞增的，通過箱中的空閑體積進行計算，即當(dāng)前箱子的體積減去包裝物品的體積.訓(xùn)練算法選用了Actor-Critic 算法.與遺傳算法和以前的強化學(xué)習(xí)方法相比，對于大小不超過30 個物品的問題，所提出的方法實現(xiàn)了較小的箱體間隙比率.

Jiang 等[71]通過設(shè)計端到端的多模態(tài)的強化學(xué)習(xí)智能體解決了三維裝箱問題，通過多模態(tài)的處理，將整體的任務(wù)分為三個子任務(wù)，包括順序、方向和位置，智能體將會按照順序解決三個子任務(wù).其狀態(tài)空間由箱體狀態(tài)和視圖狀態(tài)構(gòu)成，箱體狀態(tài)主要包含了箱體的相關(guān)信息，視圖狀態(tài)則確定了箱體的整體位置，將原本的三維進行了降維處理.動作空間的輸出則是通過解碼器直接進行位置選擇.在算法選擇中，選用了廣義優(yōu)勢估計同A2C 算法進行結(jié)合.作者通過設(shè)計的多模態(tài)強化學(xué)習(xí)算法，解決了原本只能處理50 個箱體問題的局限性，使智能體能夠解決100 個箱體及更大的實例.裝箱問題總結(jié)見表3.

表3 強化學(xué)習(xí)求解裝箱問題總結(jié)

2.4 最小頂點覆蓋問題

Song 等[72]提出了在分類領(lǐng)域得到普及的聯(lián)合協(xié)同訓(xùn)練方法，以構(gòu)建順序性策略.其使用了兩種學(xué)習(xí)策略：第一種參考了Dai 等[56]描述的方法，第二種是通過分支定界法解決的整數(shù)線性編程方法.所提出的算法在直覺上類似模仿學(xué)習(xí)，算法中的兩個策略產(chǎn)生出兩個政策，并對其進行估計以找出哪個政策更好，在它們之間交換信息，最后，進行算法更新.所進行的實驗中，列出了與S2V-DQN、模仿學(xué)習(xí)和Gurobi 求解器的比較，并顯示在500 個節(jié)點以下的問題上有較小的優(yōu)化差距.最小頂點覆蓋問題總結(jié)見表4.

表4 強化學(xué)習(xí)求解最小頂點覆蓋問題總結(jié)

2.5 最大獨立集問題

Cappart 等[66]首先使用強化學(xué)習(xí)解決了最大獨立集問題.通過強化學(xué)習(xí)算法尋找決策圖中變量的最佳排序，以縮小該問題中的松弛邊界.具體的實施方法與2.2 節(jié)中相同.Alipour 等[73]提出了一種多智能體強化學(xué)習(xí)方法以解決最大獨立集問題，該方法中，每個智能體試圖自主解決最大獨立集問題，并使用強化學(xué)習(xí)改善其局部行為，通過分享成功的結(jié)果直接與其它智能體進行交流.同時，2-1 局部搜索被用于進一步改進每一步的解決方案.實驗在多組實例上進行測試，結(jié)果表明所提方法能夠競爭甚至超過一些最先進的算法.最大獨立集問題總結(jié)見表5.

表5 強化學(xué)習(xí)求解最大獨立集問題總結(jié)

3 結(jié)論與展望

前面幾節(jié)已經(jīng)介紹了利用強化學(xué)習(xí)算法解決典型組合優(yōu)化問題的幾種方法.由于這個領(lǐng)域已經(jīng)證明了能夠與最先進的啟發(fā)式方法和求解器相媲美的性能，我們期望在以下方向繼續(xù)深入研究.

1）擴大組合優(yōu)化問題的求解范圍.當(dāng)前的主要問題之一在于求解問題所作的實驗對比的數(shù)量有限.實際的組合優(yōu)化問題所涉及到的數(shù)學(xué)問題非常龐大，而目前的方法往往需要針對一組具體的問題來實施.盡管強化學(xué)習(xí)算法能夠?qū)W(xué)到的策略應(yīng)用到未訓(xùn)練過的問題上，但是這些問題往往是同一問題的較小實例，或者具有不同分布的問題實例，甚至是來自另一組組合優(yōu)化問題的實例.如何能夠從當(dāng)前已經(jīng)訓(xùn)練好的算法出發(fā)，解決更多類型的組合優(yōu)化問題是一個很好的方向.

2）提高算法求解質(zhì)量.本文所介紹的許多研究工作，與商業(yè)求解器相比，表現(xiàn)出了卓越的性能，其中一些還實現(xiàn)了與最佳解決方案或啟發(fā)式算法實現(xiàn)的解決方案的求解質(zhì)量相等.然而，這些結(jié)果在更加復(fù)雜的組合優(yōu)化問題中往往表現(xiàn)欠佳，因此，將經(jīng)典的組合優(yōu)化算法與強化學(xué)習(xí)方法進行結(jié)合是很好的發(fā)展方向.

3）從算法模型上進行改進.目前的研究中，許多優(yōu)化模型是以端到端的方法進行求解，其解的質(zhì)量較差，大部分文獻都需要進一步通過波束搜索、局部搜索、采樣策略等方式進一步提升解的質(zhì)量，這說明當(dāng)前的模型仍然有很大的提升空間，未來需要進一步對求解組合優(yōu)化問題的深度神經(jīng)網(wǎng)絡(luò)模型進行研究.