將算法設計為自動化，可以為解決困難的COP問題可以節省大量的金錢和時間，也許可以產生比人類設計的方法更好的解決方案，正如我們在

為什麼優化很重要？

從數百萬年前的人類開始，每一項技術創新和每一項改善我們生活的發明以及我們在地球上生存和繁榮的能力，都是由聰明人的狡猾思想設計出來的。從火到車輪，從電力到量子力學，我們對世界的理解和我們周圍事物的複雜性已經增加到我們經常難以直觀地掌握它們的程度。

如今，飛機，汽車，船舶，衛星，複雜結構等許多其他設施的設計者在很大程度上依賴於算法使其具有更好的能力，通常是人類根本無法實現的微妙方式。除了設計之外，優化在日常事務中起著至關重要的作用，例如網絡路由（互聯網和移動），物流，廣告，社交網絡甚至醫學。在未來，隨著我們的技術不斷改進和複雜化，解決巨大規模的難題的能力可能會有更高的需求，並且需要在優化算法方面取得突破。

組合優化問題

從廣義上講，組合優化問題是涉及從有限的一組對象中找到"最佳"對象的問題。在這種情況下，"最佳"是通過給定的評估函數來測量的，該函數將對象映射到某個分數或成本，目標是找到值得最低成本的對象。

最實際有趣的組合優化問題也非常困難，因為由於問題大小的微小增加，集合中的對象數量增加得非常快，使得窮舉搜索變得不切實際。

為了使事情更清楚，我們將專注於一個特定的問題，即著名的旅行商問題（TSP）。在這個問題上我們有N個城市，我們的銷售員必須全部訪問它們。然而，在城市之間旅行會產生一些費用，我們必須找到一個旅行，在旅行到所有城市並返回起始城市時最大限度地減少總累積成本。例如，下圖顯示了美國所有州所在城市的最佳旅遊：

這個問題自然會出現在許多重要的應用中，例如計劃，交付服務，製造，DNA測序和許多其他應用。尋找更好的旅行團隊有時會產生嚴重的財務影響，促使科學界和企業投入大量精力來解決這些問題。

在為K城市建立TSP實例之旅的同時，我們在旅遊建設過程的每個階段都消除了一個城市，直到不再有城市為止。在第一階段，我們有K個城市可以選擇開始巡演，在第二階段我們有K-1選項，然後是K-2選項等等。我們可以構建的可能的遊覽數量是我們在每個階段的選項數量的乘積，因此這個問題的複雜性就像O（K！）。

對於小數字，這似乎並不那麼糟糕。假設我們有5個城市問題，可能的旅行次數是5！= 120。但是對於7個城市，它增加到5040，對於10個城市已經是3628800，對於100個城市來說，它是高達9.332622e + 157，這比宇宙中的原子數多出許多個數量級。

在現實世界中出現的TSP的實際實例通常具有數千個城市，並且需要在大量文獻中已經開發了數十年的高度複雜的搜索算法和啟發式算法，以便在合理的時間內解決（可能是數小時）。

遺憾的是，在現實世界的應用程序中出現的許多COP（組合優化問題）具有獨特的細微差別和約束，使我們無法僅使用最先進的解決方案解決TSP等已知問題，並要求我們開發針對該問題的方法和啟發式方法。這個過程可能是漫長而艱鉅的，並且可能需要領域專家的工作來檢測特定問題的組合搜索空間中的某些結構。

由於近年來深度學習在許多領域取得了巨大成功，讓機器學會如何自己解決問題的可能性聽起來非常有希望。將算法設計為自動化，可以為解決困難的COP問題可以節省大量的金錢和時間，也許可以產生比人類設計的方法更好的解決方案，正如我們在AlphaGo的成就中看到的那樣，這些成就擊敗了數千年的人類經驗。

學習圖形表示

在這個問題的一個早期嘗試，是在2016年的一篇論文《學習基於圖的組合優化算法》，作者訓練了一種圖形神經網絡，稱為structure2vec，以貪婪地構建幾個硬COP的解決方案，並獲得非常好的近似比率（生產成本與最優成本之間的比率） 。

基本思想是這樣的：問題的狀態可以表示為圖形，神經網絡構建解決方案。在解決方案構建過程的每次迭代中，我們的網絡觀察當前圖形，並選擇要添加到解決方案的節點，之後根據該選擇更新圖形，並且重複該過程直到獲得完整的解決方案。

作者使用DQN算法訓練他們的神經網絡，並證明了學習模型能夠推廣到比訓練更大的問題實例。他們的模型甚至可以很好地推廣到1200個節點的實例，同時在大約100個節點的實例上進行訓練，並且可以在12秒內生成解決方案，這些解決方案有時比商業解算器在1小時內找到的更好。他們的方法的一大缺點是他們使用"輔助"功能，以幫助神經網絡找到更好的解決方案。這個輔助函數是人為設計的，並且特定於問題，這是我們想要避免的。

