基于強(qiáng)化學(xué)習(xí)的組合優(yōu)化綜述

顧一凡

（南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇南京 210016）

0 引言

優(yōu)化問題的主要重點(diǎn)在于在不同可能性中尋找當(dāng)前問題的最優(yōu)解或最佳配置。這一類問題通常被分成兩種：具有連續(xù)變量的問題和具有離散變量的問題［1］。例如：在凸優(yōu)化問題中的一個(gè)可行解通常屬于實(shí)數(shù)空間，這樣的解被稱為一個(gè)連續(xù)優(yōu)化的可行解，而查找一系列城市的游覽路徑則是離散的優(yōu)化問題。一般而言，在離散空間中查找解的問題被稱為組合優(yōu)化（CO）問題。

當(dāng)前RL 與CO 結(jié)合有兩種不同方式：主體學(xué)習(xí)與聯(lián)合學(xué)習(xí)方式。主體學(xué)習(xí)方式可通過智能體直接作出決定，該方法直接通過RL 策略構(gòu)造問題的解或完整解的一部分，而不需要求解器的反饋。例如，在TSP 問題中，神經(jīng)網(wǎng)絡(luò)首先對智能體進(jìn)行參數(shù)化處理，然后該神經(jīng)網(wǎng)絡(luò)逐步構(gòu)建路徑，將路徑長度作為獎(jiǎng)勵(lì)來更新策略。聯(lián)合學(xué)習(xí)方式則是與現(xiàn)存的求解器聯(lián)合訓(xùn)練RL，使其可提升CO 問題的解在不同性能度量指標(biāo)上的表現(xiàn)。例如，在混合整數(shù)線性方程（Mixed-Integer Linear Program，MILP）中，常用方法是“分支限界”，其在每一步都選擇樹子節(jié)點(diǎn)的分支規(guī)則，該方法可能會對樹的整體大小及算法運(yùn)行時(shí)間產(chǎn)生影響。另外，分支限界屬于啟發(fā)式方法，需要一些專家知識對參數(shù)進(jìn)行調(diào)整。值得注意的是，可通過RL 智能體接收與運(yùn)行時(shí)間成正比的獎(jiǎng)勵(lì)訓(xùn)練智能體學(xué)習(xí)節(jié)點(diǎn)選擇策略。

通常來說，使用RL 解決CO 問題可看作是學(xué)習(xí)解決此類問題的策略，而不是使用運(yùn)籌學(xué)中人為設(shè)定的方法，在該層次上可將其分為學(xué)習(xí)構(gòu)造啟發(fā)式以及改進(jìn)啟發(fā)式方法。學(xué)習(xí)構(gòu)造啟發(fā)式方法通過學(xué)習(xí)策略不斷構(gòu)造解，而改進(jìn)啟發(fā)式方法則是學(xué)習(xí)一種基于迭代的改進(jìn)策略，該方法試圖解決在啟發(fā)式學(xué)習(xí)中遇到的一些問題，即需要使用一些額外過程以找到良好的解決方案，例如采樣等。

1 相關(guān)基礎(chǔ)知識

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

首先給出關(guān)于組合優(yōu)化問題的基本定義：

定義1（組合優(yōu)化問題）：假設(shè)Ω 是解的決策域，且F:Ω →R是一個(gè)決策域到目標(biāo)域映射的目標(biāo)函數(shù)。組合優(yōu)化問題旨于找到目標(biāo)域上的最優(yōu)值，以及找到該最優(yōu)值在決策域Ω 上對應(yīng)解的結(jié)構(gòu)。

通常來說，組合優(yōu)化問題的決策域Ω 是有限的，且存在局部最優(yōu)解，可通過比較所有可行解得到。但是，現(xiàn)實(shí)中的組合優(yōu)化問題一般都是NP 難問題，找到一個(gè)最優(yōu)解往往需要較高的時(shí)間成本，因此傳統(tǒng)方法是在一定時(shí)間內(nèi)找到一個(gè)折中的解。

下面主要介紹使用RL 解決的一些特殊的組合優(yōu)化問題，這些問題在現(xiàn)實(shí)中有著廣泛應(yīng)用，例如最大分割問題、旅行商問題、財(cái)務(wù)投資組合管理問題等。

