用实例感知的潜在空间生成新解法，提升组合优化的泛化能力。
Latent Guided Sampling for Combinatorial Optimization
- 基于实例条件化的潜在空间，动态生成匹配问题特性的解。
- 在典型路由任务上超越现有神经组合优化方法，达到最新最优性能。
- 适合需要强泛化性与鲁棒推理的工业级组合优化场景。
组合优化问题广泛存在于物流、制造和药物发现等领域，但其NP难性质使其计算挑战巨大。近年来的神经组合优化（NCO）方法利用深度学习学习构造解的策略，通过监督或强化学习训练。尽管前景广阔，这些方法常依赖特定任务增强，对分布外实例表现不佳，且缺乏稳健的推理机制。现有潜在空间模型要么需标注数据，要么使用与实例无关的潜在分布。本文提出LGS-Net，一种基于问题实例条件化的新型潜在空间模型，并引入基于马尔可夫链蒙特卡洛与随机逼近的高效推断方法——潜在引导采样（LGS）。我们证明该方法的迭代过程构成时变马尔可夫链，并提供严格的理论收敛保证。在基准路由任务上的实验表明，本方法在所有NCO基线中表现最优。
原文摘要 · Abstract (English)
Combinatorial Optimization problems are widespread in domains such as logistics, manufacturing, and drug discovery, yet their NP-hard nature makes them computationally challenging. Recent Neural Combinatorial Optimization (NCO) methods leverage deep learning to learn policies for constructing solutions, trained via Supervised or Reinforcement Learning. While promising, these approaches often rely on task-specific augmentations, perform poorly on out-of-distribution instances, and lack robust inference mechanisms. Moreover, existing latent space models either require labeled data or use an instance-independent latent distribution. In this work, we propose LGS-Net, a novel latent space model that conditions on problem instances, and introduce an efficient inference method, Latent Guided Sampling (LGS), based on Markov Chain Monte Carlo and Stochastic Approximation. We show that the iterations of our method form a time-inhomogeneous Markov Chain and provide rigorous theoretical convergence guarantees. Empirical results on benchmark routing tasks show that our method achieves state-of-the-art performance among NCO baselines.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。