基于深度強化學習的組合優化研究進展

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

組合優化問題(Combinatorial optimization problem,COP)是一類在離散狀態下求極值的最優化問題,其數學模型如下所示:

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

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

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

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

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

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

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

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

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

1 基于深度強化學習的組合優化:概述

利用神經網絡解決組合優化問題的方法最早可追溯至Hopfield 等在1985 年提出的Hopfield 網絡[28],該神經網絡用于求解TSP 問題以及其他組合優化問題[29],但是該神經網絡網絡每次只能學習并解決單個小規模TSP 問題實例,對于新給定的一個TSP問題需要從頭開始再次訓練,相對于傳統算法并沒有優勢.

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

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

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

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

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

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

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

2 基于深度強化學習的組合優化:基本原理介紹

Pointer network 模型和圖神經網絡模型是基于深度強化學習的組合優化方法中常用的兩種模型,本節首先對如何利用上述模型求解組合優化問題的基本原理進行介紹,并對廣泛用于訓練Pointer network 模型的REINFORCE 強化學習算法進行介紹.

2.1 Pointer Network 求解組合優化問題

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

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

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

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

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

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

因此該深度神經網絡模型的輸入是城市的坐標序列,輸出是城市的順序,通過對該模型參數的訓練 可以實現問題序列到解序列的準確映射.

2.2 Pointer Network 的強化學習訓練方法

對于Pointer network 深度神經網絡模型,可以通過監督式訓練算法或者強化學習算法進行訓練,由于監督式學習方法需要提供大量最優路徑的標簽數據集,實際應用較為困難,因此目前研究中通常以強化學習算法對模型的W和v等參數進行訓練.

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

策略由神經網絡參數θ進行參數化,在馬爾科夫過程中,每一步動作的概率為pθ(πt|s,π1:t?1),即根據已訪問過的城市π1:t?1和城市坐標s計算選擇下一步訪問各個城市的概率,根據鏈式法則累乘即可以得到城市坐標s到城市最終訪問順序π的映射pθ(π|s),該隨機策略可以建模為上節所述的指針網絡模型,其參數為θ.

由于TSP 問題的優化目標是最小化總的路徑長度L(π),而REINFORCE 也是以總反饋作為參數更新的標準,因此現有的研究中通常采用REINFORCE 強化學習算法對策略的參數θ進行訓練優化.

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

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

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

2.3 圖神經網絡方法求解組合優化問題

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

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

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

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

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

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

3 基于深度強化學習的組合優化:理論與方法

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

表1 現有算法模型、訓練方法、求解問題、以及優化效果比較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 模型進行組合優化問題求解,該文章也開啟了利用深度神經網絡進行組合優化問題求解的一系列研究,該模型借鑒機器翻譯領域中的Seq2Seq模型求解組合優化問題,即利用基于深度神經網絡的編碼器將組合優化問題的輸入序列(如城市坐標)進行編碼,然后通過解碼器和注意力計算機制(Attention)計算得到各節點的選擇概率,并以自回歸的方式逐步選擇節點,直到得到完整解(如城市訪問的順序),該方法的詳細原理見第2 節.作者采用監督式學習的方法對該模型進行訓練,即利用大量 “TSP 城市坐標?最優路徑”的樣本對該Pointer network 的參數進行離線訓練,利用該訓練好的模型,可以求解與訓練集具有相同分布特性的任意TSP 問題.相對于傳統的局部搜索或者啟發式搜索方法,該端到端模型不需要進行迭代搜索,具有泛化能力強、求解速度快的優勢,論文實現了對至多50 個城市的小規模TSP 問題的快速求解.

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

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

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

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

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

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

3.1.2 總結

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

3.2 基于圖神經網絡的端到端方法

3.2.1 方法綜述

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

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

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

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

3.2.2 總結

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

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

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

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

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

3.3 深度強化學習改進的局部搜索方法

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

3.3.1 方法綜述

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

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

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

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

3.3.2 總結

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

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

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

3.4 基于深度學習的多目標組合優化方法

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

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

3.5 基于深度學習的組合優化方法總結

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

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

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

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

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

表4 不同組合優化問題求解算法統計與比較Table 4 Summary and comparison of algorithms on different combinatorial optimization problems

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

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

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

4 深度強化學習解決組合優化問題:應用綜述

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

4.1 網絡與通信領域

由于網絡與通信領域存在多種典型的組合優化問題,如資源分配、路由拓撲優化等,因此基于深度強化學習的組合優化在網絡與通信領域存在較多的應用.

1)資源分配

在網絡與通信領域,資源分配問題是指將有限的CPU、內存、帶寬等資源分配給不同的用戶或任務需求,如虛擬網絡功能部署問題、網絡資源切片問題等.

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

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

文獻[71]對霧計算中的復雜資源分配問題進行了研究,將霧計算建模為馬爾科夫過程,以在既定時延內滿足用戶最大需求為目標,利用DQN 強化學習方法對霧計算中的資源分配進行在線求解,可以得到接近最優解的優化效果,并優于傳統的啟發式資源分配方法.

2)拓撲與路由優化

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

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

3)計算遷移

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

4.2 其他領域

1)交通領域

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

2)生產制造領域

在生產制造領域存在大量組合優化問題,近年來基于深度強化學習的組合優化模型在生產制造領域也多有應用.文獻[47,82]對經典的車間工作流調度問題進行了研究,采用深度強化學習方法對局部搜索的解搜索規則進行學習,利用Actor-critic 深度強化學習算法對搜索規則進行優化學習,實驗表明該兩個模型在優化性能上均超越了傳統啟發式局部搜索方法;置換車間工作流調度問題是對是對流水車間調度問題的進一步約束,文獻[83?84]均采用指針網絡模型對該問題進行了研究,文獻[83]采用了經典的指針網絡模型,并利用CPLEX 求解器構造大量樣本對該模型進行監督式訓練,實驗結果表明Attention 機制能夠有效提高解的質量,文獻[84]采用了Multi-head attention 機制進行建模,并利用REINFORCE 強化學習算法對模型進行訓練,實驗表明該模型超越了多個啟發式搜索算法和傳統的指針網絡模型.

3)高性能計算領域

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

4)微電網能量管理領域

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

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

5 結論與展望

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

現有研究已經顯示出深度強化學習在解決組合優化問題方面的優勢,但是相關研究還比較淺顯,當前的研究尚屬于起步階段,仍然存在一系列問題.要構建基于DRL 解決組合優化問題的理論方法體系,還需從如下幾個方面開展研究:

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

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

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

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