論文の概要: Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2004.01608v3
• Date: Mon, 14 Sep 2020 16:20:13 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-17 03:44:19.269025
• Title: Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning
• Title（参考訳）: 深層強化学習によるトラベルセールスマン問題の2-optヒューリスティックス学習
• Authors: Paulo R. de O. da Costa, Jason Rhuggenaath, Yingqian Zhang, Alp Akcay
• Abstract要約: 本研究では,2オプト演算子に基づく局所的な探索勾配を深層強化学習により学習することを提案する。 学習したポリシは、ランダムな初期解よりも改善でき、従来の最先端のディープラーニング手法よりも高速に、ほぼ最適解にアプローチできることを示す。
• 参考スコア（独自算出の注目度）: 2.4565068569913384
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent works using deep learning to solve the Traveling Salesman Problem (TSP) have focused on learning construction heuristics. Such approaches find TSP solutions of good quality but require additional procedures such as beam search and sampling to improve solutions and achieve state-of-the-art performance. However, few studies have focused on improvement heuristics, where a given solution is improved until reaching a near-optimal one. In this work, we propose to learn a local search heuristic based on 2-opt operators via deep reinforcement learning. We propose a policy gradient algorithm to learn a stochastic policy that selects 2-opt operations given a current solution. Moreover, we introduce a policy neural network that leverages a pointing attention mechanism, which unlike previous works, can be easily extended to more general k-opt moves. Our results show that the learned policies can improve even over random initial solutions and approach near-optimal solutions at a faster rate than previous state-of-the-art deep learning methods.
• Abstract（参考訳）: 近年,トラベリングセールスマン問題(TSP)の解決にディープラーニングを用いた研究は,建設ヒューリスティックスの学習に重点を置いている。 このようなアプローチは品質のよいtspソリューションを見つけるが、ビームサーチやサンプリングのような追加の手順が必要となり、ソリューションを改善し、最先端のパフォーマンスを達成する。 しかし、与えられた解が最適に近い解に達するまで改善されるような改善ヒューリスティックスに焦点を当てた研究はほとんどない。 本研究では,深層強化学習による2-opt演算子に基づく局所探索ヒューリスティックを学ぶことを提案する。 本稿では,現在の解に対して2オプト操作を選択する確率的ポリシを学習するためのポリシ勾配アルゴリズムを提案する。 さらに,従来の手法と異なり,より一般的なk-opt動作に容易に拡張できるポインティングアテンション機構を利用したポリシニューラルネットワークを提案する。 その結果、学習方針はランダム初期解よりも改善し、従来の最先端ディープラーニング手法よりも高速に、最適に近い解にアプローチできることがわかった。

関連論文リスト

• Rethinking Optimal Transport in Offline Reinforcement Learning [64.56896902186126]
  オフラインの強化学習では、データはさまざまな専門家によって提供され、一部は準最適である。 効率的なポリシを抽出するには、データセットから最高の振る舞いを強調する必要がある。 本稿では,各状態に対する最善の専門家行動の公平な分布に状態をマッピングするポリシーを見つけることを目的としたアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-10-17T22:36:43Z)
• Beyond Training: Optimizing Reinforcement Learning Based Job Shop Scheduling Through Adaptive Action Sampling [10.931466852026663]
  推論における訓練深部強化学習(DRL)エージェントの最適利用について検討した。 我々の研究は、探索アルゴリズムと同様に、訓練されたDRLエージェントの利用は許容できる計算予算に依存するべきであるという仮説に基づいている。 そこで本稿では, 与えられた多数の解と任意の訓練されたエージェントに対して最適なパラメータ化を求めるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-11T14:59:18Z)
• Sample-Efficient Multi-Objective Learning via Generalized Policy Improvement Prioritization [8.836422771217084]
  マルチオブジェクト強化学習(MORL)アルゴリズムは、エージェントが異なる好みを持つ可能性のあるシーケンシャルな決定問題に対処する。 本稿では、一般化政策改善(GPI)を用いて、原則的、正式に派生した優先順位付けスキームを定義する新しいアルゴリズムを提案する。 実験により,本手法は多目的タスクの挑戦において,最先端のMORLアルゴリズムよりも優れていることを示す。
  論文  参考訳（メタデータ） (2023-01-18T20:54:40Z)
• Online Control of Adaptive Large Neighborhood Search using Deep Reinforcement Learning [4.374837991804085]
  DR-ALNSと呼ばれる深層強化学習に基づくアプローチを導入し、演算子を選択し、パラメータを調整し、検索全体を通して受け入れ基準を制御する。 提案手法は,IJCAIコンペティションで提示されたオリエンテーリングウェイトと時間窓の問題に対して評価する。 その結果,本手法はバニラALNSよりも優れており,ALNSはベイジアン最適化と2つの最先端DRLアプローチに適合していることがわかった。
  論文  参考訳（メタデータ） (2022-11-01T21:33:46Z)
• 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)
• Sample-Efficient, Exploration-Based Policy Optimisation for Routing Problems [2.6782615615913348]
  本稿では,エントロピーに基づく新しい強化学習手法を提案する。 さらに、我々は、期待したリターンを最大化する、政治以外の強化学習手法を設計する。 我々のモデルは様々な経路問題に一般化可能であることを示す。
  論文  参考訳（メタデータ） (2022-05-31T09:51:48Z)
• Combining Reinforcement Learning and Optimal Transport for the Traveling Salesman Problem [18.735056206844202]
  我々は,従来の自己回帰的アプローチよりもはるかに高速に,監督や推論なしに学習できるモデルを構築することができることを示す。 また、ディープラーニングモデルに最適なトランスポートアルゴリズムを組み込むことで、エンドツーエンドのトレーニング中に割り当て制約を強制する利点を実証的に評価する。
  論文  参考訳（メタデータ） (2022-03-02T07:21:56Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• Learning Sampling Policy for Faster Derivative Free Optimization [100.27518340593284]
  ランダムサンプリングではなく,ZO最適化における摂動を生成するためのサンプリングポリシを学習する,新たな強化学習ベースのZOアルゴリズムを提案する。 その結果,ZO-RLアルゴリズムはサンプリングポリシを学習することでZO勾配の分散を効果的に低減し,既存のZOアルゴリズムよりも高速に収束できることが示唆された。
  論文  参考訳（メタデータ） (2021-04-09T14:50:59Z)
• Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
  本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。 D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。 本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
  論文  参考訳（メタデータ） (2021-02-23T15:33:57Z)
• Evolving Reinforcement Learning Algorithms [186.62294652057062]
  メタラーニング強化学習アルゴリズムの手法を提案する。 学習アルゴリズムはドメインに依存しないため、トレーニング中に見えない新しい環境に一般化することができる。 従来の制御タスク、gridworld型タスク、atariゲームよりも優れた一般化性能を得る2つの学習アルゴリズムに注目した。
  論文  参考訳（メタデータ） (2021-01-08T18:55:07Z)

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

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