🤖 machine learning

Regularized Large Neighborhood Search

本文引入了正则化大邻域搜索（Regularized Large Neighborhood Search, RLNS），这是一种通过正则化将 LNS 启发式算法转化为高效 MCMC 采样器的创新框架，从而实现了组合优化层的端到端学习，且无需依赖计算上难以实现的全局求解器。

原作者： Germain Vivier-Ardisson, Laurent Demonet, Axel Parmentier, Mathieu Blondel

发布于 2026-06-02

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Germain Vivier-Ardisson, Laurent Demonet, Axel Parmentier, Mathieu Blondel

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你正在试图解决一个巨大且极其复杂的谜题。你拥有成千上万个碎片，它们必须完美地契合在一起，以满足一套严格的规则。在数学和计算机科学领域，这被称为组合优化问题（combinatorial optimization problem）。

几十年来，专家们（运筹学家）使用了一种被称为大邻域搜索（Large Neighborhood Search, LNS）的巧妙技巧来解决这些谜题。把 LNS 想象成一位正在修改小说的高级编辑。他不会试图一次性重写整本书（这几乎是不可能的），而是先冻结 90% 的故事，然后一次只重写其中一个小章节。他找到该章节的最佳版本，将其锁定，然后移动到下一个章节，如此循环往复。这种方法既快速又具扩展性，但它是一种“启发式”方法——即一种寻找“极佳”解而非保证找到“完美”全局解的猜测法。

在房间的另一边，机器学习研究人员正试图通过观察示例来教计算机解决这些谜题。他们希望构建一个“神经网络”（一种人工智能），让它学习谜题的规则并输出解决方案。然而，为了教导这个 AI，计算机需要知道如何调整其“旋钮”（梯度）才能获得更好的答案。这通常需要一个精确的全局求解器——即一种每次都能找到“完美”解的方法。

问题所在：
对于巨大的现实世界谜题（如调度送货卡车或分配任务），寻找那个完美的全局解在计算上是不可能的。它花费的时间将比宇宙的年龄还要长。因此，用于 AI 训练的那些“完美”求解器，无法处理 LNS 专家们每天都在处理的大规模问题。

解决方案：正则化大邻域搜索 (RLNS)
本文的作者弥合了这一差距。他们创造了一种名为正则化大邻域搜索（Regularized Large Neighborhood Search, RLNS）的新方法。

以下是他们如何实现这一点的，使用了几个类比：

1. “平滑”的编辑

标准的 LNS 是僵硬的：它选取谜题的一小部分，并找到修复它的唯一最佳方式。
RLNS 在这个过程中加入了“温度”或“噪声”。想象一下，这位编辑不仅仅是在寻找那句“唯一的最佳”句子，而是被允许根据概率尝试几种略有不同、但“足够好”的句子。

神奇之处： 通过加入这种随机性（正则化），编辑不再仅仅是在“猜测”，而是开始像一个科学采样器一样行动。他们不再只是寻找一个局部峰值，而是在探索景观的方式，随着时间的推移，这种方式能完美地模拟出所有优秀解的统计分布。

2. “块吉布斯”（Block Gibbs）之舞

论文证明了，当你使用一种特定类型的“噪声”（称为熵正则化）时，RLNS 就变成了一个块吉布斯采样器（Block Gibbs Sampler）。

类比： 想象一个有数千人在跳舞的舞池（可能的解）。你想知道人群最可能聚集在哪里。
- 旧方法： 你试图一次性统计整个房间里的每一个人（全局求解器）。对于庞大的人群，这根本不可能。
- RLNS 方法： 你让 90% 的舞者原地不动。你要求剩下的 10% 左右挪动位置，在其他人站立的位置基础上，为他们自己找到最好的位置。然后你再冻结另外 9 de 90%，让新的 10% 进行挪动。
- 结果： 论文证明，如果你持续进行这种“挪动与冻结”的舞蹈，人群最终会呈现出一种模式，这种模式与你完美统计全场人数后得到的结果完全一致。你无需进行不可能的全局计数，就能获得统计学上的真相。

3. 无需“完美”求解器的学习

这对于 AI 学习最大的突破在于。