定義2（最大切割問題）：給定一個(gè)圖G=(V,E)，找到一個(gè)點(diǎn)集的子集S?V，且該子集最大化分割C(S,G)=∑i∈S,j∈VSwi,j，其中wi,j∈W是連接頂點(diǎn)i與邊j的權(quán)重。

定義3（旅行商問題（TSP））：給定一個(gè)完整的加權(quán)圖G=(V,E)，其目標(biāo)是找到一個(gè)最小權(quán)重的路徑，使得每個(gè)城市只被訪問一遍。

定義4（最大獨(dú)立集（MIS））：給定一個(gè)圖G=(V,E)，找到一個(gè)點(diǎn)集的子集S?V，使S中沒有兩個(gè)頂點(diǎn)通過E的邊相連，且最小化目標(biāo)為|S|。

1.2 強(qiáng)化學(xué)習(xí)

一般來說，RL 智能體通過馬爾可夫決策過程（MDP）指導(dǎo)智能體在環(huán)境中進(jìn)行動(dòng)作［2］，并通過收集相關(guān)獎(jiǎng)勵(lì)來更新模型。環(huán)境由狀態(tài)集合S 中的狀態(tài)組成，狀態(tài)集S 可以是離散的，也可以是連續(xù)的。智能體所有可能執(zhí)行的動(dòng)作都在動(dòng)作集合A 中，智能體的主要目標(biāo)是通過執(zhí)行動(dòng)作增加獲得的獎(jiǎng)勵(lì)值R。從S 中每個(gè)狀態(tài)s 到最佳動(dòng)作a 的映射函數(shù)被稱為策略，表示為π(s)。因此，為解決MDP 問題，需要找到最佳策略π*以最大化預(yù)期獎(jiǎng)勵(lì)：

其中，獎(jiǎng)勵(lì)值可表示為：

智能體在經(jīng)過N 步之后重啟，如果N 趨向于∞，則表示智能體以一種無回合的形式進(jìn)行訓(xùn)練。一般來說，γ 體現(xiàn)智能體關(guān)注短期獎(jiǎng)勵(lì)的程度，當(dāng)γ<1 時(shí)，其會阻止累計(jì)獎(jiǎng)勵(lì)被無限放大。

2 強(qiáng)化學(xué)習(xí)應(yīng)用于組合優(yōu)化分類

在過去幾十年中，科學(xué)家們研究了解決CO 問題的各種可能方法，因此也提出了許多CO 求解算法，包括基于機(jī)器學(xué)習(xí)的方法等。如文獻(xiàn)［3］從機(jī)器學(xué)習(xí)的角度總結(jié)了解決CO 問題的方法，并列出了幾個(gè)有效算法；文獻(xiàn)［4］致力于描述圖神經(jīng)網(wǎng)絡(luò)（GNN）及其在CO 問題上的可能應(yīng)用；文獻(xiàn)［5］通過調(diào)查研究，介紹了使用機(jī)器學(xué)習(xí)（ML）方法解決CO 問題的最新研究成果。

本文僅專注于使用RL 解決CO 問題，以下主要從兩個(gè)方向?qū)L 解決CO 問題的相關(guān)研究進(jìn)行分類：①基于值函數(shù)的RL 方法；②基于策略的RL 方法，具體對應(yīng)成果如表1所示。對于每一種方法，以下章節(jié)會進(jìn)行詳細(xì)介紹，并給出相關(guān)工作的不足及需要改進(jìn)的方向。

Table 1 RL methods for solving CO problems（value function，strategy）表1 用于解決CO 問題的RL 方法（值函數(shù)、策略）

3 強(qiáng)化學(xué)習(xí)應(yīng)用于組合優(yōu)化的方法

3.1 基于值函數(shù)的方法

