Attention, Learn to Solve Routing Problems!
Wouter Kool University of Amsterdam ORTEC、Herke van Hoof University of Amsterdam、Max Welling University of Amsterdam CIFAR
Abstract
The recently presented idea to learn heuristics for combinatorial optimization problems is promising as it can save costly development. However, to push this idea towards practical implementation, we need better models and better ways of training. We contribute in both directions: we propose a model based on attention layers with benefits over the Pointer Network and we show how to train this model using REINFORCE with a simple baseline based on a deterministic greedy rollout, which we find is more efficient than using a value function. We significantly improve over recent learned heuristics for the Travelling Salesman Problem (TSP), getting close to optimal results for problems up to 100 nodes. With the same hyperparameters, we learn strong heuristics for two variants of the Vehicle Routing Problem (VRP), the Orienteering Problem (OP) and (a stochastic variant of) the Prize Collecting TSP (PCTSP), outperforming a wide range of baselines and getting results close to highly optimized and specialized algorithms.
中文速览
用神经网络自动学习启发式算法来求解旅行商问题（TSP）等组合优化问题，此前受限于模型能力不足和训练效率低下。作者提出了一种基于注意力机制（Attention Model）的编码器-解码器架构，并配合一种简单却高效的训练策略——用贪心确定性"展开"（greedy rollout）作为REINFORCE算法的基线，替代传统的价值函数估计器。在TSP上，该方法对最多100个节点的问题能接近最优解；用同一套超参数还能直接迁移到车辆路径问题（VRP）、定向越野问题（OP）和奖励收集TSP等多种变体，全面超越其他已学习的启发式方法，且结果接近高度专业化的求解器。这项工作的意义在于，它证明了一个统一的可学习框架能够灵活应对多类实际路径优化问题，为未来在缺乏人工设计启发式算法的新问题上自动生成强力求解器奠定了基础。
原文 arXiv:1803.08475;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1803.08475v3