使用基於圖形的狀態表示非常有意義，因為許多COP可以通過這種方式非常自然地表達，如TSP圖的示例中所示：

節點代表城市，邊緣包含城市間距離。可以在沒有邊緣屬性的情況下構建非常相似的圖形（如果由於某種原因我們不假設距離的知識）。近年來，在圖形上運行的神經網絡模型的普及程度令人驚訝地增加，最顯著的是在自然語言處理領域，

有許多優秀的文章詳細解釋了Transformer體系結構，因此我不會深入研究它，而是給出一個非常簡短的概述。谷歌研究人員在一篇名為《Attention Is All You Need》的著名論文中引入了變換器（transformer）架構，並用於解決NLP中出現的序列問題。不同之處在於，與LSTM等遞歸神經網絡不同，後者明確地輸入一系列輸入向量，變換器作為一組對象被輸入，並且必須採取特殊手段來幫助它看到"序列"。變換器使用多個層，這些層由多頭自注意子層和完全連接的子層組成。

與圖形的關係在注意層中變得明顯，注意層實際上是輸入"節點"之間的一種消息傳遞機制。每個節點都觀察其他節點並參與那些看起來更"有意義"的節點。這與中發生的過程非常相似，事實上，如果我們使用掩碼來阻止節點將消息傳遞給不相鄰的節點，我們將獲得一個等效的過程。

學會解決沒有人類知識的問題

在他們的論文《注意力機制學習解決路由問題》，作者解決了幾個涉及在圖表由代理的組合優化問題，包括我們現在熟悉的旅行商問題。他們將輸入視為圖形並將其提供給嵌入圖形節點的修改後的Transformer體系結構，然後依次選擇要添加到巡視的節點，直到構建完整的巡視。將輸入作為圖形處理是比給它一系列節點更"正確"的方法，因為它消除了對輸入中給出城市的順序的依賴性，只要它們的座標不變。這意味著無論我們如何對城市進行置換，給定圖形神經網絡的輸出都將保持不變，這與序列方法不同。

在本文提出的體系結構中，圖形由變換器樣式編碼器嵌入，該編碼器為所有節點生成嵌入，併為整個圖形生成單個嵌入向量。

為了產生解決方案，單獨的解碼器網絡每次賦予特殊上下文向量，即由圖嵌入和那些最後和第一城市，和未訪問城市的嵌入的，並且它在未訪問的輸出概率分佈城市，其被抽樣以產生下一個要訪問的城市。

解碼器順序產生城市直到遊覽完成，然後根據遊覽的長度給出獎勵。

作者使用稱為REINFORCE的強化學習算法訓練他們的模型，該算法是基於策略梯度的算法。其版本的偽代碼可以在這裡看到：

他們使用轉出網絡確定性地評估實例的難度，並使用策略網絡的參數定期更新轉出網絡。使用這種方法，作者在幾個問題上取得了優異的成果，超越了我在前面幾節中提到的其他方法。但是，他們仍然在小型實例上訓練和評估他們的方法，最多有100個節點。雖然這些結果很有希望，但與現實世界相比，這種情況微不足道。

擴展到非常大的問題

最近《通過深度強化學習進行大圖的啟發式學習》（《Learning Heuristics Over Large Graphs Via Deep Reinforcement Learning》）一文，朝著真實世界大小的問題邁出了重要的一步。在本文中，作者訓練了一個圖形卷積網絡來解決大型問題，如最小頂點覆蓋（MVC）和最大覆蓋問題（MCP）。他們使用流行的貪婪算法來訓練神經網絡嵌入圖形並預測下一個節點在每個階段進行選擇，然後使用DQN算法進一步訓練它。

他們在具有數百萬個節點的圖表上評估了他們的方法，並且獲得了比當前標準算法更好和更快的結果。雖然他們確實利用手工的啟發式方法來幫助訓練他們的模型，但未來的工作可能會消除這種限制。

總的來說，我認為在大量搜索空間問題中尋找結構的探索是強化學習的一個重要而實用的研究方向。強化學習的許多批評者聲稱，到目前為止，它只用於解決遊戲和簡單的控制問題，並且將其轉移到現實世界的問題仍然很遙遠。雖然這些說法可能是正確的，但我認為我在本文中概述的方法代表了非常真實的用途，可以在近期內為強化學習的應用帶來好處。

閱讀更多 AI火箭營 的文章

關鍵字: 解決困難 算法設計 設計