強化學(xué)習(xí)求解組合最優(yōu)化問題的研究綜述

王 揚，陳智斌，吳兆蕊，高 遠(yuǎn)

昆明理工大學(xué) 理學(xué)院，昆明650000

在實際工程應(yīng)用中，有一類優(yōu)化問題需要從集合的所有組合中找出一個最優(yōu)方案或編排，這類離散空間中的優(yōu)化問題稱為組合最優(yōu)化問題（combinatorial optimization problem，COP）。組合最優(yōu)化（combinatorial optimization，CO）的求解方法廣泛應(yīng)用于交通運輸、管理、電力、航天、通信等領(lǐng)域，其快速求解具有重要的理論意義和實用價值。例如，車輛的調(diào)度、金融資產(chǎn)的配置、倉庫貨物存儲和運輸路線的設(shè)計等實際問題都屬于COP 問題，隨著這些優(yōu)化問題實例規(guī)模的不斷增大和實例中動態(tài)及隨機因素的增加，傳統(tǒng)方法的求解將耗費巨大的時間，問題結(jié)構(gòu)一旦發(fā)生變化，傳統(tǒng)方法需要重新搜索求解，計算成本也會隨之提高，快速求解這些優(yōu)化問題變得十分困難。

近年來隨著深度學(xué)習(xí)（deep learning，DL）技術(shù)在計算機視覺、自然語言處理、語音識別、推薦系統(tǒng)等領(lǐng)域的廣泛應(yīng)用，特別是深度強化學(xué)習(xí)（deep reinforcement learning，DRL）在AlphaGo、AlphaGo Zero的成功應(yīng)用，表明在沒有人類干預(yù)和指導(dǎo)的前提下，DL 和強化學(xué)習(xí)（reinforcement learning，RL）的結(jié)合仍然能夠取得很大的成功，甚至超越了人類經(jīng)驗的指導(dǎo)，具有快速求解、泛化能力強、求解精度高等優(yōu)勢，為求解COP 問題提供一個全新的思路方法。鑒于此，近年來涌現(xiàn)出許多采用RL 求解COP 問題的新方法，即利用RL 訓(xùn)練模型的方法替代傳統(tǒng)算法，讓機器從算法中學(xué)習(xí)算法，從而快速且有效地解決實際問題，適應(yīng)現(xiàn)代科技的發(fā)展，進而滿足人類生活需求。

業(yè)界相關(guān)的工作已經(jīng)逐漸開展，如2017 年Hu 等人采用DRL 的方法求解三維裝箱問題；2018 年Lin等人把RL 應(yīng)用在共享出行中的車輛管理和派單問題上；2019 年Mao 等人將RL 的方法應(yīng)用在分布式集群任務(wù)調(diào)度中；2020 年Mirhoseini 等人又將RL應(yīng)用到芯片布局設(shè)計中。這些研究都是通過RL 的方法解決實際生活中的COP 問題，核心思路是：RL序貫決策的功能與具有序列決策性質(zhì)的COP 問題有天然的相似性，RL 模型可以通過智能體與環(huán)境的不斷交互，自身逐步積累經(jīng)驗來獲取問題的一個較優(yōu)策略，在少量樣本甚至無樣本的情況下，通過自學(xué)習(xí)的方式快速求解實際生活中的優(yōu)化問題，從而得到優(yōu)化問題的解，在求解過程中傳統(tǒng)方法和新思路的流程如圖1 所示。

圖1 求解COP 問題的兩種思路Fig.1 Two approaches to solving COP problem

RL 求解COP 問題是近年來一個新興研究領(lǐng)域，目前系統(tǒng)的研究和綜述較少，因此本文對RL 求解COP 問題的方法進行文獻綜述，回顧總結(jié)各類求解方法和應(yīng)用研究，分析求解模型的優(yōu)缺點，為各位學(xué)者在新興方向的研究提供參考。

1 組合最優(yōu)化問題和強化學(xué)習(xí)的介紹

1.1 組合最優(yōu)化問題的簡單概述

CO（又稱離散優(yōu)化）是最優(yōu)化理論的一個重要組成部分，它是運籌學(xué)與計算機領(lǐng)域的一個交叉學(xué)科，主要研究具有離散結(jié)構(gòu)的優(yōu)化問題，即研究如何從一組有限的對象中找到一個最優(yōu)對象的一類問題，這類問題的數(shù)學(xué)模型如下：

其中，為決策變量，為目標(biāo)函數(shù)，為約束條件，為離散空間中有限點組成的定義域。

比較有代表性的幾個COP 問題：旅行商問題（traveling salesman problem，TSP）、施泰納樹問題（Steiner tree problem，STP）、車輛路徑問題（vehicle routing problem，VRP）、裝箱問題（bin packing，BP）、背包問題（knapsack problem，KP）、平行機排序問題（parallel machines scheduling problem，PMSP）、最小頂點覆蓋（minimum vertex cover，MVC）、集合覆蓋問題（set covering problem，SCP）、最大割問題（max-cut）。

這些COP 問題普遍存在于日常的生活中，它們屬于非確定性多項式問題（non-deterministic polynomial，NP），如何提高解的精度、減少時間復(fù)雜度、增強泛化能力、快速且有效地得到問題的較優(yōu)解是長期以來最優(yōu)化理論的熱點研究課題，其中求解方法的選擇顯得尤為重要，本文會在1.2 節(jié)對COP 問題的求解方法進行總結(jié)。

1.2 組合最優(yōu)化問題求解方法概述

（1）傳統(tǒng)方法

①精確算法（exact algorithm）：枚舉法、分支定界（branch and bound，BB）、動態(tài)規(guī)劃（dynamic programming，DP）等均是通過不斷迭代的方式求解COP 問題的全局最優(yōu)解。

②近似算法（approximation algorithm）：貪婪算法、局部搜索、線性規(guī)劃等可以在多項式時間內(nèi)來近似最優(yōu)解，保證最壞情況下給出的解不低于（最大化問題）最優(yōu)解一定的倍數(shù)。

③（元）啟發(fā)式算法（heuristic algorithm）：遺傳算法、蟻群算法、模擬退火算法等均可以針對一般的COP 問題求解。

上述方法通稱為傳統(tǒng)算法，以經(jīng)典的TSP 問題為例，其中枚舉法和DP 法求解TSP 問題的時間復(fù)雜度分別為(!) 和(2)，隨著實例問題規(guī)模的擴大，該方法很難快速求解大規(guī)模的TSP 問題，因此精確算法對求解COP 問題規(guī)模有一定的局限性；假定P≠NP，一般形式的TSP 問題是不可被近似的，設(shè)計近似算法多數(shù)要考慮問題的特殊情況，因此近似算法對求解COP 問題的條件有一定的限制；蟻群算法等可以快速求解TSP 問題，但缺乏理論支撐以及無法保證解的全局最優(yōu)性，導(dǎo)致啟發(fā)式算法很難保證求解的質(zhì)量。

（2）基于機器學(xué)習(xí)的COP 問題求解方法

①基于神經(jīng)網(wǎng)絡(luò)（neural network，NN）求解TSP問題：Hopfield 等人提出一種Hopfield 網(wǎng)絡(luò)，首次嘗試用機器學(xué)習(xí)（machine learning，ML）的方法求解小規(guī)模的TSP 問題，之后很多相關(guān)工作也相繼出現(xiàn)，早期采用NN 求解COP 問題的文章可見Smith的綜述。

②基于指向型網(wǎng)絡(luò)（Pointer network，PN）求解COP 問題：Vinyals 等人針對Seq2Seq序列模型輸入輸出維度是固定的問題，對其改進，提出PN 架構(gòu)，并加入注意力機制（attention mechanism，AM）使得序列模型不受輸入輸出維度的限制。PN 架構(gòu)為基于ML 等新方法求解COP 問題的工作奠定了很好的理論基礎(chǔ)。

③基于DRL 求解COP 問題：監(jiān)督學(xué)習(xí)（supervised learning，SL）需要大量標(biāo)簽，且COP 問題的高質(zhì)量標(biāo)簽不易獲得。RL 使智能體與環(huán)境不斷交互，通過獎勵值來激勵學(xué)習(xí)得到數(shù)據(jù)，克服了SL 中大量標(biāo)簽的花費問題。Zhang 等人將RL 應(yīng)用到NP-hard 的車間調(diào)度問題，Bello 等人提出神經(jīng)組合最優(yōu)化模型（neural combinatorial optimization，NCO），為后續(xù)基于RL 方法求解COP 問題的推進奠定了基礎(chǔ)。

