李凱文 張 濤 王 銳 覃偉健 賀惠暉 黃 鴻

組合優(yōu)化問題(Combinatorial optimization problem,COP)是一類在離散狀態(tài)下求極值的最優(yōu)化問題,其數(shù)學(xué)模型如下所示:

其中x為決策變量、F(x) 為目標(biāo)函數(shù)、G(x) 為約束條件,D表示離散的決策空間,為有限個點組成的集合.組合優(yōu)化問題在國防、交通、產(chǎn)品制造、管理決策、電力、通信等領(lǐng)域都有廣泛的應(yīng)用[1],常見的組合優(yōu)化問題包括旅行商問題(Traveling salesman problem,TSP)、車輛路徑問題(Vehicle routing problem,VRP)、車間作業(yè)調(diào)度問題(Job-shop scheduling)、背包問題(Knapsack)、最小頂點覆蓋問題(Minimum vertex cover,MVC)、最小支配集問題(Minimum dominating problem,MDP)等.

組合優(yōu)化問題的特點是其決策空間為有限點集,直觀上可以通過窮舉法得到問題的最優(yōu)解,但是由于可行解數(shù)量隨問題規(guī)模呈指數(shù)型增長,無法在多項式時間內(nèi)窮舉得到問題的最優(yōu)解[2],為此數(shù)十年來學(xué)者對組合優(yōu)化問題的求解算法進行了大量的研究,目前求解組合優(yōu)化問題的方法主要包括精確方法(Exact approaches)和近似方法(Approximate approaches)兩大類:

1) 精確方法是可以求解得到問題全局最優(yōu)解的一類算法,主要包括分支定界法(Branch and bound)[1,3]和動態(tài)規(guī)劃法(Dynamic programming)[4?5],其均采用分而治之的思想通過將原問題分解為子問題的方式進行求解[2],通過不斷迭代求解得到問題的全局最優(yōu)解.

2) 近似方法是可以求解得到問題局部最優(yōu)解的方法,主要包括近似算法(Approximate algorithms) 和啟發(fā)式算法(Heuristic algorithms)兩類[2].近似算法是可以得到有質(zhì)量保證的解的方法,包括貪心算法、局部搜索算法、線性規(guī)劃和松弛算法、序列算法等[6?8];啟發(fā)式算法是利用設(shè)定的啟發(fā)式規(guī)則對解空間進行搜索的一類方法,能夠在可行時間內(nèi)找到一個較好的解,但是對解的質(zhì)量沒有保證,文獻中用來求解組合優(yōu)化問題的啟發(fā)式算法主要包括模擬退火算法[9?10]、禁忌搜索[11?12]、進化算法[13](如遺傳算法[14?15],差分進化算法[16?17]等)、蟻群優(yōu)化算法[18?19]、粒子群算法[20?21]、迭代局部搜索[22?23],變鄰域搜索[24?25]等.

精確方法可以求解得到組合優(yōu)化問題的全局最優(yōu)解,但是當(dāng)問題規(guī)模擴大時,該類算法將消耗巨大的計算量,很難拓展到大規(guī)模問題;相對于精確方法,近似方法可以在可接受的計算時間內(nèi)搜索得到一個較好的解.基于群體智能的進化方法以及局部搜索等方法都是近年來的研究熱點,但是該類方法都是迭代型優(yōu)化算法,當(dāng)問題規(guī)模很大時,大量的迭代搜索仍然會導(dǎo)致較大的計算耗時,近似方法仍然很難拓展到在線、實時優(yōu)化問題.此外,一旦問題發(fā)生變化,上述方法一般需要重新進行搜索求解,或者通過不斷試錯對啟發(fā)式規(guī)則進行調(diào)整以獲得更好的效果,計算成本高.

近年來隨著人工智能技術(shù)的發(fā)展,深度學(xué)習(xí)技術(shù)已經(jīng)在很多領(lǐng)域打破了傳統(tǒng)方法的壁壘,取得了令人矚目的突破性進展.在計算機視覺領(lǐng)域,十多年前學(xué)者們主要利用人工設(shè)計的算法進行特征提取以及圖像處理,但如今深度學(xué)習(xí)已經(jīng)成為了當(dāng)前的核心方法,深度神經(jīng)網(wǎng)絡(luò)(Deep neural networks,DNN)可以自動地對圖像的特征進行學(xué)習(xí),代替了人類的手工算法設(shè)計.作為深度學(xué)習(xí)另外一個重要的分支,深度強化學(xué)習(xí)(Deep reinforcement learning,DRL)主要用來做序貫決策,即根據(jù)當(dāng)前的環(huán)境狀態(tài)做出動作選擇,并根據(jù)動作的反饋不斷調(diào)整自身的策略,從而達到設(shè)定的目標(biāo).近年來深度強化學(xué)習(xí)在AlphaGo Zero[26]、Atari[27]等問題上的表現(xiàn)顯示了其強大的學(xué)習(xí)能力和優(yōu)化決策能力.

組合優(yōu)化即在離散決策空間內(nèi)進行決策變量的最優(yōu)選擇,與強化學(xué)習(xí)的 “動作選擇” 具有天然相似的特征,且深度強化學(xué)習(xí) “離線訓(xùn)練、在線決策”的特性使得組合優(yōu)化問題的在線實時求解成為了可能,因此利用深度強化學(xué)習(xí)方法解決傳統(tǒng)的組合優(yōu)化問題是一個很好的選擇.鑒于此,近些年涌現(xiàn)出了一系列利用深度強化學(xué)習(xí)方法解決組合優(yōu)化問題的新方法,在TSP、VRP、Knapsack 等組合優(yōu)化問題上取得了很好的效果.相對于傳統(tǒng)組合優(yōu)化算法,基于DRL 的組合優(yōu)化算法具有求解速度快、泛化能力強等一系列優(yōu)勢,該類方法是近年來的研究熱點.

由于基于DRL 的組合優(yōu)化方法是近年來新興的研究領(lǐng)域,尚未有文獻對該類方法進行系統(tǒng)的研究和綜述,因此本文對近年來利用DRL 方法求解組合優(yōu)化問題的重要模型進行總結(jié)回顧,對該類方法的基本原理進行介紹,對各個算法的優(yōu)缺點和優(yōu)化性能進行總結(jié)和比較,并指出未來該方向亟待解決的若干問題,旨在為學(xué)者在該新興方向的研究提供指導(dǎo).

文章的結(jié)構(gòu)組織如下:第1 節(jié)首先對基于深度強化學(xué)習(xí)的組合優(yōu)化方法進行了概述,對其產(chǎn)生、歷史發(fā)展、方法分類以及優(yōu)缺點進行了介紹;第2節(jié)對基于深度強化學(xué)習(xí)解決組合優(yōu)化問題的基本原理進行介紹;第3 節(jié)對當(dāng)前主流的基于深度強化學(xué)習(xí)的組合優(yōu)化方法進行了綜述,根據(jù)方法的不同類別,對各個算法的原理、優(yōu)缺點和優(yōu)化性能進行了對比介紹;第4 節(jié)對該類方法在近年來的應(yīng)用研究進行介紹;最后對本文進行總結(jié).

1 基于深度強化學(xué)習(xí)的組合優(yōu)化:概述

利用神經(jīng)網(wǎng)絡(luò)解決組合優(yōu)化問題的方法最早可追溯至Hopfield 等在1985 年提出的Hopfield 網(wǎng)絡(luò)[28],該神經(jīng)網(wǎng)絡(luò)用于求解TSP 問題以及其他組合優(yōu)化問題[29],但是該神經(jīng)網(wǎng)絡(luò)網(wǎng)絡(luò)每次只能學(xué)習(xí)并解決單個小規(guī)模TSP 問題實例,對于新給定的一個TSP問題需要從頭開始再次訓(xùn)練,相對于傳統(tǒng)算法并沒有優(yōu)勢.

神經(jīng)網(wǎng)絡(luò)真正能夠有效解決組合優(yōu)化問題是在2015 年,Vinyals 等[30]將組合優(yōu)化問題類比為機器翻譯過程(即序列到序列的映射),神經(jīng)網(wǎng)絡(luò)的輸入是問題的特征序列(如城市的坐標(biāo)序列),神經(jīng)網(wǎng)絡(luò)的輸出是解序列(如城市的訪問順序),Vinyals等根據(jù)該思想,對機器翻譯領(lǐng)域的經(jīng)典序列映射模型(Sequence-to-sequence,Seq2Seq)進行了改進,提出了可以求解組合優(yōu)化問題的指針網(wǎng)絡(luò)模型(Pointer network,Ptr-Net)[30],其原理詳見第2 節(jié),作者采用監(jiān)督式學(xué)習(xí)的方式訓(xùn)練該網(wǎng)絡(luò)并在TSP問題上取得了較好的優(yōu)化效果.多年來傳統(tǒng)的組合優(yōu)化算法都是以 “迭代搜索”的方式進行求解,但是Vinyals等的模型可以利用神經(jīng)網(wǎng)絡(luò)直接輸出問題解,開啟了組合優(yōu)化一個新的研究領(lǐng)域.

自Ptr-Net 方法被提出后,近三年來多個基于Ptr-Net 架構(gòu)的新方法在NeurIPS,ICLR 等人工智能頂會上被相繼提出[30–36],在TSP、VRP、Knapsack、多目標(biāo)TSP 等組合優(yōu)化問題上顯示了強大的優(yōu)化效果,由于監(jiān)督式學(xué)習(xí)需要構(gòu)造大量帶標(biāo)簽的樣本,很難實際應(yīng)用,目前大多數(shù)研究均利用深度強化學(xué)習(xí)方法對模型進行訓(xùn)練.

