Paper Reading #6: SymNCO

本文将精读论文 “Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization”，作者 Kim et al.，时间 2022 年，链接 arXiv:2205.13209。

论文概述

这篇论文发表在 NeurIPS 2022 上，提出了 Symmetric Neural Combinatorial Optimization（Sym-NCO）这一训练框架，是一种对 RL4CO 通用的训练策略。它利用 CO 问题的对称性，在损失函数中引入新的正则项，使得模型学到更本质、更泛化的求解策略，从而提升性能。文章在 TSP、CVRP、PCTSP、OP 四类 routing 问题上做了实验。

Abstract

Deep reinforcement learning (DRL)-based combinatorial optimization (CO) methods (i.e., DRL-NCO) have shown significant merit over the conventional CO solvers as DRL-NCO is capable of learning CO solvers less relying on problem-specific ex-pert domain knowledge (heuristic method) and supervised labeled data (supervised learning method). This paper presents a novel training scheme, Sym-NCO, which is a regularizer-based training scheme that leverages universal symmetricities in various CO problems and solutions. Leveraging symmetricities such as rotational and reflectional invariance can greatly improve the generalization capability of DRL-NCO because it allows the learned solver to exploit the commonly shared symmetricities in the same CO problem class. Our experimental results verify that our Sym-NCO greatly improves the performance of DRL-NCO methods in four CO tasks, including the traveling salesman problem (TSP), capacitated vehicle routing problem (CVRP), prize collecting TSP (PCTSP), and orienteering problem (OP), without utilizing problem-specific expert domain knowledge. Remarkably, Sym-NCO outperformed not only the existing DRL-NCO methods but also a competitiveconventional solver, the iterative local search (ILS), in PCTSP at 240× faster speed.Our source code is available at https://github.com/alstn12088/Sym-NCO.

论文的核心思想是，大多数组合优化问题（尤其是那些定义在欧几里得空间上的问题，如TSP、CVRP）都具有对称性。例如，将一个 TSP 的所有城市坐标点整体旋转或翻转，其最优解的路线的形状是不会改变的。然而，现有的 RL4CO 在训练时并没有显式地利用这一先验知识。作者认为，如果能让模型在训练过程中理解并利用这种对称性，模型就能学到更本质、更泛化的求解策略，从而提升性能。Sym-NCO就是为此设计的一套基于正则化的训练框架，通过在损失函数中引入新的正则项，引导模型学习到这种对称不变性。

Introduction

这篇文章要解决的问题是，尽管 DRL-NCO 方法（即 RL4CO 方法）发展迅速，但在解的质量上，它们与高度优化的传统求解器（如LKH3, ILS）或精确求解器（如Concorde）在求解质量上仍然存在差距。那么，有没有通用的训练策略，能够提升 DRL-NCO 方法的表现呢？为此，作者提出了 Sym-NCO 这一训练方法。

首先，定义两种普遍存在于 CO 问题中的对称性：

• 问题对称性 (Problem Symmetricity)：如果两个不同的问题实例 $P^i$ 和 $P^j$ 拥有完全相同的最优解集合，那么它们就是问题对称的。一个典型的例子是，一个 TSP 实例 $P$ 和将它所有坐标点绕原点旋转 90 度后得到的新实例 $Q(P)$，它们的最优路径长度和形状是一样的。
• 解对称性 (Solution Symmetricity)：对于同一个问题实例 $P$，如果两个不同的解 $\pi^i$ 和 $\pi^j$ 得到的目标函数值完全相同，那么它们就是解对称的。例如，在 TSP 中，一条路径和它的逆序路径长度相同。

Sym-NCO 就利用了这两种对称性：问题对称性来源于旋转不变性，即经过旋转的问题实例具有相同的最优解；解对称性来源于具有相同目标值的解。

为了利用对称性，作者决定修改 REINFORCE 的 baseline 项，加入对称性的考虑。具体来说，可以从变换后的问题中，采样出多个解，用它们的平均回报作为 baseline，这样就促进了各个解之前的竞争，这个我们在 POMO 中见过。最终各个解的质量会趋于一致，即实现了问题和解的对称性。具体的做法我们等会展开。

Sym-NCO 是一种模型之上的训练策略，即插即用，能够用来提升已有 RL4CO 模型的性能。

Sym-NCO

Sym-NCO 的核心是一个新的总损失函数的设计：

$$\mathcal{L}_{\text {total }}=\mathcal{L}_{\text {Sym-RL }}+\alpha \mathcal{L}_{\text {inv }}=\mathcal{L}_{\text {ps }}+\beta \mathcal{L}_{\text {ss }}+\alpha \mathcal{L}_{\text {inv }}$$

其中 $\mathcal{L}_{\text {Sym-RL }}$ 是带对称性正则的 REINFORCE 损失，$\mathcal{L}_{\text {inv }}$ 是表征不变性损失 (Invariant Representation Loss)。$\mathcal{L}_{\text {Sym-RL }}$ 又包含了利用解对称性的 $\mathcal{L}_{\text {ss }}$，和利用问题对称性的 $\mathcal{L}_{\text {ps }}$。

带对称性正则的 REINFORCE 损失 $\mathcal{L}_{\text {Sym-RL }}$

