引言

路径规划问题，例如 旅行商问题 (TSP) 和 带容量的车辆路径问题 (CVRP) , 是无数现实应用的基础。从优化配送路线和调度维护队伍，到复杂的芯片制造，这些问题都需要高效的解决方案。然而，它们的 NP-难 性质意味着随着问题规模的增长，找到精确解在计算上变得不可行。因此，工业应用在很大程度上依赖于复杂的启发式方法和搜索算法。

近年来，强化学习 (RL) 作为一种灵活且强大的框架，在学习此类启发式策略方面崭露头角。然而，对于学习到的策略而言，一个普遍的挑战是无法充分利用推理阶段通常可用的额外计算预算——即在单个问题实例上可以进行多次尝试。现有策略通常包括从固定策略进行随机采样、对单个实例进行策略梯度微调，或者在一组预训练策略中进行搜索。每种方法在适应性、速度和数据效率方面都有其自身的权衡。

本文介绍了 MEMENTO , 一种为神经求解器提供短期记忆的全新方法。它是一种轻量且与架构无关的方法，旨在在推理期间实现更智能、更快速的适应。MEMENTO 与其对基础策略进行代价高昂且常常样本效率低下的反向传播不同，它学习了一种快速的更新规则。该规则基于检索到的经验动态调整神经求解器的动作 logits。最终结果是一种更智能、更高效的适应机制，能够有效地扩展到大规模实例，持续优于 Efficient Active Search (EAS) 等策略梯度微调方法，并且可以无缝集成 (“零-shot 组合”) 到 COMPASS 等基于群体的方法中。

这里的核心洞察对于工业环境至关重要: 当为每个实例分配多个尝试预算时，智能地重用和学习同一实例内的先前尝试结果，可以在不增加总计算预算的情况下获得显著更好的解决方案。

背景——构建模块

MEMENTO 构建在组合优化和强化学习的几个关键领域之上:

• 构造方法 (Construction Methods) : 这些是自回归神经策略，按步骤构建解决方案。例如 Pointer Networks 和基于注意力机制的 transformer。 POMO (Policy Optimization with Multiple Optima) 是一个流行的变体，它通过为构建路径采样多个起点来增强解决方案的多样性。

• 主动搜索 (Active Search，EAS) : 这种最先进的方法专注于在推理时针对特定测试实例微调预训练策略。它通过使用在线收集的转移数据执行策略梯度更新来实现。虽然有效，但 EAS 在推理时固有地受到梯度方差和反向传播计算成本的限制。

• 群体/多样性方法 (Population/Diversity Methods，COMPASS、POPPY) : 这些方法不微调单一策略，而是维护一个多样化的预训练策略集合，或在连续的策略潜在空间中进行探索，以寻找给定实例最合适的策略。这些方法提供了快速的探索，但通常仅限于从预训练的变体中进行选择，并且不能使用新收集的数据在线更新策略的动作分布。

• 检索与记忆在机器学习中的应用: 在自然语言处理 (NLP) 等领域，基于检索的方法的成功表明，检索相关的先验信息是提高性能的一种计算成本低廉且非常有效的方式。MEMENTO 将这一强大理念扩展到了基于 RL 的组合优化领域。

概览——MEMENTO 的工作原理

MEMENTO 的方法可以概括为以下关键步骤:

• 记忆存储: 在推理预算期间，它存储先前解决方案尝试的轻量级记录，并按节点进行组织。
• 经验检索: 当需要做出决策时，MEMENTO 会检索与当前状态相关的过去经验。作者采用了基于节点的“桶” (bucket) 策略以提高速度和效率。
• 特征处理: 检索到的条目被输入到一个小型多层感知机 (MLP) 中，该 MLP 输出标量权重。
• Logit 修正: 这些标量权重用于计算修正 logits，并聚合为每个动作的修正量 \(l_M\)。然后将这些修正量加到基础策略的原始 logits \(l\) 上，得到调整后的策略: \[ \hat{l} = l + l_M,\quad \text{with}\quad l_M = \sum_{i} \mathbf{a}_i \cdot H_{\theta_M}(f_{a_i}) \] 其中 \(\mathbf{a}_i\) 代表过去动作 \(a_i\) 的独热 (one-hot) 动作向量，而 \(f_{a_i}\) 是存储经验的归一化特征。
• 训练与推理: 在训练期间，记忆模块和基础模型在多次尝试 (multi-shot) 设置下进行联合训练，允许更新规则学会如何策略性地利用可用预算。至关重要的是，在推理时，所有参数都被冻结。只有记忆会被新的经验填充，而学习到的 MLP 会高效地计算修正，无需对基础模型进行任何反向传播。