除指針網(wǎng)絡(luò)模型之外,近年來隨著圖神經(jīng)網(wǎng)絡(luò)技術(shù)的興起,部分學(xué)者采用圖神經(jīng)網(wǎng)絡(luò)對組合優(yōu)化問題進行求解,與指針網(wǎng)絡(luò)模型不同的是,該類方法采用圖神經(jīng)網(wǎng)絡(luò)對每個節(jié)點的特征進行學(xué)習(xí),從而根據(jù)學(xué)習(xí)到的節(jié)點特征進行后續(xù)的鏈路預(yù)測、節(jié)點預(yù)測等任務(wù),其原理詳見第2 節(jié).Dai 等[37]首次結(jié)合圖神經(jīng)網(wǎng)絡(luò)和深度強化學(xué)習(xí)方法對MVC、TSP 等組合優(yōu)化問題進行了研究,作者利用圖神經(jīng)網(wǎng)絡(luò)對各個 “待選節(jié)點”的Q 值進行估計,每次根據(jù)Q 值利用貪婪策略向當(dāng)前解插入一個新節(jié)點,直到構(gòu)造一個完整的解.文獻[38–41]使用了不同的圖神經(jīng)網(wǎng)絡(luò)以及不同的解構(gòu)造方法對組合優(yōu)化問題進行求解,在二次分配問題、最大覆蓋問題、MVC等組合優(yōu)化問題上取得了較好的效果.由于圖神經(jīng)網(wǎng)絡(luò)主要進行節(jié)點特征的提取,部分研究[34?35]結(jié)合圖神經(jīng)網(wǎng)絡(luò)和指針網(wǎng)絡(luò)進行組合優(yōu)化算法的設(shè)計,即首先使用圖神經(jīng)網(wǎng)絡(luò)進行節(jié)點特征計算,再使用指針網(wǎng)絡(luò)的Attention 機制進行解的構(gòu)造,在TSP等問題上取得了較好的優(yōu)化性能.

以上方法均為 “端到端(End-to-end)方法”,即給定問題實例作為輸入,利用訓(xùn)練好的深度神經(jīng)網(wǎng)絡(luò)直接輸出問題的解,其中神經(jīng)網(wǎng)絡(luò)的參數(shù)一般利用深度強化學(xué)習(xí)方法訓(xùn)練得到.相對于傳統(tǒng)的迭代型優(yōu)化算法,該類端到端方法無需搜索直接輸出問題解,具有求解速度快的優(yōu)勢;且模型一旦訓(xùn)練完成,可以對具有相同分布特性的所有問題實例進行求解,而不需要重新進行訓(xùn)練,模型具有很強的泛化能力,而傳統(tǒng)算法一旦遇到一個新的問題實例,則需要從頭開始重新進行搜索求解.因此該類方法為求解組合優(yōu)化問題提供了一種全新的思路,具有求解速度快、泛化能力強的優(yōu)勢.

但是由于端到端方法通過神經(jīng)網(wǎng)絡(luò)直接輸出最終解,解的最優(yōu)性很難保證,上述方法在小規(guī)模問題上可以接近最優(yōu)解,但是在中大規(guī)模問題上與LKH3[42]、Google OR tools[43]、Gurobi[44]、Concorde[45]等專業(yè)組合優(yōu)化求解器的優(yōu)化能力還存在一定差距.

鑒于此,基于DRL 求解組合優(yōu)化問題的另外一類研究是利用DRL 方法改進傳統(tǒng)的精確/近似方法,如利用機器學(xué)習(xí)模型對分支定界法 (Branch and bound) 的節(jié)點選擇和變量選擇策略進行優(yōu)化,Bengio 等[46]已經(jīng)對該類方法進行了詳細的綜述研究,本文不再贅述.除了對精確算法進行改進,近年來興起的另一類方法是基于深度強化學(xué)習(xí)對迭代搜索類算法進行改進,局部搜索/鄰域搜索是求解組合優(yōu)化問題的常用近似方法,在局部搜索過程中,學(xué)者們通常手工設(shè)計各種啟發(fā)式規(guī)則對解進行構(gòu)造和搜索,但是隨著人工智能技術(shù)的發(fā)展,通過神經(jīng)網(wǎng)絡(luò)模型代替手工規(guī)則設(shè)計是未來的發(fā)展趨勢.鑒于此,近幾年部分學(xué)者研究采用深度強化學(xué)習(xí)對解搜索的啟發(fā)式規(guī)則進行學(xué)習(xí)和選擇[47–50],通過學(xué)習(xí)到的規(guī)則進行解的迭代搜索,根據(jù)該思路,文獻[47,50]所提方法在優(yōu)化效果上達到甚至超過了LKH3、Google OR tools 等專業(yè)組合優(yōu)化求解器,文獻[50]在求解速度上也超越了LKH3、Google OR tools 等方法.

基于深度強化學(xué)習(xí)改進的局部搜索方法具有較好的優(yōu)化效果,但其本質(zhì)上仍然是迭代型搜索算法,求解速度仍然遠不及端到端方法;端到端方法具有求解速度快、泛化能力強的優(yōu)勢,但是該類方法的缺陷是解的優(yōu)化效果無法保證,與傳統(tǒng)組合優(yōu)化方法的優(yōu)化效果仍然存在一定差距.目前該兩類方法各具優(yōu)劣,鑒于深度強化學(xué)習(xí)近年來在解決組合優(yōu)化問題上的突出成果,本文主要總結(jié)回顧近些年基于深度強化學(xué)習(xí)去解決組合優(yōu)化問題的相關(guān)理論方法和應(yīng)用研究.

2 基于深度強化學(xué)習(xí)的組合優(yōu)化:基本原理介紹

Pointer network 模型和圖神經(jīng)網(wǎng)絡(luò)模型是基于深度強化學(xué)習(xí)的組合優(yōu)化方法中常用的兩種模型,本節(jié)首先對如何利用上述模型求解組合優(yōu)化問題的基本原理進行介紹,并對廣泛用于訓(xùn)練Pointer network 模型的REINFORCE 強化學(xué)習(xí)算法進行介紹.

2.1 Pointer Network 求解組合優(yōu)化問題

Pointer network 方法可概括為利用神經(jīng)網(wǎng)絡(luò)模型實現(xiàn)序列到序列的映射,其核心思想是利用編碼器(Encoder)對組合優(yōu)化問題的輸入序列進行編碼得到特征向量,再利用解碼器(Decoder) 結(jié)合Attention 計算方法以自回歸(Autoregressive)的方式逐步構(gòu)造解,自回歸即每次選擇一個節(jié)點,并在已選擇節(jié)點的基礎(chǔ)上選擇下一個節(jié)點,直到構(gòu)造得到完整解.

本節(jié)以經(jīng)典指針網(wǎng)絡(luò)模型[31]求解TSP 問題為例,對該方法的原理進行介紹.經(jīng)典指針網(wǎng)絡(luò)模型的編碼器和解碼器均為LSTM (Long short-term memory)循環(huán)神經(jīng)網(wǎng)絡(luò).利用指針網(wǎng)絡(luò)模型構(gòu)造TSP 解的過程如下:

首先將每個城市的二維坐標(biāo)轉(zhuǎn)換成高維的節(jié)點表征向量si,編碼器的LSTM 依次讀入各個城市的si,最終編碼得到一個存儲輸入序列信息的向量Vector,同時LSTM 在計算的過程中可以得到每個城市的隱層狀態(tài)ei,其過程如圖1 所示.

圖1 Pointer network 模型示意圖Fig.1 Schematic diagram of pointer network model

然后解碼器對Vector 進行解碼,過程如圖1 所示.在第一步解碼過程中,即t=0 時,LSTM 讀入Vector,輸出當(dāng)前的隱層狀態(tài)d0,利用Attention 機制根據(jù)d0和編碼器得到的各城市的隱層狀態(tài)e計算選擇各個城市的概率,計算公式見式(2),此時可選擇概率最大的節(jié)點作為第一步選擇的城市;在接下來的解碼過程中,即t=1,2,···時,LSTM讀入上一步LSTM 的隱層輸出和上一步選擇城市的特征向量,輸出當(dāng)前的隱層狀態(tài)dt,根據(jù)dt和各城市的e計算選擇各個城市的概率,其計算公式如下,即Attention 機制:

即利用當(dāng)前的dt值和每個城市e值計算得到第t步選擇各城市的概率,其中W和v均為神經(jīng)網(wǎng)絡(luò)的參數(shù).在每一步解碼過程中,對于每個城市j,均可以根據(jù)式(2)計算得到其值,代表在第t步解碼過程中選擇城市j的概率,此時可以選擇具有最大概率值的節(jié)點添加到解當(dāng)中,按照該方式不斷選擇城市,直至構(gòu)造得到一個完整解.

因此該深度神經(jīng)網(wǎng)絡(luò)模型的輸入是城市的坐標(biāo)序列,輸出是城市的順序,通過對該模型參數(shù)的訓(xùn)練 可以實現(xiàn)問題序列到解序列的準(zhǔn)確映射.

2.2 Pointer Network 的強化學(xué)習(xí)訓(xùn)練方法

對于Pointer network 深度神經(jīng)網(wǎng)絡(luò)模型,可以通過監(jiān)督式訓(xùn)練算法或者強化學(xué)習(xí)算法進行訓(xùn)練,由于監(jiān)督式學(xué)習(xí)方法需要提供大量最優(yōu)路徑的標(biāo)簽數(shù)據(jù)集,實際應(yīng)用較為困難,因此目前研究中通常以強化學(xué)習(xí)算法對模型的W和v等參數(shù)進行訓(xùn)練.

強化學(xué)習(xí)通過試錯機制不斷訓(xùn)練得到最優(yōu)策略,首先需要將組合優(yōu)化問題建模為馬爾科夫過程,其核心要素為狀態(tài)、動作以及反饋,以TSP 問題為例,其問題的狀態(tài)為城市的坐標(biāo)s以及已經(jīng)訪問過的城市,動作為第t步選擇的城市πt,所有動作組成的城市訪問順序π即為組合優(yōu)化問題的解,反饋r是路徑總距離的負數(shù),即最小化路徑長度,策略即為狀態(tài)s到動作π的映射,策略通常為隨機策略,即得到的是選擇城市的概率pθ(π|s),該隨機策略建模為:

策略由神經(jīng)網(wǎng)絡(luò)參數(shù)θ進行參數(shù)化,在馬爾科夫過程中,每一步動作的概率為pθ(πt|s,π1:t?1),即根據(jù)已訪問過的城市π1:t?1和城市坐標(biāo)s計算選擇下一步訪問各個城市的概率,根據(jù)鏈?zhǔn)椒▌t累乘即可以得到城市坐標(biāo)s到城市最終訪問順序π的映射pθ(π|s),該隨機策略可以建模為上節(jié)所述的指針網(wǎng)絡(luò)模型,其參數(shù)為θ.

由于TSP 問題的優(yōu)化目標(biāo)是最小化總的路徑長度L(π),而REINFORCE 也是以總反饋作為參數(shù)更新的標(biāo)準(zhǔn),因此現(xiàn)有的研究中通常采用REINFORCE 強化學(xué)習(xí)算法對策略的參數(shù)θ進行訓(xùn)練優(yōu)化.

