arXiv cs.AI· Andoni Irazusta Garmendia·· 13 小时前AI 评分38
NICO：可泛化到更大规模路径规划问题的学习型局部搜索策略
A First Guess Is Rarely the Final Answer: Learned Local Search That Generalizes to Larger Routing Problems
AI 导读
NICO 是一种学习型 2-opt 策略，通过边级 token 表示当前解、无标度特征和精确增益修正，解决神经改进策略在超出训练规模后性能骤降的问题。仅在最多 100 个节点的实例上训练，它在 1000 节点欧氏 TSP 上取得 1.1% 的最优间隙，而贪心 2-opt 为 10.7%、此前最佳学习策略为 36%。
正文 · AI 翻译
摘要：神经路由求解器很少在第一个解处停止：构造出的路径通常通过搜索进行改进，例如采样或局部搜索。神经改进方法将这种搜索学习为一个反复应用局部移动的策略，但现有策略在超出其训练规模后性能急剧下降。我们认为，规模泛化取决于决定一次移动价值的信息是否以与规模无关的形式到达策略，并指出现有策略在三个方面存在不足：当前解的表示、输入特征的尺度以及移动增益的计算。我们在 NICO 中解决了这三个问题，NICO 是一种用于路由的学习型 2-opt 策略，它用解边表示当前解，每条边一个 token 且不使用位置编码，用无尺度特征描述这些边，并将每次移动的精确增益加到其 logit 上，从而使网络学习对贪心选择的修正。一项受控析因研究表明，边 token 优于带位置编码的节点 token，在测试配置中精确增益对于迁移是必要的，而无尺度特征只有与精确增益一起使用时才有帮助。在最多 100 个节点的实例上训练后，NICO 在 1000 个节点的欧几里得 TSP 上达到 1.1% 的差距，而贪心 2-opt 为 10.7%，最佳先前学习策略为 36%。它还能改进构造型和基于扩散的求解器的路径，是路网成本上的最佳改进方法，并且在 CVRP 上优于所有经典对照方法。
| 学科： | 机器学习 (cs.LG)；人工智能 (cs.AI) |
| 引用为： | arXiv:2604.06940 [cs.LG] |
| （或此版本的 arXiv:2604.06940v3 [cs.LG]） | |
| https://doi.org/10.48550/arXiv.2604.06940 由 DataCite 颁发的 arXiv DOI |
提交历史
来自：Andoni Irazusta Garmendia [查看电子邮件]
[v1]
2026年4月8日星期三 11:04:45 UTC（1,925 KB）
[v2]
2026年5月1日星期五 16:56:33 UTC（1,924 KB）
[v3]
2026年10月28日星期三 08:40:33 UTC（222 KB）
来源：arXiv cs.AI · arxiv.org