基于渐进式训练范式的神经组合优化方法研究及其应用

《Neurocomputing》：Enhancing neural combinatorial optimization by progressive training paradigm

本文提出了一种创新的渐进式训练范式，通过结合监督学习（SL）和强化学习（RL）来增强神经组合优化（NCO）模型的性能。该范式先利用SL在小规模问题上进行预训练，再通过RL进行微调，有效解决了SL标签获取难和RL奖励稀疏的问题，并在旅行商问题（TSP）和容量约束车辆路径问题（CVRP）上实现了万级节点的求解，显著提升了模型的泛化能力。

　　

Section snippets

Related work

研究人员尝试了多种方法来提升神经网络求解组合优化问题的性能。我们聚焦于当前主流的构造性NCO方法，该方法通过自回归节点选择生成解，并从训练方法、模型架构和增强技术等方面分析了现有研究。我们的方法也属于构造性范式。对于其他典型的非构造性方法（例如，...

Preliminaries

本节描述了包括TSP和CVRP在内的组合优化问题，这些将在实验中用于评估我们的方法。之后，我们介绍了基于Transformer的构造性NCO模型LEHD，该模型用于我们的训练范式。

Methodology

渐进式训练范式包括两阶段训练设计、结合不同训练方法的策略以及针对大规模问题的分解训练方法。我们将在以下三个小节中详细描述它们。

Experiments

我们从不同角度实证评估了我们的渐进式训练范式。首先，我们详细描述了实验设置。随后，我们将我们的方法与多个其他基线进行比较，并报告了在均匀分布的TSP和CVRP实例上的结果。然后，我们测试了其在真实世界实例和不同分布上的泛化能力。最后，我们进一步展示了其多功能性和训练性能。

Conclusion

本工作提出了一种用于NCO的渐进式训练范式，有效提升了NCO模型在分布内测试和分布外泛化方面的性能。我们创新性地结合了NCO模型训练方法SL和RL，有效避免了SL中难以获取大量高质量解的问题以及RL中奖励稀疏的问题。通过大量实验表明，我们的渐进式训练范式...