論文の概要: Graph Neural Network Guided Local Search for the Traveling Salesperson Problem

• arxiv url: http://arxiv.org/abs/2110.05291v1
• Date: Mon, 11 Oct 2021 14:06:08 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-12 15:54:33.260378
• Title: Graph Neural Network Guided Local Search for the Traveling Salesperson Problem
• Title（参考訳）: グラフニューラルネットワークによる巡回セールスパーソン問題の局所探索
• Authors: Benjamin Hudson and Qingbiao Li and Matthew Malencia and Amanda Prorok
• Abstract要約: グラフニューラルネットワーク(GNN)とガイドローカルサーチ(GLS)に基づくトラベリングセールスパーソン問題(TSP)を解決するためのハイブリッドデータ駆動型アプローチを提案する。 提案手法では,次のベストラーニングベースベンチマークよりも10倍,平均最適性ギャップ2.5%の解を求める。
• 参考スコア（独自算出の注目度）: 5.906031288935515
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Solutions to the Traveling Salesperson Problem (TSP) have practical applications to processes in transportation, logistics, and automation, yet must be computed with minimal delay to satisfy the real-time nature of the underlying tasks. However, solving large TSP instances quickly without sacrificing solution quality remains challenging for current approximate algorithms. To close this gap, we present a hybrid data-driven approach for solving the TSP based on Graph Neural Networks (GNNs) and Guided Local Search (GLS). Our model predicts the regret of including each edge of the problem graph in the solution; GLS uses these predictions in conjunction with the original problem graph to find solutions. Our experiments demonstrate that this approach converges to optimal solutions at a faster rate than state-of-the-art learning-based approaches and non-learning GLS algorithms for the TSP, notably finding optimal solutions to 96% of the 50-node problem set, 7% more than the next best benchmark, and to 20% of the 100-node problem set, 4.5x more than the next best benchmark. When generalizing from 20-node problems to the 100-node problem set, our approach finds solutions with an average optimality gap of 2.5%, a 10x improvement over the next best learning-based benchmark.
• Abstract（参考訳）: トラベルセールスパーソン問題(tsp)の解決策は、輸送、物流、自動化のプロセスに実用的な応用があるが、基礎となるタスクのリアルタイム性を満たすために、最小限の遅延で計算する必要がある。 しかし、現在の近似アルゴリズムでは、ソリューションの品質を犠牲にすることなく、大規模なTSPインスタンスを迅速に解決することは困難である。 このギャップを埋めるために、グラフニューラルネットワーク(GNN)とガイドローカルサーチ(GLS)に基づくTSPを解くためのハイブリッドデータ駆動型アプローチを提案する。 我々のモデルは問題グラフの各エッジを解に含めることの後悔を予測し、GLSはこれらの予測を元の問題グラフと併用して解を見つける。 我々の実験は、この手法が最先端の学習ベースアプローチやTSPの非学習GLSアルゴリズムよりも速い速度で最適解に収束することを示し、特に50ノード問題セットの96%、次のベストベンチマークの7%、100ノード問題セットの20%、次のベストベンチマークの4.5倍の最適解を見出した。 20ノード問題から100ノード問題集合に一般化すると、平均最適性差2.5%の解が、次の最良の学習ベースのベンチマークよりも10倍向上する。

関連論文リスト

• BalMCTS: Balancing Objective Function and Search Nodes in MCTS for Constraint Optimization Problems [7.196057722218442]
  制約問題最適化(COP)は、通常ブランチ・アンド・バウンド(B&B)法によって解決される問題において、複雑な課題を提起する。 COPを解くための深度優先探索アルゴリズムに基づく新しいニューラルネットワークアルゴリズムを提案する。 提案手法は,最初の5つの実現可能な解のうち17.63%未満のギャップを有する実現可能な解を同定する。
  論文  参考訳（メタデータ） (2023-12-26T03:09:08Z)
• DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization [51.517956081644186]
  グラフベースの拡散フレームワークであるDIFUSCOを導入する。 本フレームワークは, NPC問題を離散0, 1ベクトル最適化問題とみなす。 MIS問題に対して、DIFUSCOは、挑戦的なSATLIBベンチマークにおいて、以前の最先端のニューラルソルバよりも優れている。
  論文  参考訳（メタデータ） (2023-02-16T11:13:36Z)
• Learning to repeatedly solve routing problems [5.08128537391027]
  データのマイナーチェンジ後に問題の再最適化について学習した。 元のソリューションのエッジを考慮すれば、最適なソリューションに留まる確率の高いソリューションを予測し、修正することが目標です。 この解の偏差予測は問題の複雑さを減らし、解を高速化する。
  論文  参考訳（メタデータ） (2022-12-15T19:33:54Z)
• 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)
• Neural Improvement Heuristics for Graph Combinatorial Optimization Problems [49.85111302670361]
  本稿では,ノード,エッジ,あるいはその両方に情報をエンコードするグラフベースの問題を扱う新しいニューラル改善(NI)モデルを提案する。 提案モデルは,各地区の操作の選択を誘導する丘登頂に基づくアルゴリズムの基本的な構成要素として機能する。
  論文  参考訳（メタデータ） (2022-06-01T10:35:29Z)
• Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration [72.15369769265398]
  実験により、ECORDは最大カット問題に対するRLアルゴリズムのための新しいSOTAを実現する。 最も近い競合と比較して、ECORDは最適性ギャップを最大73%削減する。
  論文  参考訳（メタデータ） (2022-05-27T17:13:10Z)
• Solve routing problems with a residual edge-graph attention neural network [10.42872026679616]
  本稿では,NP-ハード最適化問題を解決するために,エンドツーエンドの深層強化学習フレームワークを提案する。 提案するフレームワークは、ニューラルネットワークモデルとトレーニングアルゴリズムの観点から、リテラシーのモデルを改善することを目指している。 具体的には、平均最適性ギャップは、100ノードのTSPで4.53%(ベスト citeR22として報告)から3.67%(ベスト citeR22で報告)、100ノードのCVRPで7.34%(ベスト citeR22で報告)から6.68%に縮小される。
  論文  参考訳（メタデータ） (2021-05-06T14:47:47Z)
• Distributed Multi-agent Meta Learning for Trajectory Design in Wireless Drone Networks [151.27147513363502]
  本稿では,動的無線ネットワーク環境で動作するエネルギー制約型ドローン群に対する軌道設計の問題点について検討する。 値ベース強化学習(VDRL)ソリューションとメタトレイン機構を提案する。
  論文  参考訳（メタデータ） (2020-12-06T01:30:12Z)
• A Generative Graph Method to Solve the Travelling Salesman Problem [1.552282932199974]
  我々は,旅行セールスマン問題(TSP)を概ね解決するために,生成的アプローチである新しいグラフ学習ネットワーク(GLN)を提案する。 GLNモデルは、トレーニングデータセットとしてTSPインスタンスのパターンを直接学習し、グラフプロパティをエンコードし、異なるノードの埋め込みをマージして、最適なツアーを出力する。
  論文  参考訳（メタデータ） (2020-07-09T17:23:55Z)
• Self-Directed Online Machine Learning for Topology Optimization [58.920693413667216]
  自己指向型オンライン学習最適化は、ディープニューラルネットワーク(DNN)と有限要素法(FEM)計算を統合している。 本アルゴリズムは, コンプライアンスの最小化, 流体構造最適化, 伝熱促進, トラス最適化の4種類の問題によって検証された。 その結果, 直接使用法と比較して計算時間を2～5桁削減し, 実験で検証した全ての最先端アルゴリズムより優れていた。
  論文  参考訳（メタデータ） (2020-02-04T20:00:28Z)

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

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