最初の推測はめったに最終解ではない：巡回セールスマン問題における探索の学習
arXiv cs.LG / 2026/4/9
💬 オピニオンSignals & Early TrendsIdeas & Deep AnalysisModels & Research
要点
- 本論文は、多くのニューラルTSPソルバが通常は1本の巡回路のみを出力するように訓練されている一方で、実際のワークフローでは一般的にテスト時サンプリングやローカルサーチの追加が行われることを主張し、探索プロセスそのものを学習する動機を示している。
- 既存の学習による改善（learned-improvement）手法の中核的な制約として、単一解の予測向けに設計された部品を使い回してしまっており、ローカルサーチの仕組みや状態に基づいて構築されていないことを指摘している。
- 提案するNICO-TSPフレームワークは、現在の巡回路を2-opt近傍に整合したエッジトークンで表現することで、2-opt改善ポリシーを学習する。さらに、巡回路の位置埋め込み（positional encodings）を用いずに、候補となる手を直接スコアリングする。
- NICO-TSPは2段階で学習する。まず、短いホライズンにおける最適な改善軌跡で模倣学習を行い、次に、長いロールアウトに対してcritic（批評家）なしのグループベース強化学習を行う。
- 計算量およびウォールクロック時間を揃えた評価において、NICO-TSPはより一貫した、かつ著しくステップ効率の高い改善を達成し、大きな外れ値（out-of-distribution）のTSPインスタンスへの汎化性能も向上する。さらに、古典的なローカルサーチの代替として、あるいは構成的ソルバのテスト時リファインメント（改善）モジュールとして機能し得る。
