TPAMI 2024 | ASP：提升深度神经求解器在组合优化问题中泛化能力的通用框架|asp|神经求解器|算法|视频生成模型

随着机器学习技术在组合优化问题中的应用日益广泛，设计一个具有强大泛化能力的神经求解器显得尤为关键。强大的泛化能力不仅关系到求解器在面对不同问题、特别是新问题的分布和规模时能否保持高效的性能，也是推动机器学习技术在复杂系统决策和优化中能否进一步应用的关键。然而，现有的神经求解器往往只关注特定的数据分布及问题规模，极大地阻碍了其在实际场景中的应用。

北京大学人工智能研究院杨耀东课题组联合香港中文大学（深圳）数据科学学院于天舒课题组通过提出自适应提升的策略空间响应（ASP：Adaptive Staircase Policy Space Response Oracle）框架，有效应对数据分布和问题规模的泛化难题。该框架通过构建数据分布生成器和神经求解器的二人零和博弈，不断提升神经求解器针对数据分布的泛化性；同时受人类学习过程的启发，通过课程学习来提升神经求解器在不同问题规模上的泛化性。经过ASP框架的训练，现有的神经求解器在多种车辆路径问题上，无论问题规模大小或是面对数据未知分布都展现了出色的泛化能力。此项成果论文ASP: Learn a Universal Neural Solver!已被TPAMI 2024接收。

论文题目： ASP: Learn a Universal Neural Solver! 论文链接： https://ieeexplore.ieee.org/abstract/document/10387785 GitHub链接： https://github.com/LOGO-CUHKSZ/ASP

一、引言

利用深度学习技术解决组合优化问题已成为当今机器学习领域的一个前沿课题。目前许多的研究都致力于设计各种神经求解器来应对不同的组合优化问题。这些研究尽管在求解质量和实践中相较传统方法已经具有较大优势，然而他们通常缺乏泛化能力，大多数只适用于给定组合优化问题的特定规模，当面对问题实例的分布或规模发生变化时性能往往会急剧下降。

为了缓解上述问题，我们为现有的神经求解器提供了一个通用的提升泛化能力的训练框架：ASP(Adaptive Staircase Policy Space Response Oracle)。该框架由两部分组成：

分布探索机制：构造问题实例生成器和神经求解器的二人零和博弈，通过PSRO(Policy Space Response Oracle)的对抗训练来提升神经求解器在未知分布上的泛化性；
持续性规模适应机制：借助课程学习，按照从简单到复杂的学习轨迹不断提升神经求解器在不同问题规模上的泛化能力。

实验表明，在多个车辆路径规划问题上，经过ASP框架训练的神经求解器无论是在生成数据集还是在实际数据集上都展现出了极大的泛化性能提升。

二、方法介绍

ASP算法框架：在第i次迭代过程中，ASP 根据当前神经求解器在验证集上的表现，决定是关注更大问题规模上的泛化能力（左图Algorithm 1），还是加强在已知问题规模上的泛化能力（右图Algorithm 2）。

2.1 基于PSRO的分布探索机制

PSRO (Policy Space Response Oracle) 是一种在多智能体环境发现高效策略的算法框架，旨在寻找多智能体构成的博弈中的纳什均衡。在本工作中，我们首先针对特定的问题规模，构建了一个由数据生成器和神经求解器组成的二人正则零和博弈：

数据生成器的目标是寻找神经求解器难以解决的实例分布（即神经求解器的弱点分布），神经求解器通过在已找到的弱点分布上进行训练来克服这些弱点，从而提升在数据分布上的泛化能力。算法框架包括如下三个关键步骤：

元策略的获取：在PSRO博弈中，使用纳什均衡作为所构造的二人正则零和博弈的元求解器；
最优反应的获取：在博弈过程中，使用策略梯度算法分别获取更新的数据生成器和神经求解器的梯度：

其中，数据生成器基于Normalizing Flow生成模型的RealNVP[1]，神经求解器可以采用任何基于神经网络的求解方法。

策略性能的衡量：通过给定的数据生成器和神经求解器采样问题实例并进行求解，来衡量当前策略的优劣：

2.2 基于课程学习的持续性规模适应机制

心理物理学中有一种常用的实验方法：自适应阶梯法（Adaptive Staircase），其核心原理是根据参与者对刺激的反应来调整后续刺激的强度。如果参与者能够正确感知到刺激，实验者将降低刺激强度，直到参与者无法感知；相反，如果参与者未能感知到刺激，刺激强度将增加，直到参与者能够感知。

我们将这种方法与课程学习相结合：从简单的任务开始，当神经求解器在当前任务上的求解性能超过一定阈值时提升任务难度；当出现灾难性遗忘（即提升较难任务的处理能力时，在较容易任务上性能下降）时，及时强化历史任务上的能力以实现在不同任务上总体性能的提升。这与人类的学习过程一致：从简单的知识开始逐步提升难度并及时复习。遵循组合优化问题中的常识：问题规模越大，任务越困难。我们提出持续性规模适应机制，算法如下：

2.3 整体算法流程

ASP训练框架由分布探索和持续性规模适应交替进行：给定问题规模，通过分布探索机制提升神经求解器在数据分布上的泛化性能，若验证性能超过阈值，下一步在更大的问题规模上使用分布探索机制，否则针对历史任务根据持续性规模适应机制进行性能强化，直至达到阈值或触发终止条件。具体算法流程如下：

