Attention Learn to Solve VRP Problem

ABSTRACT

最近提出的理念是在组合优化问题中加入启发式算法,这种想法是有希望的,因为它可以节省昂贵的开发费用。然而,要将这一理念付诸实践,我们需要更好的模式和更好的培训方式。我们在两个方面都做出了贡献:

(1)我们提出了一个基于attention layers的模型,该模型的优势在于Pointer Network,我们展现了如何使用REINFORCE(基于deterministic greedy rollout的simple baseline)来训练此模型,我们发现这方法比使用value function更有效。

(2)我们对旅行商问题(TSP)的最近学习的启发式算法进行了显著的改进,对于多达100个节点的问题接近最优结果。在相同的超参数下,我们学习了车辆路径问题(VRP)、定向运动问题(OP)和奖品收集TSP(PCTSP)的两个变量的强启发式算法,其性能优于大部分的baseline,并且得到了接近高度优化和专业化算法的结果。

1.INTRODUCTION

想象你正在参加一个科学会议。这个学术领域非常受欢迎,你不想错过其中的任何内容。你已经选择了数张想要了解的海报(应该类似讲座海报),然后要在看完海报后回到你现在所处的地方:咖啡角。那么你应该选取何种参观路线,来让所走的路线最短呢?这就是旅行科学家问题(TSP)

你发现你遇到的问题等价于旅行商问题(TSP),这看起来有点让人沮丧——这个问题属于NP难题。幸运的是,复杂性理论分析了该问题的最坏情况,于是你的贝叶斯学派观点认为该问题不可能的。特别的,你有一个限制条件:这些海报将被定期布置。你想要一个特殊的算法,它不是解决所有问题,而是这类问题的实例。你还有几个月的时间准备。作为一个机器学习者,你想知道你的算法是否可以学习?

动机 机器学习算法已经代替人类作为解决各种任务的算法工程师。十年前,计算机视觉算法使用手工制作的特征,但今天他们被深度神经网络(DNNs)端到端(end to end)地学习。通过从数据中学习,DNNs在语音识别、机器翻译、图像字幕翻译等问题上的表现优于经典方法(LeCun et al., 2015).虽然DNNs主要用来做预测,强化学习(RL)已经使得算法通过与环境互动来学习如何做决定。例如学习玩Atari游戏(Mnih et al., 2015),或通过前瞻性搜索诱导知识:这是用来掌握围棋游戏的(Silver等人,2017)。

世界不是一个游戏,我们希望训练能做出决定以解决实际问题的模型。这些模型必须学习如何从一个巨大的、组合的可行解集合中挑选出好的可行解。传统上,解决组合优化问题的方法可以分为(1)保证找到最优解的精确方法(2)权衡计算成本的启发式方法,尽管精确方法可以在内部使用启发式方法,反之亦然。启发式算法通常以规则的形式表示,规则可以解释为制定决策的原则。我们相信这些原则可以用DNNs参数化,并被训练以获得针对许多不同组合优化问题的新的、更强的算法,类似于DNNs在前面提到的应用程序中提高性能的方法。本文主要研究路径问题:一类重要且实用的组合优化问题。

一些有希望的学习启发式的方法已经在TSP上有所尝试(Bello et al., 2016)。为了推动这个方法,我们需要更好的模型和更好的训练方法。因此,我们建议使用一个基于注意力机制的强力模型,并且建议使用强化学习(基于deterministic greedy rollout的simple baseline)来训练模型。我们模型的目的不是超过类似Concorde的非学习的、特化的TSP算法。相反,我们展示了我们的模型(只有单一的超参数集合)在多种合理规模的路由问题上的灵活适用性。借助该模型,我们可以学习强启发式算法来解决不同的、没有好的启发式算法应用的实用性问题。