核心方法——分步详解

让我们深入了解 MEMENTO 的组成部分:

1. 问题与多次尝试目标

传统的组合问题强化学习通常旨在找到一个策略 \(\pi\)，使得单次解决方案 rollout 的期望回报最大化:

\[ \pi^* = \arg\max_\pi \mathbb{E}_{\tau\sim\pi}[R(\tau)] \]

然而，在实际场景中，求解器通常被分配一个预算 \(B\) 来对每个实例进行多次尝试。在这种情况下，真正的目标是找到所有这些尝试中最优的解决方案。MEMENTO 将这一多次尝试目标形式化:

\[ \pi^* = \arg\max_\pi \mathbb{E}\Big[\max_{b\in\{1,\dots,B\}} R(\tau_b)\Big] \]

通过围绕这一多次尝试目标进行训练，MEMENTO 教会代理理解并将剩余预算作为其决策的重要上下文来加以利用。

2. 记忆内容——存储什么

在构建解决方案的过程中，对于每个经历的转移，MEMENTO 的记忆会存储以下轻量级数据:

• 访问的节点 (Node Visited) : 作为主要的检索键 (例如，在 TSP/CVRP 中是当前城市或客户位置) 。
• 采取的动作 (Action Taken) : 策略决定要访问的下一个节点。
• 对数概率 (Log-Probability) : 基础模型为该动作分配的概率的对数。
• 回报 (Return) : 整个轨迹/解决方案构建的总奖励 (负成本或路径长度) 。
• 剩余预算 (Budget Remaining) : 在采取该动作时仍可用的计算预算。
• 记忆对数概率 (Memory Log-Probability) : 当时 MEMENTO 的记忆为该动作建议的对数概率。
• 轨迹对数概率 (Trajectory Log-Probability) : 与整个解决方案轨迹相关的对数概率。

这组全面的特征包含了 REINFORCE 型更新所需的核心信息 (动作、对数概率、回报) ，以及重要的附加上下文 (剩余预算、轨迹对数概率、数据年龄) 。这些额外特征使 MEMENTO 能够学习更丰富、更细致且具有预算感知性的更新规则。

3. 检索策略——快速且局部

对高维部分解决方案嵌入执行朴素的最近邻搜索会带来巨大的计算开销。MEMENTO 采用了一种务实且高效的折衷: 它仅检索从同一节点收集的数据，该节点是当前决策点。这种基于节点的查找策略显著降低了检索成本，同时保持了高相关性，是 MEMENTO 在速度和可扩展性上的关键工程选择。

4. 记忆处理与构建修正 Logits

当策略处于给定状态 \(s\) 并刚访问了特定节点时，MEMENTO 会从其记忆中检索一小组历史元组 \((a_i, f_{a_i})\)，记为 \(M_s\)。每个特征向量 \(f_{a_i}\) 被归一化，然后与当前剩余预算拼接。一个小型多层感知机 (MLP) ，记为 \(H_{\theta_M}\)，处理每个 \(f_{a_i}\) 以输出一个标量权重。然后，这些权重被用来形成独热动作向量的加权平均:

\[ l_M = \sum_i \mathbf{a}_i H_{\theta_M}(f_{a_i}). \]

这个过程生成一个修正向量，其中每个可能动作对应一个修正值。策略用于采样下一个动作的最终 logits 是通过将这些新修正与基础模型的原始 logits 相加得到的: \(l + l_M\)。

图 3: 使用记忆构建新的动作分布。 检索相关数据并通过 MLP 进行处理，为每个可能的动作推导出 logits。

5. MLP 如何能够重新发现 REINFORCE

REINFORCE 策略梯度更新规则通常会按其回报乘以 \((1-\pi(a))\) 的比例来增加动作的概率。由于 MEMENTO 的输入特征同时包含回报和动作的原始对数概率，MLP 本身就具备学习类似于 REINFORCE 的加权规则的能力。然而，MEMENTO 的优势在于它能够以额外上下文 (如剩余预算) 为条件来学习，从而产生比单独的 vanilla REINFORCE 更新更复杂、更具适应性的行为。

6. 训练: 多次尝试，关注优势的损失函数