Q-learning［15］是一個(gè)典型的基于值函數(shù)的RL 方法，但對于大部分實(shí)際問題而言，要找到最優(yōu)解十分困難。NP 難問題因其對應(yīng)的RL 狀態(tài)與動(dòng)作空間連續(xù)或過大，使得傳統(tǒng)RL 方法無法得到有效使用。隨著深度學(xué)習(xí)的崛起，證明神經(jīng)網(wǎng)絡(luò)（NN）對于高維輸入數(shù)據(jù)可以學(xué)習(xí)出有效的函數(shù)逼近方式，從而促進(jìn)了深度Q 網(wǎng)絡(luò)（DQN）的發(fā)展［16］。由于結(jié)合了神經(jīng)網(wǎng)絡(luò)（NN）與Q 學(xué)習(xí)的優(yōu)點(diǎn)，DQN 已成為目前解決許多強(qiáng)化學(xué)習(xí)問題最受歡迎的方法之一。

對于大多數(shù)問題，如最大分割［17］、TSP 問題［18］等，現(xiàn)有研究使用了與DQN 相同的Q 值更新公式，即使用圖形嵌入網(wǎng)絡(luò)對Q 函數(shù)進(jìn)行參數(shù)化。文獻(xiàn)［17］中使用圖注意力網(wǎng)絡(luò)［19］與一種transformer 結(jié)構(gòu)［20］對CO 問題進(jìn)行編碼；文獻(xiàn)［18］使用了structure2vec 圖神經(jīng)網(wǎng)絡(luò)，這也是一種流行的圖編碼技術(shù)。

文獻(xiàn)［18］旨在解決TSP 問題，其主要通過DQN 學(xué)習(xí)良好的啟發(fā)式策略，然后將其直接集成到各種基于約束的算法中，如分支限界以及迭代的差分搜索等。在訓(xùn)練中，從某些分布中隨機(jī)抽取測試用例Qi，計(jì)算其獎(jiǎng)勵(lì)值函數(shù)為其中，UB(Qi)表示Qi在值函數(shù)中的上界，c 表示成本，ρ是一個(gè)比例因子。

最近有一些研究專注于解決最大公共子圖問題［7］，其構(gòu)建了一種聯(lián)合子圖節(jié)點(diǎn)的新型嵌入網(wǎng)絡(luò)，以便使用單個(gè)網(wǎng)絡(luò)嵌入兩個(gè)圖，網(wǎng)絡(luò)權(quán)重更新方法與DQN 一致。

上述工作都會遇到一個(gè)與DQN 共同的問題，即DQN依次構(gòu)造最優(yōu)解使得算法不能重新考慮次優(yōu)解。為解決該問題，對DQN 的訓(xùn)練過程進(jìn)行了修改，形成了另外一組解決CO 問題的RL 方法［8］，其使用在分類領(lǐng)域很受歡迎的協(xié)同訓(xùn)練方法構(gòu)建CO 問題的順序策略。本文介紹了針對最小頂點(diǎn)覆蓋問題的兩種策略學(xué)習(xí)方法：第一種方法復(fù)制文獻(xiàn)［18］中描述的策略，第二種方法利用分支限定法解決整數(shù)線性規(guī)劃問題。通過創(chuàng)建一種與模仿學(xué)習(xí)［21］相似的算法，根據(jù)兩種策略之間的信息交互識別出哪種方法更具有優(yōu)勢，以此開展更新過程。

3.2 基于策略的方法

文獻(xiàn)［11］進(jìn)行了將策略梯度算法應(yīng)用于組合優(yōu)化的首次嘗試，即使用有學(xué)習(xí)基線的強(qiáng)化學(xué)習(xí)算法解決TSP 與背包問題。文獻(xiàn)［22］提出指針網(wǎng)絡(luò)體系結(jié)構(gòu)作為編碼的輸入網(wǎng)絡(luò)，該方法使用解碼器的指針機(jī)制，根據(jù)輸入的分布順序構(gòu)造CO 問題的可行解，類似于文獻(xiàn)［23］的異步并行訓(xùn)練。

文獻(xiàn)［11］中提出的方法由于其動(dòng)態(tài)性質(zhì)不能直接應(yīng)用于車輛路徑規(guī)劃問題（VRP），即節(jié)點(diǎn)一旦被訪問，該節(jié)點(diǎn)則不能再次被訪問。文獻(xiàn)［12］對文獻(xiàn)［11］的方法進(jìn)行拓展以找到VRP 的可行解。具體來說，其通過使用一維的卷積嵌入層替換LSTM 單元來簡化編碼器，從而使模型對輸入不敏感，因此不同的輸入順序不會影響模型性能，之后使 用RL 對TSP 與VRP 進(jìn)行策略學(xué)習(xí)，而A3C［23］中使用隨機(jī)VRP 進(jìn)行策略學(xué)習(xí)。

