?PaperWeekly 原創 · 作者 |?王馨月

學校 |?四川大學本科生

研究方向?|?自然語言處理

摘要

推許多解決組合優化問題的傳統算法都涉及使用手工構造的啟發式算法，這些啟發式算法能夠依次地構造解決方案。這種啟發式方法是由領域專家設計的，且一般由于問題的困難性，這種方法不是最佳的。強化學習（RL）提出了一種很好的選擇，使用監督或自我監督的方式訓練 agent 來自動搜索這些啟發式方法。

在這篇調研中，我們探索了將 RL 框架應用于困難的組合問題的最新進展。我們的調研為運籌學和機器學習社區提供了必要的背景，并展示了推動領域向前發展的工作。我們將最近提出的 RL 方法并置在一起，列出了每個問題改進方法的時間線，并與傳統算法進行了比較，這表明 RL 模型可以成為解決組合問題的有希望的方向。

論文標題：

Reinforcement Learning for Combinatorial Optimization: A Survey

論文作者：

Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, Evgeny Burnaev

論文鏈接：

https://arxiv.org/abs/2003.03600

?

引言

優化問題涉及在不同可能中找到優化配置或是“值”，他們天然地屬于兩個類別中的一個：具有連續變量和離散變量的配置。比如，找到一個凸規劃問題的解決方案是一個連續優化問題，而在圖的所有路徑中找到最短路徑則是一個離散優化問題。

有時兩者之間的界線很難確定。比如，在連續空間中的線性規劃任務可以看作是一個離散的組合問題，因為他的解決方案在凸多邊形的頂點的有限集合中，這已經由 Dantzig 的算法證明。通常，離散空間中的優化問題稱為組合優化（CO）問題，且與連續空間中的問題相比擁有不同類型的解決方案?？梢詫?CO 問題表達如下：

定義1：令 是一個元素的集合， 是代價函數。組合優化問題旨在找到函數 的最優值以及在域 上實現該最優值的任何對應的最優元素。

通常，集合 是是有限的，在這種情況下，存在全局最優值。因此，對于任何CO問題，都可以通過比較所有 中的元素 來得到平凡解。注意，定義 1 還包括決策問題的情況，當解決方案是二元（或更普遍的多類）的解決方案時，錯誤答案的成本比正確答案的成本高。

組合問題的一個常見示例是旅行商問題（TSP）。目標是提供訪問每個頂點并返回到初始端點的最短路徑，或者換句話說，在全連接的加權圖中找到具有最小長度的漢密爾頓回路 。在這種情況下，所有漢密爾頓回路都定義了一組元素，即 所有漢密爾頓路徑，以及與每個漢密爾頓賄賂相關的成本是回路中邊 的權重 的總和 ，即 。

CO 問題的另一個示例是混合整數線性規劃（MILP），其目標是對于滿足約束 , 的參數 和 ，給定向量 ，最小化 。

許多 CO 問題都是 NP-hard 問題，沒有一個有效的多項式時間解。因此，有很多近似或啟發式解決這些問題的算法被設計出來。近幾年的新興趨勢之一是通過訓練機器學習（ML）算法來解決 CO 問題。例如，我們可以在已經解決的 TSP 實例的數據集上訓練 ML 算法，以決定對于新 TSP 實例下一步要移動到哪個節點。

我們在本次調研中考慮的 ML 的一個特定分支稱為強化學習（RL），對于給定的 CO 問題，它可以定義一個環境并在該環境中起作用的 agent 構造了解決方案。為了將 RL 應用于 CO，將問題建模為順序決策過程，在此過程中，agent 將通過執行一系列操作來與環境交互以找到解決方案。馬爾科夫決策過程（MDP）為建模此類問題提供了廣泛使用的數學框架。

定義2：MDP 可以被定義為一個元組 ，其中：

