Leader Reward for POMO-Based Neural Combinatorial Optimization

基于强化学习的深度神经网络用于解决组合优化问题正在迅速发展，并且已经显示出接近或甚至胜过传统求解器的趋势。然而，现有方法忽视了一个重要的区别：组合优化问题与其他传统问题的不同之处在于，它们仅关注模型在特定时间内提供的最优解，而不考虑模型生成的所有解的整体质量。在本文中，我们提出了Leader Reward，并在Policy Optimization with Multiple Optima（POMO）模型的两个不同训练阶段应用它，以增强模型生成最优解的能力。这种方法适用于各种组合优化问题，如旅行商问题（TSP）、有容量车辆路径问题（CVRP）和灵活流水车间问题（FFSP），同时也适用于其他基于POMO的模型或推理阶段的策略。我们证明了Leader Reward极大地提高了模型生成的最优解的质量。具体而言，在几乎没有额外计算负担的情况下，在TSP100上，我们将POMO的差距缩小了100多倍。

本论文旨在解决组合优化问题中，传统方法忽视了模型在特定时间内生成的最优解与所有解的整体质量之间的区别的问题。因此，作者提出了Leader Reward方法，以增强POMO模型生成最优解的能力。

Leader Reward方法是通过在POMO模型的两个不同训练阶段中应用奖励机制，来提高模型生成最优解的能力。这种方法不仅适用于旅行商问题、车辆路径问题和灵活流水车间问题等各种组合优化问题，而且还适用于其他基于POMO的模型或推理阶段的策略。

实验结果表明，Leader Reward方法大大提高了模型生成最优解的质量。在TSP100上，我们将POMO模型的差距减少了100倍以上，几乎没有额外的计算开销。此外，本论文的方法可以推广到其他组合优化问题和模型中。

最近的研究中，也有一些关于使用深度强化学习解决组合优化问题的方法。例如，基于启发式搜索的方法和基于神经网络的方法等。