另一個(gè)重要的CO 問題是3D 裝箱問題。文獻(xiàn)［13］使用RL 方法制定策略，該策略代表物品的最佳包裝順序。在提供的入庫商品序列特征上進(jìn)行算法訓(xùn)練，通過計(jì)算包裝商品的表面積評估生成的策略，其中使用啟發(fā)式算法生成的結(jié)果作為訓(xùn)練基準(zhǔn)。為了進(jìn)行推斷，使用貪婪的解碼方式以及一種通過波束搜索的方法進(jìn)行采樣。文獻(xiàn)［14］將該方法進(jìn)一步拓展到監(jiān)督學(xué)習(xí)方向，采用RL 與監(jiān)督學(xué)習(xí)相結(jié)合的方法。文獻(xiàn)［24］提出一種條件查詢學(xué)習(xí)（CQL）方法，使用注意機(jī)制調(diào)節(jié)裝箱過程中需要執(zhí)行的3 個(gè)子動(dòng)作，即盒子的選擇、旋轉(zhuǎn)與定位。

文獻(xiàn)［25］通過學(xué)習(xí)改進(jìn)啟發(fā)式方法解決VRP 問題、在線作業(yè)調(diào)度問題等。該算法不斷重寫解的不同部分，直到收斂為止，而不是按順序構(gòu)建解。狀態(tài)空間表示為問題所有解的集合，而動(dòng)作集則由區(qū)域（圖中的節(jié)點(diǎn)）及其相應(yīng)的重寫規(guī)則組成。文獻(xiàn)［25］通過Q-Actor-Critic 算法共同訓(xùn)練區(qū)域選擇和規(guī)則選擇策略。

與之相似的是，文獻(xiàn)［26］提出通過學(xué)習(xí)改進(jìn)啟發(fā)式方法，使用2-opt、交換與重定位方法解決CVRP 與TSP 問題。此外，還可以學(xué)習(xí)改進(jìn)啟發(fā)式方法并使用2-opt 解決文獻(xiàn)［26］中的缺點(diǎn)，該缺點(diǎn)使得策略網(wǎng)絡(luò)體系結(jié)構(gòu)很難拓展到k-opt［27-28］。為此，將圖形神經(jīng)網(wǎng)絡(luò)與遞歸神經(jīng)網(wǎng)絡(luò)一起作為解碼器，并在解碼器中使用指向策略，根據(jù)指向機(jī)制順序輸出k-opt 操作。文獻(xiàn)［29］進(jìn)一步擴(kuò)展了上述工作，使用通用的銷毀與維修操作改進(jìn)啟發(fā)式算法。文獻(xiàn)［30］提出深度自動(dòng)延遲策略（ADP），將圖卷積網(wǎng)絡(luò)編碼器與最近策略優(yōu)化（PPO）算法結(jié)合使用，可通過回滾過程學(xué)習(xí)最大策略，排除無效解。

4 結(jié)語

本文介紹了幾種通過強(qiáng)化學(xué)習(xí)方法解決經(jīng)典組合優(yōu)化問題的算法，隨著相關(guān)研究的發(fā)展，各種新算法不斷被提出。這些問題都是從計(jì)算時(shí)間的角度處理大規(guī)模問題，這也使得計(jì)算時(shí)間成為相關(guān)算法與傳統(tǒng)算法性能對比時(shí)一個(gè)重要的考慮因素。此外，另一個(gè)需要解決的問題是提高算法策略的泛化能力，即在小規(guī)模CO 問題上訓(xùn)練后得到的模型可用于大規(guī)模組合問題。在同一研究領(lǐng)域，將已有RL 模型遷移到其他具有不同分布特性的問題上也是一個(gè)具有前景的研究方向。最后，當(dāng)前方法都是使用RL 方法的變體結(jié)合更高效、穩(wěn)定的數(shù)據(jù)采樣方法，這種結(jié)合方式能夠有效地解決組合優(yōu)化問題。