1.? - 狀態空間，。在此調研中，組合優化問題的狀態空間通常由以下兩種方式之一進行定義。一組方法構造解決方案時，將其逐步定義為問題的部分解決方案集（例如，TSP 問題的部分構造路徑）。另一組方法從對問題的次優解決方案開始，然后迭代地加以改善（例如，TSP 的次優方案）；

2.? - 動作空間，。動作表示對部分解決方案的更改或正在更改的完整解決方案（例如，更改 TSP 路徑中的節點順序）；

3.? - 獎勵函數是從狀態和動作到實數的映射 。獎勵表示在特定狀態下選擇的動作如何改善或惡化該問題的解決方案（例如，TSP 的行程長度）；

4.? - 過渡函數 響應于動作，控制從一種狀態到另一種狀態的過渡動力學。在組合優化設置中，過渡動力學通常是確定性的，并且事先已知。

5.? - 標量折扣因子，。折扣因子鼓勵 agent 為短期獎勵考慮更多；

6.? - Horizon，它定義了 epoch 的長度，其中 epoch 被定義為序列 。對于逐步構造解決方案的方法，情節的長度自然是由執行的操作數定義的，直到找到解決方案為止。對于迭代方法，引入了一些人工停止標準。

Agent 在 MDP 中行動的目標是找到一個將狀態映射為行動的策略函數 。解決 MDP 意味著找到使預期的累積折扣總和最大化的最佳策略：

一旦為 CO 問題定義了 MDP，我們就需要決定 agent 如何搜索最優策略 。廣義上講，有兩種 RL 算法：

1. 基于價值的方法：首先計算價值行動函數 ，作為給定狀態 ???? 并采取行動 a 的策略 的預期報酬。然后，agent 的策略對應于針對給定狀態選擇一個最大化 的動作。基于價值的方法之間的主要區別在于如何準確有效地估算 。

2.基于策略的方法：直接將 agent 的策略建模為參數函數 。通過收集 agent 在環境中先前做出的決定（也就是經驗），我們可以通過最大化最終獎勵 來優化參數 。基于策略的方法之間的主要區別在于用于找到最大化預期的獎勵總和的函數 的優化方法。

可以看出，RL 算法取決于將 MDP 狀態作為輸入并輸出動作值或動作的函數。狀態代表有關該問題的一些信息，例如給定的圖或當前的 TSP 路徑，而 Q 值或動作是數字。因此，RL 算法必須包括編碼器 encoder，即將狀態編碼為數字的函數。已經提出了許多針對 CO 問題的編碼器，包括遞歸神經網絡 RNN，圖神經網絡 GNN，基于注意力的網絡和多層感知器。?

總而言之，圖 1 中顯示了用于解決 RL 的 CO 問題的 pipeline。首先根據 MDP 重新構造 CO 問題，即我們為給定問題定義狀態、動作和獎勵。然后我們定義狀態的編碼器，即對輸入狀態進行編碼并輸出數字向量（每個動作的 Q 值或概率）的參數函數。

下一步是實際的 RL 算法，該算法確定 agent 如何學習編碼器的參數并為給定的 MDP 做出決策。代理選擇動作后，環境移至新狀態，并且 agent 會因其執行的動作而獲得獎勵。然后，該過程從分配的時間預算內的新狀態開始重復。訓練完模型的參數后，agent 就能針對問題的未知實例搜索解決方案。?

RL 領域技術和方法的最新成功應用激發了我們的工作以解決 CO 問題。盡管原則上可以通過運籌學界中已有相關文獻的強化學習算法來解決許多實際的組合優化問題，但我們將專注于針對 CO 問題的 RL 方法。這篇綜述涵蓋了最新的論文，這些論文展示了如何將強化學習算法應用于重新規劃和解決一些規范的優化問題，例如旅行商問題（TSP）、最大割（Max-Cut）問題、最大獨立集（MIS） 、最小頂點覆蓋（MVC）和裝箱問題（BPP）。

總結和進一步的工作

