論文の概要: Reinforcement Learning-based Non-Autoregressive Solver for Traveling
Salesman Problems
- arxiv url: http://arxiv.org/abs/2308.00560v1
- Date: Tue, 1 Aug 2023 14:00:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-02 13:52:46.440654
- Title: Reinforcement Learning-based Non-Autoregressive Solver for Traveling
Salesman Problems
- Title(参考訳): トラベルセールスマン問題に対する強化学習に基づく非自己回帰解法
- Authors: Yubin Xiao, Di Wang, Huanhuan Chen, Boyang Li, Wei Pang, Xuan Wu, Hao
Li, Dong Xu, Yanchun Liang, and You Zhou
- Abstract要約: 我々は、特別に設計されたグラフニューラルネットワーク(GNN)を用いて、非自己回帰(NAR)方式でトラベリングセールスマン問題(TSP)ソリューションを生成するNAR4TSPを提案する。
NAR4TSPは強化強化学習(RL)戦略を用いて訓練されており、従来のNARモデルのトレーニングに使用される高価なラベルへの依存を排除している。
NAR4TSPは, ソリューションの品質, 推論遅延, 一般化能力の点で, 4つの最先端モデルより優れていることを示す。
- 参考スコア(独自算出の注目度): 39.0481133448852
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Traveling Salesman Problem (TSP) is a well-known problem in combinatorial
optimization with applications in various domains. However, existing TSP
solvers face challenges in producing high-quality solutions with low latency.
To address this issue, we propose NAR4TSP, which produces TSP solutions in a
Non-Autoregressive (NAR) manner using a specially designed Graph Neural Network
(GNN), achieving faster inference speed. Moreover, NAR4TSP is trained using an
enhanced Reinforcement Learning (RL) strategy, eliminating the dependency on
costly labels used to train conventional supervised learning-based NAR models.
To the best of our knowledge, NAR4TSP is the first TSP solver that successfully
combines RL and NAR decoding. The experimental results on both synthetic and
real-world TSP instances demonstrate that NAR4TSP outperforms four
state-of-the-art models in terms of solution quality, inference latency, and
generalization ability. Lastly, we present visualizations of NAR4TSP's decoding
process and its overall path planning to showcase the feasibility of
implementing NAR4TSP in an end-to-end manner and its effectiveness,
respectively.
- Abstract(参考訳): トラベリングセールスマン問題(TSP)は、様々な分野のアプリケーションと組み合わせ最適化においてよく知られた問題である。
しかし、既存のTSPソルバは、低レイテンシで高品質なソリューションを作成する際の課題に直面している。
この問題に対処するために,特殊設計したグラフニューラルネットワーク(GNN)を用いて,非自己回帰(NAR)方式でTSPソリューションを生成するNAR4TSPを提案する。
さらに、NAR4TSPは強化強化学習(RL)戦略を用いて訓練されており、従来の教師付き学習ベースNARモデルのトレーニングに使用される高価なラベルへの依存を排除している。
我々の知る限り、NAR4TSPはRLとNARデコーディングをうまく組み合わせた最初のTSPソルバである。
合成TSPインスタンスと実世界のTSPインスタンスの両方の実験結果は、NAR4TSPがソリューションの品質、推論レイテンシ、一般化能力の点で4つの最先端モデルを上回っていることを示している。
最後に, NAR4TSPの復号化過程の可視化と, NAR4TSPをエンド・ツー・エンドで実装する可能性とその有効性を示す全体的な経路計画について述べる。
関連論文リスト
- Enhancing Spectrum Efficiency in 6G Satellite Networks: A GAIL-Powered Policy Learning via Asynchronous Federated Inverse Reinforcement Learning [67.95280175998792]
ビームフォーミング,スペクトルアロケーション,リモートユーザ機器(RUE)アソシエイトを最適化するために,GAILを利用した新しいポリシー学習手法を提案する。
手動チューニングなしで報酬関数を自動的に学習するために、逆RL(IRL)を用いる。
提案手法は従来のRL手法よりも優れており,コンバージェンスと報酬値の14.6%の改善が達成されている。
論文 参考訳(メタデータ) (2024-09-27T13:05:02Z) - CCSRP: Robust Pruning of Spiking Neural Networks through Cooperative Coevolution [2.5388345537743056]
スパイキングニューラルネットワーク(SNN)は、様々な動的視覚タスクにおいて有望であることを示しているが、現実的なデプロイメントの準備が整ったものは、リソース制限と安全クリティカルな設定に不可欠なコンパクト性と堅牢性を欠いていることが多い。
我々は,協調的共進化を基盤としたSNNの革新的な頑健な刈り取り法であるCSRPを提案する。
論文 参考訳(メタデータ) (2024-07-18T04:28:16Z) - Quantum Annealing and Graph Neural Networks for Solving TSP with QUBO [0.0]
本稿では、量子アニーリングアルゴリズムとグラフニューラルネットワークによるトラベリングセールスマン問題(TSP)の解法として、二次非拘束バイナリ最適化(QUBO)モデルの適用について検討する。
TSP(QGNN-TSP)のためのグラフニューラルネットワークソリューションを導入し、問題の基盤構造を学習し、QUBOに基づく損失関数の勾配降下による競合ソリューションを生成する。
論文 参考訳(メタデータ) (2024-02-21T05:55:00Z) - LC-TTFS: Towards Lossless Network Conversion for Spiking Neural Networks
with TTFS Coding [55.64533786293656]
我々は,AIタスクにおいて,ANNのアクティベーション値とSNNのスパイク時間とのほぼ完全なマッピングを実現することができることを示す。
この研究は、電力制約のあるエッジコンピューティングプラットフォームに超低消費電力のTTFSベースのSNNをデプロイする方法を舗装している。
論文 参考訳(メタデータ) (2023-10-23T14:26:16Z) - 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) - Travel the Same Path: A Novel TSP Solving Strategy [0.0]
我々は、必要に応じて適切な選択を行う決定論的アルゴリズムを支援する模倣学習フレームワークについて検討する。
我々は、模倣学習フレームワークの下で訓練されたグラフニューラルネットワークの強力な一般化能力を示す。
論文 参考訳(メタデータ) (2022-10-12T03:56:37Z) - Online Training Through Time for Spiking Neural Networks [66.7744060103562]
スパイキングニューラルネットワーク(SNN)は、脳にインスパイアされたエネルギー効率のモデルである。
近年のトレーニング手法の進歩により、レイテンシの低い大規模タスクにおいて、ディープSNNを成功させることができた。
本稿では,BPTT から派生した SNN の時間的学習(OTTT)によるオンライントレーニングを提案する。
論文 参考訳(メタデータ) (2022-10-09T07:47:56Z) - Improving Generalization of Deep Reinforcement Learning-based TSP
Solvers [19.29028564568974]
本稿では,ディープラーニングアーキテクチャとDRL学習方法を含むMAGICという新しいアプローチを提案する。
マルチレイヤパーセプトロン,グラフニューラルネットワーク,アテンションモデルを統合したアーキテクチャでは,旅行セールスマンソリューションを逐次生成するポリシを定義している。
1) DRLポリシー更新をローカル検索とインターリーブし(新しいローカル検索技術を用いて)、(2) 新たなシンプルなベースラインを使用し、(3) 勾配学習を適用した。
論文 参考訳(メタデータ) (2021-10-06T15:16:19Z) - Combining Pessimism with Optimism for Robust and Efficient Model-Based
Deep Reinforcement Learning [56.17667147101263]
実世界のタスクでは、強化学習エージェントはトレーニング中に存在しない状況に遭遇する。
信頼性を確保するため、RLエージェントは最悪の状況に対して堅牢性を示す必要がある。
本稿では,Robust Hallucinated Upper-Confidence RL (RH-UCRL)アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-03-18T16:50:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。