基于深度強(qiáng)化學(xué)習(xí)的組合優(yōu)化研究進(jìn)展

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

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

其中x為決策變量、F(x) 為目標(biāo)函數(shù)、G(x) 為約束條件,D表示離散的決策空間,為有限個(gè)點(diǎn)組成的集合.組合優(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)、最小頂點(diǎn)覆蓋問題(Minimum vertex cover,MVC)、最小支配集問題(Minimum dominating problem,MDP)等.

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

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

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

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

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

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

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

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

1 基于深度強(qiáng)化學(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í)并解決單個(gè)小規(guī)模TSP 問題實(shí)例,對(duì)于新給定的一個(gè)TSP問題需要從頭開始再次訓(xùn)練,相對(duì)于傳統(tǒng)算法并沒有優(yōu)勢(shì).

神經(jīng)網(wǎng)絡(luò)真正能夠有效解決組合優(yōu)化問題是在2015 年,Vinyals 等[30]將組合優(yōu)化問題類比為機(jī)器翻譯過程(即序列到序列的映射),神經(jīng)網(wǎng)絡(luò)的輸入是問題的特征序列(如城市的坐標(biāo)序列),神經(jīng)網(wǎng)絡(luò)的輸出是解序列(如城市的訪問順序),Vinyals等根據(jù)該思想,對(duì)機(jī)器翻譯領(lǐng)域的經(jīng)典序列映射模型(Sequence-to-sequence,Seq2Seq)進(jìn)行了改進(jìn),提出了可以求解組合優(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)化算法都是以 “迭代搜索”的方式進(jìn)行求解,但是Vinyals等的模型可以利用神經(jīng)網(wǎng)絡(luò)直接輸出問題解,開啟了組合優(yōu)化一個(gè)新的研究領(lǐng)域.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

REINFORCE 算法通過式(4)對(duì)θ的梯度進(jìn)行計(jì)算并更新,不斷訓(xùn)練從而得到準(zhǔn)確的pθ(π|s),即實(shí) 現(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ò)對(duì)組合優(yōu)化問題進(jìn)行建模,其核心思想是根據(jù)每個(gè)節(jié)點(diǎn)的原始信息(如城市坐標(biāo))和各個(gè)節(jié)點(diǎn)之間的關(guān)系(如城市之間的距離),利用圖神經(jīng)網(wǎng)絡(luò)方法計(jì)算得到各個(gè)節(jié)點(diǎn)的特征向量,根據(jù)各個(gè)節(jié)點(diǎn)的特征向量進(jìn)行節(jié)點(diǎn)預(yù)測(cè)、邊預(yù)測(cè)等任務(wù).

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

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

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

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

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

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