REINFORCE 強化學(xué)習(xí)算法又稱基于蒙特卡洛的策略梯度方法,即不斷執(zhí)行動作直到結(jié)束,在一個回合結(jié)束之后計算總反饋,然后根據(jù)總反饋對策略的參數(shù)進行更新.以TSP 問題為例,總反饋即為路徑總長度的負數(shù) ?L(π) .可見REINFORCE 算法天然適用于訓(xùn)練該類問題.REINFORCE 基于以下公式對策略θ進行更新:

根據(jù)鏈?zhǔn)椒▌t,pθ(π|s) 為每步動作選擇概率的累乘,則 l npθ(π |s) 計算為每步動作選擇概率對數(shù)的求和,以該值對參數(shù)θ計算偏導(dǎo)可得梯度值?lnpθ(π |s),(L(π)?b(s)) 決定了梯度下降的方向,b(s)代表策略的平均表現(xiàn)(Baseline),如果當(dāng)前策略的表現(xiàn)比 “平均”好,則對該策略進行正向激勵,反之亦然.有多種方式對b(s) 進行估計,運用較多的方法是新增一個Critic 神經(jīng)網(wǎng)絡(luò)計算b(s),即給定一個TSP 問題s,利用Critic 神經(jīng)網(wǎng)絡(luò)估計該問題解的路徑長度.Critic 網(wǎng)絡(luò)與策略網(wǎng)絡(luò)同步進行訓(xùn)練,以策略網(wǎng)絡(luò)訓(xùn)練過程中產(chǎn)生的 (s,L(π)) 作為訓(xùn)練集對Critic 進行訓(xùn)練.

REINFORCE 算法通過式(4)對θ的梯度進行計算并更新,不斷訓(xùn)練從而得到準(zhǔn)確的pθ(π|s),即實 現(xiàn)組合優(yōu)化問題序列到解序列的準(zhǔn)確映射.

2.3 圖神經(jīng)網(wǎng)絡(luò)方法求解組合優(yōu)化問題

圖神經(jīng)網(wǎng)絡(luò)(Graph neural network,GNN)是近年來提出的能夠有效處理圖結(jié)構(gòu)數(shù)據(jù)的新方法,因此部分學(xué)者研究如何利用圖神經(jīng)網(wǎng)絡(luò)對組合優(yōu)化問題進行建模,其核心思想是根據(jù)每個節(jié)點的原始信息(如城市坐標(biāo))和各個節(jié)點之間的關(guān)系(如城市之間的距離),利用圖神經(jīng)網(wǎng)絡(luò)方法計算得到各個節(jié)點的特征向量,根據(jù)各個節(jié)點的特征向量進行節(jié)點預(yù)測、邊預(yù)測等任務(wù).

一般將圖定義為G=(V,E),V代表節(jié)點的集合,E為邊的集合.圖神經(jīng)網(wǎng)絡(luò)通過不斷學(xué)習(xí)節(jié)點的特征、鄰居節(jié)點的特征、邊的特征,并將其以各種方法進行聚合,從而最終得到各個節(jié)點的特征向量,根據(jù)各個節(jié)點的特征向量完成預(yù)測、分類等任務(wù).以經(jīng)典GNN[51]為例,各個節(jié)點的表征以如下公式更新:

其中代表節(jié)點v的表征向量,N(v) 代表v的鄰居節(jié)點的集合,xv是節(jié)點v的特征,是與v相連的邊的特征,xu是鄰居節(jié)點u的特征,是鄰居節(jié)點u在上一步更新的特征向量.因此該公式根據(jù)節(jié)點v本身的特征、邊的特征以及鄰居節(jié)點的特征對節(jié)點v的表征向量進行更新,從t=0 開始對不斷對進行更新直到收斂,從而得到節(jié)點v的準(zhǔn)確特征向量.

根據(jù)各個節(jié)點的特征向量,可以進行組合優(yōu)化問題的求解,如針對節(jié)點選擇問題(如最小頂點覆蓋問題),可以將圖神經(jīng)網(wǎng)絡(luò)得到的節(jié)點特征向量以一個全連接層神經(jīng)網(wǎng)絡(luò)映射到節(jié)點選擇概率,從而根據(jù)概率進行節(jié)點的選擇;針對邊選擇問題(如TSP 問題),可以以兩個節(jié)點的特征向量作為輸入,以一個全連接層神經(jīng)網(wǎng)絡(luò)映射得到一個選擇概率,即該兩點之間存在邊的概率,從而進行邊選擇,值得注意的是,按照概率進邊的選擇并不一定可以構(gòu)成一個完整的哈密頓回路,因此需要輔以搜索方法進行解的構(gòu)造.

以文獻[37?38]所用的方法為例,模型首先利用G NN計算得到各個節(jié)點的表征,將各個節(jié)點的向量進一步運算得到各個節(jié)點的Q 值.根據(jù)Q 值以迭代的方式構(gòu)造解,即每次選擇Q 值最大的節(jié)點添加到當(dāng)前解當(dāng)中,直到構(gòu)造得到完整解,通常以DQN 強化學(xué)習(xí)方法對該圖神經(jīng)網(wǎng)絡(luò)進行訓(xùn)練,從而得到準(zhǔn)確的Q 值估計.部分文獻[39,41]根據(jù)GNN 得到的節(jié)點特征向量計算節(jié)點/邊選擇概率,隨后以波束搜索、樹搜索的方式根據(jù)選擇概率進行可行解的構(gòu)造.

由于圖神經(jīng)網(wǎng)絡(luò)主要用于計算節(jié)點的特征向量,因此部分學(xué)者[34?35]將圖神經(jīng)網(wǎng)絡(luò)和指針網(wǎng)絡(luò)進行結(jié)合,即用圖神經(jīng)網(wǎng)絡(luò)計算得到的節(jié)點特征向量代替指針網(wǎng)絡(luò)LSTM 編碼器計算得到的各節(jié)點的隱層輸出向量e,仍然采用式(2)的Attention機制計算每一步的節(jié)點選擇概率,以自回歸的方式逐步構(gòu)造得到完整解.

3 基于深度強化學(xué)習(xí)的組合優(yōu)化:理論與方法

目前基于DRL 的組合優(yōu)化方法主要分為基于DRL 的端到端算法和基于DRL 的局部搜索改進算法兩大類,其中端到端算法主要包括基于Pointer network 的端到端方法和基于圖神經(jīng)網(wǎng)絡(luò)的端到端方法兩類,本文主要對以上方法在近年來的研究進展進行綜述介紹,對各類方法代表性算法的原理、優(yōu)化性能、優(yōu)缺點進行對比和介紹,對各類方法未來的研究方向進行了分析,各個算法的總結(jié)如表1.

表1 現(xiàn)有算法模型、訓(xùn)練方法、求解問題、以及優(yōu)化效果比較Table 1 Comparison of model,training method,solving problems and performance with existing algorithms

3.1 基于Pointer Network 端到端方法

3.1.1 方法綜述

Vinyals 等[30]最早在2015 年提出了Pointer network 模型進行組合優(yōu)化問題求解,該文章也開啟了利用深度神經(jīng)網(wǎng)絡(luò)進行組合優(yōu)化問題求解的一系列研究,該模型借鑒機器翻譯領(lǐng)域中的Seq2Seq模型求解組合優(yōu)化問題,即利用基于深度神經(jīng)網(wǎng)絡(luò)的編碼器將組合優(yōu)化問題的輸入序列(如城市坐標(biāo))進行編碼,然后通過解碼器和注意力計算機制(Attention)計算得到各節(jié)點的選擇概率,并以自回歸的方式逐步選擇節(jié)點,直到得到完整解(如城市訪問的順序),該方法的詳細原理見第2 節(jié).作者采用監(jiān)督式學(xué)習(xí)的方法對該模型進行訓(xùn)練,即利用大量 “TSP 城市坐標(biāo)?最優(yōu)路徑”的樣本對該Pointer network 的參數(shù)進行離線訓(xùn)練,利用該訓(xùn)練好的模型,可以求解與訓(xùn)練集具有相同分布特性的任意TSP 問題.相對于傳統(tǒng)的局部搜索或者啟發(fā)式搜索方法,該端到端模型不需要進行迭代搜索,具有泛化能力強、求解速度快的優(yōu)勢,論文實現(xiàn)了對至多50 個城市的小規(guī)模TSP 問題的快速求解.

由于Vinyals 等[30]提出的方法采用監(jiān)督式方式進行訓(xùn)練,導(dǎo)致其得到的解的質(zhì)量永遠不會超過樣本的解的質(zhì)量,并且事先構(gòu)造訓(xùn)練樣本需要耗費大量時間,因此限制了其應(yīng)用于更大規(guī)模的組合優(yōu)化問題.鑒于此,Bello 等[31]采用強化學(xué)習(xí)方法訓(xùn)練Pointer network 模型,他們將每個問題實例視為一個訓(xùn)練樣本,以問題的目標(biāo)函數(shù)作為反饋信號,采用REINFORCE 強化學(xué)習(xí)算法進行訓(xùn)練,并引入Critic 網(wǎng)絡(luò)作為Baseline 以降低訓(xùn)練方差.論文對至多100 個城市的TSP 問題以及200 物品的0?1背包問題對該模型進行了測試,結(jié)果發(fā)現(xiàn)該模型在50 城市TSP 問題上超越了Vinyals 等監(jiān)督式訓(xùn)練得到的模型,并可以在100 城市的TSP 問題上接近最優(yōu)解,在背包問題上達到了最優(yōu)解.

進一步的,Nazari 等[32]將Pointer network拓展至具有動態(tài)特性的VRP 問題,作者將輸入分為兩部分,包括靜態(tài)輸入(顧客位置/坐標(biāo))和動態(tài)輸入(顧客需求),由于考慮到在輸入端改變顧客的順序不會影響問題的求解,因此作者將Encoder 輸入層的LSTM 替換成簡單的一維卷積層,從而可以有效降低計算成本.在仍然采用REINFORCE 強化學(xué)習(xí)算法進行訓(xùn)練的情況下,他們的模型將訓(xùn)練時間降低了60 %,在TSP 問題上與Bello 等的模型[31]取得了幾乎相同的優(yōu)化效果,并且在VRP、隨機VRP 問題上取得了比Clarke-Wright savings和Sweep 經(jīng)典啟發(fā)式搜索算法更好的優(yōu)化效果.