④基于Transformer框架求解COP 問題：Transformer 框架延續(xù)了AM 中編碼-解碼的結(jié)構(gòu)，其網(wǎng)絡(luò)架構(gòu)均由自注意力機制和全連接層（fully connected，F(xiàn)C）組成，模型中多重注意力機制（multihead attention，MHA）的自注意力機制計算方法，增加更多計算層，以便提取到深層節(jié)點的特征信息，有效克服信息丟失問題。

⑤基于圖神經(jīng)網(wǎng)絡(luò)（graph neural networks，GNNs）求解COP 問題：GNNs 近幾年發(fā)展迅速，是一種將深度神經(jīng)網(wǎng)絡(luò)（deep neural network，DNN）模型應(yīng)用于解決圖上相關(guān)任務(wù)的方法，通過低維的向量信息來表征圖的節(jié)點及拓?fù)浣Y(jié)構(gòu)，此方法可以很好地處理非歐幾里德數(shù)據(jù)，有效抽取圖結(jié)構(gòu)中的關(guān)鍵節(jié)點信息。

⑥基于ML 與傳統(tǒng)方法結(jié)合的求解方法：此方法求解COP 問題主要是端到端的輸出解。針對搜索過程中子問題不同的特性，Liberto 等人提出DASH（dynamic approach for switching heuristics）架構(gòu)，動態(tài)切換合適的啟發(fā)算法求解COP 問題。He 等人引入模仿學(xué)習(xí)（imitation learning，IL），以SL 的方式得到自適應(yīng)的節(jié)點搜索策略。此方法能夠利用ML 方法的優(yōu)點，同時還能保證傳統(tǒng)方法的最優(yōu)性。

近年來采用ML 方法求COP 的方法逐漸增多，其中Bengio 等人的綜述介紹了ML 與COP 求解的方法導(dǎo)論，說明ML 方法可以求解部分COP 問題，這對COP 問題的求解提供了部分理論支撐。文中表1 分析并總結(jié)了基于RL 的COP 問題求解方法，圖2 匯總了求解COP 問題的方法框架。

圖2 COP 解決方案框架Fig.2 COP solution framework

表1 研究方法、求解問題、模型算法的分析與總結(jié)Table 1 Analysis and summary of research methods,solving problems and models

1.3 強化學(xué)習(xí)的簡單概述

RL 被定義為智能體與環(huán)境不斷交互，獲取相應(yīng)的獎勵，不斷學(xué)習(xí)以完成特定的目標(biāo)任務(wù)。從圖3可以理解為智能體在與環(huán)境進行交互的過程中，通過不斷的嘗試，從錯誤中學(xué)習(xí)經(jīng)驗，并根據(jù)經(jīng)驗調(diào)整其策略，來最大化最終所有獎勵的累積值。RL 的獎勵很重要，具有獎勵導(dǎo)向性，這種獎勵導(dǎo)向性類似于SL 中正確的標(biāo)簽，從一開始沒有數(shù)據(jù)和標(biāo)簽，不斷嘗試在環(huán)境中獲取這些數(shù)據(jù)和標(biāo)簽，然后再學(xué)習(xí)哪些數(shù)據(jù)對應(yīng)哪些標(biāo)簽，通過學(xué)習(xí)這樣的規(guī)律，不斷更新智能體的狀態(tài)，使之盡可能選擇高分行為。RL 不是簡單學(xué)習(xí)運算一個結(jié)果，而是學(xué)習(xí)問題的一種求解策略。

圖3 強化學(xué)習(xí)簡要模型Fig.3 Brief model of reinforcement learning

DRL 是DL 和RL 的結(jié)合，同時具有感知能力和決策能力。具體來說，DRL 通過RL 來定義問題本身和優(yōu)化目標(biāo)函數(shù)，DL 來解決狀態(tài)表示、策略表達等問題，DNN 來擬合RL 中的值函數(shù)、策略，然后采用誤差反向傳播算法來優(yōu)化目標(biāo)函數(shù)。DRL 是一種端到端的感知與控制系統(tǒng)框架，一種更接近人類思考的ML 方法。從圖4 可以看出，DRL 結(jié)構(gòu)與RL 結(jié)構(gòu)類似，為解決復(fù)雜決策系統(tǒng)提供方便。

圖4 深度強化學(xué)習(xí)簡要模型Fig.4 Brief model of deep reinforcement learning

RL 根據(jù)馬爾可夫決策過程（Markov decision process，MDP）可以分為基于模型的RL 算法和無模型的RL 算法，其原理分別是基于DP 和蒙特卡羅方法，RL 算法的具體分類見圖5。

圖5 強化學(xué)習(xí)主流算法Fig.5 Mainstream reinforcement learning algorithms

（1）強化學(xué)習(xí)

RL 可以建模為一個MDP，其過程可以用五元組(,,,,)表示。其中表示環(huán)境的狀態(tài)集合，表示智能體的動作集合，是各個狀態(tài)的轉(zhuǎn)移概率，是采取某一動作后到達下一個狀態(tài)的獎勵值，是折扣因子。

MDP 可表示成：

的概率：

給定策略(|)，智能體與環(huán)境一次交互過程的軌跡所收到的累積獎勵為總回報：

其中，∈[0,1]是折扣率，當(dāng)接近于0 時，智能體會注重短期回報，而當(dāng)接近于1 時，智能體會注重長期回報。

最優(yōu)策略是每個狀態(tài)所獲得的總回報最大的策略，最優(yōu)策略的目標(biāo)函數(shù)為：

（2）基于策略梯度的深度強化學(xué)習(xí)

基于策略梯度（policy gradient，PG）的DRL 常應(yīng)用于狀態(tài)空間過大或連續(xù)空間的RL 問題上，它不需要計算值函數(shù)，可以用DNN 來表示從狀態(tài)空間到動作空間的一個參數(shù)化映射函數(shù)=π()。策略搜索是通過尋找參數(shù)使得目標(biāo)函數(shù)π()輸出概率最大，直接計算與動作相關(guān)的PG，沿梯度方向調(diào)整動作，好的行為會增加被選中的概率，不好的行為會減弱下一次被選中的概率，是一種端到端的輸出形式。

通常選擇隨機梯度下降（stochastic gradient descent，SGD）的REINFORCE 算法對策略的參數(shù)進行訓(xùn)練優(yōu)化：

其中，(τ)為作為起始時刻收到的總回報。

采用REINFORCE 算法求解TSP 問題會導(dǎo)致不同路徑之間的方差很大，從而模型結(jié)果難以收斂，這是高維空間中使用蒙特卡羅方法普遍存在的，為此引入一個和a無關(guān)的基準(zhǔn)函數(shù)(s)來減小PG 的方差，其中(s)和(τ)相關(guān)性越大效果越好，一個很自然的選擇是令(s)作為值函數(shù)V(s)，其中帶基準(zhǔn)線REINFORCE 算法中參數(shù)的值函數(shù)和策略函數(shù)的更新如下：

（3）基于值函數(shù)的深度強化學(xué)習(xí)

2013 年Mnih 等人提出深度Q-網(wǎng)絡(luò)（deep Qnetwork，DQN）算法，2015 年Mnih 等人又改進了DQN 算法，使其訓(xùn)練過程具有穩(wěn)定性。此算法是DL與RL 的首次結(jié)合，采用DNN 端到端地擬合Q-學(xué)習(xí)中的Q 值，充分發(fā)揮出DNN 對高維數(shù)據(jù)處理的能力，其中關(guān)鍵的評估策略π(|)可分為兩個值函數(shù)：狀態(tài)值函數(shù)和狀態(tài)-動作值函數(shù)。

狀態(tài)值函數(shù)的策略期望回報可以分解為：

從狀態(tài)開始，策略得到的期望總回報：

狀態(tài)-動作值函數(shù)是指初始狀態(tài)為并執(zhí)行動作，然后通過策略得到期望總回報：

（4）基于行動者-評論家的深度強化學(xué)習(xí)

行動者-評論家（actor critic，AC）算法是結(jié)合PG和時序差分（temporal difference，TD）的一種RL 算法。行動者通過策略函數(shù)π(,)學(xué)習(xí)到一個更高回報的策略。評論家經(jīng)由值函數(shù)V()表示，對當(dāng)前策略的值函數(shù)進行估計，即評估行動者策略的好壞。借助于值函數(shù)，AC 算法可以進行單步策略更新參數(shù)，不需要所有回合結(jié)束再更新參數(shù)，如Lillicrap等人采用深度確定性策略梯度（deep deterministic policy gradient，DDPG）來實現(xiàn)AC 算法。

