伊利诺伊大学香槟分校:Ruizhong Qiu | DIMES：组合优化问题的可微元解法

【标题】DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems

【作者团队】Ruizhong Qiu, Zhiqing Sun, Yiming Yang

【发表日期】2022.10.8

【论文链接】https://arxiv.org/pdf/2210.04123.pdf

【推荐理由】最近，深度强化学习（DRL）模型在解决NP难组合优化（CO）问题方面显示出了良好的结果。然而，对于图上的组合优化问题，如旅行推销员问题（TSP），大多数DRL求解器只能扩展到几百个节点。本文通过提出一种新的方法，即DIMES，解决了大规模组合优化中的可扩展性挑战。与以前的DRL方法不同，该方法需要昂贵的自回归解码或离散解的迭代细化，DIMES引入了一个紧凑的连续空间，用于参数化候选解的潜在分布。这样的连续空间允许通过大规模并行采样进行稳定的基于增强的训练和微调。并进一步提出了一个元学习框架，以便在微调阶段有效初始化模型参数。大量实验表明，对于Traveling Salesman问题和Maximal Independent Set问题，DIMES在大型基准数据集上的性能优于最近基于DRL的方法。