旧问题： 为了训练 AI，你通常需要知道“完美”答案来计算误差。如果你找不到完美答案，你就无法训练 AI。
RLNS 的解决方法： 作者展示了你只需利用这些“局部挪动”即可训练 AI。
- 如果你进行一次挪动（K=1），AI 基于“伪似然”（pseudolikelihood，一种局部近似）进行学习。这既快速又廉价。
- 如果你进行多次挪动（K=100），AI 则更接近于“精确极大似然”（exact maximum likelihood，即全局真相）进行学习。
- 益处： 你可以调节一个旋钮，在速度和准确性之间进行权衡。你不再需要全局求解器；你只需要一个现成的、运筹学家已经在使用的“局部编辑”（LNS）。

4. 现实世界测试

作者在三种类型的谜题上测试了 RLNS：

选择子集： 比如从 1,000 个项目中恰好挑选 500 个。
广义分配问题： 比如将 50 个包裹分配给空间有限的 5 辆卡车。
车辆调度问题： 比如在交通延迟具有不确定性的情况下，规划送货卡车的路线。

在所有案例中，RLNS 都表现出色。它学习预测优秀解的速度和效率，都高于那些试图使用“黑盒”近似或需要不可能的全局计算的方法。

总结

本文引入了 RLNS，这种方法将一种标准的“局部搜索”启发式算法（通常只能找到一个较好的答案）转变为一种严谨的统计工具，可用于训练 AI 模型。

它允许机器学习模型学习如何解决大规模、复杂的现实世界谜题（如物流和调度），而无需预先解决这些谜题的“完美”版本。它有效地表达了：“我们不需要看到整片森林才能学会如何穿行其中；我们只需要知道如何应对眼前的每一棵树，并且做得足够频繁。”

技术摘要：正则化大邻域搜索 (RLNS)

问题陈述

将组合优化层集成到神经网络中已成为一种强大的结构化预测范式，使模型能够输出满足复杂约束的离散决策。标准形式涉及一个由 $\hat{y}(\theta) \triangleq \arg \max_{y \in \mathcal{Y}} \langle \theta, y \rangle$ 定义的层，其中 $\mathcal{Y}$ 是一个有限但组合规模巨大的可行输出集合。

该设置中的核心挑战在于可微性。由于 $\arg \max$ 算子几乎处处梯度为零，现有方法通常依赖于正则化来产生连续且可微的松弛形式。然而，大多数当前方法（例如 Fenchel-Young 损失、扰动优化器）从根本上假设可以访问全局精确求解器（全局 MAP Oracle）或用于计算 Gibbs 分布期望的边际 Oracle。对于运筹学中常见的 NP 困难优化问题，在每个训练步骤中调用全局 Oracle 在计算上是不可行的。因此，从业者依赖于可扩展的启发式算法，如大邻域搜索 (LNS)，它通过冻结变量的子集并重新优化剩余部分来迭代改进解。缺乏一个将 LNS 作为可微组合层的原则性框架，仍然是一个关键的瓶颈。

方法论：正则化大邻域搜索 (RLNS)

作者引入了正则化大邻域搜索 (RLNS)，这是一种 LNS 的随机版本，旨在弥合可扩展启发式算法与可微优化层之间的差距。其核心思想是在 LNS 框架内正则化或扰动局部子问题，从而将启发式算法转化为在组合可行解集上的高效马尔可夫链蒙特卡洛 (MCMC) 采样器。

1. 框架与局部正则化

RLNS 定义了一族源自全局正则化项 $\Omega$ 的局部正则化函数。对于解的子集 $\mathcal{Z} \subseteq \mathcal{Y}$ ，通过包含映射定义局部正则化项 $\Omega_{\mathcal{Z}}$ 。RLNS 并不直接求解全局正则化问题，而是迭代地从局部正则化分布 $p_{\Omega_{\mathcal{Y}(k)}}((s_\theta)[\mathcal{Y}(k)])$ 中采样，其中 $\mathcal{Y}(k)$ 是通过冻结变量子集 $S^{(k)}$ 定义的局部邻域。

2. 熵正则化与块 Gibbs 采样