DeepMind研究人員基于AC 算法，提出它的變體A3C，即多個智能體并行學(xué)習(xí)，以固定的時間間隔但不同步地去探索環(huán)境，實時更新權(quán)重，然后讓其主網(wǎng)絡(luò)接受這些權(quán)重，這樣每個智能體都可以改善主網(wǎng)絡(luò)，并且智能體之間可以相互激勵，以便更好地訓(xùn)練參數(shù)，增強模型的穩(wěn)定性。針對A3C 算法智能體的異步性，DeepMind團隊接著提出A2C 算法模型，其更新都是同步的，且均在較大批次上運行，這樣可以更好地利用GPU 加速。針對訓(xùn)練過程中權(quán)重更新不穩(wěn)定的問題，Schulman 等人提出近端策略優(yōu)化算法（proximal policy optimization，PPO），修改了A2C 算法的損失函數(shù)，解決訓(xùn)練不穩(wěn)定的問題。同時為了更好地激勵智能體自主探索環(huán)境，加快訓(xùn)練速度，Haarnoja 等人基于AC 算法提出柔性行動者-評論家算法（soft actor-critic，SAC），它可以很好地學(xué)習(xí)獎勵，還能最大化其行為的熵，即盡可能地讓智能體的行為不可預(yù)測，同時還能獲得更大的獎勵。由于RL 中經(jīng)常會出現(xiàn)獎勵的稀疏性，這使智能體的學(xué)習(xí)效率很低，為此Pathak 等人提出Curiosity-based的探索算法，讓智能體極端好奇地去探索環(huán)境，利用好奇心這一特性，讓智能體嘗試預(yù)測接下來的行為動作，并預(yù)測與結(jié)果不吻合的值，讓獎勵成為智能體固有的性質(zhì)，而不是從環(huán)境獲得,有利于智能體進行高性能計算。為了更好地理解RL 主流算法，可以參考劉全等人和Li對RL 的研究綜述。

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

2.1 組合最優(yōu)化問題的求解難點

針對NP-難的COP 問題實例進行快速求解，傳統(tǒng)方法是以設(shè)計近似算法為主，這類算法都是針對問題本身而設(shè)計的。首先需證明所求解的問題是存在近似算法的，比如：假定P ≠NP，一般形式的TSP 問題沒有近似算法；NP 難解的KP 問題沒有多項式時間算法；對任意的＞0，BP 問題不存在近似比保證為3/2-的近似算法。其次考慮要求解的問題是否可以歸約到其對偶問題上求解（利用線性規(guī)劃的思想）。不論如何設(shè)計算法都需要對其正確性進行證明并找到合適的緊例子，才可以說明算法的嚴(yán)謹(jǐn)性及對算法的分析是好的，因此許多COP 問題的算法設(shè)計需要大量的人力和專家的經(jīng)驗。在未來，隨著科技發(fā)展和進步，對求解各種COP 問題（變體問題）的要求會更高，在優(yōu)化算法設(shè)計上要取得重大的突破也是困難的。

同時，針對同一個COP 問題的求解，常常會出現(xiàn)下述情況，先前的求解對后面問題的求解基本沒有幫助，但是大多數(shù)優(yōu)化問題又具有相同的優(yōu)化結(jié)構(gòu)，而傳統(tǒng)算法的設(shè)計不僅沒有很好利用相同問題之間的相似性，還難以考慮動態(tài)及隨機因素，由此建立的數(shù)學(xué)模型泛化能力弱，不能很好地遷移到相同問題的不同實例上。比如為匹配（matching）問題和SCP問題設(shè)計近似算法時，會立即遇到下述困難，為確定近似比，會對算法產(chǎn)生的邊費用以及最優(yōu)解的邊費用進行比較，其中不僅尋找最優(yōu)解是NP 難解的，而且計算最優(yōu)解費用也是NP 難解的，這正是此類問題的難點所在，即使通過確定OPT 的下界方法來保證近似比，還需尋找不同COP 問題的對偶問題，這個過程也是困難的。假如通過上述方法確定了下界，想要改進基數(shù)頂點覆蓋的近似保證，這是不可能的，因為考慮二部圖K給出的無限實例族，說明近似算法的分析是緊的，以這種OPT 的下界方式建立的近似保證，不可能設(shè)計出比它更好保證的近似算法。

隨著人工智能、大數(shù)據(jù)時代的到來，COP 問題實例的規(guī)模不斷增大，隨之會出現(xiàn)“組合爆炸”的現(xiàn)象，相關(guān)問題計算的時間和空間復(fù)雜度會呈指數(shù)增長，傳統(tǒng)方法很難快速求解大規(guī)模性的實際問題，即使解決了這類問題，求解時間和花費也是人們無法接受的。在權(quán)衡時間和精度的條件下，目前傳統(tǒng)算法仍然是求解NP 問題的有效方法，但高效求解大規(guī)模COP 問題實例及其變體問題成為一個很大的挑戰(zhàn)。在P ≠NP 的假設(shè)下，放眼國內(nèi)外專家團隊對COP 算法的研究，傳統(tǒng)方法在短時間內(nèi)不會取得重大突破，未來的發(fā)展是基于線下訓(xùn)練、線上求解的高性能計算設(shè)計上。

這款臻釀標(biāo)志著Penfolds當(dāng)代釀制工藝，突出地域特色的同時，也代表了法國橡木桶釀制赤霞珠的成熟技巧，既是Penfolds精巧技藝的映射，同時也是Penfolds對多樣性的不倦追求。

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

許多COP 問題都是NP 難解的，設(shè)計算法的過程本身難度就很大，且不容易被刻畫，無模型的RL 方法可以通過智能體與環(huán)境的不斷交互，學(xué)習(xí)到相應(yīng)策略，模型訓(xùn)練完成后，短時間內(nèi)給出一個高質(zhì)量解，甚至比傳統(tǒng)算法求解的質(zhì)量要高。如Alipour 等人提出一種遺傳算法和多主體RL 算法結(jié)合的混合算法來求解TSP 問題，文獻[52]采用GA-MARL+NICH-LS 算法使得求解的精度高于幾個傳統(tǒng)算法；Fairee 等人提出一種采用RL 算法更新解的模型和基于人工蟻群的組合變體算法，文獻[53]在6 個測試集上測試，在收斂速度上，RL 更新的解快于人工蟻群算法。

針對傳統(tǒng)方法難以解決多維度的問題方面，RL可以采用值函數(shù)近似和直接策略搜索等算法，使問題的描述更加全面，從而得到更高質(zhì)量的解。如Hu等人提出一種多智能體RL 框架求解多重旅行商問題（multiple traveling salesman problem，MTSP）。網(wǎng)絡(luò)架構(gòu)由GNNs 和分布式策略網(wǎng)絡(luò)組成，利用RL 算法訓(xùn)練模型參數(shù)，采用S-樣本（批次訓(xùn)練）的方法減少梯度方差，提高模型的整體性能。針對大規(guī)模問題求解，該框架學(xué)習(xí)的策略優(yōu)于整數(shù)線性規(guī)劃和啟發(fā)式算法。

針對求解動態(tài)和受隨機因素影響的問題上，RL可在智能體與環(huán)境之間的交互以及狀態(tài)轉(zhuǎn)移過程中加入隨機因素，增強模型的魯棒性，且模型一旦訓(xùn)練完成，對同一問題的變體，也可以很好地適應(yīng)新數(shù)據(jù)的變化。如Yao 等人提出一種端到端的RL 框架求解COP 問題，核心思想是把狀態(tài)空間作為問題的解，解的擾動信息作為智能體的動作空間。模型利用GNNs 抽取潛在的表征信息，對狀態(tài)行為進行編碼。推理階段采用深度Q-學(xué)習(xí)改善解（轉(zhuǎn)換或交換向量標(biāo)簽）的質(zhì)量，得到問題的最優(yōu)策略。在Max-cut 和TSP 問題上，此模型相比學(xué)習(xí)算法和啟發(fā)式算法有更優(yōu)的表現(xiàn)和泛化能力，更好地適應(yīng)動態(tài)和隨機因素。

目前，DL 的實驗平臺配置逐漸完善，如Pytorch、TensorFlow 等DL 框架，這些面向?qū)ο蟮拈_源庫，降低了各位學(xué)者的使用門檻，還有硬件設(shè)施GPU、TPU 的快速發(fā)展，使得COP 問題會在更短的時間內(nèi)得到顯著的優(yōu)化效果。利用RL 和計算機科學(xué)的這些優(yōu)點，對求解路徑優(yōu)化、庫存控制以及車間工件調(diào)度等COP 問題領(lǐng)域的大規(guī)模動態(tài)問題、隨機決策問題、各種變體問題會更為有利，為COP 的研究提供一種新方法。雖然處于初級階段，但也取得一定的成果，說明此方法求解COP 問題的可行性。具體來說，采用RL 求解COP 問題的優(yōu)勢總結(jié)如下：

