【“旅行商”問題太棘手？用圖神經網絡尋找最優解】：運用深度強化學習法和圖神經網絡的學習策略，來解優化難題。希望對你有幫助～
全文共3438字，預計學習時長7分鐘或更長
從幾百萬年前人類生命起源開始，為了提升生活質量，提高在地球上的生存技能，人類利用睿智的腦袋進行了一次次的科技創新和發明。從火（藥）到車輪，從電力到量子力學，我們對于世界及周遭事物復雜性的理解水平已經到了難以僅憑直覺去判斷的程度。
如今，飛機、汽車、輪船、衛星以及用于其他目的復合結構的設計師們，極大地依賴于運用算法來提升其能力，而這種提升方式往往微妙到人們自身永遠無法實現。
除了設計，優化在日常生活中也扮演著至關重要的角色，比如網絡路由（互聯網和移動終端）、物流、廣告投放、社交網絡甚至是醫藥信息。未來，隨著科技水平的不斷改進與復雜化，解決大規模難題的能力將會迎來更高需求，同時，我們也需要在算法優化上有所突破。
組合優化的問題
廣義上來說，組合優化問題即是解決從有限對象集合中尋找“最佳”對象的問題。這個語境中的“最佳”是由給定的評價函數來衡量的，該函數將對象映射到某個分數或成本，其目標是找到成本最低的對象。大多數在實際中看起來有意思的組合優化問題(后文都簡略為COPs)很棘手，因為即使問題的規模大小只增加一點點，集合中的對象數量也會以極快的速度增加，這使窮舉搜索顯得不切實際。
為了讓問題更加直觀明了，我們把關注點放在一個特定的問題上，即著名的旅行商問題(TSP)。在這個問題中，假設有N座城市，銷售人員必須訪問所有的城市。無論如何，在城際間旅行會產生一定的成本，而我們必須找到一條路線，使整個出行成本降到最低。例如，下圖顯示了行遍美國各州首府的最佳路線圖：
這個旅行商問題廣泛存在于許多重要領域的應用，例如規劃、交付服務、制造業、DNA測序以及其他許多方面。尋找更好的路徑與解決財務等問題息息相關，這也促使科學界和企業投入大量物力財力來尋找更好的方法。
以K個城市為TSP例子構建一個旅游路線，在路徑構建過程的每個階段會刪除一個城市，直到沒有剩余的城市為止。在第一個階段，有K個城市可供選擇，在第二個階段，有K-1個選項，接著是K-2個選項，以此類推。我們能夠構建的潛在路徑總數量是每個階段所擁有選項數量的乘積，這個問題的復雜性為O(K!)。
然而，這種方法比較適用于數量較小的計算。比方說，假設有5個城市，則潛在旅游路線的總數量為5!=120。但是對于有7個城市的情況來說，這個計算結果會立增到5040，10個城市已經達到則是3628800，100的結果更是驚人地高達9.332622e+157，而這數量遠遠超過了宇宙中原子的數量。
在現實生活中TSP的運用實例涉及到的是成千上萬的城市數量運算，為了能在合理的時間(可能是幾個小時)內解決問題，通常需要運用那些高度復雜的搜索算法和啟發式算法，而這些算法是通過幾十年下來的大量文獻所開發形成的。
不幸的是，在實際應用中出現的許多COPs具有獨特的細微差別和條件約束，它們阻止我們用最先進的解決方案來解決諸如TSP之類的已知問題，并且要求我們開發針對該問題的方法和啟發式。這個過程可謂長路漫漫障礙重重，可能需要相關領域專家來檢測特定問題組合，搜索空間中的某些結構。
這些年來，由于深度學習在許多領域都取得了巨大的成功，讓機器自主學習如何解決問題似乎有望在未來實現。將算法的設計過程自動化，使其能夠自發解決難以應對的COPs——這樣不僅能節約大量財力和時間，也許還能生成比人工設計更加可行的解決方案（就像我們目前在AlphaGo等成果中所能看到的一樣，它已經打敗了人類過去通過數千年所取得的經驗成就）。
運用圖例學習
早在2016年，一篇名為《基于圖表學習組合優化算法》的論文就對這個問題進行了早期嘗試。在這篇文章中，作者訓練了一種叫structure2vec的圖神經網絡，針對幾個有難度的COPs制定貪婪的構造解決方案，并獲得了非常好的近似比值(生成成本與最優成本之比)。
它的基本思路是這樣子的：用圖譜來表示待解決的問題，然后讓圖神經網絡依據圖譜建立解決方案。在解決方案構建過程的每次迭代中，神經網絡會觀察當前的圖表，并選擇一個節點添加到解決方案中，然后根據該選擇更新圖表，接著重復這個過程，直到得到一個完整的解決方案。
論文作者們使用DQN算法來訓練神經網絡，并證明了習得模型在運用到比所受訓練更復雜的問題實例時的泛化能力。這種模型甚至可以很好地泛化到1200個節點的實例中（同時在大約100節點的實例進行訓練），同時還能在12秒內生成比商業求解程序用時一小時所求得的更佳解決方案。
但是這個方法有一個很大的缺陷，就是他們會使用一個“輔助”方程來幫助圖神經網絡尋找更好解法。這個輔助方程是人為設計用于解決特定問題的，而這恰恰是我們想要避免的。
這種基于圖例的展現方式非常容易理解，因為許多組合優化問題可以自然而然地以這種方式呈現出來，就如下面這個TSP圖例所展示的一樣：
圖中的每個節點代表每個城市，節點邊緣包含了城際間的距離，如果不考慮邊緣屬性，類似的圖形也能夠構建起來（如果我們出于某種原因不考慮距離因素在內的話）。近年來，基于圖形的神經網絡模型（無關乎是否具備架構知識）以令人難以置信的速度流行開來。尤其令人矚目的是自然語言處理領域，它所使用的Transformer架構模型已經成為業內眾多任務處理的最先進技術。
有許多優秀的文章詳細地解釋了Transformer架構，所以本文不再深入剖析，而是做一個簡述。Transformer架構是由谷歌研究人員在一篇題為“AttentionIsAllYouNeed”的論文中所介紹的。在這篇著名的論文中，Transformer架構被用于處理NLP中所面對的序列難題。不同之處在于，我們可以向遞歸神經網絡，如長短記憶網絡（LSTM），直觀輸入一系列的輸入向量，而Transformer架構中只能以一系列對象的形式輸入，且必須采用特殊的方式來讓它看見“序列”的排列順序。這個Transformer是由一個多頭自注意力子層和一個完全連接的子層所組成的。
它與圖譜的關系在注意力層變得明顯起來，而這個注意力層實際上是輸入“節點”間的一種信息傳遞機制。每一個節點都會觀察其他節點，同時定向那些對于它們自己看起來更“有意義”的節點。這與在圖譜注意力機制（GraphAttentionNetwork）中運行的過程非常相似。實際上，如果使用一個掩碼來阻止單個節點向不相鄰的節點傳遞信息，我們將會得到一個等價的過程。
學習如何在沒有人類知識的情況下解決問題
在論文《注意！學習解決路由問題》中，作者們嘗試解決了幾個涉及圖解路由代理的組合優化難題，包括我們現在熟悉的旅行商問題。將輸入數據視為一個圖，并將其投入一個經過調整的Transformer構架并在構架中嵌入了圖的節點，然后依次選擇添加到路由的節點直到完成構建一個完整的路由為止。
將輸入數據視為圖形是一個比向其提供節點序列更為“正確”的方法，因為只要它們的坐標不變，就能夠消除對所輸入城市順序的依賴性。這意味著，不同于上述的節點序列法，無論我們如何改變輸入城市的排列，給定圖神經網絡的輸出值都將保持不變。
在論文所提及的構架中，圖譜是由Transformer編碼器嵌入的，它在為所有的節點生成嵌入層的同時也為全圖生成單個嵌入向量。為了生成解決方案，每次給予一個特殊的上下文向量時都會給出一個單獨的解碼器網絡，這個網絡由圖嵌入、最后一個和第一個城市以及未訪問城市的嵌入組成，并會輸出一個未訪問城市的概率分布，然后采樣生成下一個將要訪問的城市。這個解碼器會按順序生成要訪問的城市直到整個行程結束，然后根據旅程的長度給予反饋。
文中使用了一種名為REINFORCE的強化學習算法來訓練模型，這是一種基于策略梯度的算法。其版本所使用的偽代碼如下圖所示：
文中使用一個滾輪網絡來確切評估實例的難度，并定期使用策略網絡的參數來更新這個滾輪網絡。這種方法在解決幾個難題上取得了不錯的成效，性能上超越了前文所提到的其他方法。盡管如此，作者們仍在擁有至多100個節點的小型例子上訓練和評估模型。雖然這些結果很有希望，但這些例子與現實生活中其他情況相比，猶如小巫見大巫。
擴展到大型問題
最近，一篇題為《通過深度強化學習在大型圖上學習啟發式算法》的論文中向解決現實世界那般規模大小的問題邁出了重要一步。在文中，作者訓練了一個圖卷積網絡來解決諸如最小頂點覆蓋(MVC)和最大覆蓋問題(MCP)這樣的大型實例問題。
針對這些問題，他們采用一種流行的貪心算法來訓練神經網絡進行嵌入圖并預測每一階段需要選擇的下一個節點，在此之后使用DQN算法對其進行進一步的訓練。
他們在含有數百萬個節點的圖上測評了其方法，并取得了比當前標準算法更優異快速的結果。雖然他們確實通過使用動手搭建的啟發式來幫助訓練模型，但在未來，這種方式可能會消除這種約束，并從白板狀態學會解決巨大難題。
總之，在無邊的搜索領域中，尋找架構是強化學習的一個重要且實用的研究方向。許多批評強化學習的人聲稱，到目前為止，這項技術僅被用于解決游戲和簡單的操作問題，想要將其應用到解決現實問題中還很有很長的路要走。