当全局正则化项为香农负熵（ $\Omega = -\gamma H_s$ ）时，作者证明了 RLNS 执行的是精确块 Gibbs 采样 (Exact Block Gibbs Sampling)。具体而言，局部正则化分布与给定固定变量后的全局正则化 Gibbs 分布相匹配：
$p_{\Omega_{\mathcal{Y}(k)}}((s_\theta)[\mathcal{Y}(k)](y) = p_{\Omega}(s_\theta)(y \mid y^{(k)}_{[S^{(k)}]})$
在不可约的变量选择方案下，RLNS 迭代的平稳分布精确收敛到全局正则化 Gibbs 分布。这一结果是熵正则化所特有的；命题 2 表明香农熵是唯一能保证这种精确性的可分离正则化项。

3. 基于扰动的正则化

在局部边际 Oracle（实现熵采样所需）难以处理，但局部 MAP Oracle 可用的场景下，作者建议使用基于扰动的正则化。通过在局部得分中加入噪声 $\epsilon Z$ 并求解扰动后的局部极大化问题，RLNS 可以从局部正则化分布中进行采样。这种方法利用了标准的 LNS Oracle（例如用于背包子问题的动态规划），而不需要像基于 Metropolis-Hastings 的局部搜索那样使用样本拒绝机制。

4. 学习与插值

本文建立了 RLNS 迭代次数 ( $K$ ) 与学习目标之间的联系：

$K=1$ (局部 Fenchel-Young 损失)： 单步 RLNS 提供局部 Fenchel-Young 损失的无偏估计量。在熵设置下，这恢复了伪似然 (Pseudolikelihood)（复合似然）目标，即最大化在给定其余变量条件下各变量子集的似然。
$K \to \infty$ (全局 Fenchel-Young 损失)： 随着迭代次数增加，估计量收敛到全局 Fenchel-Young 损失的梯度，近似于精确极大似然估计。
这使得从业者可以通过调整 $K$ 在伪似然与精确极大似然估计之间进行插值，从而实现无需全局求解器的端到端学习。

核心贡献

RLNS 框架： 引入了一种随机正则化版本的 LNS，它将局部正则化集成到 LNS 子问题中，从而创建了一个可微的组合层。
理论等价性： 证明了在熵正则化下，RLNS 实现了一个精确的块 Gibbs 采样器，其平稳分布与全局正则化 Gibbs 分布相匹配。
通过扰动实现易处理性： 论证了基于扰动的正则化允许 RLNS 使用标准的局部 MAP Oracle，确保只要标准 LNS 是可处理的，RLNS 也是可处理的。
学习范式的插值： 从理论和实证上展示了 RLNS 的迭代次数允许在伪似然与精确极大似然估计之间进行插值。
实证验证： 在三个不同问题上进行了评估：
- $\kappa$ -hot 向量： 通过受控估计任务验证了其相对于真实值的收敛性。
- 广义指派问题 (GAP)： 学习预测分配，其中局部子问题为 0/1 背包问题。
- 随机车辆调度： 一个现实世界的基准测试，其中 RLNS-1 的表现优于黑盒微分和二元交叉熵基准，同时所需的计算量显著低于全局求解器。

结果

收敛性： 在 $\kappa$ -hot 向量实验中，RLNS 比局部搜索 MCMC 收敛更快，并且在相同样本数下比蒙特卡洛估计具有更低的平均绝对误差 (MAE)，尤其是在保持高比例变量自由的情况下。
可扩展性： 在 GAP 实验中，RLNS 使用的局部 MAP Oracle 比全局混合整数线性规划 (MILP) 求解器快几个数量级，尤其是在问题规模增加时。
性能： 在随机车辆调度中，RLNS-1（使用单次迭代）在延迟成本方面几乎达到了全局扰动 Fenchel-Young (PFY) 学习的水平，而仅需处理规模约为原问题三分之一的子问题。它显著优于黑盒微分 (DBB) 和二元交叉熵 (BCE) 基准。
偏差分析： 理论界限表明，近似误差随冻结变量与自由变量之间的共享约束（割约束）数量而缩放，这说明了应采用最小化此类交叉依赖关系的变量选择方案（例如最小割选择）。

重要性与主张

本文声称填补了文献中的一个关键空白，即通过使用高度可扩展的启发式算法 (LNS) 作为神经网络中的可微层，消除了对计算上不可行的全局求解器的依赖。通过建立 LNS 与 Gibbs 采样的严格联系，这项工作提供了一个仅通过局部 Oracle 即可对组合优化层进行微分的原则性框架。作者将 RLNS 定位为处理涉及 NP 困难约束的结构化预测任务中，实现端到端学习的一种实用解决方案，通过迭代次数 $K$ 提供了一种在计算成本与统计准确性之间的可调权衡。