（1）泛化能力的增強：傳統(tǒng)方法對于一個新問題或者其變體問題，大多都需要重新設(shè)計新算法，然而ML 有讓算法具有學(xué)習(xí)的能力，從算法中學(xué)習(xí)設(shè)計算法，替代手工設(shè)計算法。模型一旦訓(xùn)練完成，其參數(shù)可以相互調(diào)用，通過遷移學(xué)習(xí)的方式傳遞給相應(yīng)的策略函數(shù)，從而在給定一個新問題時能夠有效快速地獲得解。

（2）求解速度的加快：傳統(tǒng)的算法是基于初始解的迭代，RL 對一些COP 問題可以產(chǎn)生質(zhì)量較高的初始解，不斷更新解得到更優(yōu)的解。DRL 采用DNN 對模型進行合適的特征表示，進而降低求解空間的大小，即減少了搜索寬度和深度。

（3）伸縮性的提高：RL 中一些算法可以降低COP 問題的時間復(fù)雜度，再結(jié)合GPU、TPU 的加速計算，使其應(yīng)用于求解大規(guī)模的COP問題。模型一旦訓(xùn)練完成，可以適用于不同的COP 問題，無需為每個問題設(shè)計新的算法或重新建立新的模型，從而避免人力資源的浪費，為實時求解動態(tài)COP 問題成為可能，以便高效求解實際生活中所面臨的眾多NP-難問題。

（4）初始解的要求降低：DL 中的SL 需要大量訓(xùn)練數(shù)據(jù)作為標(biāo)簽，COP 問題中生成這些數(shù)據(jù)需要解決大量的NP 難問題，獲得標(biāo)簽的代價是巨大的，限制了SL 的適用性。然而RL 在給定一組實例解時通過計算優(yōu)化目標(biāo)來評估解的質(zhì)量相對容易，在大多數(shù)RL 的框架中，其目標(biāo)是學(xué)習(xí)一種隨機策略，以高概率輸出高質(zhì)量的解。訓(xùn)練出的模型可以在各種復(fù)雜的真實環(huán)境中更好地泛化，減少對數(shù)據(jù)標(biāo)簽的依賴和未知數(shù)據(jù)的擾動。

2.3 強化學(xué)習(xí)與組合最優(yōu)化問題的結(jié)合分析

首先RL 用于序貫決策，即根據(jù)當(dāng)前的環(huán)境狀態(tài)做出相應(yīng)的行為選擇，并根據(jù)行為的反饋不斷調(diào)整自身的策略，從而達到特定的學(xué)習(xí)目標(biāo)。COP 問題即在離散空間中選擇事件的最優(yōu)次序、編排等，與RL的行為選擇具有天然的相似性。以經(jīng)典的TSP 問題為例，當(dāng)任意兩城市之間的距離與城市排列順序無關(guān)時，定義環(huán)游長度如下：

首先將TSP 問題建模成MDP，再利用RL 相關(guān)算法訓(xùn)練參數(shù)，學(xué)習(xí)到一個最優(yōu)策略(|)以較大概率輸出路徑長度最短的環(huán)游，該策略可以建模為：

其狀態(tài)、行為、獎勵、策略表示為：

（1）狀態(tài)：已經(jīng)訪問過城市的坐標(biāo)集合。

（2）狀態(tài)轉(zhuǎn)移：根據(jù)已經(jīng)訪問過的城市和城市的坐標(biāo)計算接下來將要訪問的城市概率。

（3）動作空間：第步將要選擇的城市π。

（4）獎勵：已訪問過城市路徑總距離的負(fù)數(shù)（最短路徑）。

（5）策略：狀態(tài)到動作的映射，即得到的是選擇城市的概率p(|)。

通過這樣的建模，簡單地實現(xiàn)了RL 與COP 問題的結(jié)合，不斷地訓(xùn)練相關(guān)參數(shù)得到更為準(zhǔn)確的策略，為COP 問題求解提供一種全新的思路。

3 強化學(xué)習(xí)求解組合最優(yōu)化問題的方法

目前基于RL 求解COP 問題的方法主要分為基于NCO 模型的求解方法、基于動態(tài)輸入的COP 模型的求解方法、基于圖結(jié)構(gòu)模型的求解方法、基于RL結(jié)合傳統(tǒng)算法的求解方法、基于改進RL 模型的求解方法等五大類，本文主要對以上方法的研究進行綜述，對各類代表性研究所解決COP 問題的研究問題、算法模型、優(yōu)化效果進行對比分析（見表1），并對不同方法局限性及使用場景的限制進行了綜合評述。

3.1 基于神經(jīng)組合最優(yōu)化模型求解方法

為克服SL 樣本需求的問題，Bello 等人把NN和RL 相結(jié)合，提出NCO 模型。文章以PN 為基礎(chǔ)，采用REINFORCE 算法訓(xùn)練模型參數(shù)，將TSP 問題的每個實例作為一個訓(xùn)練樣本，目標(biāo)函數(shù)是實例中城市的最短環(huán)游長度。模型引入critic 網(wǎng)絡(luò)為基準(zhǔn)構(gòu)建與策略網(wǎng)絡(luò)參數(shù)無關(guān)的估值網(wǎng)絡(luò)，降低訓(xùn)練方差，該網(wǎng)絡(luò)使用均方誤差（mean square error，MSE）評判估值網(wǎng)絡(luò)和SGD 法來優(yōu)化目標(biāo)函數(shù)，還指出結(jié)合推理搜索的求解方式能進一步改善解的質(zhì)量。由于評估一條環(huán)游長度需要很小的計算量，可以讓模型輸出更多候選解，然后在求解空間中找到最優(yōu)解，加快求解速度。文獻[32]的實驗結(jié)果顯示，NCO 求解100-TSP問題的環(huán)游長度優(yōu)于Christofides算法和專業(yè)求解器，200-Knapsack 達到最優(yōu)解。

針對傳統(tǒng)的搜索方法依賴于啟發(fā)式算法且在許多COP 實例中采用啟發(fā)式算法求解速度慢等問題，Chen 和Tian對此提出NeuRewriter 框架求解COP問題，以迭代的方式不斷改進問題的解直到收斂，從而加快求解速度。整個策略分為兩部分：區(qū)域挑選策略和規(guī)則挑選策略。區(qū)域挑選策略用于選取當(dāng)前狀態(tài)（每個解是一個狀態(tài)）要更改的區(qū)域；規(guī)則挑選策略用于選取重寫的規(guī)則。文獻[57]采用RL 中的QAC 算法訓(xùn)練模型參數(shù)。實驗結(jié)果顯示：簡化表達超過Z3 模型；JSP 超過DeepRM 模型和專業(yè)求解器；CVRP 超越了部分基于ML 的方法，比基于啟發(fā)式算法和DNN 直接生成解的質(zhì)量要高。

為進一步提高模型的泛化能力，Joshi 等人結(jié)合SL 和RL 訓(xùn)練100-TSP 問題，測試模型在一個變化的圖上，最大到500 個節(jié)點。在固定大小的圖上，采用協(xié)同訓(xùn)練的方式會更接近最優(yōu)解，用GCN 編碼替代Transformer 架構(gòu)編碼對模型求解影響較小，還證明了模型的泛化能力取決于RL 模型中的學(xué)習(xí)范式。Joshi 等人之后改進NCO 模型，將小范圍TSP問題泛化成求解大范圍的TSP 問題（128 萬個節(jié)點）。

Miki 等人針對經(jīng)典的TSP 問題提出了DL 和RL 算法（EV-貪婪+EV-2opt）結(jié)合的框架。此方法采用卷積神經(jīng)網(wǎng)絡(luò)（convolutional neural network，CNN）將TSP 問題的最優(yōu)路線作為圖像進行卷積學(xué)習(xí)操作。推理階段結(jié)合EV-貪婪和EV-2opt 算法，高效輸出最優(yōu)解，同時比較2opt 和S2V-DQN 算法在TSBLIB 數(shù)據(jù)集上的優(yōu)化效果。文獻[60]結(jié)合DL 和RL 模型在求解質(zhì)量和速度上優(yōu)于單個模型，通過SL 得到的解再結(jié)合RL 訓(xùn)練可以提高解的質(zhì)量。

鑒于DNN 模型以端到端的方式輸出問題的解，Li等人采用DRL方法近似求解覆蓋商問題（covering salesman problem，CSP）。模型以PN為基礎(chǔ)，利用MHA采集結(jié)構(gòu)信息，加入動態(tài)嵌入模型處理動態(tài)信息，使用REINFORCE 算法訓(xùn)練模型參數(shù)。該模型下求解CSP 問題的時間比傳統(tǒng)啟發(fā)式算法（LS1、LS2）快20倍，相比PN、動態(tài)指向型網(wǎng)絡(luò)、AM 模型有更好的收斂性，且模型一旦訓(xùn)練完成（時間較慢），可以泛化到多種類型的CSP 問題上。

