重新思考基于监督学习的神经组合优化在路由问题中的应用

《ACM Transactions on Evolutionary Learning and Optimization》：Rethinking Supervised Learning based Neural Combinatorial Optimization for Routing Problem

神经组合优化（NCO）是解决TSP、VRP等问题的有效方法，但训练高效NCO解算器面临挑战：强化学习存在奖励稀疏、数据效率低的问题，而监督学习需要大量高质量标注数据。本文提出数据增强可显著减少标注需求，并利用多解特性设计提升策略，使仅需5万标注样本的监督学习模型在分布内性能上可与强化学习相当，同时验证了其在大分布外问题的泛化能力，为NCO训练的数据高效性提供新思路。

　　

摘要

神经组合优化（NCO）是一种基于学习的方法，适用于解决复杂的组合优化问题，如旅行商问题（TSP）、车辆路径问题（VRP）和定向越野问题（OP）。然而，如何高效地训练出强大的NCO求解器以应对路径问题仍然是一个关键挑战。广泛使用的强化学习方法存在奖励稀疏和数据效率低的问题，而监督学习方法则需要大量高质量解决方案（即标签），这些解决方案的获取成本可能很高。在这项工作中，我们发现简单的数据增强操作可以大幅减少监督学习所需的高质量解决方案数量。此外，利用多个最优解特性的简单提升策略能够显著提高训练效率。仅需少量（$50$个）标记的实例，监督学习就能达到与广泛使用的强化学习方法相当的性能。此外，我们还研究了该方法在处理更大规模、分布不同的问题时的泛化能力。我们认为，这项工作的发现可能会促使人们重新思考数据高效监督学习在NCO求解器训练中的价值。