点击上方“
计算机书童
”，选择加"
星标
"或“
置顶
”
顶刊论文解读，第一时间分享
题目：ASP: Learn a Universal Neural Solver!
ASP: 学习一个通用的神经求解器！
作者：C. Wang; Z. Yu; S. McAleer; T. Yu; Y. Yang
源码链接：https://github.com/LOGO-CUHKSZ/ASP
摘要
将机器学习应用于组合优化问题有潜力提高效率和准确性。然而，现有的基于学习的求解器在面对问题分布和规模变化时通常难以泛化。在本文中，我们提出了一种新方法，称为ASP：自适应阶梯策略空间响应神谕（Adaptive Staircase Policy Space Response Oracle），以解决这些泛化问题，并学习一个通用的神经求解器。ASP由两个组成部分构成：分布探索（Distributional Exploration），它使用策略空间响应神谕增强求解器处理未知分布的能力；以及持久规模适应（Persistent Scale Adaption），它通过课程学习提高可扩展性。我们在几个具有挑战性的组合优化问题（COPs）上测试了ASP，包括旅行商问题（TSP）、车辆路径问题（VRP）和带奖励收集的TSP，以及来自TSPLib和CVRPLib的真实世界实例。我们的结果表明，即使在相同的模型大小和弱训练信号下，ASP也能帮助神经求解器探索和适应未知的分布和变化的规模，实现卓越的性能。特别是，与标准训练流程下的相同神经求解器相比，ASP在TSP生成实例和真实世界实例的最优性差距方面分别显著降低了90.9%和47.43%，在CVRP上降低了19%和45.57%。
关键词
-
组合优化问题 (Combinatorial optimization problems)
-
课程学习 (curriculum learning)
-
泛化能力和可扩展性 (generalization ability and scalability)
-
策略空间响应神谕 (policy space response oracles)
I. 引言
组合优化问题（Combinatorial Optimization Problems, COPs）由于其在运筹学（Operation Research, OR）和理论计算机科学（Theoretical Computer Science, TCS）中的广泛应用而受到了极大的关注。OR和TCS社区开发了各种求解器来解决COPs，包括精确算法和启发式方法。然而，这些求解器的设计非常劳动密集，需要广泛的领域知识，使得创建新的求解器变得困难。
近期，COPs也引起了机器学习社区的关注，因为发现基于深度学习的“神经求解器”能够通过分析大量的问题实例来捕捉复杂的结构和启发式方法。这些神经求解器在大规模问题上表现出了极高的效率，并且具有减轻设计传统求解器所需繁琐劳动的额外好处。然而，当前的神经求解器在两个主要领域面临泛化问题：问题分布和可扩展性。
几乎所有之前的神经求解器都是在定义良好的问题分布和规模上进行训练和测试的，当应用到实际场景中，问题分布和规模可能会有显著变化时，它们的表现并不理想。这限制了神经求解器作为传统求解器的替代品或替代品的使用。解决以前神经求解器所面临泛化问题的一个潜在解决方案是为不同的设置训练不同的求解器，或者使用一个非常大的模型来处理各种问题实例。然而，这些方法都有其缺点。训练多个求解器可能在计算上非常密集，需要大量的资源，而使用非常大的模型可能会牺牲效率，并可能导致在适应不同设置时性能下降。因此，我们对以下问题感兴趣：我们能否在不牺牲性能的情况下获得一个容量高效的神经求解器，同时克服分布和规模问题？
一些最近的研究尝试从特定角度解决以前神经求解器面临的泛化问题。例如，一些研究专注于在训练期间创建新的分布以解决数据分布问题，而其他研究则检查了将神经求解器适应不同规模的方法。然而，这些方法都没有提供一个全面、系统的方法来普遍解决泛化问题。
在本文中，我们提出了一种称为ASP（自适应阶梯策略空间响应神谕，Adaptive Staircase Policy Space Response Oracle）的新方法，旨在解决以前神经求解器面临的泛化问题，并提供一个可以应用于各种问题分布和规模的“通用神经求解器”。我们的方法结合了博弈论和课程学习，并展示了与传统求解器和以前的神经求解器相比，在多种COPs上的性能改进。具体来说，我们的方法遵循了[6]中提出的两玩家零和元游戏框架，并采用策略空间响应神谕（PSRO）来适应不同的问题分布和规模。我们还引入了阶梯策略的概念，允许我们的方法跨问题规模学习，以便更有效地利用模型的容量。
ASP由两个主要部分组成：分布探索（Distributional Exploration, DE）和持久性规模适应（Persistent Scale Adaption, PSA）。DE使用策略空间响应神谕（PSRO）使神经求解器适应不同的问题分布，而PSA使用自适应阶梯程序逐步增加问题规模的难度，允许神经求解器在广泛的规模上持续提高其性能。与[6]中通过学习混合高斯扰动生成攻击分布并通过蒙特卡洛方法近似策略梯度不同，我们采用了Real-NVP[10]，这是一种通过归一化流生成各种数据分布的更通用的方法，能够以精确概率生成数据。
我们在几个经典的COPs上测试了ASP，包括旅行商问题（Traveling Salesman Problem, TSP）和有容量限制的车辆路径问题（Capacitated Vehicle Routing Problem, CVRP），使用了两种典型的基于强化学习的神经求解器：注意力模型（Attention Model, AM）[2]和POMO[5]。我们的结果显示，与在标准范式下训练的原始求解器相比，ASP能够取得令人印象深刻的改进，并且在TSPLib[11]和CVRPLib[12]数据集上的表现超过了所有其他基于深度学习的神经求解器。此外，我们还进行了消融研究，以证明我们方法的有效性以及模型容量对训练的影响。
总结来说，我们的主要贡献如下：
-
我们提出了ASP框架，旨在克服以前神经求解器在COPs上面临的泛化问题。该框架是模型和问题不可知的，使其可以广泛应用于各种神经求解器和COPs。
-
在不增加模型容量的情况下，ASP允许神经求解器通过交替从不同分布和规模中学习，发现复杂结构，即使在与其他在固定设置下训练的方法相当的训练资源下，也能实现最先进的性能。
-
我们进行了广泛的消融研究，并提供了关于训练策略设计、模型容量、COPs的功能景观等方面的见解。这些发现可以拓宽COPs领域未来研究的视野。
III. NOTATIONS AND PRELIMINARIES
在本节中，我们介绍用于构建我们方法的符号和初步概念。
正规型博弈（Normal Form Game, NFG）是一个元组
，其中
是玩家的数量，
是联合策略集，
是每个联合策略的效用矩阵。如果所有玩家具有相同的策略集
和相同的收益结构，使得玩家可以互换，那么游戏是对称的。
最优响应是针对固定对手策略获得最佳预期性能的策略。如果
是针对
的最优响应，则：
直观地说，如果所有玩家都在玩他们各自的纳什均衡策略，那么没有任何玩家有动机偏离当前策略。
旅行商问题（Traveling Salesman Problem, TSP）的目标是找到一条最短的路线，该路线仅访问每个位置一次并返回原始位置。在本文中，我们只考虑二维欧几里得情况，即每个位置的信息由
组成。
在有容量限制的车辆路径问题（Capacitated Vehicle Routing Problem, CVRP）中，有一个仓库节点和多个需求节点，车辆从仓库节点开始并在多个路线中结束，其中每条路线中的需求节点的总需求不超过车辆的容量。CVRP的目标是在满足所有约束的同时最小化总路线成本。我们还考虑了允许在多条路线上拆分客户需求的拆分交付车辆路径问题（Split Delivery VRP, SDVRP）。
在带奖励收集的旅行商问题（Prize Collecting TSP, PCTSP）中，旅行者在给定的二维位置旅行，每个访问的位置都会获得奖励，并对未能访问的位置支付罚款。目标是在收集足够数量的奖励的同时最小化旅行长度和罚款。我们还考虑了随机PCTSP（Stochastic PCTSP, SPCTSP），其中预期的位置奖励可以预先知道，但实际收集的奖励只有在访问时才知道。
组合优化问题的一个实例涉及单个样本。例如，在旅行商问题（TSP）中，它涉及在二维空间中找到一条最短的游览所有给定点的路线。我们用
表示问题规模为
的实例，它是从实例分布
中抽取的。以TSP为例，一个具有
个节点的实例可以通过随机抽取
对二维坐标来获得，记为
，其中
是预定义的分布。因此，实例分布由下式给出：
最优性差距是衡量求解器质量与最优解预言者（Oracle）的比较。给定实例
和求解器
，最优性差距定义为：
其中
给出了实例的真实最优值。进一步地，求解器在实例分布
下的预期最优性差距定义为：
IV. 方法
在本节中，我们介绍了ASP框架，旨在获得一个在分布和规模上具有强大泛化能力的通用神经求解器。总体上，ASP包含两个主要组成部分：(1) 分布探索（DE）：基于PSRO的训练，针对特定问题规模下分布变化的改进；(2) 持久规模适应（PSA）：基于自适应阶梯的课程，增强在一系列问题规模上的泛化。以下部分将详细阐述它们。
A. 分布勘探
本节中，我们将分布探索制定为一个两玩家的NFG，在元级别上提高神经求解器在分布维度上的泛化能力。在处理问题规模为n的COP实例时，我们假设元游戏中有两个玩家：
-
ΠSS =
Sn_i
是求解器选择器的策略集，其中Sn_i是神经求解器；
-
ΠDG =
PIn,i
是实例分布生成器的策略集，其中PIn,i是问题规模ni下的实例分布。
正式地，我们有一个两玩家非对称NFG (Π, UΠ, 2)，Π = (ΠSS, ΠDG) 是联合策略集，UΠ : Π → R^|ΠSS|×|ΠDG| 是元游戏效用矩阵。给定一个联合策略 π = (Sn, PIn) ∈ Π，其效用由下式给出：
其中 ( UΠSS(π) = -UΠDG(π) = -G(π) ) 是在联合策略π下的预期最优性差距，定义见(2)。元级别上的整体目标是：
其中 Δ(·) 表示给定集合上的概率分布。我们遵循PSRO框架，具体如下：在每次迭代中，给定策略集 Π = (ΠSS, ΠDG) 和元策略 σ = (σSS, σDG)，我们训练两个最优响应：
-
( S' ) 代表一个新的神经求解器，它是针对实例分布生成器σDG的元策略关于策略空间ΠDG的最佳响应。
-
P′_In 代表一个新的实例分布，求解器选择器在遵循σSS关于策略空间ΠSS时表现不佳。给定这两个Oracle，我们更新NFG的联合策略集 Π ← Π ∪ (S′, P′_In) 和元游戏效用 UΠ 根据新的 Π。联合策略集的扩展在寻找难以解决的实例分布的同时，也提高了求解器选择器处理它们的能力。通用算法框架可见算法 1。
上述公式为我们留下了三个算法组件需要解决：(1) 如何获得元策略 σ；(2) 如何训练每个玩家的最优响应；(3) 如何评估效用 UΠ。在接下来的部分中，我们将描述算法的流程。
Meta-Strategy Solvers-鉴于我们在(3)中制定了一个两玩家游戏，最好使用元游戏的纳什均衡作为元策略解决方案，因为它在计算上是高效的。
Best Response Training-我们现在提供训练每个玩家最优响应的高层次结果，更详细的推导见在线附录A。这里我们将ΠSS中的神经求解器表示为 Sθ，ΠDG中的实例分布表示为 PIn,γ，其中θ和γ是可训练参数。
-
对于神经求解器的最佳响应：给定实例分布生成器的元策略 σDG，神经求解器的最佳响应训练目标是：
鉴于在训练期间不能对大量的迭代调用(5)中的“Oracle”，我们可以训练最优响应以获得在分布 PI 下给定的强神经求解器，梯度是：
-
对于实例分布生成器的最佳响应：给定求解器选择器的元策略 σSS，训练目标是：
与神经求解器的训练类似，我们可以省略“Oracle”的调用。否则，为了准确计算(8)中的概率 PIn,γ(In)，我们应用 RealNVP [10]，一种基于归一化流的生成模型，生成对抗性数据。具体来说，我们从简单的先验概率分布开始：
其中 ( pZ(z) = 1, ∀z ∈ [0, 1]^k ) 其中 k 是输入特征的维度。我们通过一个参数化的双射：
由于 Real-NVP 中 fγ 的构造，我们可以高效且准确地计算这个概率，因此我们能够以这种方式计算 PIn,γ(In)。
Evaluation-给定 NFG 中的联合策略 π ∈ Π，我们可以计算效用矩阵 UΠ(π) = (−G(S, PIn), G(S, PIn)) 中的元素，通过近似定义在 (2) 中的预期最优性差距：
完成问题规模 n 的 PSRO 训练后，我们获得最佳神经求解器 Sn_best 和混合分布 Pn = ∑i σDG,iPIn,i 供后续使用。
B. 持续的缩放自适应
考虑一系列问题规模 (n1, n2, ..., nm) 和相应的一些实例分布 P1, ..., Pm，我们希望获得一个在这些规模上具有持久性能的通用神经求解器。在本节中，我们提出了持久规模适应（PSA）程序，在课程学习框架下实现这一点。具体来说，我们可以将这制定为一个多目标问题：
通常通过为每个目标分配权重，将其转换为单一目标问题，导致期望形式：
其中 PPS 是任务选择策略，是问题规模 (n1, n2, ..., nm) 上的离散概率分布，使得 PPS(n = nk) = pk，∑k pk = 1。有许多 PPS 的候选人，例如原始自适应阶梯程序中的均匀分布，但这会误导神经求解器在不适当的任务上训练。这里我们提出了一种基于动量的机制，引导神经求解器专注于正确的任务。
我们将采样概率 {pi} 视为弱信号，引导训练过程朝着目标分布 D 的改进方向。通过评估神经求解器 Sθ 在每个实例分布 Dk = (D, nk) 上的性能，我们可以获得代价向量 c ∈ Rm：
