点击上方“计算机书童”，选择加"星标"或“置顶”
顶刊论文解读，第一时间分享
题目：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：
其中 ck 是通过 (10) 评估的，衡量 Sθ 在实例分布 Dk 上的性能。在实现过程中，我们将执行 PSA 程序，直到达到某些条件（例如，达到预设的性能或进行了一定次数的训练迭代），然后我们将第 t 次 PSA 迭代的代价向量表示为 ct = (ct_k)k，并按照以下方式构建 {pt_i}：
其中 pt_i,1 ∝ ⌊ct_i − ct−1_i ⌋+ 与 ⌊x⌋+ = x 如果 x > 0，否则为 0; pt_i,2 ∝ √Var[ct_i]。pt_i,1 帮助我们专注于求解器表现不佳的问题规模，而 pt_i,2 衡量历史表现的稳定性，这有利于训练过程的稳定性。λ 是平衡两个项的权重。
由于 ct 事先未知，并且在训练过程中会变化，我们维护了前 10 步代价向量的历史记录，并在训练期间动态更新 Var[ct_i]，以便我们可以指导训练过程专注于那些性能不满意和不稳定的任务。在训练开始时，我们均匀地采样 ni。整个过程可以在算法 2 中看到。
C. 整个ASP管道
在这一部分，我们通过整合前面部分中的组件，提供自适应阶梯 PSRO (ASP) 框架的详细概述。借鉴课程学习的理念，从简单任务开始，逐步提高难度，我们从最小的问题规模开始训练神经求解器，因为在 COPs 的背景下，较大规模的问题被认为比较小规模的问题更难。受自适应阶梯程序[9]的启发，在每个 ASP 迭代中，我们考虑两个可选程序：(1) 第 IV-A 节中描述的 DE 程序；(2) 第 IV-B 节中描述的 PSA 程序。鉴于我们已经处理的问题规模n1, n2, ..., nm} 和到目前为止训练的神经求解器 Sθ，如果 Sθ 在评估数据集 {Di ∼ Di上的评估结果优于预设阈值 α，我们将在更大的问题规模 nm+1 上进行 DE 程序，这意味着向更难的任务（更大的问题规模）迈进，否则我们将在 {n1, n2, ..., nm} 上调用 PSA 程序，这意味着增强 Sθ 在当前任务上的能力。我们重复这个过程，直到满足某些停止条件，整个流程在算法 3 中展示。
V. 实验
在本节中，我们在几种组合优化问题（COPs）上展示了我们的结果：旅行商问题（TSP）、带容量限制的车辆路径问题（CVRP）、分割交付旅行商问题（SDVRP）、带奖励收集的旅行商问题（PCTSP）和随机带奖励收集的旅行商问题（SPCTSP）。与之前在同一分布上训练和测试、因而无法展示泛化能力的工作不同，我们证明了在从未训练过的分布上的性能，并且只评估一个模型在不同问题规模上的表现。
A. 实验设置
Base Solver - 我们的方法适用于不同的模型和问题，因此我们采用现有的各种COPs上的神经求解器来证明该框架的有效性。我们将未经我们方法训练的神经求解器称为基础求解器，并将使用我们方法训练的神经求解器标注为基础求解器(ASP)。
Training Setting - 所有不同基础求解器和COPs的训练都是从头开始的。考虑到神经求解器在不同COPs上的不同表现，每种COPs选择的基础求解器和性能阈值α的设置也不同，如表I所示。在公式(13)中的权重，我们对所有实验使用λ = 0.5。我们为所有COPs设置了最小和最大的问题规模n1 = 20, nK = 100，以及增量步长nstep = 20。在训练过程中，我们在预设的目标分布D上评估神经求解器，并得到平均评估结果r。还设置了耐心参数γ = 5，以防止神经求解器在当前任务中陷入困境，即如果PSA过程的5次训练迭代后没有进一步的改进，我们将转向更难的任务。
实例分布生成器是基于归一化流的模型Real-NVP[10]，具有5个耦合层，我们使用Adam优化器[44]以学习率为1e-4训练其参数100个周期。此外，当我们开始对更大的问题规模进行DE训练时，我们会重置参数。我们将在在线附录B中留下关于基础求解器和实例分布生成器的模型结构和训练配置的详细设置。
Baselines - 对于TSP，我们比较了通过我们框架训练的神经求解器的解质量和推理速度与精确求解器、非基于学习的启发式方法和基于学习的方法。更具体地说，对应的求解器包括Concorde、Gurobi[45]、LKH3[46]，这是最先进的启发式求解器，以及基于元启发式的近似求解器OR-tools。此外，我们还与最近点、随机点和最远点插入进行了比较。此外，我们还比较了多种基于学习的方法：LIH[16]、AM[2]、MDAM[47]、POMO[5]、GCN[20]和CVAE-opt[48]。对于CVRP，我们测试了通过ASP训练的神经求解器与LKH3、不同时间限制的Gurobi以及以下提到的基于学习的方法的性能：AM、POMO、RL(gr.)[49]、NeuRewriter[50]和CVAE-opt。对于SDVRP，我们与RL(gr.)、AM[2]和MDAM[47]进行了比较。对于PCTSP，我们与Gurobi、OR-Tools以及迭代局部搜索（ILS）的Python版本进行了比较。此外，我们还将神经求解器AM(ASP)与其基线AM[2]进行了比较。对于SPCTSP，我们将神经求解器AM(ASP)与其基线AM和MDAM进行了比较。
Time Consumption - 训练时间是神经求解器的一个重要方面。应用ASP时，除了标准训练消耗外，还将额外消耗训练实例分布生成器和评估DE中的元收益的时间。所有实验都在单个GeForce RTX 3090上进行。在我们的设置下，分别训练POMO在TSP和CVRP上需要1.67天和2.25天；训练AM在TSP和CVRP上分别需要4天和3.3天。当训练AM在其他COPs时，一旦没有进一步的改进，我们会提前停止训练，导致大约2天的训练时间。与基础求解器的训练成本相比，在问题规模50上，训练ASP下的神经求解器所需时间略长，而在问题规模100上则少得多。关于训练成本的详细讨论，我们参考在线附录H。
B. 生成数据的结果
Data Generation - 对于TSP，我们通过从单位正方形中随机采样x ∈ R^2，并从N(0, Σ)中采样y ∈ R^2来生成数据，其中Σ ∈ R^2×2是对角矩阵，其元素从[0, λ]中采样，λ ∼ U(0, 1)。接下来，通过z = x + y生成二维坐标，我们可以通过n次这种采样得到任何规模n的TSP。我们采样了10000个实例，这些实例构成了10组由不同的λ值生成的数据。对于CVRP，二维坐标的生成与TSP相同，需求δ是离散的，从{1, ..., 9}中均匀采样，容量是D20 = 30，D30 = D40 = D50 = 30，D60 = D70 = ... = D100 = 50，最终需求被标准化为ˆδ = δ/D。
评估规模是128。对于PCTSP和SPCTSP，最大长度是L20 = 2, L30 = L40 = L50 = 3, L60 = L70 = ... = L100 = 4。然后我们保持AM[2]中奖励和惩罚的相同生成设置，二维坐标的生成与TSP相同，评估规模是1000。问题规模20、50、100的整体结果如表II所示。
Remark - 值得一提的是，比较场景在开始时：我们在不同问题规模上评估一个基础求解器(ASP)，而其他神经求解器则使用在不同问题规模上训练的模型进行评估。也就是说，我们使用一个通用神经求解器来实现比几个基础求解器（我们的例子中是3个）更好的性能。
Results on TSP - 我们比较了几种基线与几种神经求解器。首先，在接受均匀分布训练的神经求解器在未见过的分布上的性能有大幅下降。具体来说，在平均差距方面，LIH[16]、GCN[20]、MDAM[47]和AM[2]的性能不如经典启发式方法，例如最远点插入和随机插入。这特别不理想，因为神经求解器需要额外的训练成本。CVAE-Opt[48]和POMO[5]的性能相对稳定。对于基础求解器和我们方法的比较，AM(ASP)和POMO(ASP)与AM和POMO相比分别有90.9%和49.4%的巨大下降，而时间消耗几乎没有增加。此外，POMO(ASP)在除了精确方法之外的所有求解器中取得了最佳结果。
Results on VRP - 对于CVRP，神经求解器在时间消耗方面相对于传统求解器具有主导性能。对于解的质量，神经求解器除了POMO[5]外，仍然受到数据分布的严重影响。对于基础求解器和我们方法的比较，AM(ASP)和POMO(ASP)分别比AM和POMO提高了19%和5%，在时间消耗没有增加的情况下。此外，即使与Gurobi (10 s, 50 s, 100 s) [45]和ORTools [51]在解质量和时间消耗方面进行比较，POMO(ASP)在所有这些基线中也取得了最佳性能，显示出神经求解器处理更复杂任务的潜力。对于SDVRP，AM(ASP)与AM相比也有36.2%的改进。
Results on PCTSP - 与经典求解器和启发式方法相比，神经求解器在时间消耗方面仍然具有优越性。对于解的质量，AM和AM(ASP)以很大的优势超过了迭代局部搜索（ILS）。此外，AM(ASP)的性能比AM好，下降了32.2%。与SPCTSP的结果类似，AM(ASP)的性能超过了AM 29.2%，显示出对实际问题的更好的泛化能力。
C. 真实世界数据的结果
我们在表III和IV中展示了在真实数据集上的实验结果。注意，AM和POMO都是在问题规模100下训练的，需要比AM(ASP)和POMO(ASP)多得多的训练时间。
Results on TSP - 我们进一步验证了通过ASP训练的神经求解器在TSPLib [11]上的性能。如表III所示，AM(ASP)在几乎所有实例上都优于AM，平均最优性差距下降了5%。具体而言，对于几个实例：lin105、st70、pr136、kroB150、berlin52、eil101、kroC100、eil76和ch130，ASP可以帮助AM超越OR-Tools。对于POMO [5]，ASP仍然可以在一定程度上改进它。此外，POMO(ASP)在所有列出的方法中表现最佳并且具有更好的平均最优性差距。这些结果表明，通过ASP训练的神经求解器能够处理困难和真实的实例，通过泛化到复杂分布和一系列问题规模。
Results on CVRP - 我们在CVRPLib [12]的B、E、F和X中的真实实例上比较了通过ASP训练的神经求解器与基础求解器AM [2]、POMO [5]和OR-Tools的解质量，涵盖了从22到181的问题规模范围。在这些真实实例中，AM(ASP)在平均最优性差距方面比AM表现更好。神经求解器POMO(ASP)在大约70%（37/53）的选定CVRPlib实例上优于POMO [5]，并且平均差距为3.32%，优于基线6.10%。此外，POMO(ASP)还在47/53实例上优于OR-Tools，平均差距下降了65%。
基于真实基准测试的结果，我们可以得出结论，通过ASP训练的神经求解器可以显著提高泛化能力，同时保持相同的模型容量和更少的训练时间。
VI. 讨论
在本节中，我们对一些关键的训练细节进行了各种消融研究：训练范式、任务选择策略、性能阈值、模型容量和训练样本大小。基于这些结果，我们为ASP框架提供了全面的视角，并为未来神经求解器的训练提供了一些见解。对于所有的消融研究，我们保持其他设置不变，除了我们关注的要素，并在5个随机生成的种子下运行它们。
A. 不同训练模式的比较
为了验证ASP框架的有效性，我们用混合问题规模20、40、60、80和100在均匀分布上训练POMO和AM，我们称之为“Uniformly Train”。如图2所示，Uniformly Train的POMO与ASP框架在TSP上取得了有竞争力的结果，并且在CVRP上表现略差。然而，AM通过均匀训练的表现相当差，甚至在TSP和CVRP的训练失败。这一观察表明，神经求解器并不总是能从简单地混合不同类型的问题实例中受益。然而，ASP框架显示出卓越的可转移性，因此适用于多种神经求解器和COPs。
B. 任务选择策略的影响
它接收来自目标分布的信息以指导训练过程。任务选择策略的两个简单选择是(1) 均匀的，意味着对特定任务没有偏好，和(2) λ = 1，一个短视的选择，强调当前性能。与这些候选策略相比，我们的策略显然具有优越性，因为它同时考虑了改进的需要和稳定性。实验结果表明，这两种候选策略在某些情况下可能会失败。如图3所示，我们在训练过程中对评估数据集进行了神经求解器的评估：Base solver-COP意味着我们在特定的COP上使用ASP框架训练基础求解器，有不同的任务选择策略，“No Std.”、“NoTaskSelection”和“Ours”分别表示λ = 1、均匀策略和λ = 0.5的情况。三个子图表明，这三种策略在某些情况下可能表现良好，例如POMO-TSP的左侧子图。然而，“No Std”和“No Task Selection”在不同随机种子下训练POMO-CVRP时表现出不稳定性，甚至在AM-TSP的训练中失败，因为只考虑改进的短视策略和均匀策略可能会误导训练。然而，ASP对所有神经求解器和COPs在不同随机种子下都表现出稳定性。
C. 性能阈值的影响
适当的阈值对性能有很大益处。过高的期望可能导致犹豫不决，而低期望可能导致松懈。图4显示了在不同性能阈值下神经求解器在训练阶段的评估曲线。对于POMO-TSP，我们选择了三个性能阈值：1、0.8、0.5，并保持其他设置不变；对于AM-TSP，我们选择了阈值 = 8、5、3进行比较。一方面，如果性能阈值设置得过高，ASP框架的训练过程将提前停止，导致PSA程序（算法2）的迭代次数减少。例如，当我们为AM-TSP设置阈值为8时，训练过程在非常早的迭代中就停止了。另一方面，如果阈值过于苛刻，由于模型容量、训练样本大小等限制，神经求解器可能永远无法达到预期。例如，POMO-TSP的阈值为0.5和AM-TSP的阈值为3是如此严格，以至于它们在训练结束时无法实现目标。然而，严格的阈值仍然促使神经求解器获得更好的性能。例如，尽管POMO-TSP无法实现0.5的阈值，但它仍然可以在阈值为0.8的训练中获得更好的性能。
设计阈值的一个明显指导是原始神经求解器的性能，在整个训练过程中是固定的。我们相信，动态阈值调整过程将大有帮助，因为神经求解器在不同问题规模上的性能不同。
D. 模型容量的影响
在整个训练过程中，我们即将处理一组问题规模和更复杂的分布，这比仅关注特定问题规模和均匀分布要困难得多。在处理更难的任务时，模型容量是影响最终结果的重要因素，如图5所示。我们可以看到，具有3个编码器层的AM在训练中失败了，而具有6层和9层的AM可以稳定收敛，这反过来验证了我们的假设。此外，具有9个编码器层的AM-TSP比具有6层的可以获得更好的结果，这意味着更大的容量带来更好的性能。
E. 训练样本量的影响
训练样本大小也是影响最终性能的重要因素。我们在图6中展示了POMO-TSP和AM-TSP的消融结果，性能阈值对于POMO-TSP是0.5，对于AM-TSP是3。在该图的图例中，"Normal" 表示我们训练中默认设置的样本大小N，"Small" 和 "Tiny" 分别表示N/10和N/100的样本大小。相同的阈值可以作为标准，使比较清晰和公平。显然，较大的样本大小显著有助于最终结果的收敛速度和停止迭代。然而，较大的样本大小也意味着更大的计算负担。图6中的右侧条形图显示了不同随机种子的平均训练时间消耗，以小时的对数尺度表示，因此我们需要在现实情况中平衡这种权衡。
F. ASP对景观的影响
关于度量景观的形状是否与泛化能力相关的主张已经有广泛的讨论[52][53][54]。一些研究者认为，"尖锐"的景观会有较差的泛化能力[55][56]，因为训练期间的大批量大小，但其他人提出了专门的训练方法，以在大批量大小下实现良好的泛化能力[56]。在这一部分，我们通过可视化目标函数的景观并讨论一些见解，深入研究了AM和POMO的泛化能力。我们留下了具体的可视化配置和进一步的可视化结果在在线附录F。
Discussion for AM: 我们可视化了AM和AM(ASP)在混合高斯分布上的最优性差距(%)的景观，如图7所示。在参数上相同的扰动设置下，我们可以看到，随着问题规模的增长，景观变得更加陡峭或尖锐。例如，在TSP20、TSP50和TSP100上，AM(ASP)的最优性差距(%)的范围分别为1.7% ～ 129.8%，3.9% ～ 237.4%和5.5% ～ 390.6%，表明问题规模越大，范围就越宽。更尖锐的最小值意味着更难实现[57]，因此我们需要更多地关注优化水平或在训练上花费更多的时间。结合大规模COPs比小规模COPs更难的先验知识，我们可以得出结论，大规模COPs（更难的任务）比小规模COPs（更容易的任务）更难训练，这与常见的实践相符：我们总是需要更多的训练时间，在大规模COPs上的性能比小规模COPs更差。有趣的是，优化水平的观察也与从简单任务开始的课程训练规则相一致：课程训练所做的是从“宽最小值”到“尖锐最小值”。
关于AM和AM(ASP)的比较，我们可以看到AM在TSP50和TSP100的景观相当混乱，而在TSP20上相对平滑，这与表II和6中的结果一致，即AM在TSP20上表现良好，但在TSP50和TSP100上表现差。然而，所有从AM(ASP)获得的景观在所有问题规模上都具有平滑性。
Discussion for POMO: 我们可视化了POMO和POMO(ASP)在混合高斯分布上的最优性差距(%)的景观，如图8所示。问题规模与POMO的泛化能力景观的曲率之间的关系遵循相同的规则：更大的问题规模拥有更尖锐的最优性差距景观。此外，与AM不同，POMO在所有问题规模上都拥有像POMO(ASP)一样的平滑景观，这与表II和6中的结果一致。根据景观的形状，我们可以认为，从某种意义上说，POMO是一个比AM更强大神经求解器。
VII. 结论
受PSRO框架和自适应阶梯的启发，在本文中，我们提出了基于博弈论和课程学习的解决方案ASP，这是第一次从多个方面改进了基于强化学习的神经求解器在COPs上的泛化能力。我们在几种典型的COPs上评估了我们的方法，并采用了不同的神经求解器。在随机生成的和真实世界的基准测试中，我们展示了在与一系列基线比较时，我们框架下训练的神经求解器展示了令人印象深刻的泛化性能。因此，通过ASP训练的神经求解器可能避免过拟合，并在从未训练过的分布和问题规模上一致地实现鲁棒性能，这在现有的神经求解器中是前所未有的。因此，我们合理地相信，ASP可以成为将神经求解器应用于工业用途的第一步。
声明
本文内容为论文学习收获分享，受限于知识能力，本文对原文的理解可能存在偏差，最终内容以原论文为准。本文信息旨在传播和学术交流，其内容由作者负责，不代表本号观点。文中作品文字、图片等如涉及内容、版权和其他问题，请及时与我们联系，我们将在第一时间回复并处理。
下载1：OpenCV-Contrib扩展模块中文版教程
在「小白学视觉」公众号后台回复：扩展模块中文教程，即可下载全网第一份OpenCV扩展模块教程中文版，涵盖扩展模块安装、SFM算法、立体视觉、目标跟踪、生物视觉、超分辨率处理等二十多章内容。
在「小白学视觉」公众号后台回复：Python视觉实战项目，即可下载包括图像分割、口罩检测、车道线检测、车辆计数、添加眼线、车牌识别、字符识别、情绪检测、文本内容提取、面部识别等31个视觉实战项目，助力快速学校计算机视觉。
在「小白学视觉」公众号后台回复：OpenCV实战项目20讲，即可下载含有20个基于OpenCV实现20个实战项目，实现OpenCV学习进阶。
交流群
欢迎加入公众号读者群一起和同行交流，目前有SLAM、三维视觉、传感器、自动驾驶、计算摄影、检测、分割、识别、医学影像、GAN、算法竞赛等微信群（以后会逐渐细分），请扫描下面微信号加群，备注：”昵称+学校/公司+研究方向“，例如：”张三 + 上海交大 + 视觉SLAM“。请按照格式备注，否则不予通过。添加成功后会根据研究方向邀请进入相关微信群。请勿在群内发送广告，否则会请出群，谢谢理解~
