
推许多解决组合优化问题的传统算法都涉及使用手工构造的启发式算法,这些启发式算法能够依次地构造解决方案。这种启发式方法是由领域专家设计的,且一般由于问题的困难性,这种方法不是最佳的。强化学习(RL)提出了一种很好的选择,使用监督或自我监督的方式训练 agent 来自动搜索这些启发式方法。
在这篇调研中,我们探索了将 RL 框架应用于困难的组合问题的最新进展。我们的调研为运筹学和机器学习社区提供了必要的背景,并展示了推动领域向前发展的工作。我们将最近提出的 RL 方法并置在一起,列出了每个问题改进方法的时间线,并与传统算法进行了比较,这表明 RL 模型可以成为解决组合问题的有希望的方向。

论文标题:
Reinforcement Learning for Combinatorial Optimization: A Survey
论文作者:
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, Evgeny Burnaev
论文链接:
https://arxiv.org/abs/2003.03600

优化问题涉及在不同可能中找到优化配置或是“值”,他们天然地属于两个类别中的一个:具有连续变量和离散变量的配置。比如,找到一个凸规划问题的解决方案是一个连续优化问题,而在图的所有路径中找到最短路径则是一个离散优化问题。
有时两者之间的界线很难确定。比如,在连续空间中的线性规划任务可以看作是一个离散的组合问题,因为他的解决方案在凸多边形的顶点的有限集合中,这已经由 Dantzig 的算法证明。通常,离散空间中的优化问题称为组合优化(CO)问题,且与连续空间中的问题相比拥有不同类型的解决方案。可以将 CO 问题表达如下: