通过构造特定分布的路由问题，缩小神经求解器与传统算法的性能差距。
On Distributional Dependent Performance of Classical and Neural Routing Solvers
- 构建基于固定节点分布的合成问题实例用于训练
- 神经求解器在新分布上表现接近专业启发式算法
- 适合研究神经组合优化泛化能力的学者参考
神经组合优化通过数据驱动方法学习求解一类组合问题，通常依赖于对问题实例分布的学习。然而，目前的神经方法仍难以超越高度工程化的专用元启发式算法。本文提出一种新方法，通过构建具有特定结构的基准问题实例分布，并从中采样训练数据。测试实例则从该基础分布中独立采样生成，以评估模型泛化能力。在路由问题上的实验表明，当神经求解器从固定节点分布的子样本中学习时，其性能与专业运筹学元启发式算法之间的差距显著缩小。
原文摘要 · Abstract (English)
Neural Combinatorial Optimization aims to learn to solve a class of combinatorial problems through data-driven methods and notably through employing neural networks by learning the underlying distribution of problem instances. While, so far neural methods struggle to outperform highly engineered problem specific meta-heuristics, this work explores a novel approach to formulate the distribution of problem instances to learn from and, more importantly, plant a structure in the sampled problem instances. In application to routing problems, we generate large problem instances that represent custom base problem instance distributions from which training instances are sampled. The test instances to evaluate the methods on the routing task consist of unseen problems sampled from the underlying large problem instance. We evaluate representative NCO methods and specialized Operation Research meta heuristics on this novel task and demonstrate that the performance gap between neural routing solvers and highly specialized meta-heuristics decreases when learning from sub-samples drawn from a fixed base node distribution.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。