上述PN 模型原理是將COP 問題的實例編碼成向量，使其在隱藏層輸出，最后解碼時通過Softmax對向量進行處理，輸出具體實例中較大的概率向量，且輸出向量維度與輸入向量維度一致，具體模型如圖6 所示。

圖6 Pointer networks模型Fig.6 Pointer networks model

表2 NCO 模型的局限性分析Table 2 Limitation analysis of NCO model

3.2 基于動態(tài)輸入的組合最優(yōu)化模型求解方法

針對VRP 問題的輸入是動態(tài)變化的，使用PN 無法直接求解這類問題，Nazari 等人將PN 拓展成能夠處理動態(tài)信息的COP 模型，采用一維CNN 替代編碼輸入層的LSTM，即替換編碼部分，保留解碼部分，這樣使得模型的輸出和輸入的順序無關(guān)，從而有效地解決動態(tài)問題的輸入對問題求解的影響。模型的訓(xùn)練采用了經(jīng)典的PG 方法，并加入貪婪算法和波束搜索（beam search，BS）兩種推理技術(shù)提高解的質(zhì)量。模型一旦訓(xùn)練完成，對于不同規(guī)模的實例，無需重新訓(xùn)練。文獻[62]的實驗是在50 和100 規(guī)模的VRP 問題上進行的，運用該模型在求解質(zhì)量上相比經(jīng)典Clarke-Wright savings heuristic、Sweep heuristic啟發(fā)式算法有一定優(yōu)勢。推理階段結(jié)合BS 后求解時間對比專業(yè)求解器有60%以上的優(yōu)勢。

鑒于Transformer 在語義信息深層特征的提取上有良好表現(xiàn)，Kool 等人改進其架構(gòu)，編碼部分中未采用位置編碼，使節(jié)點嵌入與順序無關(guān)。模型沿用了Transformer 架構(gòu)中的MHA 和前饋FF 結(jié)構(gòu)來得到每個城市對應(yīng)的節(jié)點嵌入。解碼采用了經(jīng)典的自回歸調(diào)整模式，并引入上下文節(jié)點來表征解碼時的上下文向量，它包含了圖嵌入層以及第一個節(jié)點（它是起點也是終點）與前一個輸出節(jié)點的嵌入。最后解碼結(jié)構(gòu)加入一個單層AM（即=1 的MHA），通過激活函數(shù)softmax 輸出，即為當(dāng)前一步的輸出。文獻[63]采用經(jīng)典REINFORCE 算法訓(xùn)練模型參數(shù)，其中基準(zhǔn)函數(shù)通過策略模型進行確定的貪婪搜索得到。實驗考慮了幾種路徑問題：TSP和VRP及其變體問題（SDVRP、PCTSP、SPCTSP），實驗結(jié)果顯示基于確定貪婪搜索的方法在求解質(zhì)量和速度上優(yōu)于先前端到端的模型，在100-TSP 問題上的優(yōu)化性能超越了傳統(tǒng)啟發(fā)式算法，且模型的收斂性明顯優(yōu)于傳統(tǒng)方法。

許多RL 模型會受到實例輸入維度大小的影響，Emami 等人提出一種基于SPG（sinkhon policy gradient）算法學(xué)習(xí)策略模型，克服上述問題，并結(jié)合AC 架構(gòu)求解COP 問題中的排列問題，該模型可以端到端地求解TSP 問題和Matching 問題，并把問題遷移到更大規(guī)模的圖問題中求解。

更進一步，Oren 等人提出一個離線學(xué)習(xí)、在線搜索的框架（SOLO）求解COP 問題，該框架的求解過程可以看作一個MDP，采用深度Q-學(xué)習(xí)網(wǎng)絡(luò)從圖模型的狀態(tài)行為空間中學(xué)習(xí)出一個最優(yōu)策略，并結(jié)合蒙特卡羅樹搜索（Monte Carlo tree search，MCTS）提升模型的穩(wěn)定性和泛化能力等。文獻[61]的實驗在PMSP 和CVRP 兩個COP 問題上進行，實驗結(jié)果顯示，該框架下在求解時間和模型的表達能力上超越了專業(yè)數(shù)學(xué)求解器和前沿的學(xué)習(xí)算法以及傳統(tǒng)的啟發(fā)式算法。

為了使智能體在每一個回合限制中可以探索動態(tài)的節(jié)點信息和隱藏層的信息結(jié)構(gòu)，快速處理實例中的動態(tài)隨機因素，Bo 等人提出動態(tài)的編碼-解碼架構(gòu)，建立一個動態(tài)AM 模型求解VRP問題，文獻[66]實驗結(jié)果顯示此模型求解VRP 的表現(xiàn)優(yōu)于先前RL的方法且有很強的泛化能力。

上述模型中，AM 編碼-解碼的結(jié)構(gòu)不受COP 問題輸入和輸出序列長度的限制，結(jié)合RL 算法后文獻[62-66]中模型表現(xiàn)出顯著的優(yōu)勢，可以廣泛應(yīng)用于求解COP 問題，具體模型如圖7 所示。

圖7 Attention 模型示意圖Fig.7 Schematic diagram of Attention model

2018 年Nazari 等人提出了一種求解具有動態(tài)因素COP 問題的模型，整體框架以AC 為基準(zhǔn)，對PN 進行改進。借鑒循環(huán)神經(jīng)網(wǎng)絡(luò)（recurrent neural network，RNN）的原理，針對處理時間相關(guān)性較強的COP 問題，編碼采用一維CNN 替代RNN 序列元素的嵌入。解碼階段利用AM 融合動態(tài)和靜態(tài)的嵌入向量，最后通過softmax 函數(shù)進行歸一化處理，從估值網(wǎng)絡(luò)中得到每個輸入元素的概率分布，再通過策略網(wǎng)絡(luò)輸出嵌入向量序列并進行加權(quán)求和，以較大概率輸出解。針對RL 處理動態(tài)信息在決策過程中出現(xiàn)的不穩(wěn)定性、有效節(jié)點信息的稀疏性問題，限制模型的優(yōu)化效果，表3 分析了基于動態(tài)輸入的COP 模型求解方法的局限性。

表3 動態(tài)輸入模型的局限性分析Table 3 Analysis of limitation of dynamic model

3.3 基于圖結(jié)構(gòu)模型的模型求解方法

GNNs 是基于DL 的方法處理具有圖結(jié)構(gòu)信息的一種網(wǎng)絡(luò)結(jié)構(gòu)，通過聚合、更新、融合等操作對圖結(jié)構(gòu)進行特征提取，快速處理圖數(shù)據(jù)。鑒于此，Dai 等人將RL 和GNNs 結(jié)合，提出一種新的優(yōu)化算法（S2V-DQN），即將RL 算法與圖嵌入結(jié)合，充分利用圖中的特殊結(jié)構(gòu)，讓S2V-DQN 模型泛化到更多新問題的實例中。文獻[67]利用GNNs 中S2V 的方法并配合使用RL 中Q-學(xué)習(xí)算法求解MVC、Max-cut、TSP問題。同時對比NCO 模型與啟發(fā)式算法，該模型將TSP 和MVC 問題的規(guī)模分別擴大到300 個和500 個節(jié)點，同時可以將訓(xùn)練完成的圖模型參數(shù)遷移到規(guī)模更大的圖上（最大1 200 個節(jié)點）。

Drori 等人采用RL 訓(xùn)練GNNs 模型參數(shù)的方法，提出一種基于GNNs 的RL 架構(gòu)，模型采用GAT編碼，解碼時加入Attention，求解MST、TSP、VRP 等經(jīng)典COP 問題。文獻[68]的實驗訓(xùn)練過程在小圖和隨機圖上，測試過程在大圖和真實圖上，最終使得所求解問題的近似比接近1。

針對處理百萬級大小圖上的困難問題，如何讓算法解決訓(xùn)練集中類似分布的問題實例，并將之延拓到更大規(guī)模的問題（百萬級節(jié)點）上，Mittal 等人提出GCOMB 框架（由SL 和RL 模型結(jié)合組成）克服上述問題，整個算法分為訓(xùn)練和推理兩個階段。訓(xùn)練階段第一步通過SL 的方式訓(xùn)練GCN 中的參數(shù)，采用新的概率貪婪機制預(yù)測單個節(jié)點的質(zhì)量和修剪不是解空間的集合，其本質(zhì)上是讓嵌入的點集合能夠反映每個節(jié)點對于解的重要程度，用于構(gòu)造嵌入輸入；第二步采用RL 中Q-學(xué)習(xí)算法體系分析剩余高質(zhì)量節(jié)點，把高質(zhì)量解挑選出，作為COP 問題的解。推理階段，先用訓(xùn)練完成的GCN 模型作為嵌入，然后通過Q-學(xué)習(xí)的Q 函數(shù)迭代計算問題的輸出解，即用貪心算法以增量方式構(gòu)造解。文獻[69]的實驗結(jié)果顯示，此框架在求解最大流問題的速度上比最前沿的學(xué)習(xí)算法快100 倍，解的質(zhì)量也略有提高。