传统的 REINFORCE 算法通过比较一个解的 Reward 和一个 Baseline 来更新策略。Sym-NCO 巧妙地设计了新的基线来引入对称性。

利用解对称性 $\mathcal{L}_{\text {ss }}$

为了利用解的对称性，在训练时，对于一个问题实例 $\boldsymbol{P}$，不再是采样一个解，而是一次性采样 $K$ 个解 $\{π^1, \dots, π^K\}$。然后，使用这 $K$ 个解的平均奖励作为所有这 $K$ 个解共同的 Baseline。这和 POMO 其实非常像。

$$\begin{aligned} \mathcal{L}_{\mathrm{ss}} & =-\mathbb{E}_{\boldsymbol{\pi} \sim F_\theta(\cdot \mid \boldsymbol{P})}[R(\boldsymbol{\pi} ; \boldsymbol{P})] \\ \nabla_\theta \mathcal{L}_{\mathrm{ss}} & =-\mathbb{E}_{\boldsymbol{\pi} \sim F_\theta(\cdot \mid \boldsymbol{P})}\left[[R(\boldsymbol{\pi} ; \boldsymbol{P})-b(\boldsymbol{P})] \nabla_\theta \log F_\theta\right] \\ & \approx-\frac{1}{K} \sum_{k=1}^K\left[\left[R\left(\pi^k ; \boldsymbol{P}\right)-\frac{1}{K} \sum_{k=1}^K R\left(\pi^k ; \boldsymbol{P}\right)\right] \nabla_\theta \log F_\theta\right] \end{aligned}$$

这会在这 K 个解之间产生一种内部竞争。奖励高于平均值的解会被增强，低于平均值的会被抑制。这迫使模型生成的多个解质量都比较高且稳定（方差小），利用了解的对称性。

利用问题对称性 $\mathcal{L}_{\text {ps }}$

对于一个原始问题实例 $\boldsymbol{P}$，首先通过随机旋转操作，生成 $L$ 个与之对称的新问题 $\{Q^1(\boldsymbol{P}), \dots, Q^L(\boldsymbol{P})\}$。接着，对这 $L$ 个对称问题中的每一个，都采样 $K$ 个解。最后，计算这 $L \times K$ 个解的总平均奖励，并将其作为所有解的共同 baseline。

$$\begin{aligned} \mathcal{L}_{\mathrm{ps}} & =-\mathbb{E}_{Q^l \sim \mathbf{Q}} \mathbb{E}_{\boldsymbol{\pi} \sim F_\theta\left(\cdot \mid Q^l(\boldsymbol{P})\right)}[R(\boldsymbol{\pi} ; \boldsymbol{P})] \\ \nabla_\theta \mathcal{L}_{\mathrm{ps}} & =-\mathbb{E}_{Q^l \sim \mathbf{Q}}\left[\mathbb{E}_{\boldsymbol{\pi} \sim F_\theta\left(\cdot \mid Q^l(\boldsymbol{P})\right)}\left[[R(\boldsymbol{\pi} ; \boldsymbol{P})-b(\boldsymbol{P}, \boldsymbol{Q})] \nabla_\theta \log F_\theta\right]\right] \\ & \left.\approx \frac{1}{L K} \sum_{l=1}^L \sum_{k=1}^K\left[\left[R\left(\pi^{l, k} ; \boldsymbol{P}\right)-\frac{1}{L K} \sum_{l=1}^L \sum_{k=1}^K R\left(\pi^{l, k} ; \boldsymbol{P}\right)\right] \nabla_\theta \log F_\theta\right]\right] \end{aligned}$$

这个机制不仅要求模型在同一个问题上给出稳定高质量的解，还要求模型对于原始问题和它的旋转版本给出的解质量都一样好。这就在策略层面强迫模型去学习问题的不变性。

表征不变性损失 $\mathcal{L}_{\text {inv }}$

这部分通过一个额外的正则化项，直接在特征层面（representation level）强制模型学习不变性。它将原始问题实例 $x$ 和其随机旋转后的版本 $Q(x)$ 分别输入到模型的 Encoder 中，得到两个隐层表征 $h(x)$ 和 $h(Q(x))$。理论上，如果编码器学到了旋转不变性，这两个表征应该是相似的。

作者通过一个投影头（Projection Head）$g$，将 $h(x)$ 和 $h(Q(x))$ 映射到新的空间，然后最大化这两个投影向量的余弦相似度。

$$\mathcal{L}_{\text {inv }}=-S_{\cos }(g(h(x)), g(h(Q(x))))$$

这个损失项直接监督编码器，使其抽取的特征不受旋转等几何变换的影响。

实验及其结果

在 TSP 和 CVRP 问题上，选择了 POMO 作为基础模型；在 PCTSP 和 OP 问题上，选择了 AM 作为基础模型。这两个模型我们之前都介绍过。

在四个问题上，Sym-NCO 都显著提升了原始基础模型的性能，无论是 Greedy 解码还是 Multi-start 解码，达到 SOTA。在 PCTSP 问题上，Sym-NCO 增强的模型在 Multi-start 采样设置下，其解的质量甚至超越了传统启发式算法 ILS，并且速度快了约 240 倍。这证明了 ML 方法的巨大潜力。