論文の概要: L2R: Learning to Reduce Search Space for Generalizable Neural Routing Solver

• arxiv url: http://arxiv.org/abs/2503.03137v1
• Date: Wed, 05 Mar 2025 03:25:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-06 15:52:27.366731
• Title: L2R: Learning to Reduce Search Space for Generalizable Neural Routing Solver
• Title（参考訳）: L2R: 一般化可能なニューラルルーティングソルバのための検索スペース削減学習
• Authors: Changliang Zhou, Xi Lin, Zhenkun Wang, Qingfu Zhang,
• Abstract要約: 構成的ニューラル最適化(NCO)は、手作りのルールに頼ることなく複雑なルーティング問題を解決する能力によって、研究の注目を集めている。 既存のNCO手法は、計算の複雑さと構造パターンの非効率な捕捉により、大規模問題に一般化する際の課題に直面している。 建設的NCOプロセスの各ステップにおいて,少数の有望な候補ノードを適応的に選択する,学習に基づく探索空間削減手法を提案する。
• 参考スコア（独自算出の注目度）: 12.396576646539252
• License:
• Abstract: Constructive neural combinatorial optimization (NCO) has attracted growing research attention due to its ability to solve complex routing problems without relying on handcrafted rules. However, existing NCO methods face significant challenges in generalizing to large-scale problems due to high computational complexity and inefficient capture of structural patterns. To address this issue, we propose a novel learning-based search space reduction method that adaptively selects a small set of promising candidate nodes at each step of the constructive NCO process. Unlike traditional methods that rely on fixed heuristics, our selection model dynamically prioritizes nodes based on learned patterns, significantly reducing the search space while maintaining solution quality. Experimental results demonstrate that our method, trained solely on 100-node instances from uniform distribution, generalizes remarkably well to large-scale Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) instances with up to 1 million nodes from the uniform distribution and over 80K nodes from other distributions.
• Abstract（参考訳）: 構成的ニューラルネットワーク最適化(NCO)は、手作りのルールに頼ることなく複雑なルーティング問題を解決する能力によって、研究の注目を集めている。 しかし、既存のNCO法は、計算の複雑さと構造パターンの非効率な捕捉により、大規模問題への一般化において重大な課題に直面している。 そこで本研究では,建設的NCOプロセスの各ステップにおいて,少数の候補ノードを適応的に選択する,学習に基づく検索空間削減手法を提案する。 固定ヒューリスティックスに依存する従来の手法とは異なり、我々の選択モデルは学習パターンに基づいて動的にノードを優先順位付けし、解の質を維持しながら検索スペースを大幅に削減する。 実験結果から, 均一分布から100ノードインスタンスのみを訓練した本手法は, 大規模トラベリングセールスマン問題 (TSP) や, 最大100万ノード, 他分布から80万ノード以上を有するキャパシタイト車両ルーティング問題 (CVRP) に対して, 極めてよく適用可能であることが示された。

関連論文リスト

• Boosting Generalization in Diffusion-Based Neural Combinatorial Solver via Energy-guided Sampling [27.898573891403075]
  拡散に基づくニューラルネットワーク最適化(NCO)は、解生成のための離散拡散モデルを学習し、手作りのドメイン知識を排除し、NP完全(NPC)問題の解決に有効であることを示した。 既存のNCO手法は、クロススケールおよびクロスプロブレムの一般化において課題に直面し、従来の解法と比較して高いトレーニングコストがかかる。 我々は,拡散型NCOソルバのクロススケールおよびクロスプロブレムの一般化能力を,追加の訓練を必要とせずに向上させる,一般エネルギー誘導サンプリングフレームワークを提案する。
  論文  参考訳（メタデータ） (2025-02-15T08:04:00Z)