為了更好解決具有圖結(jié)構(gòu)性質(zhì)的COP 問題，Barrett 等人提出探究組合最優(yōu)化（ECO-DQN）的方法框架，其模型架構(gòu)由S2V-DQN、RevAct、ObsTun、IntRew 組成。其中S2V-DQN 是Dai 等人提出的方法；RevAct 指允許一個節(jié)點翻轉(zhuǎn)多次仍可以被選擇的操作；ObsTun 指求解狀態(tài)包含7 個觀察步驟，如基于頂點狀態(tài)等，提供的信息呈現(xiàn)多元化，用于確定選取相應(yīng)動作的價值，實時提供歷史信息避免出現(xiàn)過擬合狀況，在有限步的回合保證外部和內(nèi)部獎勵回報符合馬爾可夫特性；IntRew 指通過獎勵塑造的形式，當(dāng)達到新的局部最優(yōu)解時，給一個小的中間獎勵作為內(nèi)部獎勵，很好地克服獎勵稀疏的問題。文獻[70]的實驗結(jié)果顯示，該框架下在Max-cut 上的求解效果優(yōu)于SOTA 的RL 方法。該算法可以從任意的初始解迭代，因此可以與其他搜索方法相結(jié)合，進一步提升解的質(zhì)量。

隨著AlphaGo Zero的成功應(yīng)用，Abe 等人將其思想延拓到COP 問題上，提出了CombOpt Zero 框架。模型利用MCTS 算法，在訓(xùn)練時提升了探索效率，增強了模型的泛化能力，在進行決策推理時增強了智能體的穩(wěn)定性。一般的COP 問題與圍棋相比有兩點不同：一是狀態(tài)由不同大小的圖表示，通過GNNs 處理非歐幾里德數(shù)據(jù)，能夠抽取數(shù)據(jù)中的有效特征；二是獲得獎勵的值域不固定，文獻[72]中通過回報歸一化技術(shù)來解決。文獻[72]還在網(wǎng)絡(luò)模型中嘗試不同GNNs 的變體模型，如圖同構(gòu)網(wǎng)絡(luò)（graph isomorphism network，GIN）、不變圖網(wǎng)絡(luò)（invariant graph network，IGN）。實驗在MVC、Max-cut、MC 問題上結(jié)果顯示此模型的泛化能力優(yōu)于S2V-DQN，且求解速度更快。

為了更好利用圖模型的優(yōu)勢，Bresson 等人將Transformer 架構(gòu)應(yīng)用到求解TSP 問題上，模型采用RL 算法訓(xùn)練參數(shù)，通過自注意力機制編碼，解碼中加入BS 推理技術(shù)。文獻[73]的實驗結(jié)果顯示，該框架的表現(xiàn)能力超越了基于學(xué)習(xí)的啟發(fā)式算法，采樣2 500 次后，50-TSP 問題的最優(yōu)間隙為0.004%，100-TSP 問題的最優(yōu)間隙為0.39%。

針對COP 中出現(xiàn)的大量與圖模型相關(guān)的問題，采用GNNs對圖模型進行預(yù)處理，文獻[66-74]中GNNs架構(gòu)對求解COP 問題顯示出優(yōu)異的效果，未來RL 和GNNs 模型的結(jié)合是一個較好的研究方向，GNNs 模型如圖8 所示。

圖8 GNNs模型示意圖Fig.8 Schematic diagram of GNNs model

2017 年Dai 等人提出一種處理圖結(jié)構(gòu)的COP問題的新方法。模型框架在PN 架構(gòu)基礎(chǔ)上加入Attention、Transformer、GNNs 等結(jié)構(gòu)處理圖信息。編碼-解碼時，采用圖嵌入操作，即將圖中的頂點信息映射成一個低維稠密向量，保證在原圖中相似的低維表達空間也接近，從而有利于信息提取。模型參數(shù)的訓(xùn)練大多采用Q-學(xué)習(xí)和Q-迭代的RL 算法，從而克服了獎勵延遲問題，保證參數(shù)更新的穩(wěn)定性和獨立性。圖的特殊結(jié)構(gòu)可以承載更多的節(jié)點信息，讓網(wǎng)絡(luò)模型學(xué)習(xí)到有效的特征信息，從而擴大COP 問題的求解范圍，同時圖的拓?fù)湫再|(zhì)導(dǎo)致RL 學(xué)習(xí)困難，巨大的解空間在搜索過程中也是困難的，限制了圖結(jié)構(gòu)模型的優(yōu)化效果，表4 分析了基于圖結(jié)構(gòu)模型的求解方法的局限性。

表4 圖結(jié)構(gòu)模型的局限性分析Table 4 Limitation analysis of graph structure model

3.4 基于強化學(xué)習(xí)結(jié)合傳統(tǒng)算法的求解方法

以PN 為基礎(chǔ)的RL 模型在求解COP 問題上已經(jīng)展現(xiàn)出良好的效果，為提高解的質(zhì)量，Deudon 等人改進Bello 等人的NCO 模型，編碼層延續(xù)了Transformer 架構(gòu)，其編碼的網(wǎng)絡(luò)架構(gòu)均由層疊的自注意力機制和逐點的全連接層組成，編碼層沒有使用LSTM 架構(gòu)。此模型中采用自注意力機制替換Seq2Seq 模型中的Attention。在解碼層改進策略網(wǎng)絡(luò)，采用PG 和REINFORCE 算法訓(xùn)練模型參數(shù)。模型在解的質(zhì)量與運行時間等方面的表現(xiàn)結(jié)果與Christofides算法的表現(xiàn)結(jié)果相當(dāng)，可以快速求解大規(guī)模的路徑優(yōu)化問題。實驗還將50-TSP 問題的模型參數(shù)遷移到100-TSP 問題上進行求解，其表現(xiàn)結(jié)果相當(dāng)，說明該模型有很好的泛化能力。此外，推理階段結(jié)合2-opt推理技術(shù)，可以快速提升解的質(zhì)量，體現(xiàn)出ML 與傳統(tǒng)算法結(jié)合的優(yōu)勢。

針對如何有效找到最優(yōu)解的確界問題，Cappart等人提出一種利用DRL 來確定變量順序的方法。決策圖（decision diagram，DD）是一種分層的有向無環(huán)圖，它得到的上界和下界比傳統(tǒng)方法更好，由于界的質(zhì)量又依賴于構(gòu)建DD 過程中變量的選取順序，采用NN 擬合Q-學(xué)習(xí)中Q 值的方法來確定變量順序。文獻[75]的實驗數(shù)據(jù)表明此方法所確定變量順序的結(jié)果比利用線性規(guī)劃取得的更優(yōu)。針對DRL 求解TSP 問題泛化能力弱且沒有一個系統(tǒng)的方法去提高解的質(zhì)量及無法有效證明近似比等缺陷，Cappart 等人又提出了一個基于DRL 結(jié)合約束規(guī)劃求解COP問題的模型，為了更好地結(jié)合這兩種方法，對于給定的COP 問題，首先采用動態(tài)規(guī)劃的方法對問題進行建模，然后將模型編碼成DRL 和約束規(guī)劃可以學(xué)習(xí)的輸入形式，在編碼中加入約束規(guī)劃可以更好地探索解空間，其中RL 中的網(wǎng)絡(luò)使用了GAT 和Transformer架構(gòu)作為圖嵌入。文獻[76]還考慮了三種約束規(guī)劃搜索策略：BB、迭代有限差異搜索法（iteration limited discrepancy search，ILDS）、基于搜索的重新啟動法（restart based search，RBS）。此方法求得的解與業(yè)界的專業(yè)求解器相比，在帶時間窗的旅行商問題（traveling salesman problem with time window，TSPTW）和4-PORT 問題上有很好的優(yōu)化效果，體現(xiàn)了DRL 結(jié)合約束規(guī)劃的方法具有一定優(yōu)勢。

