通过分阶段决策提升神经组合优化的泛化能力
ASAP: Exploiting the Satisficing Generalization Edge in Neural Combinatorial Optimization
- 先生成候选解，再动态选择最优解，增强鲁棒性
- 在3D-BPP、TSP等任务上显著提升分布外适应性能
- 适合需要快速应对新场景的实时优化应用
深度强化学习在求解组合优化问题（如3D-BPP、TSP、CVRP）方面展现出潜力，但面对分布偏移时往往表现脆弱。本文揭示并验证了‘满意性泛化优势’：识别一组有希望的候选动作，比选出单一最优动作更具泛化能力。为此提出ASAP框架，将决策过程分为两阶段：由提案策略作为稳健过滤器，选择策略作为灵活决策者。该结构支持高效的在线适应，可通过模型无关元学习（MAML）进行两阶段训练，使选择策略快速适配新分布。在3D-BPP、TSP和CVRP上的大量实验表明，ASAP提升了现有基线的泛化能力，并在分布外实例上实现更优的在线适应性能。
原文摘要 · Abstract (English)
Deep Reinforcement Learning (DRL) has emerged as a promising approach for solving Combinatorial Optimization (CO) problems, such as the 3D Bin Packing Problem (3D-BPP), Traveling Salesman Problem (TSP), or Vehicle Routing Problem (VRP), but these neural solvers often exhibit brittleness when facing distribution shifts. To address this issue, we uncover the Satisficing Generalization Edge, which we validate both theoretically and experimentally: identifying a set of promising actions is inherently more generalizable than selecting the single optimal action. To exploit this property, we propose Adaptive Selection After Proposal (ASAP), a generic framework that decomposes the decision-making process into two distinct phases: a proposal policy that acts as a robust filter, and a selection policy as an adaptable decision maker. This architecture enables a highly effective online adaptation strategy where the selection policy can be rapidly fine-tuned on a new distribution. Concretely, we introduce a two-phase training framework enhanced by Model-Agnostic Meta-Learning (MAML) to prime the model for fast adaptation. Extensive experiments on 3D-BPP, TSP, and CVRP demonstrate that ASAP improves the generalization capability of state-of-the-art baselines and achieves superior online adaptation on out-of-distribution instances.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。