在训练期间，MEMENTO 的增强策略会遵循预定义的训练预算，在同一实例上进行多次 rollout。损失函数经过精心设计，优先考虑改进: 每次 rollout 的回报被定义为其回报与当前该实例已达到的最佳回报之差的 ReLU (修正线性单元) 。这确保只有那些改进了当前最佳解决方案的 rollout 才会对学习信号产生积极贡献，从而防止模型因其他虽然尚可但未带来改进的尝试而受到惩罚。此外，预算后期 (later attempts) 的尝试会用对数增长的因子加权，鼓励模型在预算减少时继续探索并寻找更好的解决方案。完整的训练流程 (在原始论文的算法 1 中详细介绍) 涉及迭代地进行尝试、更新记忆，然后在完成一批尝试后，计算梯度来更新基础策略和记忆模块的参数。

7. 推理: 无反向传播，只有记忆和快速 MLP

MEMENTO 的一个关键优势在于其推理时的效率。一旦训练完成，繁重的工作由记忆模块中学习到的 MLP 和内存检索机制处理。基础策略和 MLP 参数均被冻结，这意味着在推理过程中没有计算成本高昂的反向传播。该过程简单地交替进行: 检索相关示例，计算修正 logits，采样新的 rollout，将其转移存储到记忆中，然后重复直到推理预算耗尽。这一设计选择是 MEMENTO 在时间尺度上表现优于依赖反向传播进行在线适应的方法的主要原因之一。

架构与工作流程 (可视化)

从检索过去经验到生成和存储新解决方案的整个 MEMENTO 循环，在图 2 中得到了优雅地捕捉。

图 2: MEMENTO 在推理时使用记忆来调整神经求解器。 在做出决策时，检索并准备来自相似状态的数据 (步骤 1、2) ，然后由 MLP 处理以推导出每个动作的修正 logits (步骤 3) 。将原始 logits 和新 logits 相加可以更新动作分布。然后对结果策略进行 rollout (步骤 4) ，并将转移数据 (包括访问的节点、采取的动作、对数概率和获得的回报) 存储到记忆中 (步骤 5、6) 。

MEMENTO 的学习更新如何与 REINFORCE 比较

论文中一项揭示性的诊断测试展示了 MEMENTO 在动作对数概率与归一化回报平面上的学习到的 logit 修正。虽然经典的 REINFORCE 类似规则会增加具有高回报的低概率动作的概率，但 MEMENTO 学到的方向总体相似，但存在关键区别。它的规则是不对称的 , 要求回报严格高于平均值才能强化一个动作，并且通过其学习到的非线性，它比 vanilla REINFORCE 更有效地放大了强信号。

图 4: MEMENTO 的学习更新规则与 REINFORCE 的比较。 类似于 REINFORCE (左) ，MEMENTO (右) 鼓励具有高回报的动作，尤其是在这些动作的概率较低时。MEMENTO 学到的是一种不对称规则: 要求归一化回报严格为正才能强化一个动作，但它对强信号的鼓励程度更大。

该图直观地展示了为什么 MEMENTO 可以比纯粹的策略梯度微调更有效: 它学习到了何时以及以多大程度去强化动作，并以剩余预算和基础策略置信度等丰富的上下文信息为条件。

实验——关键发现和要点

该研究论文在各种设置下广泛评估了 MEMENTO，并取得了令人信服的结果。

基准设置

• 任务: 两个经典的路径问题: TSP 和 CVRP。
• 实例: 训练和测试实例使用标准的均匀分布。初始训练在 100 节点的实例上进行，泛化测试在更大的分布外尺寸 (125、150、200) 上进行，并进一步扩展到最多 500 个节点的规模实验。
• 基础模型: MEMENTO 在 POMO (一种单策略构造方法) 和 COMPASS (一种基于群体/多样性的方法) 上进行评估。
• 基线: 比较包括 POMO (采样/贪心) 、EAS (策略梯度微调) 、SGBS (树搜索) ，以及 LKH3 和 Concorde 等经典求解器。
• 预算: 实验探索了各种预算区间，从标准基准的 1600 次尝试，到更大实例的低 (25,000) 和高 (100,000) 预算。

MEMENTO vs. EAS (策略梯度推理调优)

在 TSP 和 CVRP 的标准基准 (实例规模 100–200) 上，MEMENTO 在分布内和分布外的任务中均持续优于 EAS 和基础 POMO 模型，改进幅度通常很大。这主要归因于 MEMENTO 的 MLP 使用比简单策略梯度更丰富的特征学会了更具表达力的更新规则，并且在有限预算下具有更好的数据效率。

性能和时间复杂度可视化总结

图 1 提供了 MEMENTO 优势的高层概览。它显示了 MEMENTO 在不同任务中相比 EAS 成为最佳方法的频率，并说明了其时钟时间随解码器深度和实例规模增加时的有利伸缩性。一个关键观察是，随着模型深度的增加，MEMENTO 的速度保持得更稳定，而 EAS 由于在推理时依赖反向传播而出现更陡峭的减速。