為擴大求解范圍，Gao 等人采用AC 框架去學(xué)習(xí)一個局部搜索啟發(fā)式算法求解VRP 問題，模型通過GAT 進行編碼操作和使用GRU（gate recurrent unit）架構(gòu)進行解碼操作。兩者結(jié)合的學(xué)習(xí)方式可以解決大規(guī)模（400 個節(jié)點）的VRP 問題，優(yōu)化效果超過其他傳統(tǒng)的啟發(fā)式算法。

更進一步，Costa 等人提出一種由DRL 的方法學(xué)習(xí)2-opt操作的局部搜索啟發(fā)式算法。模型為一個策略神經(jīng)網(wǎng)絡(luò)，即采用PG 算法學(xué)習(xí)2-opt 操作，從隨機策略得到一個循環(huán)解，采用點注意力機制，使模型更容易拓展到更一般的情形k-opt 操作。文獻[78]的實驗結(jié)果顯示，此模型學(xué)習(xí)到的策略與先前的DL 方法對比，該方法會以更快的收斂速度逼近問題的最優(yōu)解。

在RL 算法的基礎(chǔ)上，為提高模型的伸縮性和魯棒性，Zheng 等人基于變鄰域搜索和LKH3 算法，提出一個VSR-LKH 新框架求解TSP 問題。該框架采用Q-學(xué)習(xí)、Sarsa、蒙特卡羅三個RL 算法取代LKH3算法的遍歷操作，即讓訓(xùn)練好的模型自動挑選適合的邊加入到候選集合中。實驗結(jié)果顯示，在TSPLIB數(shù)據(jù)集上測試，該方法求解的精度超越了傳統(tǒng)的LKH3 算法。

該思路是近年來諸多學(xué)者嘗試的一種新方法，在RL 中加入傳統(tǒng)算法構(gòu)造解的方法已經(jīng)在COP問題中取得較好成果。文獻[52,54,74-79]中的方法大多數(shù)還是需要結(jié)合一些傳統(tǒng)的方法，如經(jīng)過貪婪搜索、2-opt 操作、BS、采樣（sampling）、LK 等處理后，解的最優(yōu)間隙會隨之降低，進一步加快搜索時間和提升解的質(zhì)量，甚至?xí)絺鹘y(tǒng)的SOAT 模型。RL結(jié)合傳統(tǒng)方法的策略表明目前的模型仍然有較大的優(yōu)化空間，其中RL 模型學(xué)習(xí)效率低、收斂慢等問題會對COP 問題的求解造成影響，表5 分析了基于RL結(jié)合傳統(tǒng)算法模型的求解方法的局限性。

表5 RL 結(jié)合傳統(tǒng)算法模型的局限性分析Table 5 Limitation analysis of RL combined with traditional algorithm model

3.5 基于改進強化學(xué)習(xí)模型的求解方法

針對LHK 和傳統(tǒng)算法中出現(xiàn)的求解速度慢及求解節(jié)點稀疏等問題，使用經(jīng)典RL 模型不能很好選擇高質(zhì)量解，為此Lu 等人改進框架結(jié)構(gòu)，首次提出一種基于學(xué)習(xí)迭代的方法求解CVRP，采用分層和REINFORCE 算法訓(xùn)練模型。文獻[81]中模型優(yōu)化后的解在速度上超越傳統(tǒng)算法，并且求解100-CVRP 問題上達到了目前最好的結(jié)果（平均花費15.57）。

針對進化算法無法解決大規(guī)模優(yōu)化問題的缺陷，Li 等人改進框架結(jié)構(gòu)，提出一種基于DRL 解決多目標(biāo)COP 問題的框架（DRL-MOA），在PN 中融入分解策略和鄰居多參數(shù)傳遞策略，采用AC 算法訓(xùn)練模型參數(shù)。文獻[82]的實驗結(jié)果顯示，該模型下求解動態(tài)TSP 問題、多目標(biāo)TSP 問題的速度和泛化能力超越NSGA-Ⅱ、MOEA/D、MOGLS 等經(jīng)典多目標(biāo)優(yōu)化模型。

為了讓智能體快速、準(zhǔn)確調(diào)整自身的行為（通過環(huán)境和其他智能體的交互），Silva 等人對智能體改進，加入一個新的自適應(yīng)技巧，提出多元啟發(fā)式算法優(yōu)化多元智能體的框架（AMAM）。文獻[83]的實驗結(jié)果顯示，VRPTW 和UPMS 兩個COP 問題在AMAM框架下求解的質(zhì)量優(yōu)于其他傳統(tǒng)算法和單智能體優(yōu)化框架。

更進一步，Tassel 等人提出一個高效的DRL 模型求解PMSP 問題，該模型以端到端的形式輸出解，即在一個時間方案的限制下，模型可以自動地學(xué)習(xí)調(diào)度工作方案。文獻[84]的實驗結(jié)果顯示，該方法的表現(xiàn)超越了現(xiàn)有的DRL 方法，接近于當(dāng)前SOTA 傳統(tǒng)COP 問題的求解方法。

針對現(xiàn)有框架難以求解大規(guī)模TSP 和TSPTW問題，Ma 等人改進框架結(jié)構(gòu)，提出圖指向型網(wǎng)絡(luò)（graph pointer network，GPN）架構(gòu)。具體采用分層強化學(xué)習(xí)（hierarchical reinforcement learning，HRL）訓(xùn)練模型參數(shù)，編碼由點編碼和圖編碼兩部分組成，點編碼依賴于LSTM 架構(gòu)，由此得到城市的點嵌入，圖編碼依賴GNNs 架構(gòu)，得到城市的圖嵌入。解碼過程中加入Context vector操作后，使得attention 更好地分配到相應(yīng)節(jié)點，高效輸出COP 問題的最優(yōu)解。文獻[85]的實驗結(jié)果顯示該模型下求解小規(guī)模（50/100個節(jié)點）TSP 問題的模型參數(shù)可以很好地遷移到大規(guī)模（500/1 000 個節(jié)點）TSP 問題上，說明此操作提高了GPN 模型的泛化能力。此方法求解TSPTW 問題在時間和精度上超越了專業(yè)求解器和蟻群算法。另外，實驗證明了分層圖指向型網(wǎng)絡(luò)（hierarchical graph pointer network，HGPN）模型的優(yōu)化效果和收斂速度均優(yōu)于GPN。

Delarue 等人提出一種基于值函數(shù)的RL 框架（RLCA-16）求解CVRP 問題。該框架下每步更新考慮單個距離，而不是等待模型訓(xùn)練完成后獲取距離，通過一個直接的策略迭代更新每步距離。文獻[86]在CVRPLIB 數(shù)據(jù)集上測試，實驗結(jié)果顯示，相比其他RL 算法和傳統(tǒng)運籌優(yōu)化算法有較好的效果，該模型平均最優(yōu)間隙達到1.7%，并將此模型推廣到求解PCTSP 問題上。

該思路是近年來諸多學(xué)者進一步求解COP問題的一種新方法。針對目前RL 模型存在訓(xùn)練的不穩(wěn)定性和輸出難以收斂的問題，可以通過不斷改進RL 算法或者采用更多復(fù)雜DRL 的方法，更好地適應(yīng)各類COP 問題的求解?，F(xiàn)有DRL 模型中難免會存在價值網(wǎng)絡(luò)、策略網(wǎng)絡(luò)獎勵機制構(gòu)造不合理的情況，網(wǎng)絡(luò)結(jié)構(gòu)的瑕疵會對求解的質(zhì)量造成影響，表6 分析了基于改進RL 模型的求解方法的局限性。

表6 改進RL 模型的局限性分析Table 6 Limitation analysis of improved RL model

3.6 經(jīng)典COP 問題的實驗對比

由于TSP 是COP 問題中的經(jīng)典問題，TSP 又是VRP 的特例，這兩個問題都是運籌學(xué)和CO 領(lǐng)域的熱點問題。基于RL 求解COP問題的方法在TSP、VRP以及它們的變體問題上已經(jīng)取得較好結(jié)果，相比傳統(tǒng)算法，該方法是近年來研究的熱點內(nèi)容。表7、表8對上述求解方法在不同規(guī)模TSP、VRP 上的優(yōu)化效果進行實驗對比，實驗數(shù)據(jù)來自各個文獻的實驗結(jié)果，均通過Pytorch、TensorFlow 深度學(xué)習(xí)框架實現(xiàn)。

表7 不同模型在TSP 上的優(yōu)化效果比較Table 7 Comparison of optimization effects of different models on TSP

表8 不同模型在VRP 上的優(yōu)化效果比較Table 8 Comparison of optimization effects of different models on VRP