相對于傳統(tǒng)的Seq2Seq 模型,近年來Transformer 模型[52]在自然語言處理領(lǐng)域取得了巨大的成功,Transformer 的Multi-head attention 機制可以使模型更好地提取問題的深層特征,鑒于此,多個最新的研究借鑒了Transformer 模型進行了組合優(yōu)化問題求解的研究.

Deudon 等[33]借鑒Transformer 模型改進了傳統(tǒng)的指針網(wǎng)絡(luò)模型,其編碼層采用了與Transformer 模型編碼層相同的結(jié)構(gòu),即利用Multi-head attention 方法計算得到節(jié)點的特征向量;其解碼層沒有采用LSTM,而是將最近三步的決策進行線性映射得到參考向量,從而降低模型復(fù)雜度,其Attention 計算方式與傳統(tǒng)Pointer network 模型相同,仍然采用經(jīng)典的REINFORCE 方法對該模型進行訓(xùn)練,文章僅對TSP 問題進行了求解,作者首先利用該訓(xùn)練好的神經(jīng)網(wǎng)絡(luò)模型輸出初始解,隨后在該初始解的基礎(chǔ)上進行一個簡單的2OPT 局部搜索,結(jié)果發(fā)現(xiàn)這種方式可以有效提高解的質(zhì)量.

Kool 等[34]在2019 年指出,雖然Deudon 等[33]的模型結(jié)合局部搜索可以提高性能,但是其神經(jīng)網(wǎng)絡(luò)模型本身與傳統(tǒng)的Pointer network 模型相比并沒有顯著的優(yōu)勢,鑒于此,Kool 等借鑒Transformer 模型,提出了一個可以利用Attention 機制求解多種組合優(yōu)化問題的新方法[34],在TSP、Capacitated VRP (CVRP)、OP (Orienteering problem)、PCTSP (The prize collecting TSP)等問題上性能超越了前述介紹的所有Pointer network 模型[30?33],并且高度接近Concorde、LKH3、Gurobi 等專業(yè)求解器得到的最優(yōu)解.該方法的改進主要包括兩方面:1) 與文獻[33]相同,該模型的編碼層采用了和Transformer 模型相同的Multi-head attention 機制,但解碼層和Attention 機制存在很大不同,首先該模型每一步的解碼過程中考慮的是第一步所做的決策和最近兩步的決策,Deudon 等[33]模型Attention 的計算方式仍然和經(jīng)典指針網(wǎng)絡(luò)相同,而該模型采用了Transformer 模型的Self-attention 計算方法,增加了更多計算層以提高模型的表現(xiàn);2) 另外,文章對強化學(xué)習(xí)訓(xùn)練算法進行了改進,前述所有文章均采用REINFORCE 算法結(jié)合Criticbaseline 的方式進行訓(xùn)練,即增加一個Critic 神經(jīng)網(wǎng)絡(luò)來估計b(s) .作者指出同時訓(xùn)練兩個神經(jīng)網(wǎng)絡(luò)是低效的,而且Critic 很難得到b(s) 的準(zhǔn)確估計,因此文章設(shè)計了一種Rollout baseline 來代替Critic 神經(jīng)網(wǎng)絡(luò):即在之前訓(xùn)練過程中得到的所有策略模型里,選擇在測試集中表現(xiàn)最好的模型作為基線策略,并采用貪婪方式進行動作選擇,將利用該基線策略對狀態(tài)s求解得到的目標(biāo)函數(shù)值作為b(s),如果當(dāng)前策略比歷史最優(yōu)策略的表現(xiàn)好,則進行正向激勵,從而對當(dāng)前策略進行評價和參數(shù)更新.實驗證明該訓(xùn)練方法的收斂能力明顯優(yōu)于傳統(tǒng)方法.經(jīng)過以上改進,該方法的優(yōu)化性能超越了之前所有的端到端模型.

進一步的,Ma 等[35]結(jié)合指針網(wǎng)絡(luò)和圖神經(jīng)網(wǎng)絡(luò)設(shè)計了一種圖指針網(wǎng)絡(luò)(Graph pointer network,GPN)用來求解大規(guī)模TSP 問題以及帶時間窗約束的TSP 問題.該模型的編碼器包含兩部分:Point encoder 以及Graph encoder,Point encoder 對城市坐標(biāo)進行線性映射,并輸入到LSTM中得到每個城市的點嵌入,Graph encoder 通過GNN 圖神經(jīng)網(wǎng)絡(luò)對所有城市進行編碼,得到每個城市的圖嵌入.模型根據(jù)圖嵌入和點嵌入,基于Attention 機制計算每一步城市選擇的概率,并引入Vector context 提高模型的泛化能力.文章采用分層強化學(xué)習(xí)方法(Hierarchical RL,HRL)對模型進行訓(xùn)練.在50-TSP 問題上訓(xùn)練得到的模型可以有效求解250,500,750,1000 等規(guī)模的TSP 問題,在大規(guī)模TSP 問題上超越了Kool 等[34]的方法,但是在100以內(nèi)規(guī)模的TSP 問題上仍然劣于文獻[34].文章并對帶時間窗約束的TSP 問題進行了實驗,性能超越了OR-tool 以及蟻群算法,證明了分層強化學(xué)習(xí)訓(xùn)練方法在處理約束問題上的有效性.

3.1.2 總結(jié)

以上為按時間線對各個代表性方法的介紹,Vinyals 等[30]最早提出了求解組合優(yōu)化問題的Pointer network 模型,Bello 等[31]最先提出采用強化學(xué)習(xí)方法對該模型進行訓(xùn)練.目前Kool 等[34]的方法在100 規(guī)模以下的TSP 問題上取得了當(dāng)前業(yè)界最優(yōu)(State-of-the-art,SOA)的優(yōu)化效果,超越了其他基于Ptr-Net 模型的方法[30?33].Ma 等[35]的方法在小規(guī)模TSP 問題上劣于[34],但是在大規(guī)模TSP 問題(250,500,1000)上超越了文獻[34],各方法詳細的性能對比詳見表1.值得注意的是,上述方法在50 規(guī)模以上的TSP 問題上均未達到Concorde、LKH3 等求解器得到的最優(yōu)解.

3.2 基于圖神經(jīng)網(wǎng)絡(luò)的端到端方法

3.2.1 方法綜述

Dai 等[37]在2017 年首先研究了如何采用圖神經(jīng)網(wǎng)絡(luò)對組合優(yōu)化問題進行求解,作者采用structure2vec 圖神經(jīng)網(wǎng)絡(luò)對當(dāng)前解的圖結(jié)構(gòu)進行建模,并根據(jù)圖神經(jīng)網(wǎng)絡(luò)計算剩余可選節(jié)點中各個節(jié)點的Q 值,隨后基于貪婪策略根據(jù)Q 值選擇一個新的節(jié)點添加到當(dāng)前解中,直至得到完整解.作者采用了深度Q 學(xué)習(xí)(Deep Q-learning,DQN)算法對該圖神經(jīng)網(wǎng)絡(luò)的參數(shù)進行訓(xùn)練,以使模型輸出準(zhǔn)確的Q 值估計.文章首先在50～100 節(jié)點的MVC、MAXCUT、TSP 問題上對該模型進行了訓(xùn)練,將訓(xùn)練好的模型在多達1200 個節(jié)點的上述問題上進行了測試,以CPLEX 求得的解作為最優(yōu)解對模型的優(yōu)化能力和求解速度進行了研究,實驗結(jié)果表明該方法在TSP 問題上取得了接近Bello 等[31]方法的效果,在MVC、MAXCUT 問題上得到了接近最優(yōu)解的優(yōu)化效果,且超越了多個基準(zhǔn)算法.

Mittal 等[38]采用了與Dai 等[37]相同的模型架構(gòu)對大型組合優(yōu)化問題進行求解,即結(jié)合圖神經(jīng)網(wǎng)絡(luò)、DQN 以及貪婪策略進行解的構(gòu)造,作者采用了圖卷積神經(jīng)網(wǎng)絡(luò)(Graph convolutional networks,GCN)對圖結(jié)構(gòu)進行建模,在20k 規(guī)模的最大覆蓋問題(MCP)、50k 規(guī)模的MVC 問題上進行了模型測試,實驗發(fā)現(xiàn)該模型在大規(guī)模問題上的表現(xiàn)比Dai 等[37]的模型獲得了41 %的優(yōu)化能力的提升.

Li 等[39]采用圖神經(jīng)網(wǎng)絡(luò)對最小頂點覆蓋問題、最大獨立點集(Maximal independent set,MIS)、極大團(Maximal clique,MC)、適定性問題(Satisfiability)進行了研究,由于所研究問題均為點選擇問題,與TSP 問題不同,對節(jié)點選擇的順序無要求,因此文章沒有采用逐步添加節(jié)點的方式構(gòu)造解,而是使用GCN 圖神經(jīng)網(wǎng)絡(luò)直接輸出所有點選擇概率的估計值,并基于該估計值以引導(dǎo)樹搜索的方式構(gòu)造可行解.為了解決問題可能存在多個最優(yōu)解的情況,文章采用Hindsight loss 方式輸出多個概率分布,在此基礎(chǔ)上進行樹搜索,并采用局部搜索的方式對解進行再處理.文章與Dai 等[37]的模型以及測試問題的多個基準(zhǔn)方法進行了對比,在優(yōu)化效果上均超越了對比算法.

以上方法均為對選擇各個節(jié)點的概率進行估計,文獻[40?41]利用圖神經(jīng)網(wǎng)絡(luò)對選擇各個 “邊”的概率進行估計,以TSP 問題為例,利用圖神經(jīng)網(wǎng)絡(luò)模型輸出一個鄰接矩陣,dij代表兩點之間存在邊的概率,dij值大則節(jié)點i和j大概率相連.隨后根據(jù)各個邊出現(xiàn)概率的估計值,使用波束搜索(Beam search)的方式構(gòu)造最終的可行解.文獻[40?41]均采用監(jiān)督式方法進行訓(xùn)練,即利用LKH3 或Concorde 求解器構(gòu)造大量 “坐標(biāo)?最優(yōu)路徑”的訓(xùn)練數(shù)據(jù),根據(jù)最優(yōu)解的真實鄰接矩陣和圖神經(jīng)網(wǎng)絡(luò)輸出的鄰接矩陣計算交叉熵,以交叉熵為損失函數(shù)訓(xùn)練模型.Nowak 等[40]使用的是經(jīng)典GNN 圖神經(jīng)網(wǎng)絡(luò)模型[51],該模型的優(yōu)化效果沒有超越傳統(tǒng)的啟發(fā)式方法以及指針網(wǎng)絡(luò)模型,Joshi 等[41]采用的是GCN圖神經(jīng)網(wǎng)絡(luò),該模型在20,50,100 規(guī)模TSP問題上的優(yōu)化效果略微超越了Kool 等[34]的方法,接近LKH3、Concorde 等求解器得到的最優(yōu)解,但是該方法的求解時間長于LKH3、Concorde 等方法,在泛化能力上該方法也不及Kool 等[34]的方法.