图 1: MEMENTO 优于 Efficient Active Search 在多种实例规模和不同评估预算上。其时间复杂度使其能够扩展到大规模实例和策略。

与 COMPASS (群体搜索) 的零-shot 组合

COMPASS 通过搜索潜在空间来寻找最适合的预训练策略来适应实例。论文展示了一种强大的协同效应: 可以在不重新训练 MEMENTO 或 COMPASS 的情况下，在 COMPASS 搜索期间激活 MEMENTO 的记忆模块。该策略是让 COMPASS 在预算的前半段进行广泛探索，然后激活 MEMENTO，利用收集到的 rollout 来微调所选策略的动作分布。这种“零-shot”组合在 MEMENTO 激活后导致了可观的路径长度下降，在大多数基准上达到了最先进 (SOTA) 的性能，而无需额外的训练开销。

图 5: 在搜索过程中结合 MEMENTO 与 COMPASS 于 CVRP200，无需重新训练。

扩展到更大的实例 (500 节点)

在非常大的实例 (例如 500 节点) 上训练自回归 RL 求解器，由于注意力机制的内存限制和批处理限制，面临着严峻的挑战。作者详细介绍了他们如何结合课程学习、高效的注意力机制和梯度累积，成功地在 500 节点实例上训练了 POMO 和 COMPASS。随后，MEMENTO 在这些大规模基础模型之上进行了训练。

在 TSP500 和 CVRP500 上，MEMENTO (无论是单独与 POMO 结合，还是与 COMPASS 结合) 都匹配或超越了其他学习方法，并显著缩小了与 LKH3 和 Concorde 等经典高度优化的求解器之间的差距。论文的表 3 和表 4 总结了这些令人印象深刻的结果，展示了 MEMENTO 在此规模上实现单代理和整体 SOTA 性能的能力。

表 3: MEMENTO 在 TSP500 上取得了 SOTA 性能。 它在两种预算范式下均优于基线，与 POMO 和 COMPASS 结合时分别达到了单代理和整体的 SOTA。

热力图和预算敏感性

图 6 展示了在不同顺序尝试次数和每尝试并行解数下，MEMENTO 和 EAS 的比较热力图。MEMENTO 在低预算区间表现出尤其强劲的增益，并在 TSP 设置中持续占优。对于 CVRP，MEMENTO 在大多数配置下领先，尽管在非常大批量、高预算的情况下 EAS 有时会超过它。这一分析突显了 MEMENTO 的数据效率以及在不同计算约束下的稳健性能。

图 6: MEMENTO 在 500 节点实例上优于 EAS , 跨批量大小和顺序尝试次数。绿色区域表示 MEMENTO 适应更有效率的设置。它在 TSP 中始终优于 EAS，在大多数 CVRP 设置中也表现出色，在低预算下收益显著。

时间复杂度与实际速度

EAS 由于在推理时执行梯度计算和反向传播，其运行时长随基础策略大小 (解码器深度) 和实例规模的增加而更陡峭地增长。相比之下，MEMENTO 的开销主要来自其小型 MLP 和记忆查找，因此要小得多。结果是，MEMENTO 的运行时长增长更平缓。图 7 说明了这一点，显示随着解码器层数和实例规模的增加，MEMENTO 相对于 EAS 变得更快，尤其是在更大、更真实的模型上。

图 7: MEMENTO 和 EAS 的时间复杂度 随解码器大小和实例大小的增加。结果表明 MEMENTO 在时间上比 EAS 具有更好的扩展性。

消融研究——为什么额外的特征和预算条件很重要

MEMENTO 的记忆模块存储的不仅仅是动作、回报和对数概率。它还保留了关键的上下文信息:

• 采取动作时的剩余预算 。
• 数据的年龄 。
• 轨迹级别的对数概率 。
• 当经验最初存储时, MEMENTO 建议的对数概率 。

消融研究揭示了这些额外特征的深远影响。仅仅将“剩余预算”添加为一个特征，就显著改变了学习到的策略。在预算早期，MEMENTO 的学习规则鼓励更广泛的探索，而在后期则转向更集中的利用策略。图 8 展示了在使用完整特征集与仅使用 (回报，对数概率) 相比，在最佳已找到解决方案和最新采样解决方案上的显著性能提升。它表明额外的特征使得复杂的探索策略成为可能，从而导致一个显著更高效的适应机制。

图 8: MEMENTO 记忆特征的消融研究。 该图比较了通常策略梯度估计方法中不可用的记忆特征的影响。左图报告了迄今为止找到的最佳解决方案，而右图显示了最新采样解决方案的性能。它说明了附加特征如何实现复杂的探索策略，从而实现显著更高效的适应机制。