通過實驗結(jié)果比較可以看出，Joshi（BS）和Costa的方法在20-TSP 問題上與專業(yè)求解器的優(yōu)化效果基本相同，但運行時間相對較慢。Kool（GS）的方法可以在短時間高效求解，但精度略低于最優(yōu)解。Bresson的方法可以達到最優(yōu)解，求解速度超越了傳統(tǒng)的優(yōu)化器和目前的SOTA 模型，但求解范圍有限?？傮w來看，目前RL 方法求解TSP 在精度、泛化能力等方面有許多問題待解決，僅僅在推理速度方面超越目前最先進的求解器Concorde、Gurobi、OR-Tools。改進Transformer 架構(gòu)以及結(jié)合GNNs提升模型穩(wěn)定性是未來一個重要的研究內(nèi)容。

通過實驗結(jié)果比較可以看出，Lu和Chen的方法在精度上超越了LKH3 和OR-Tools 等專業(yè)求解器，運行時間慢于OR-Tools。Kool的貪婪搜索方法在幾秒內(nèi)可得到近似解，適用于在線快速求解。近年來多數(shù)采用RL 結(jié)合傳統(tǒng)算法的方式求解VRP問題，僅僅在推理速度超越目前最先進的啟發(fā)式算法LKH3 和求解器OR-Tools。由于VRP 問題復(fù)雜的約束條件，目前的整體研究較少，如何選取適合的RL算法和融入傳統(tǒng)算法的思想是未來一個重要的研究內(nèi)容。

3.7 RL 求解COP 問題的方法總結(jié)

由上述綜述方法可見，以RL 模型為基礎(chǔ)的求解方法在求解速度、求解規(guī)模上超越了傳統(tǒng)算法，甚至可以求解傳統(tǒng)算法難以解決的問題，是近年來研究的熱點方法，此方法不受人工經(jīng)驗的限制，可以自動發(fā)現(xiàn)求解問題的策略，模型一旦訓(xùn)練完成，可對任意類似問題進行泛化求解，擺脫了傳統(tǒng)算法針對相同結(jié)構(gòu)問題專門設(shè)計算法的弊端。隨著問題規(guī)模的增大，RL 的優(yōu)化效果和速度遠(yuǎn)遠(yuǎn)超越傳統(tǒng)算法，其中基于RL 結(jié)合傳統(tǒng)算法的求解方法、部分改進RL 模型的求解方法取代了人工設(shè)計的搜索規(guī)則，對搜索算法進行自主學(xué)習(xí)，但本質(zhì)上仍然是迭代求解，速度遠(yuǎn)不如端到端的模型?；贜CO 模型的求解方法、動態(tài)輸入的COP 模型的求解方法、圖結(jié)構(gòu)模型的求解方法等都是以端到端的形式輸出解，解的收斂性和質(zhì)量難以保證。由于結(jié)合PN 和GNNs，加入Attention機制，模型的性能得到提高，權(quán)衡優(yōu)化效果和求解速度，可以根據(jù)實際問題的需求選擇不同的優(yōu)化方法。

基于RL 的COP 求解方法是一個新興的研究領(lǐng)域，處于剛剛起步的階段，到目前為止，取得的成果只能驗證這個思路是可行的，并沒有取得重大實質(zhì)性的突破，關(guān)鍵在于缺少理論基礎(chǔ)和近似比的保證。為了結(jié)合兩者的優(yōu)點，如采用RL 方法并加入相應(yīng)的后處理操作，直接根據(jù)所給定的問題實例以端到端的方式輸出解，或者將RL 算法加入到傳統(tǒng)算法設(shè)計中，如建立RL 模型學(xué)習(xí)策略指導(dǎo)分支定界算法的執(zhí)行。同時，可以看到一些工作中，基于RL 的方法已經(jīng)能在一些實例中與傳統(tǒng)SOTA 算法相當(dāng)，從其發(fā)展歷程可以看出，這個方向正隨著ML 中的一些算法的蓬勃發(fā)展而快速推進，相信將來會有更多的想法被提出并融入到COP 中，它會成為傳統(tǒng)算法的有力補充甚至?xí)耆娲鷤鹘y(tǒng)算法，期待RL 與CO 可以緊密結(jié)合，共同發(fā)展，推動NP 問題的求解算法與理論進展。

4 研究展望

RL 是ML 中的一個研究熱點，RL 解決問題的方式和學(xué)習(xí)策略是實現(xiàn)智能化的一個重要途徑，尤其是DRL 這種端到端的感知與決策系統(tǒng)的快速發(fā)展，使得這類方法廣泛應(yīng)用于智能交通、機器人、計算機視覺等領(lǐng)域。COP 問題又是實際生活中普遍存在的，傳統(tǒng)的方法如精確算法、近似算法、啟發(fā)式算法等，很難在可接受的時間內(nèi)獲取到問題實例的最優(yōu)解。目前RL 求解COP 問題的方法與傳統(tǒng)方法相比，是一種全新的數(shù)據(jù)驅(qū)動的求解方式，也是一個新型交叉學(xué)科。

近年來基于RL 求解COP 問題的相關(guān)工作已經(jīng)大量出現(xiàn)，在運籌優(yōu)化領(lǐng)域已經(jīng)形成新的研究熱點，如Mazyavkina 等人的綜述主要梳理RL 求解COP問題的進展，提供了運籌優(yōu)化和ML 的必要背景，比較了RL 算法和傳統(tǒng)優(yōu)化算法求解COP 問題的效果，說明未來可以采用RL 的方法求解COP 問題。Yang等人的綜述主要針對RL 在COP 問題中的應(yīng)用，以TSP 問題為例，比較了RL 算法與傳統(tǒng)算法的差異。隨著ML 的發(fā)展，闡明了計算能力對RL 中算法的影響，文獻[91]闡明了DL 的方法可以遷移到COP 問題上來，可以優(yōu)化TSP 問題的結(jié)果。Vesselinova 等人的綜述重點梳理RL 解決圖上的COP 問題的相關(guān)文獻，以及總結(jié)拓展COP 問題在通訊領(lǐng)域中的應(yīng)用。

雖然RL 理論及其應(yīng)用已經(jīng)取得重大進展，現(xiàn)有研究也展現(xiàn)出RL 求解COP 問題的優(yōu)勢，相關(guān)的應(yīng)用研究仍處于探索階段，希望各位學(xué)者可以從以下幾個方面繼續(xù)研究：

（1）擴大COP 問題的求解范圍：針對傳統(tǒng)算法求解大規(guī)模COP 問題速度過慢的問題，可借鑒分而治之的思想，通過子圖采樣、圖轉(zhuǎn)換、分割等技術(shù)簡化搜索空間的大小，再采用熱圖合并、主動搜索等技術(shù)合成解，從而在RL 領(lǐng)域擴大求解范圍。比如研究HRL，即將大規(guī)模問題分解成若干子問題來學(xué)習(xí)層次化策略，再組合子問題的策略形成全局的最優(yōu)策略。同時如何有效地將其與COP 問題進行結(jié)合及解決狀態(tài)分解過程的有效信息丟失問題是一個很好的研究點。

（2）求解更復(fù)雜、多類型的COP 問題：目前大多數(shù)學(xué)者的研究集中在經(jīng)典的TSP、VRP 等問題上，且研究內(nèi)容相對單一簡單，實際上COP 問題具有動態(tài)性、多目標(biāo)、多約束條件等特征，傳統(tǒng)算法難以求解該類問題以及變體問題。未來在追求模型的精度和快速求解的要求下，基于RL 對多目標(biāo)優(yōu)化、多約束條件、在線動態(tài)求解等問題進行求解是一個重要的研究熱點。

（3）模型上的改進：目前的研究中，許多優(yōu)化模型是以端到端的形式輸出解，從而解的質(zhì)量較差，因此在模型改進上有很大的提升空間。同時BS、MCTS耗時長等問題影響其效率，為了提高求解速度和求解質(zhì)量，未來可以進一步結(jié)合GNNs 和DRL，改進Transformer 架構(gòu)中編碼-解碼的結(jié)構(gòu)，考慮在網(wǎng)絡(luò)結(jié)構(gòu)上結(jié)合微分方程數(shù)值解的方法（用于網(wǎng)絡(luò)參數(shù)的權(quán)重學(xué)習(xí)）進行研究，如何提高網(wǎng)絡(luò)性能和壓縮模型的大小是一個較好的研究點，進一步改善模型訓(xùn)練過程中收斂性差、不穩(wěn)定等問題。

（4）應(yīng)用范圍的推廣：許多運籌優(yōu)化問題都滿足序貫決策的性質(zhì)，與高性能計算相結(jié)合，可以應(yīng)用嘗試快速求解各種決策問題，如何利用基于RL 求解COP 問題的方法高效解決工程實際中的動態(tài)路徑規(guī)劃問題、在線調(diào)度問題是一個重要的研究方向。