人工智能顶级会议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帷幄』

欢迎查看原文，获取更多讯息！