• Unsupervised Training of Diffusion Models for Feasible Solution Generation in Neural Combinatorial Optimization [7.85458999849461]
  我々は,拡散モデルをゼロから直接訓練する,教師なしCOフレームワークであるIC/DCを提案する。 私たちは、問題固有の制約を順守しながら、ソリューションのコストを最小限に抑えるために、自己監督的な方法でモデルをトレーニングします。 並列マシンスケジューリング問題(PMSP)と非対称トラベリングセールスマン問題(ATSP)における既存のNCO手法と比較して、IC/DCは最先端の性能を達成する
  論文  参考訳（メタデータ） (2024-10-15T06:53:30Z)
• Instance-Conditioned Adaptation for Large-scale Generalization of Neural Combinatorial Optimization [15.842155380912002]
  本研究は,ニューラル最適化の大規模一般化のための新しいインスタンス・コンディション適応モデル(ICAM)を提案する。 特に,NCOモデルのための強力なインスタンス条件付きルーティング適応モジュールを設計する。 我々は,ラベル付き最適解を使わずに,モデルがクロススケールな特徴を学習することのできる,効率的な3段階強化学習ベーストレーニング手法を開発した。
  論文  参考訳（メタデータ） (2024-05-03T08:00:19Z)
• Self-Improved Learning for Scalable Neural Combinatorial Optimization [15.842155380912002]
  本研究は、ニューラルネットワーク最適化のスケーラビリティを向上させるための新しい自己改善学習(SIL)手法を提案する。 我々は,ラベル付きデータを使わずに大規模問題インスタンス上での直接モデルトレーニングを可能にする,効率的な自己改善機構を開発した。 さらに,計算モデルに対する線形注意複雑化機構を設計し,オーバヘッドの少ない大規模問題インスタンスを効率的に処理する。
  論文  参考訳（メタデータ） (2024-03-28T16:46:53Z)
• An Efficient Learning-based Solver Comparable to Metaheuristics for the Capacitated Arc Routing Problem [67.92544792239086]
  我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。 まず,方向対応型注意モデル(DaAM)を提案する。 第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
  論文  参考訳（メタデータ） (2024-03-11T02:17:42Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。 我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。 本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
  論文  参考訳（メタデータ） (2023-10-08T23:39:38Z)
• Too Big, so Fail? -- Enabling Neural Construction Methods to Solve Large-Scale Routing Problems [10.832715681422842]
  最先端のニューラルコンストラクション手法でさえ、単純なイテレーションによって性能が向上していることを示す。 本稿では, 解の局所的な部分を完全に破壊し, 改良された変種を再現する。
  論文  参考訳（メタデータ） (2023-09-29T09:36:37Z)
• DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization [51.517956081644186]
  グラフベースの拡散フレームワークであるDIFUSCOを導入する。 本フレームワークは, NPC問題を離散0, 1ベクトル最適化問題とみなす。 MIS問題に対して、DIFUSCOは、挑戦的なSATLIBベンチマークにおいて、以前の最先端のニューラルソルバよりも優れている。
  論文  参考訳（メタデータ） (2023-02-16T11:13:36Z)
• MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion Control in Real Networks [63.24965775030673]
  そこで本研究では,汎用的な渋滞制御(CC)アルゴリズムを設計するための新しい強化学習(RL)手法を提案する。 我々の解であるMARLINは、Soft Actor-Criticアルゴリズムを用いてエントロピーとリターンの両方を最大化する。 我々は,MARLINを実ネットワーク上で訓練し,実ミスマッチを克服した。
  論文  参考訳（メタデータ） (2023-02-02T18:27:20Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  置換フローショップスケジューリング(PFSS)は製造業で広く使われている。 我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。 我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
  論文  参考訳（メタデータ） (2022-10-31T09:46:26Z)
• MineReduce: an approach based on data mining for problem size reduction [58.720142291102135]
  本稿では,マイニングパターンを用いて問題サイズの削減を行うMineReduceという手法を提案する。 異種車両ルーティング問題に対するMineReduceの適用について述べる。
  論文  参考訳（メタデータ） (2020-05-15T08:49:50Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。