3.2.2 總結(jié)

指針網(wǎng)絡(luò)模型主要用于求解TSP、VRP 等具有序列特性的組合優(yōu)化問題(即該類問題的解與節(jié)點的順序有關(guān)),由于指針網(wǎng)絡(luò)利用Attention 機制以自回歸的方式對解進行構(gòu)造,因此適用于求解序列組合優(yōu)化問題.而基于圖神經(jīng)網(wǎng)絡(luò)的方法由于得到的是節(jié)點的特征向量,自然地可以計算得到節(jié)點選擇的概率,因此在MVC、MIS 等順序無關(guān)的點選擇問題上多有應(yīng)用,針對TSP 等序列優(yōu)化問題,一類方法是仍然以自回歸的方式逐步選擇節(jié)點[37],另一類方式是根據(jù)節(jié)點的特征向量計算邊選擇的概率,然后利用波束搜索等方法構(gòu)造解[41].

由于TSP 問題是文獻中研究組合優(yōu)化問題的經(jīng)典算例,表2 對上述端到端模型在不同規(guī)模TSP問題上的優(yōu)化性能進行了實驗對比,結(jié)果取自各個文獻中的實驗數(shù)據(jù),各個模型采用TensorFlow 或者Pytorch 深度學(xué)習(xí)工具平臺實現(xiàn),由于文獻[34,41]是各類方法的SOA 模型且均在相同型號的1080Ti-GPU 上進行的實驗,因此對文獻[34,41]的求解時間也進行了對比.

表2 端到端模型在TSP 問題上優(yōu)化性能比較Table 2 Comparison of end-to-end model on TSP

其中Greedy 是采用貪婪策略構(gòu)建TSP 問題的解,即每次選取具有最大選擇概率的城市;2OPT是對模型得到的解進行進一步的2OPT 局部搜索以提高解的質(zhì)量;BS 是采用Beam search 波束搜索的方式根據(jù)邊選擇的概率構(gòu)造解.通過實驗結(jié)果可見Kool 等[34]的方法是當(dāng)前基于Attention 機制的端到端方法的SOA 模型,采用簡單的貪婪策略即可在短時間內(nèi)實現(xiàn)對TSP 問題的高效求解;Joshi等[41]利用圖神經(jīng)網(wǎng)絡(luò)結(jié)合波束搜索對TSP 問題進行求解,其優(yōu)化效果超越了Kool 等[34]的模型,但是該方法耗時過長.

由于圖神經(jīng)網(wǎng)絡(luò)能夠有效處理很多組合優(yōu)化問題的圖結(jié)構(gòu),近年來利用圖神經(jīng)網(wǎng)絡(luò)求解組合優(yōu)化問題的研究呈上升趨勢,但該類方法仍然有很多問題待解決,例如波束搜索通常需要大量搜索時間,并且大多研究仍然采用監(jiān)督式方式進行訓(xùn)練,需要構(gòu)造大量標(biāo)簽樣本,實際應(yīng)用困難.Ma 等[35]將圖卷積神經(jīng)網(wǎng)絡(luò)和指針網(wǎng)絡(luò)相結(jié)合,但是該方法在100規(guī)模的TSP 問題上仍然劣于Kool 等[34]的方法,但是在大規(guī)模TSP 上存在優(yōu)勢,未來如何將指針網(wǎng)絡(luò)的Attention 機制和圖神經(jīng)網(wǎng)絡(luò)相結(jié)合是一個重要的研究點.

3.3 深度強化學(xué)習(xí)改進的局部搜索方法

雖然端到端方法可以通過深度神經(jīng)網(wǎng)絡(luò)模型直接輸出問題的解,實現(xiàn)組合優(yōu)化的快速求解,但是其優(yōu)化效果與LKH3、Google OR tools 等專業(yè)求解器相比仍有一定差距.局部搜索(Local search)是求解組合優(yōu)化問題的經(jīng)典方法,當(dāng)前的局部搜索算法主要是通過人工對搜索的啟發(fā)式規(guī)則進行設(shè)計,以獲得更好的優(yōu)化效果,鑒于近年來深度強化學(xué)習(xí)在在各領(lǐng)域取得的矚目的學(xué)習(xí)能力,學(xué)者們開始研究利用深度強化學(xué)習(xí)方法來自動學(xué)習(xí)局部搜索算法的啟發(fā)式規(guī)則,從而比人工設(shè)計的搜索規(guī)則具有更好的搜索能力.

3.3.1 方法綜述

Chen 等[47]于2019 年提出了一個基于深度強化學(xué)習(xí)的組合優(yōu)化問題搜索模型NeuRewriter,它和局部搜索具有相似的算法流程,即首先隨機構(gòu)造一個可行解,在該初始解的基礎(chǔ)上通過局部搜索不斷提高解的質(zhì)量.相比于傳統(tǒng)算法所采用的人工設(shè)計的啟發(fā)式規(guī)則,作者利用深度強化學(xué)習(xí)方法對局部搜索的策略進行訓(xùn)練,利用學(xué)習(xí)到的策略對搜索過程進行引導(dǎo).其策略由兩部分構(gòu)成:Region-picker 和Rule-picker,以作業(yè)車間調(diào)度問題為例,首先利用Region-picker 選定一個工序,其次利用Rulepicker 對該工序的操作策略進行決策,如與另一個工序進行調(diào)換.文章利用Actor-critic 方法對Region-picker 和Rule-picker 策略進行了訓(xùn)練,其優(yōu)化效果在作業(yè)車間調(diào)度問題上超越了DeepRM和Google OR-tools 求解器,在VRP 問題上超越了Google OR-tools 求解器.

Yolcu 等[48]采用深度強化學(xué)習(xí)改進的局部搜索方法對適定性問題(Satisfiability)進行了研究,仍然采用局部搜索的求解框架,利用深度強化學(xué)習(xí)對局部搜索中變量選擇算子進行學(xué)習(xí),作者采用圖神經(jīng)網(wǎng)絡(luò)對變量選擇的策略進行參數(shù)化,利用REINFORCE 算法更新圖神經(jīng)網(wǎng)絡(luò)的參數(shù),實驗顯示相對于傳統(tǒng)的啟發(fā)式算法,該方法可以在更少的步數(shù)內(nèi)找到最優(yōu)解,但是運行時間卻遠長于傳統(tǒng)算法.

Gao 等[49]基于大規(guī)模鄰域搜索框架對組合優(yōu)化問題進行求解,作者利用深度強化學(xué)習(xí)方法對大規(guī)模鄰域搜索的Destroy 和Repair 算子進行學(xué)習(xí),采用圖注意力神經(jīng)網(wǎng)絡(luò)(Graph attention network)對問題特征進行編碼,并采用基于循環(huán)神經(jīng)網(wǎng)絡(luò)的解碼器輸出Destroy 和Repair 算子.具體的,Destroy 算子是從當(dāng)前解中選擇多個節(jié)點,并將其從當(dāng)前解中移除,Repair 算子是將移除的節(jié)點以一定的順序重新插入到當(dāng)前解中,因此該模型對Destroy 算子的點集選擇策略和Repair 算子的排序策略進行學(xué)習(xí).文章采用 Proximal policy optimization (PPO)算法對模型進行訓(xùn)練,并用來解決CVRP、帶時間窗的CVRP 等問題,實驗表明該方法在100 節(jié)點的CVRP 問題上優(yōu)化效果超越了Kool 等[34]的方法,并在400 節(jié)點的大規(guī)模CVRP問題上具有比傳統(tǒng)啟發(fā)式算法更快的收斂性能,在優(yōu)化能力上接近但未達到最優(yōu)解,但本文并沒有提供求解時間對比.

Lu 等[50]于2020 年提出了一種Learn to improve (LSI)組合優(yōu)化問題求解方法,該方法不只在優(yōu)化效果上超越了LKH3、Google OR-tools 等組合優(yōu)化求解器,其求解速度也超越了上述專業(yè)求解器.作者首先對LSI 框架進行設(shè)計,算法總體流程仍然采用局部搜索的方式,在每一步搜索過程中,算法決定是繼續(xù)提升當(dāng)前解還是對當(dāng)前解進行擾動,因此算法包括兩個算子:提升算子和擾動算子,作者采用了9 種不同的提升算子作為算子庫,采用深度強化學(xué)習(xí)訓(xùn)練提升算子的選擇策略,每次迭代,算法根據(jù)問題特征和當(dāng)前的解,利用學(xué)習(xí)到的策略從算子庫中選擇提升算子,從而不斷提升當(dāng)前解的質(zhì)量,如果達到局部最優(yōu),算法對當(dāng)前解進行擾動.論文通過實驗證明該方法在20-,50-,100-CVRP 問題上超越了當(dāng)前State-of-the-art 的LKH3 求解器,并且其求解速度也遠超LKH3 算法.

3.3.2 總結(jié)

深度強化學(xué)習(xí)改進的局部搜索方法是自2019 年以來最新提出的一類組合優(yōu)化方法,主要用于求解VRP 等路徑優(yōu)化問題,表3 對該類方法以及端到端模型在求解不同規(guī)模VRP 問題上的優(yōu)化能力進行了比較,結(jié)果取自各個文獻的實驗數(shù)據(jù).各算法均在GPU 上運行(各算法使用不同型號GPU,但運算時間不存在較大差距),均采用Pytorch 深度學(xué)習(xí)工具實現(xiàn).

表3 多個模型在VRP 問題上優(yōu)化性能比較Table 3 Comparison of models on VRP

