论文标题
学习控制当地搜索组合优化
Learning to Control Local Search for Combinatorial Optimization
论文作者
论文摘要
组合优化问题在许多实际情况（例如物流和生产）中遇到，但是精确的解决方案特别难以找到，通常对于大量的问题大小而言。为了计算近似解决方案，通常使用了局部搜索的通用和特定问题的动物园。但是，哪种变体也适用于哪种特定问题，即使对于专家来说也很难决定。 在本文中，我们确定了这种本地搜索算法的三个独立算法方面，并将其在优化过程中正式选择为马尔可夫决策过程（MDP）。我们将深图神经网络设计为该MDP的政策模型，为当地搜索提供了一个名为Neurols的局部搜索控制器。充分的实验证据表明，神经元能够胜过操作研究的众所周知的当地搜索控制器，以及最新的基于机器学习的方法。
Combinatorial optimization problems are encountered in many practical contexts such as logistics and production, but exact solutions are particularly difficult to find and usually NP-hard for considerable problem sizes. To compute approximate solutions, a zoo of generic as well as problem-specific variants of local search is commonly used. However, which variant to apply to which particular problem is difficult to decide even for experts. In this paper we identify three independent algorithmic aspects of such local search algorithms and formalize their sequential selection over an optimization process as Markov Decision Process (MDP). We design a deep graph neural network as policy model for this MDP, yielding a learned controller for local search called NeuroLS. Ample experimental evidence shows that NeuroLS is able to outperform both, well-known general purpose local search controllers from Operations Research as well as latest machine learning-based approaches.