完整的加法消融研究 (图 9) 进一步证实了每一组输入都对整体性能做出了积极贡献。从 (回报 + 对数概率) 的基线开始，添加剩余预算显著提高了性能。随后添加诸如采取动作时的预算、轨迹对数概率等特征，进一步精炼了学习到的更新规则。

图 9: MEMENTO 的完整消融研究。 该图比较了通常策略梯度估计方法中不可用的记忆特征的影响。左图报告了迄今为止找到的最佳解决方案，右图显示了最新采样解决方案的性能。A: return + logp；B: A + remaining budget；C: B + budget when action was taken；D: C + memory logp + trajectory logp + end trajectory logp。

学习规则在整个预算期间的演变

图 11 可视化了 MEMENTO 的 MLP 修正规则如何随着剩余预算的减少而动态变化。在预算早期，规则比较宽泛，通过对多样化的结果赋予中等修正来促进探索。随着预算的减少，修正变得越来越尖锐和有选择性，专注于高回报、高置信度的动作。这种在探索-利用权衡中的时间转移正是多尝试搜索场景中所期望的自适应行为。

图 11: MEMENTO 的学习更新规则随预算阶段的演变。 MEMENTO 在不同预算阶段 (低、中、高) 发现的更新规则。学习到的更新规则随着预算的减少，从广泛探索转向更尖锐的利用。

实践注意事项与局限性

• 记忆大小和检索: MEMENTO 采用轻量的、每节点的缓冲区 (例如，每个节点 40 个条目) 并使用基于节点的检索机制。虽然这一选择在速度上优先于可能更优的检索，但在实践中被证明非常有效。记忆占用随实例规模线性增长，但仍然很小 (通常为几 MB) 。

• 开销与收益: 与无记忆的基础策略相比，MEMENTO 引入了一些额外的计算和内存开销。然而，解决方案质量的显著提升通常会抵消这些成本。重要的是，与推理时反向传播整个 transformer 的成本相比，这种开销很小，使得 MEMENTO 在更大的模型上通常比 EAS 更快。

• 零-shot 兼容性: 尽管 MEMENTO 最初是在 POMO 之上训练的，但它展示了对 COMPASS 的令人印象深刻的零-shot 转移能力。虽然这是一个强大的能力，但作者指出，直接与 COMPASS (或与其他基于多样性的方法联合训练) 训练 MEMENTO 可能会带来进一步的性能提升。

• EAS 获胜的情形: 在特定的 CVRP 配置中，当并行批次非常大，梯度估计特别丰富时，EAS 有时会优于 MEMENTO。这表明这两种方法并非互斥，未来的工作可以探索将基于梯度的精炼与 MEMENTO 的基于记忆的修正相结合。

结论与启示

MEMENTO 为增强神经组合优化求解器提供了一个引人注目且实用的框架。它引入了一个强大的理念: 教会一个小型、快速的模块如何将收集到的局部经验有效地转化为可操作的修正，从而在推理期间增强预训练的神经求解器。主要优势包括:

• 提高样本效率: MEMENTO 比单步梯度更新更有效地利用每次 rollout，从而在相同预算下获得更好的解决方案。
• 预算感知的适应: 通过将更新以剩余预算为条件，MEMENTO 能够智能地在探索和利用之间取得平衡。
• 增强的可扩展性: 与策略梯度微调相比，其推理成本的增长更为平缓，尤其对于更深的解码器和更大的问题实例。
• 更大的灵活性: MEMENTO 与架构无关，并且可以以零-shot 的方式应用于 COMPASS 等其他求解器，证明了其广泛的适用性。

对于从事神经组合优化的实践者来说，MEMENTO 提供了一个轻量且经过充分验证的工具。如果你的用例允许在每个实例上进行多次尝试，并且已经有一个训练好的自回归求解器 (如 POMO) ，那么 MEMENTO 提供了一种简单直接的方法，只需最小的实现工作量即可获得显著更高的性能。

未来方向:

• 将 MEMENTO 与基于多样性的方法 (例如 COMPASS) 联合训练可能会进一步提升性能。
• 探索更复杂的检索策略 (例如基于嵌入的最近邻) 可能会带来更强的更新，但可能会增加计算成本。
• 推导出 MEMENTO 学习到的更新规则的闭式近似，可能会产生更快、更低内存的变体，非常适合资源受限的部署。

MEMENTO 使每一次尝试都变得有价值，推动了高效、自适应神经组合优化领域的最新进展。

---