從實驗對比可以看出,深度強化學(xué)習(xí)改進的局部搜索方法在優(yōu)化能力上優(yōu)于當(dāng)前性能最好的端到端模型,Lu 等[50]模型的優(yōu)化性能甚至超越了LKH3 專業(yè)組合優(yōu)化求解器,且算法運行時間數(shù)倍少于LKH3;但是該方法的運算時間仍然遠長于端到端模型,Kool 等[34]的模型采用簡單的貪婪策略可見在數(shù)秒內(nèi)運算得到接近最優(yōu)解的方案,具有快速在線求解的優(yōu)勢.可見兩類不同的方法具有不同的優(yōu)勢,需要根據(jù)不同應(yīng)用場景和問題規(guī)模進行選擇.

3.4 基于深度學(xué)習(xí)的多目標(biāo)組合優(yōu)化方法

目前絕大多數(shù)基于深度強化學(xué)習(xí)解決傳統(tǒng)優(yōu)化問題的研究都是針對單目標(biāo)優(yōu)化問題,而使用深度強化學(xué)習(xí)方法解決傳統(tǒng)多目標(biāo)優(yōu)化問題的研究很少,值得注意的是,“多目標(biāo)(深度)強化學(xué)習(xí)”的概念[53?54]很早就被提出并且存在很多文獻對其進行研究,但是其研究的是如何設(shè)計具有多個獎勵信號的強化學(xué)習(xí)算法,例如如何利用強化學(xué)習(xí)算法控制潛艇尋找目標(biāo)[53],其中需要最大化尋找到目標(biāo)的數(shù)量和最小化尋找的時間,其研究的主體是多目標(biāo)強化學(xué)習(xí)算法,而不是如何利用強化學(xué)習(xí)方法解決傳統(tǒng)的多目標(biāo)優(yōu)化問題.

針對該問題,Li 等[36]最近提出了一個簡單卻有效的框架DRL-MOA,嘗試使用深度強化學(xué)習(xí)方法對傳統(tǒng)的多目標(biāo)優(yōu)化問題進行求解,該方法在2 個、3 個和5 個目標(biāo)的多目標(biāo)TSP (MOTSP)問題上取得了顯著優(yōu)于傳統(tǒng)MOEA/D 和NSGA-II 多目標(biāo)優(yōu)化算法的優(yōu)化效果,且優(yōu)于多目標(biāo)局部搜索算法MOGLS,并且隨著問題規(guī)模的擴大(如200-、500-MOTSP 問題),該方法的優(yōu)化效果顯著超越了傳統(tǒng)優(yōu)化算法,且具有數(shù)倍于傳統(tǒng)算法的求解速度.該方法借鑒Pointer network 模型采用端到端的求解框架,采用基于分解的思想將多目標(biāo)問題分解為多個子問題,并將每個子問題建模為Pointer network 模型,多個子模型利用基于鄰居的參數(shù)遷移的方法進行協(xié)同訓(xùn)練,文章利用隨機生成的40 城市TSP 問題進行模型訓(xùn)練,一旦模型訓(xùn)練好,可以求解任意生成的100、200、500 城市的TSP 問題,而不用重新訓(xùn)練模型,具有較強的泛化能力.得益于端到端的求解框架,求解速度快以及泛化能力強是該方法的優(yōu)勢,且該方法的思想很容易遷移到其他多目標(biāo)優(yōu)化問題的求解中,但是文章僅對多目標(biāo)TSP 問題進行了實驗研究,對其他多目標(biāo)組合優(yōu)化問題以及更為普遍的多目標(biāo)連續(xù)優(yōu)化問題沒有進行研究,并且由于該類方法神經(jīng)網(wǎng)絡(luò)模型個數(shù)與權(quán)重個數(shù)成正比,如何提高該類方法的訓(xùn)練效率也是未來的研究方向.

3.5 基于深度學(xué)習(xí)的組合優(yōu)化方法總結(jié)

從上述方法可見,端到端模型具有求解速度遠超傳統(tǒng)優(yōu)化算法的優(yōu)勢,也是近年來研究較多的一類方法,模型一旦訓(xùn)練完成,可以對任意同類型的問題進行求解,具有很強的泛化能力,但是很難保證解的優(yōu)化效果,尤其隨著問題規(guī)模的擴大,其優(yōu)化能力與傳統(tǒng)優(yōu)化算法之間的差距會不斷擴大.深度強化學(xué)習(xí)改進的局部搜索方法是近年來興起的另外一類方法,其本質(zhì)上仍然是啟發(fā)式搜索算法,但是沒有采用人工設(shè)計的搜索規(guī)則,而是利用深度強化學(xué)習(xí)算法對搜索規(guī)則進行學(xué)習(xí),因此該方法具有較強的優(yōu)化能力,其優(yōu)化效果可以超越傳統(tǒng)的優(yōu)化算法,但是其求解時間仍然遠慢于端到端模型,因此決策者需要根據(jù)優(yōu)化效果和求解速度之間的權(quán)衡來選擇不同的方法.

由于端到端模型可以采用監(jiān)督式和強化學(xué)習(xí)方法進行訓(xùn)練,文獻[55?56]對監(jiān)督式和強化學(xué)習(xí)訓(xùn)練方法進行了詳細的實驗對比和分析,論文發(fā)現(xiàn)強化學(xué)習(xí)訓(xùn)練方法收斂比監(jiān)督式訓(xùn)練方法慢,但強化學(xué)習(xí)得到的模型具有更強的泛化能力.

由于存在多種組合優(yōu)化問題,不同文獻的研究重點不同,導(dǎo)致存在多種不同的模型方法.例如文獻[32,34,50]等偏重于解決TSP、VRP 等路徑優(yōu)化問題,其中節(jié)點選擇的順序?qū)Y(jié)果有很大影響,因此基于Attention 機制的方法在此類問題上有較好的效果.并且對于復(fù)雜的路徑選擇問題,如CVRP問題,目前的研究均采用Attention 機制,而沒有單純采用圖神經(jīng)網(wǎng)絡(luò)的方法,可見Attention 機制在處理具有序列特性的組合優(yōu)化問題上具有較好的性能;而文獻[37,39,48]等偏重于解決MVC、MAXCUT 等問題,即點選擇問題,該類問題對節(jié)點的順序沒有要求,此種情況下圖神經(jīng)網(wǎng)絡(luò)在該類問題上應(yīng)用較多;同時,結(jié)合圖神經(jīng)網(wǎng)絡(luò)和Attention 機制的方法在TSP 等路徑優(yōu)化問題上也取得了較好的效果[35,49].

鑒于此,為了更清晰地對求解不同類型組合優(yōu)化問題的不同模型方法進行比較,本節(jié)對解決不同組合優(yōu)化問題的不同文獻進行統(tǒng)計,并對各個研究所采用的模型進行歸納,結(jié)果如表4 所示,其中部分文獻是2020 年剛提出的新方法,在模型和實驗結(jié)果上都有突出的特點和表現(xiàn)并且被多次引用,但是僅發(fā)表了預(yù)印版(在審)而暫未通過同行評審,因此上文并沒有對這些文獻進行詳細介紹,僅列出供讀者查閱并以星號(*)標(biāo)注.

由表4 可見,近年來圖神經(jīng)網(wǎng)絡(luò)結(jié)合各種搜索方法(波束搜索、樹搜索)在各種組合優(yōu)化問題上得到了廣泛的應(yīng)用,其主要應(yīng)用于沒有序列特性的組合優(yōu)化問題,如MVC、MAXCUT 等.而基于Attention 機制的指針網(wǎng)絡(luò)方法是解決具有序列決策特性組合優(yōu)化問題的主要方法,如TSP、VRP 等問題.

表4 不同組合優(yōu)化問題求解算法統(tǒng)計與比較Table 4 Summary and comparison of algorithms on different combinatorial optimization problems

針對基于指針網(wǎng)絡(luò)的端到端模型,由于其核心是借鑒機器翻譯領(lǐng)域的Attention 機制,因此追蹤當(dāng)前自然語言處理領(lǐng)域的前沿成果是提升指針網(wǎng)絡(luò)模型性能的重要思路,如Kool 等[34]借鑒了Transformer 模型中的Multi-head attention 機制,使得其模型在組合優(yōu)化問題上取得了當(dāng)前業(yè)界最優(yōu)的效果.同時,如何改進編碼器和解碼器的神經(jīng)網(wǎng)絡(luò)模型結(jié)構(gòu)也是提高模型性能的一個重要研究方向.

針對基于圖神經(jīng)網(wǎng)絡(luò)的端到端模型,由于圖神經(jīng)網(wǎng)絡(luò)是當(dāng)前人工智能領(lǐng)域的研究熱點,如何從眾多模型中選擇改進適合求解不同組合優(yōu)化問題的圖神經(jīng)網(wǎng)絡(luò)模型是一個重要的研究方向,同時波束搜索、樹搜索耗時長也是制約該類方法的一個問題,如何高效地將圖神經(jīng)網(wǎng)絡(luò)和Attention 機制相結(jié)合是未來可行的研究思路.

針對深度強化學(xué)習(xí)改進的局部搜索方法,目前的研究仍然處于起步階段,但已經(jīng)取得了超越傳統(tǒng)組合優(yōu)化求解器的成果,如何提高解搜索的效率以及擴大啟發(fā)式算子的搜索空間是未來提升算法性能的重要研究方向.

4 深度強化學(xué)習(xí)解決組合優(yōu)化問題:應(yīng)用綜述

組合優(yōu)化問題廣泛存在于工業(yè)、制造、通信、交通等各個領(lǐng)域,隨著在各個領(lǐng)域中實際問題規(guī)模的不斷擴大以及對算法求解時間的嚴格要求,傳統(tǒng)運籌優(yōu)化方法很難在可接受時間內(nèi)實現(xiàn)問題的在線求解,基于深度強化學(xué)習(xí)的組合優(yōu)化方法作為近年來提出的一類前沿方法,具有求解速度快、泛化能力強的優(yōu)勢,本節(jié)對近年來該類方法的應(yīng)用研究進行綜述.首先對應(yīng)用較多的網(wǎng)絡(luò)與通信領(lǐng)域的研究進行綜述,其次對交通、電網(wǎng)等其他領(lǐng)域的應(yīng)用研究進行介紹.

4.1 網(wǎng)絡(luò)與通信領(lǐng)域

由于網(wǎng)絡(luò)與通信領(lǐng)域存在多種典型的組合優(yōu)化問題,如資源分配、路由拓撲優(yōu)化等,因此基于深度強化學(xué)習(xí)的組合優(yōu)化在網(wǎng)絡(luò)與通信領(lǐng)域存在較多的應(yīng)用.

1)資源分配

