arXiv cs.AI· Jinhyung Bae·· 10 小时前AI 评分20
神经路由求解器何时值得重新分配采样预算?实例级分配研究
When Does Reallocating a Sampling Budget Pay? Instance-wise Allocation for Neural Routing Solvers
AI 导读
针对 POMO、Attention Model 和 Sym-NCO 三个预训练神经路由求解器,在旅行商问题上非均匀分配采样预算在训练分布内最多只降低 2.5% 的总最优性差距,均匀分配已接近最优。
正文 · AI 翻译
摘要:神经路由求解器对每个实例采样大量解并保留最优解,且对每个实例使用相同数量的采样。我们衡量在总预算相同的情况下,非均匀分配能带来多少价值,以及工作负载的哪种属性决定了这一点。通过对存储样本的随机排序取平均来估计的 best-of-k 曲线会高估收益,而用一半样本做决策、在另一半上评估则会低估收益;我们使用精确的 best-of-k 曲线,即对所有排序的 U 统计量。对于三个预训练求解器(POMO、Attention Model 和 Sym-NCO)在旅行商问题上,重新分配在训练分布上最多将总最优性差距降低 2.5%,因此均匀分配在那里接近最优。在混入分布外实例的工作负载上,对于两个在分布偏移下性能下降的求解器,它将差距降低 11.8-13.3%(巡回长度的 1.1-1.8%),而对于没有性能下降的那个求解器几乎没有任何改善。在两种异质性机制、三个求解器、两个确认集合以及每个实例 25 到 200 个样本的预算下,收益由工作负载内难度的离散程度而非其平均值预测。根据每个实例二十个计费探测样本拟合的幂律曲线进行分配,可恢复未计费最优值的 88-93%;逐次减半效果更差。然而,2-opt 局部搜索以可忽略的成本消除了大部分差距,此后重新分配仅增加巡回长度的百分之几。
| 评论: | v2:合并并修正版本;取代本文 v1 和 arXiv:2608.13087,使用精确 best-of-k 曲线重新分析,并加入新基线和局部搜索对比。27 页,5 幅图。已投稿至 Journal of Heuristics。代码和数据:此 https URL |
| 主题: | 机器学习(cs.LG);人工智能(cs.AI);优化与控制(math.OC) |
| 引用为: | arXiv:2609.27917 [cs.LG] |
| (或 arXiv:2609.27917v2 [cs.LG] 用于此版本) | |
| https://doi.org/10.48550/arXiv.2609.27917 由 DataCite 颁发的 arXiv DOI |
提交历史
来自:Jinhyung Bae [查看电子邮件]
[v1]
2026 年 8 月 21 日星期五 17:54:00 UTC(2,281 KB)
[v2]
2026 年 11 月 18 日星期三 15:53:35 UTC(85 KB)
来源:arXiv cs.AI · arxiv.org