前面的部分介紹了幾種通過使用強化學習算法來解決經典組合優化問題的方法。由于該領域已經證明可以與最新的啟發式方法和求解器相提并論，因此我們期望在以下可能的方向上出現新的算法和方法，我們認為這是有希望的：?

推廣到其他問題：在第五節中，我們提出了 RL-CO 領域當前狀態的主要問題之一，即有限的實驗比較。確實，數學問題的 CO 組非常龐大，并且當前的方法通常需要針對一組具體的問題實施。但是，RL 領域已經采取了一些措施，將學習到的策略推廣到未解決的問題。對于 CO，這些看不見的問題可能是同一問題的較小實例、分布不同的問題實例、甚至是另一組 CO 問題中的問題實例。我們相信，盡管這個方向充滿挑戰，但它對于 RL-CO 領域的未來發展是極有希望的。?

提高解決方案質量：與商業解決方案相比，本調研中展示的許多先前的工作都表現出卓越的性能。而且，它們中的一些還已經達到了與最優解或通過啟發式算法實現的解相等的質量。但是，這些結果僅適用于復雜度較低的 CO 問題，例如節點數量較少的問題。這給我們留下了在客觀質量方面進一步改進當前算法的可能性。某些可行的方法可能是將經典 CO 算法與 RL 方法進一步結合，例如，使用模仿學習。?

填補 gap：我們前面已經提到過，對 RL-CO 方法進行分類的方法之一是將它們分為聯合方法和構造方法。表 1、2、3、4、5 包含有關每篇評論文章的這些標簽的信息，從中，我們可以為每種 CO 問題確定一些未探索的方法。從表3中可以看出，還沒有任何聯合和構造算法來解決 Bin Packing 問題的方法被發表?？梢詫⑾嗤倪壿嫅糜诒?3 的最小頂點問題，其中沒有聯合構造和聯合非構造類型的方法。探索這些算法的可能性不僅可以為我們提供新方法，而且還可以為我們提供有關這些方法有效性的有用見解。?

總之，與傳統的啟發式方法相比，由于解決方案質量方面的有效性、優于現有算法的能力以及巨大的運行時間收益，我們可以看到將 RL 用于 CO 問題的領域對于 CO 研究來說是非常有希望的方向。?

更多閱讀

#投 稿?通 道#

?讓你的論文被更多人看到?

如何才能讓更多的優質內容以更短路徑到達讀者群體，縮短讀者尋找優質內容的成本呢？答案就是：你不認識的人。

總有一些你不認識的人，知道你想知道的東西。PaperWeekly 或許可以成為一座橋梁，促使不同背景、不同方向的學者和學術靈感相互碰撞，迸發出更多的可能性。?

PaperWeekly 鼓勵高校實驗室或個人，在我們的平臺上分享各類優質內容，可以是最新論文解讀，也可以是學習心得或技術干貨。我們的目的只有一個，讓知識真正流動起來。

?????來稿標準：

? 稿件確系個人原創作品，來稿需注明作者個人信息（姓名+學校/工作單位+學歷/職位+研究方向）?

? 如果文章并非首發，請在投稿時提醒并附上所有已發布鏈接?

? PaperWeekly 默認每篇文章都是首發，均會添加“原創”標志

?????投稿郵箱：

? 投稿郵箱：hr@paperweekly.site?

? 所有文章配圖，請單獨在附件中發送?

? 請留下即時聯系方式（微信或手機），以便我們在編輯發布時和作者溝通

????

現在，在「知乎」也能找到我們了

進入知乎首頁搜索「PaperWeekly」

點擊「關注」訂閱我們的專欄吧

關于PaperWeekly

PaperWeekly 是一個推薦、解讀、討論、報道人工智能前沿論文成果的學術平臺。如果你研究或從事 AI 領域，歡迎在公眾號后臺點擊「交流群」，小助手將把你帶入 PaperWeekly 的交流群里。

總結

以上是生活随笔為你收集整理的最新综述：用于组合优化的强化学习的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。