MiLoop：用于神经组合优化的选择性记忆传播

arXiv:2610.01685v1 发布类型：new 摘要：构造式神经组合优化（NCO）已成为一种颇具前景的范式，通过逐步学习构造组合优化问题（COP）的解，减少对手工规则的依赖，并实现快速推理。尽管许多采用动态嵌入的方法具有良好的泛化能力，但它们通常在每一步都使用深度注意力堆栈从头构建子问题表示。该类别中许多性能优异的方法依赖解标签或伪标签来实现高效训练，或在强化学习（RL）过程中进行激进的搜索空间剪枝。为解决这些局限性，我们提出了 Memory-in-the-Loop（MiLoop），一种完全基于 RL 的构造式框架，利用 rollout 已经需要执行的多步计算来进行选择性记忆传播。每次 rollout 都会提供解质量反馈以用于学习，同时传播历史表示，从而使浅层策略能够在不依赖外部解标签或训练期间搜索空间剪枝的情况下，学习有效的动态嵌入。具体而言，MiLoop 在注意力层之前将当前嵌入与历史记忆融合，并在之后应用自适应门控更新。更新后的表示既支持当前决策，也支持按步骤复用。针对四种 COP 的广泛实验表明，MiLoop 在规模从 100 个节点到 1000 万个节点的实例上都能持续产生高质量解，凸显了其强大的泛化能力。