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