Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement

目前，进行端到端构造神经组合优化的方法通常使用行为克隆从专家解决方案中训练策略，或使用强化学习的策略梯度方法。虽然行为克隆是直接的，但需要昂贵的专家解决方案，而策略梯度方法通常需要大量计算和复杂的微调。在这项工作中，我们将这两种方法结合起来，通过在每个时期使用当前模型对随机实例进行多次采样，然后选择最佳解决方案作为监督模仿学习的专家轨迹，简化了训练过程。为了实现逐步改进的解决方案并尽量减少采样，我们引入了一种方法，将轮次随机束搜索与可证明的策略改进的更新策略相结合。这种策略通过利用采样序列的优势，在几乎没有计算开销的情况下在轮次之间优化策略。我们在旅行商问题和带容量车辆路径问题上评估了我们的方法。使用我们的方法训练的模型实现了与使用专家数据训练的模型相当的性能和泛化能力。此外，我们使用基于Transformer的架构将我们的方法应用于工作车间调度问题，并大幅超越现有的最先进方法。

论文旨在解决端到端构造神经组合优化的训练问题，通过结合行为克隆和策略梯度方法来简化训练过程，从而避免昂贵的专家解决方案和计算复杂的fine-tune过程。

论文提出了一种方法，在每个epoch中使用当前模型对随机实例进行多个解的采样，然后选择最佳解作为监督模仿学习的专家轨迹，通过将随机贪心搜索与可证明的策略改进相结合的策略更新策略，实现了逐步改进解决方案的目的。

论文在旅行商问题和车辆路径问题上进行了评估，结果表明该方法训练出的模型具有可比较的性能和泛化能力，同时也在作业车间调度问题上应用了这种方法，使用基于transformer的架构超越了现有的最先进方法。

在这个领域，最近的一些相关研究包括：1. Learning Combinatorial Optimization Algorithms over Graphs; 2. Neural Combinatorial Optimization with Reinforcement Learning and Monte Carlo Tree Search; 3. Pointer Networks.