三、实验结果

针对多种车辆路径规划问题：TSP, CVRP, SDVRP, PCTSP和SPCTSP，我们分别在生成数据集和实际数据集上进行测试。

3.1 生成数据上的实验性能

我们首先生成未经过训练的数据，然后考察针对车辆路径规划问题的两种常用神经求解器：AM[2]和POMO[3]在是否使用ASP时性能的差异，结果如表1所示。

对于TSP，我们将多个基准模型与几种神经求解器进行了比较。首先，在均匀分布上训练的神经求解器在未见分布上的性能大幅下降。通过ASP方法的AM(ASP)和POMO(ASP)相较于AM和POMO分别有了90.9%和49.4%的巨大提升，而且没有明显增加时间消耗。

对于CVRP，神经求解器在时间消耗方面相比于经典求解器有着明显的优势。在基准求解器与我们方法的比较中，AM(ASP)和POMO(ASP)相对于AM和POMO分别有了19%和5%的提升，且没有增加时间消耗。此外，即便与Gurobi和OR-Tools在求解质量和时间消耗方面进行比较，POMO(ASP)也展现出了所有这些基准中最好的性能，显示了神经求解器处理更复杂任务的潜力。

对于SDVRP，AM(ASP)相对于AM也有36.2%的提升。

关于PCTSP的结果与经典求解器和启发式算法相比，神经求解器在时间消耗上仍然有优势。就求解质量而言，AM和AM(ASP)大幅领先于迭代局部搜索(ILS)。此外，AM(ASP)的性能明显优于AM，有32.2%的提升。

在SPCTSP上，AM(ASP)的性能大幅超过了AM，达到了29.2%的提升，展示了对实际问题更好的泛化能力。

表1：生成数据集上的实验效果。粗体数字表示经过ASP训练的神经求解器的性能优于未经ASP训练的版本，下划线数字表示所有启发式方法中的最佳性能。

3.2 实际数据上的实验性能

我们进一步在TSPLib中验证了经过ASP训练的神经求解器的性能。如表2所示，AM(ASP)在几乎所有实例中都优于AM，平均最优性间距降低了5%。具体来说，对于实例lin105、st70、pr136、kroB150、berlin52、eil101、kroC100、eil76和ch130，ASP可以帮助AM超越OR-Tools。对于POMO，ASP仍然能在一定程度上改善其性能。更重要的是，POMO(ASP)超过了所有列出的方法，并且具有更好的平均最优性差距。上述结果表明，经过ASP框架训练的神经求解器具备处理困难和真实实例的能力。

表2：在TSPLib上的实验效果。下划线和粗体数字分别表示优于 OR-Tools 和未经ASP训练的神经求解器的结果。

四、总结

博弈学习的引入为深度神经求解器的训练提供了一种新的视角：通过模拟决策者之间的相互作用和竞争，促进求解器更好地理解和适应动态变化的环境。这不仅有助于提高求解器的鲁棒性，还能提升其在面对新问题时的适应能力和泛化性，这为神经求解器在复杂实际场景中的应用提供了可能性。近期，AlphaGeometry的成功说明了大语言模型在求解数学问题上具有巨大的潜力，接下来将探索利用大型语言模型辅助解决组合优化问题将成为未来研究的焦点。

References

[1]. Dinh L, Sohl-Dickstein J, Bengio S. Density estimation using real nvp[J]. arXiv preprint arXiv:1605.08803, 2016.

[2]. Kool, Wouter et al. “Attention, Learn to Solve Routing Problems!” International Conference on Learning Representations (2018).

[3]. Kwon Y D, Choo J, Kim B, et al. Pomo: Policy optimization with multiple optima for reinforcement learning[J]. Advances in Neural Information Processing Systems, 2020, 33: 21188-21198.

Illustration From IconScout By Delesign Graphics

-The End-

扫码观看！

本周上新！

“AI技术流”原创投稿计划

TechBeat是由将门创投建立的AI学习社区（www.techbeat.net）。社区上线500+期talk视频，3000+篇技术干货文章，方向覆盖CV/NLP/ML/Robotis等；每月定期举办顶会及其他线上交流活动，不定期举办技术人线下聚会交流活动。我们正在努力成为AI人才喜爱的高质量、知识型交流平台，希望为AI人才打造更专业的服务和体验，加速并陪伴其成长。

投稿内容

// 最新技术解读/系统性知识分享 //

// 前沿资讯解说/心得经历讲述 //

投稿须知

稿件需要为原创文章，并标明作者信息。

我们会选择部分在深度技术解析及科研心得方向，对用户启发更大的文章，做原创性内容奖励

投稿方式

发送邮件到

chenhongyuan@thejiangmen.com

或添加工作人员微信（chemn493）投稿，沟通投稿详情；还可以关注“将门创投”公众号，后台回复“投稿”二字，获得投稿说明。

关于我“门”

将门是一家以专注于数智核心科技领域的新型创投机构，也是北京市标杆型孵化器。公司致力于通过连接技术与商业，发掘和培育具有全球影响力的科技创新企业，推动企业创新发展与产业升级。