在網(wǎng)絡(luò)與通信領(lǐng)域,資源分配問題是指將有限的CPU、內(nèi)存、帶寬等資源分配給不同的用戶或任務(wù)需求,如虛擬網(wǎng)絡(luò)功能部署問題、網(wǎng)絡(luò)資源切片問題等.

網(wǎng)絡(luò)功能虛擬化技術(shù)(Network function virtualization,NFV)通過標(biāo)準(zhǔn)的IT 虛擬化技術(shù)將網(wǎng)絡(luò)功能虛擬化,是當(dāng)前網(wǎng)絡(luò)通信的前沿技術(shù),虛擬網(wǎng)絡(luò)功能(Virtual network function,VNF) 是NFV 架構(gòu)中的虛擬網(wǎng)絡(luò)功能單元,VNF 的放置與部署問題是當(dāng)前網(wǎng)絡(luò)通信領(lǐng)域研究較多的一類問題,鑒于傳統(tǒng)的VNF 部署方法通常需要數(shù)十分鐘才可以完成優(yōu)化過程,近年來涌現(xiàn)出利用深度強化學(xué)習(xí)實現(xiàn)VNF 智能在線部署的多個研究.文獻[64]將VNF 部署問題建模為混合整數(shù)規(guī)劃問題,并將其轉(zhuǎn)化為馬爾科夫過程,在滿足不同的端到端時延需求的前提下,以最小化總?cè)蝿?wù)時間為目標(biāo),文章以DQN 強化學(xué)習(xí)方法對模型進行訓(xùn)練,從而實現(xiàn)VNF 在線部署,該方法在收斂性能以及優(yōu)化能力上優(yōu)于多個基準(zhǔn)方法.文獻[65?66]基于GNN 圖神經(jīng)網(wǎng)絡(luò)對VNF 網(wǎng)元資源需求進行預(yù)測,以提高VNF部署的準(zhǔn)確性.文獻[67]考慮VNF 網(wǎng)元資源分配的特性,指出傳統(tǒng)強化學(xué)習(xí)方法很難處理VNF 部署問題中的大規(guī)模離散決策空間探索問題,因此文章對DDPG (Deep deterministic policy gradient algorithm)強化學(xué)習(xí)算法進行了改進,提出了增強DDPG 算法,該方法的優(yōu)化能力超過了傳統(tǒng)DDPG方法以及整數(shù)規(guī)劃方法.文獻[68]采用Ptr-Net 的Encoder-decoder 架構(gòu)對VNF 部署問題進行了求解,其Encoder 和Decoder 均采用LSTM模型,文章利用拉格朗日松弛將該約束問題轉(zhuǎn)化為無約束問題,并采用基于蒙特卡洛的策略梯度方法對模型進行訓(xùn)練.通過與約束問題求解器Gecode和傳統(tǒng)啟發(fā)式方法對比,實驗顯示該方法的優(yōu)化性能在大多數(shù)小規(guī)模和大規(guī)模問題上均優(yōu)于對比算法.

文獻[69]基于深度強化學(xué)習(xí)對無線邊緣計算網(wǎng)絡(luò)的切片策略進行了研究,文章設(shè)計了一種D-DRL分布式強化學(xué)習(xí)框架,采用一個中心協(xié)調(diào)器和多個分布式智能體對切片策略進行協(xié)同優(yōu)化,并采用DDPG 強化學(xué)習(xí)算法對模型進行訓(xùn)練.傳統(tǒng)網(wǎng)絡(luò)切片方法通常會受到不確定的資源需求、不確定的服務(wù)時間等不確定性因素影響,文獻[70]將網(wǎng)絡(luò)切片過程建模為半馬爾科夫過程,采用Deep double Qlearning 方法對切片策略進行優(yōu)化,以克服DQN收斂慢的缺點,模型在訓(xùn)練時可以充分地對大規(guī)模決策空間進行探索,從而能夠在在線優(yōu)化時有效處理不確定的狀態(tài)信息,進行實時在線響應(yīng),將不同的網(wǎng)絡(luò)資源分配給不同種類的用戶,實驗證明該方法的長期優(yōu)化能力相比于當(dāng)前最優(yōu)的方法提高40 %,且在線優(yōu)化耗時可以忽略不計.

文獻[71]對霧計算中的復(fù)雜資源分配問題進行了研究,將霧計算建模為馬爾科夫過程,以在既定時延內(nèi)滿足用戶最大需求為目標(biāo),利用DQN 強化學(xué)習(xí)方法對霧計算中的資源分配進行在線求解,可以得到接近最優(yōu)解的優(yōu)化效果,并優(yōu)于傳統(tǒng)的啟發(fā)式資源分配方法.

2)拓撲與路由優(yōu)化

在通信網(wǎng)絡(luò)或者無線傳感網(wǎng)絡(luò)中,通常需要對路由策略、傳感器的連接拓撲進行優(yōu)化,以降低通信時延和成本.

文獻[72]基于深度強化學(xué)習(xí)方法對無線通信網(wǎng)絡(luò)的路由策略進行研究,文章采用圖神經(jīng)網(wǎng)絡(luò)對通信網(wǎng)絡(luò)的圖結(jié)構(gòu)進行建模,對當(dāng)前網(wǎng)絡(luò)信息進行編碼,并輸出選擇不同節(jié)點的Q 值,采用DQN 算法對圖神經(jīng)網(wǎng)絡(luò)進行訓(xùn)練.實驗顯示該方法具有很強的泛化能力,一旦模型訓(xùn)練完成,能夠?qū)θ我饨Y(jié)構(gòu)的網(wǎng)絡(luò)進行路由策略的在線優(yōu)化.文獻[73]基于DRL 和蒙特卡洛樹搜索提出了一種DRL-TC 方法,利用該方法對無線自組織傳感網(wǎng)絡(luò)的通信拓撲連接進行優(yōu)化,文章采用深度神經(jīng)網(wǎng)絡(luò)對問題進行建模,利用強化學(xué)習(xí)方法對其進行訓(xùn)練,利用該神經(jīng)網(wǎng)絡(luò)的輸出指導(dǎo)蒙特卡洛樹搜索的過程,從而得到最優(yōu)的通信拓撲連接.文獻[74]對無線傳感網(wǎng)絡(luò)中移動代理的路由策略進行了研究,采用Ptr-Net模型輸出移動代理的最優(yōu)路徑,文章利用Actorcritic 算法對其進行訓(xùn)練,實驗顯示該方法能夠有效地對無線傳感網(wǎng)絡(luò)的流量進行控制,降低能量消耗.文獻[75]基于深度強化學(xué)習(xí)方法對D2D 無線通信網(wǎng)絡(luò)的鏈路選擇策略進行優(yōu)化,文章采用Ptr-Net 模型對鏈路進行選擇,其Encoder 和Decoder 均使用LSTM模型,并利用策略梯度方法對模型進行訓(xùn)練,實驗證明該方法能夠在更短計算時間內(nèi)達到和傳統(tǒng)方法相似的優(yōu)化性能.

3)計算遷移

計算遷移(Computation offloading)是通過將部分計算任務(wù)從本地遷移到遠程設(shè)備以解決移動終端資源受限問題的一個有效途徑,由于無線信道狀況變化較快,需要快速進行策略相應(yīng),而傳統(tǒng)的數(shù)值優(yōu)化方法很難實現(xiàn)在線快速優(yōu)化,鑒于此,多個文獻[76–78]采用深度強化學(xué)習(xí)實現(xiàn)計算遷移策略的在線優(yōu)化.文獻[76]提出了一種基于深度強化學(xué)習(xí)的DROO 計算遷移框架,基于DQN 算法對移動邊緣計算網(wǎng)絡(luò)對在線計算遷移策略進行優(yōu)化,在優(yōu)化時間和優(yōu)化效果上優(yōu)于傳統(tǒng)整數(shù)規(guī)劃算法.文獻[77]基于深度強化學(xué)習(xí)方法對多址邊緣計算的計算遷移策略進行了研究,文章采用Seq2Seq 模型對策略進行建模,利用PPO 算法對模型進行訓(xùn)練,在不同任務(wù)數(shù)量的情況下均接近最優(yōu)解,且超越了多個基準(zhǔn)方法.文獻[78]將移動邊緣計算網(wǎng)絡(luò)中的計算遷移問題轉(zhuǎn)換成了多維多背包問題,利用多指針網(wǎng)絡(luò)(MPtr-Net)對策略進行建模,并采用REINFORCE 強化學(xué)習(xí)方法對該指針網(wǎng)絡(luò)進行訓(xùn)練,最后采用波束搜索得到最終的方案.實驗表明該方法的優(yōu)化性能較基準(zhǔn)啟發(fā)式算法提高了25 %,且運行時間優(yōu)于ORtool.

4.2 其他領(lǐng)域

1)交通領(lǐng)域

在貨物配送領(lǐng)域,隨著電商規(guī)模的不斷擴大,當(dāng)前的配送路徑優(yōu)化方法很難做到城際交通規(guī)劃系統(tǒng)的在線實時響應(yīng),鑒于此,文獻[79]利用深度強化學(xué)習(xí)方實現(xiàn)了配送路徑的在線快速生成,文章設(shè)計了一種基于Struct2Vec 圖神經(jīng)網(wǎng)絡(luò)和Ptr-Net注意力網(wǎng)絡(luò)的模型,采用圖注意力機制對路徑生成的過程進行建模,并采用策略梯度方法對該模型進行訓(xùn)練,文章基于德國科隆市的城市交通路網(wǎng)對該方法進行了測試,實驗顯示該方法可以在可接受時間內(nèi)實現(xiàn)配送路徑的快速生成,且在相同求解時間內(nèi)優(yōu)于傳統(tǒng)的整數(shù)規(guī)劃方法和啟發(fā)式方法.在網(wǎng)約車領(lǐng)域,訂單的分配和司機載客區(qū)域的分配是一個復(fù)雜的組合優(yōu)化問題,傳統(tǒng)運籌優(yōu)化方法很難處理大規(guī)模訂單的在線調(diào)度和響應(yīng),文獻[80]利用深度強化學(xué)習(xí)方法對該問題進行了研究,文章參考Attention 機制對深度神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)進行了設(shè)計,并分別研究了DQN 和PPO 訓(xùn)練算法在不同場景下的表現(xiàn),實驗表明DQN 和PPO 訓(xùn)練方法在不同的客流需求場景各具優(yōu)勢,且能夠?qū)崿F(xiàn)在線實時優(yōu)化.文獻[81]采用深度強化學(xué)習(xí)方法對交通信號燈控制策略進行優(yōu)化,以信號燈持續(xù)時間作為優(yōu)化變量,結(jié)合決策網(wǎng)絡(luò)、目標(biāo)網(wǎng)絡(luò)、Double-Q-Learning 等深度強化學(xué)習(xí)方法對模型進行訓(xùn)練,取得了比傳統(tǒng)交通信號燈控制方法更好的效果.