目前基于DRL 的組合優(yōu)化方法主要分為基于DRL 的端到端算法和基于DRL 的局部搜索改進(jìn)算法兩大類,其中端到端算法主要包括基于Pointer network 的端到端方法和基于圖神經(jīng)網(wǎng)絡(luò)的端到端方法兩類,本文主要對(duì)以上方法在近年來的研究進(jìn)展進(jìn)行綜述介紹,對(duì)各類方法代表性算法的原理、優(yōu)化性能、優(yōu)缺點(diǎn)進(jìn)行對(duì)比和介紹,對(duì)各類方法未來的研究方向進(jìn)行了分析,各個(gè)算法的總結(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 模型進(jìn)行組合優(yōu)化問題求解,該文章也開啟了利用深度神經(jīng)網(wǎng)絡(luò)進(jìn)行組合優(yōu)化問題求解的一系列研究,該模型借鑒機(jī)器翻譯領(lǐng)域中的Seq2Seq模型求解組合優(yōu)化問題,即利用基于深度神經(jīng)網(wǎng)絡(luò)的編碼器將組合優(yōu)化問題的輸入序列(如城市坐標(biāo))進(jìn)行編碼,然后通過解碼器和注意力計(jì)算機(jī)制(Attention)計(jì)算得到各節(jié)點(diǎn)的選擇概率,并以自回歸的方式逐步選擇節(jié)點(diǎn),直到得到完整解(如城市訪問的順序),該方法的詳細(xì)原理見第2 節(jié).作者采用監(jiān)督式學(xué)習(xí)的方法對(duì)該模型進(jìn)行訓(xùn)練,即利用大量 “TSP 城市坐標(biāo)?最優(yōu)路徑”的樣本對(duì)該P(yáng)ointer network 的參數(shù)進(jìn)行離線訓(xùn)練,利用該訓(xùn)練好的模型,可以求解與訓(xùn)練集具有相同分布特性的任意TSP 問題.相對(duì)于傳統(tǒng)的局部搜索或者啟發(fā)式搜索方法,該端到端模型不需要進(jìn)行迭代搜索,具有泛化能力強(qiáng)、求解速度快的優(yōu)勢(shì),論文實(shí)現(xiàn)了對(duì)至多50 個(gè)城市的小規(guī)模TSP 問題的快速求解.

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

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

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

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

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

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

3.1.2 總結(jié)

以上為按時(shí)間線對(duì)各個(gè)代表性方法的介紹,Vinyals 等[30]最早提出了求解組合優(yōu)化問題的Pointer network 模型,Bello 等[31]最先提出采用強(qiáng)化學(xué)習(xí)方法對(duì)該模型進(jìn)行訓(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)上超越了文獻(xiàn)[34],各方法詳細(xì)的性能對(duì)比詳見表1.值得注意的是,上述方法在50 規(guī)模以上的TSP 問題上均未達(dá)到Concorde、LKH3 等求解器得到的最優(yōu)解.

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

3.2.1 方法綜述

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

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

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

以上方法均為對(duì)選擇各個(gè)節(jié)點(diǎn)的概率進(jìn)行估計(jì),文獻(xiàn)[40?41]利用圖神經(jīng)網(wǎng)絡(luò)對(duì)選擇各個(gè) “邊”的概率進(jìn)行估計(jì),以TSP 問題為例,利用圖神經(jīng)網(wǎng)絡(luò)模型輸出一個(gè)鄰接矩陣,dij代表兩點(diǎn)之間存在邊的概率,dij值大則節(jié)點(diǎn)i和j大概率相連.隨后根據(jù)各個(gè)邊出現(xiàn)概率的估計(jì)值,使用波束搜索(Beam search)的方式構(gòu)造最終的可行解.文獻(xiàn)[40?41]均采用監(jiān)督式方法進(jìn)行訓(xùn)練,即利用LKH3 或Concorde 求解器構(gòu)造大量 “坐標(biāo)?最優(yōu)路徑”的訓(xùn)練數(shù)據(jù),根據(jù)最優(yōu)解的真實(shí)鄰接矩陣和圖神經(jīng)網(wǎng)絡(luò)輸出的鄰接矩陣計(jì)算交叉熵,以交叉熵為損失函數(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)解,但是該方法的求解時(shí)間長于LKH3、Concorde 等方法,在泛化能力上該方法也不及Kool 等[34]的方法.

3.2.2 總結(jié)

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

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

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

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

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

3.3 深度強(qiáng)化學(xué)習(xí)改進(jìn)的局部搜索方法

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

3.3.1 方法綜述

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

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

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

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

3.3.2 總結(jié)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

由于網(wǎng)絡(luò)與通信領(lǐng)域存在多種典型的組合優(yōu)化問題,如資源分配、路由拓?fù)鋬?yōu)化等,因此基于深度強(qiáng)化學(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)出利用深度強(qiáng)化學(xué)習(xí)實(shí)現(xiàn)VNF 智能在線部署的多個(gè)研究.文獻(xiàn)[64]將VNF 部署問題建模為混合整數(shù)規(guī)劃問題,并將其轉(zhuǎn)化為馬爾科夫過程,在滿足不同的端到端時(shí)延需求的前提下,以最小化總?cè)蝿?wù)時(shí)間為目標(biāo),文章以DQN 強(qiáng)化學(xué)習(xí)方法對(duì)模型進(jìn)行訓(xùn)練,從而實(shí)現(xiàn)VNF 在線部署,該方法在收斂性能以及優(yōu)化能力上優(yōu)于多個(gè)基準(zhǔn)方法.文獻(xiàn)[65?66]基于GNN 圖神經(jīng)網(wǎng)絡(luò)對(duì)VNF 網(wǎng)元資源需求進(jìn)行預(yù)測(cè),以提高VNF部署的準(zhǔn)確性.文獻(xiàn)[67]考慮VNF 網(wǎng)元資源分配的特性,指出傳統(tǒng)強(qiáng)化學(xué)習(xí)方法很難處理VNF 部署問題中的大規(guī)模離散決策空間探索問題,因此文章對(duì)DDPG (Deep deterministic policy gradient algorithm)強(qiáng)化學(xué)習(xí)算法進(jìn)行了改進(jìn),提出了增強(qiáng)DDPG 算法,該方法的優(yōu)化能力超過了傳統(tǒng)DDPG方法以及整數(shù)規(guī)劃方法.文獻(xiàn)[68]采用Ptr-Net 的Encoder-decoder 架構(gòu)對(duì)VNF 部署問題進(jìn)行了求解,其Encoder 和Decoder 均采用LSTM模型,文章利用拉格朗日松弛將該約束問題轉(zhuǎn)化為無約束問題,并采用基于蒙特卡洛的策略梯度方法對(duì)模型進(jìn)行訓(xùn)練.通過與約束問題求解器Gecode和傳統(tǒng)啟發(fā)式方法對(duì)比,實(shí)驗(yàn)顯示該方法的優(yōu)化性能在大多數(shù)小規(guī)模和大規(guī)模問題上均優(yōu)于對(duì)比算法.

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

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

2)拓?fù)渑c路由優(yōu)化

在通信網(wǎng)絡(luò)或者無線傳感網(wǎng)絡(luò)中,通常需要對(duì)路由策略、傳感器的連接拓?fù)溥M(jìn)行優(yōu)化,以降低通信時(shí)延和成本.

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

3)計(jì)算遷移

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

4.2 其他領(lǐng)域

1)交通領(lǐng)域

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

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

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

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

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

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

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

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

5 結(jié)論與展望

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

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

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

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

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

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