優化丨人工智慧頂級會議NeurIPS 2018中優化與AI的融合

原標題：優化丨人工智慧頂級會議NeurIPS 2018中優化與AI的融合

文章作者：留德華叫獸

責任編輯：閻泳楠，覃含章 編輯整理自知乎回答

編者按：第32屆人工智慧頂級會議NeurIPS（原簡稱NIPS， Neural Information Processing Systems）已於昨天（2018.12.02）拉開帷幕。今年的投稿量繼續增長，比起之前的歷史最高點再次大幅度提升。

在接收的文章當中，深度學習的勢頭也是有增無減，而優化方面的文章也繼續佔據著相當的規模。與此同時，本次會議也出現了不少結合優化理論與人工智慧/深度學習的文章，本文就旨在為讀者在這方面提供一個索引式的介紹和概覽。

因為博士階段從運籌學|優化理論轉行到人工智慧|計算機視覺|自動駕駛領域，目前我關注比較多的是運籌學|優化理論與人工智慧的交叉。具體來說是以下幾個方面：

1. 深度學習求解傳統的優化問題（例如：深度學習求解NP難的組合優化、整數規劃）

2. 人工智慧底層的優化問題的進展（凸優化、非凸優化演算法）

3. 人工智慧解決運籌學傳統問題（例如：深度學習做預測、強化學習做自動駕駛的planning）

4. 深度強化學習（近似動態規劃方法、策略梯度方法、 搜索+監督學習）

今年 NeurIPS 的投稿數量上升到了史無前例的 4856 篇，比去年增加了約 50%

接收率保持著與去年持平的 20.8%，共收錄論文 1011 篇，包括 30 篇 Oral（0.6%）和 168 篇 Spotlight（3.5%）。

按照以上思路，我搜索了一下NeurIPS2018的收錄paper：

1深度學習求解組合優化、整數規劃、0/1優化

我試圖搜索Combinatorial、integer和binary這三個關鍵詞

得到7個搜索結果：（以下顯示其中部分）

2人工智慧底層優化問題

我搜索"optimization"關鍵詞，這次得到了62次響應，可見優化理論在NIPS是比較熱門的研究領域。以下是部分帶optimization關鍵詞的文章。

3人工智慧解決運籌學傳統問題

我嘗試搜索運籌學經典應用領域，例如：scheduling（調度）、planning（規劃）、forecasting（預測）、logistics（物流）、transportation（交通）、routing（路徑規劃）等等。其中只有planning、forecasting、routing出現了4+2+1次響應。

4深度強化學習

Reinforcement Learning關鍵詞一共得到了37次響應。以下顯示部分帶該關鍵詞的文章。

文章Reinforcement Learning for Solving the Vehicle Routing Problem結合了深度強化學習技術來求解車輛路徑規劃問題。本文給出這篇文章的一個簡單解讀，後續【運籌OR帷幄】也將有專門解讀本屆NeurlPS優化等其它方面領域的文章，敬請期待。

5精選文章導讀

Deep Reinforcement Learning for Solving the Vehicle Routing Problem (用深度強化學習求解VRP問題)

文章梗概

文章作者是來自美國Lehigh University, Department of Industrial Engineering的Mohammadreza Nazari等四位。

這篇文章的主要工作是用深度加強學習（DRL）提出了求解各類型組合優化問題的框架，並將其用於求解車輛路徑問題（VRP）。基於這一目的，作者用馬爾科夫決策過程（MDP）公式來表述這個問題，最優解就可以看成一系列決策。通過用DRL來提高解碼理想序列的概率，從而得到近似最優解。該模型採用的是參數化隨機策略，通過梯度演算法策略來優化參數。訓練後的模型能實時產生連續的一系列解，不需要為每一個新的算例重新訓練。這篇文章的提出的方法與求解旅行商問題（TSP）較新的方法相比，訓練和測試時間較快，且求解質量能得到保證，能得到幾乎一樣的解方案。此外，對於更一般化的VPR問題，這篇文章的方法在求解質量和計算時間（訓練之後的時間）上都優於經典的啟發式演算法。這篇文章的框架還可應用於不同類型的VRP問題，如隨機VRP；並有可能廣泛地應用於組合優化問題。

模型對比

這篇文章的工作是對Bello等人[1]近期一篇論文的改進。通過改進Bello等人的研究框架，使其能夠求解包含VRP問題在內的各類組合優化模型。Bello等人提出用指針網路[2]（Pointer Network）解碼這個解。指針網路的缺點在於它假設系統是穩定不變的，而VRP問題中的需求有可能隨時間變化，如圖1中的

所示。如果需求變化了，為了計算下一個決策點的概率，需要更新整個指針網路。為了解決這個問題，作者提出了一種比指針網路更簡單的方法，即一個帶有注意力機制（attention mechanism）的遞歸神經網路（RNN）解碼器。如圖2所示，左邊的嵌入層將輸入映射到高維的向量空間，右邊的RNN解碼器存儲解碼序列的信息。然後，RNN隱含狀態和嵌入輸入使用注意力機制在下一個輸入上生成概率分布。

模型亮點

本文所提出的模型在求解VRP中的優勢如下：

• 利用自我驅動的學習過程，只需要根據輸出結果進行獎勵計算。也就是說，只要我們能夠通過觀察獎勵，並驗證生成序列的可行性，就可以學習想要的元演算法。例如，如果不知道如何求解VRP，但是可以計算給定解的成本，就可以使用本文提出的方法。
• 對問題的變化具有魯棒性。與許多經典的啟發式方法不同，本文提出的模型隨問題規模增大表現較好，並在求解時間上具有較高的優越性。此外，當問題的輸入改變時，該模型能夠自動更新解。
• 不需要距離矩陣。使用經典的VRP啟發式演算法，往往需要重新計算整個距離矩陣，並且必須從頭重新優化系統。這通常是不切實際的，尤其在問題規模較大的時候。本文所使用的模型不需要進行距離矩陣的計算，將極大提高計算效率。

6總結

1, 以上所有搜索結果基於網址： NIPS 2018（https://nips.cc/）

2, 搜索結果僅基於以上關鍵詞

3, 人工智慧與運籌學，特別是優化理論關係緊密（深度學習所謂的訓練即求解一個高度複雜的非凸優化問題）。

隨著近幾年商學院大量引進AI相關的教授，相信OR和AI交叉會越來越多。

最後為大家推薦一個運籌學與人工智慧交叉的學術會議CPAIOR（2019年在希臘舉辦）

16th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (http://cpaior2019.uowm.gr/ )

NeurlPS 2018日期臨近，各位小夥伴一定有不少參會--『運籌OR帷幄』特此推出『NeurlPS 2018交流群』。

『NIPS2018』入群方式：關注微信公眾號『運籌OR帷幄』，公眾號後台回復「加微信群」。

參考文獻

[1] Bello I , Pham H , Le Q , et al. Neural Combinatorial Optimization with Reinforcement Learning[J]. 2017.

[2] Vinyals O, Fortunato M, Jaitly N. Pointer networks[C]. International Conference on Neural Information Processing Systems. 2015.

原文鏈接：https://mp.weixin.qq.com/s/Ca4PjruxiktZmN8EPlXE4A

版權說明：首發於微信公眾號『運籌OR帷幄』

歡迎查看原文，獲取更多訊息！

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！