NICO：可泛化到更大规模路径问题的学习式局部搜索 2-opt 策略
A First Guess Is Rarely the Final Answer: Learned Local Search That Generalizes to Larger Routing Problems
AI 导读
一项 arXiv 研究提出 NICO，一种学习式 2-opt 局部搜索策略，通过边 token、无量纲特征和精确增益修正来改善规模泛化。仅在至多 100 节点实例上训练，NICO 在 1000 节点欧几里得 TSP 上达到 1.1% gap，而 greedy 2-opt 为 10.7%，此前最佳学习策略为 36%。它还能改进构造式与扩散式求解器的解，并在 CVRP 上优于所有经典对照方法。
正文 · 原文
Abstract:Neural routing solvers rarely stop at their first solution: constructed tours are usually refined by search, such as sampling or local search. Neural improvement methods learn this search as a policy that repeatedly applies local moves, but existing policies degrade sharply beyond their training size. We argue that size generalization depends on whether the information that determines the value of a move reaches the policy in a size-independent form, and identify three places where existing policies fall short: the representation of the incumbent solution, the scale of the input features, and the computation of move gains. We address all three in NICO, a learned 2-opt policy for routing that represents the incumbent by its solution edges, one token per edge without positional encodings, describes them with scale-free features, and adds the exact gain of each move to its logit, so that the network learns a correction to greedy selection. A controlled factorial study shows that edge tokens outperform node tokens with positional encodings, that the exact gains are necessary for transfer in the tested configuration, and that scale-free features help only together with them. Trained on instances with at most 100 nodes, NICO reaches a 1.1% gap on the Euclidean TSP with 1000 nodes, against 10.7% for greedy 2-opt and 36% for the best prior learned policy. It also improves the tours of constructive and diffusion-based solvers, is the best improvement method on road-network costs, and on the CVRP outperforms every classical control.
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2604.06940 [cs.LG] |
| (or arXiv:2604.06940v3 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2604.06940 arXiv-issued DOI via DataCite |
Submission history
From: Andoni Irazusta Garmendia [view email]
[v1]
Wed, 8 Apr 2026 11:04:45 UTC (1,925 KB)
[v2]
Fri, 1 May 2026 16:56:33 UTC (1,924 KB)
[v3]
Wed, 28 Oct 2026 08:40:33 UTC (222 KB)
来源：arXiv cs.AI · arxiv.org