2)生產(chǎn)制造領(lǐng)域

在生產(chǎn)制造領(lǐng)域存在大量組合優(yōu)化問題,近年來基于深度強化學(xué)習(xí)的組合優(yōu)化模型在生產(chǎn)制造領(lǐng)域也多有應(yīng)用.文獻[47,82]對經(jīng)典的車間工作流調(diào)度問題進行了研究,采用深度強化學(xué)習(xí)方法對局部搜索的解搜索規(guī)則進行學(xué)習(xí),利用Actor-critic 深度強化學(xué)習(xí)算法對搜索規(guī)則進行優(yōu)化學(xué)習(xí),實驗表明該兩個模型在優(yōu)化性能上均超越了傳統(tǒng)啟發(fā)式局部搜索方法;置換車間工作流調(diào)度問題是對是對流水車間調(diào)度問題的進一步約束,文獻[83?84]均采用指針網(wǎng)絡(luò)模型對該問題進行了研究,文獻[83]采用了經(jīng)典的指針網(wǎng)絡(luò)模型,并利用CPLEX 求解器構(gòu)造大量樣本對該模型進行監(jiān)督式訓(xùn)練,實驗結(jié)果表明Attention 機制能夠有效提高解的質(zhì)量,文獻[84]采用了Multi-head attention 機制進行建模,并利用REINFORCE 強化學(xué)習(xí)算法對模型進行訓(xùn)練,實驗表明該模型超越了多個啟發(fā)式搜索算法和傳統(tǒng)的指針網(wǎng)絡(luò)模型.

3)高性能計算領(lǐng)域

人工智能模型的訓(xùn)練是一個耗時極長的任務(wù),合理地對計算資源進行規(guī)劃和調(diào)度能夠有效提高計算效率,隨著神經(jīng)網(wǎng)絡(luò)規(guī)模的不斷擴大,多CPU 和多GPU 混合訓(xùn)練是當(dāng)前通用的一個方法,將神經(jīng)網(wǎng)絡(luò)模型的不同計算功能部署在不同的計算設(shè)備上對訓(xùn)練速度有很大的影響,該問題是一個典型的組合優(yōu)化問題,文獻[85?86]利用深度強化學(xué)習(xí)方法對該部署問題進行了研究,文獻[85]采用了經(jīng)典的Ptr-Net 模型架構(gòu)對問題進行建模,并利用策略梯度方法進行分布式訓(xùn)練,實驗證明該方法可以將Tensorflow 計算圖的訓(xùn)練速度提高20 %以上.文獻[86]在此基礎(chǔ)上提出了一個分層模型,首先Grouper 層將計算圖中的不同計算部分進行分組,然后 Placer層根據(jù)Grouper 層得到的分組結(jié)果輸出部署方案,Placer 層仍采用Encoder-decoder 模型,實驗證明該方法可以將Tensorflow 計算圖的訓(xùn)練速度提高60 %.

4)微電網(wǎng)能量管理領(lǐng)域

在微電網(wǎng)能量管理問題中,用電、儲能等設(shè)備的啟?？刂剖堑湫偷碾x散優(yōu)化問題,部分學(xué)者采用不同的深度強化學(xué)習(xí)方法對該問題進行了研究.Francois-Lavet等[87]使用深度強化學(xué)習(xí)方法對微電網(wǎng)能量管理問題進行了研究,文章考慮了一個包含短期儲能、長期儲能以及光伏發(fā)電的微電網(wǎng)系統(tǒng),將微電網(wǎng)能量管理問題建模為馬爾科夫過程,以最小化用電費用為目標(biāo),以充電、放電、無操作作為動作空間,以卷積神經(jīng)網(wǎng)絡(luò)對該問題進行建模,采用DQN 算法進行訓(xùn)練,實驗發(fā)現(xiàn)該訓(xùn)練好的模型能夠有效地提高能源利用率,降低用電費用,但是文章沒有和基準(zhǔn)方法進行對比.文獻[88]構(gòu)建了一個包含光伏發(fā)電、儲氫裝置、蓄電池的孤島型復(fù)合能源系統(tǒng),并將復(fù)合儲能系統(tǒng)的協(xié)調(diào)控制轉(zhuǎn)化為序列決策問題,文章仍然采用卷積神經(jīng)網(wǎng)絡(luò)對問題進行建模,采用Double DQN 深度強化學(xué)習(xí)方法對該系統(tǒng)的協(xié)調(diào)控制策略進行優(yōu)化,實驗表明該方法與DQN 算法相比具有更快的收斂速度.文獻[89]利用Double Q-learning 深度強化學(xué)習(xí)方法對空調(diào)和通風(fēng)系統(tǒng)的溫度調(diào)節(jié)、啟停等策略進行優(yōu)化,從而在保證良好的溫度舒適度和空氣質(zhì)量的前提下達到最低的能量消耗,以實現(xiàn)最優(yōu)能量管理優(yōu)化,文章在實際環(huán)境中對該模型進行測試,結(jié)果發(fā)現(xiàn)該方法與傳統(tǒng)的溫度調(diào)節(jié)方法相比更具有優(yōu)越性.文獻[90]利用深度強化學(xué)習(xí)算法對對樓宇的智能能量管理問題進行了研究,對樓宇中空調(diào)、電視、電動汽車等用電設(shè)備的啟停進行控制,文章利用深度神經(jīng)網(wǎng)絡(luò)對該問題進行建模,分別研究了DQN 和DPG (Deep policy gradient)訓(xùn)練算法在該問題上的表現(xiàn),實驗表明DPG 策略梯度方法能夠更加有效地實現(xiàn)削峰填谷和降低能源消耗.

由于基于深度強化學(xué)習(xí)的組合優(yōu)化方法是近年來剛提出的一類方法,其應(yīng)用研究較少.近年來的應(yīng)用研究對Ptr-Net、圖神經(jīng)網(wǎng)絡(luò)模型以及其他深度神經(jīng)網(wǎng)絡(luò)模型均有應(yīng)用,對DQN、Double DQN、Actor-critic、PPO、DDPG 等先進的深度強化學(xué)習(xí)方法也均有涉及.但由于各個應(yīng)用研究都是針對各自不同的實際問題進行建模,其模型的結(jié)構(gòu)、狀態(tài)空間、動作空間都有較大區(qū)別,很難在文獻之間進行橫向比較,且大多數(shù)文獻的實驗對比較為匱乏,雖能體現(xiàn)出算法的優(yōu)化效果,但對算法的優(yōu)化性能分析較少,只有少量文獻對算法結(jié)果與最優(yōu)解之間的差距進行了分析.目前的應(yīng)用研究大多應(yīng)用在傳統(tǒng)算法很難進行在線優(yōu)化的背景下,基于深度強化學(xué)習(xí)的優(yōu)化算法具有求解速度快、泛化能力強的優(yōu)勢,由于工業(yè)、制造、交通等領(lǐng)域存在大量組合優(yōu)化問題,因此該類方法具有廣泛的應(yīng)用背景.

5 結(jié)論與展望

實際生產(chǎn)生活中存在很多組合優(yōu)化問題,已有大量研究對各種組合優(yōu)化方法進行了研究,但是面對大規(guī)模復(fù)雜組合優(yōu)化難題時,現(xiàn)有方法很難在可接受時間內(nèi)找到滿意解,難以滿足很多問題在線優(yōu)化的需求.而近年來基于深度強化學(xué)習(xí)的組合優(yōu)化方法在多種組合優(yōu)化問題上展示出了良好性能,具有較強的泛化性能和快速的求解速度,為組合優(yōu)化問題的在線求解提供了新的思路.因此本文從理論方法和應(yīng)用研究兩個層面綜述了近些年關(guān)于基于深度強化學(xué)習(xí)組合優(yōu)化方法的相關(guān)研究,以期為未來該領(lǐng)域的研究提供較好的支撐.

現(xiàn)有研究已經(jīng)顯示出深度強化學(xué)習(xí)在解決組合優(yōu)化問題方面的優(yōu)勢,但是相關(guān)研究還比較淺顯,當(dāng)前的研究尚屬于起步階段,仍然存在一系列問題.要構(gòu)建基于DRL 解決組合優(yōu)化問題的理論方法體系,還需從如下幾個方面開展研究:

1)在模型方面.在當(dāng)前的研究中,直接采用深度神經(jīng)網(wǎng)絡(luò)模型輸出的解通常較差,大部分文獻都需要進一步通過波束搜索、局部搜索、采樣策略等方式進一步提升解的質(zhì)量,這說明當(dāng)前的模型仍然有很大的提升空間,未來需要進一步對求解組合優(yōu)化問題的深度神經(jīng)網(wǎng)絡(luò)模型進行研究,如何有效結(jié)合圖神經(jīng)網(wǎng)絡(luò)和Attention 機制是一個較好的研究點.

2)在研究對象方面.當(dāng)前文獻研究的問題都相對簡單,而實際中的組合優(yōu)化問題通常具有多目標(biāo)、多約束、非靜態(tài)等復(fù)雜特性,當(dāng)前方法很難對該類問題進行求解,目前考慮多目標(biāo)優(yōu)化、約束優(yōu)化的文章較少.未來基于深度強化學(xué)習(xí)方法對多目標(biāo)、約束優(yōu)化、動態(tài)優(yōu)化問題進行研究是一個重要的研究方向.

3)在深度強化學(xué)習(xí)訓(xùn)練算法方面.目前對端到端模型的訓(xùn)練大多采用REINFORCE、DQN 等傳統(tǒng)訓(xùn)練算法,具有采樣效率低、收斂慢等缺陷,如何根據(jù)組合優(yōu)化問題的特性設(shè)計更加高效的強化學(xué)習(xí)訓(xùn)練算法也是一個未來需要著重研究的內(nèi)容.

4)最后,如何利用基于深度強化學(xué)習(xí)的組合優(yōu)化方法來解決工程實際中的在線調(diào)度優(yōu)化問題將會成為未來重要的研究方向.