論文の概要: Reinforced Lin-Kernighan-Helsgaun Algorithms for the Traveling Salesman
Problems
- arxiv url: http://arxiv.org/abs/2207.03876v1
- Date: Fri, 15 Jul 2022 06:43:33 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-24 11:40:50.913514
- Title: Reinforced Lin-Kernighan-Helsgaun Algorithms for the Traveling Salesman
Problems
- Title（参考訳）: トラベルセールスマン問題の強化lin-kernighan-helsgaunアルゴリズム
- Authors: Jiongzhi Zheng and Kun He and Jianrong Zhou and Yan Jin and Chu-Min Li
- Abstract要約: Lin-Kernighan-Helsgaunアルゴリズム(Lin-Kernighan-Helsgaunアルゴリズム、Lin-Kernighan-Helsgaunアルゴリズム)は、旅行セールスマン問題(TSP)のための最先端の局所探索アルゴリズムの1つである。
LKHとLKH-3は、アルゴリズムの効率を改善するために各都市に設定された候補を関連付け、$alpha$-measureとPOPMUSICと呼ばれる2つの異なる方法を持ち、候補セットを決定する。
本稿では,まず,3つの強化学習手法(Q-learning,Sarsa,Monte Carlo)を組み込んだ可変戦略強化LKH(VSR-LKH)アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 17.564543997481508
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: TSP is a classical NP-hard combinatorial optimization problem with many
practical variants. LKH is one of the state-of-the-art local search algorithms
for the TSP. LKH-3 is a powerful extension of LKH that can solve many TSP
variants. Both LKH and LKH-3 associate a candidate set to each city to improve
the efficiency, and have two different methods, $\alpha$-measure and POPMUSIC,
to decide the candidate sets. In this work, we first propose a Variable
Strategy Reinforced LKH (VSR-LKH) algorithm, which incorporates three
reinforcement learning methods (Q-learning, Sarsa, Monte Carlo) with LKH, for
the TSP. We further propose a new algorithm called VSR-LKH-3 that combines the
variable strategy reinforcement learning method with LKH-3 for typical TSP
variants, including the TSP with time windows (TSPTW) and Colored TSP (CTSP).
The proposed algorithms replace the inflexible traversal operations in LKH and
LKH-3 and let the algorithms learn to make a choice at each search step by
reinforcement learning. Both LKH and LKH-3, with either $\alpha$-measure or
POPMUSIC, can be significantly improved by our methods. Extensive experiments
on 236 widely-used TSP benchmarks with up to 85,900 cities demonstrate the
excellent performance of VSR-LKH. VSR-LKH-3 also significantly outperforms the
state-of-the-art heuristics for TSPTW and CTSP.
- Abstract（参考訳）: TSPは、多くの実用的な変種を持つ古典的なNPハード組合せ最適化問題である。
LKHはTSPの最先端のローカル検索アルゴリズムの1つである。
LKH-3は、多くのTSP変異を解くことができるLKHの強力な拡張である。
LKHとLKH-3はどちらも、効率を向上させるために各都市に設定された候補を関連付け、候補を決定するために$\alpha$-measureとPOPMUSICの2つの異なる方法を持つ。
本稿では,TSPのための3つの強化学習手法(Q-learning, Sarsa, Monte Carlo)を組み込んだ可変戦略強化LKH(VSR-LKH)アルゴリズムを提案する。
さらに,時間窓付きTSP (TSPTW) や有色TSP (CTSP) を含む典型的なTSP変種に対して,可変戦略強化学習法とLKH-3を併用した VSR-LKH-3 という新しいアルゴリズムを提案する。
提案手法は,lkh と lkh-3 の非フレキシブルトラバーサル演算を置換し,強化学習により各探索ステップで選択するアルゴリズムを学習させる。
LKH と LKH-3 はともに$\alpha$-measure または POPMUSIC のどちらでも,本法により有意に改善できる。
最大85,900都市で広く利用されている236のTSPベンチマークに対する大規模な実験は、VSR-LKHの優れた性能を示している。
VSR-LKH-3は、TSPTWとCTSPの最先端のヒューリスティックよりも大幅に優れている。
関連論文リスト
- Offline Imitation Learning from Multiple Baselines with Applications to Compiler Optimization [17.729842629392742]
我々は,Kベースラインポリシーで収集した一連のトラジェクトリを与えられる強化学習問題について検討する。
目標は、状態空間全体におけるベースラインの最高の組み合わせと同様に、機能するポリシーを学ぶことです。
論文 参考訳（メタデータ） (2024-03-28T14:34:02Z) - H-TSP: Hierarchically Solving the Large-Scale Travelling Salesman
Problem [11.310986634385742]
本稿では,大規模トラベリングセールスマン問題(TSP)に対処する階層的強化学習(H-TSP)に基づくエンドツーエンド学習フレームワークを提案する。
我々は,H-TSPがSOTA検索に匹敵する結果が得られることを示し,時間消費を2桁まで削減する(3.32s vs. 395.85s)。
ソリューションの品質に関してはまだSOTAの結果にギャップがあるが、H-TSPは実用的なアプリケーション、特にオンコールルーティングや乗車などの時間に敏感なアプリケーションに有用であると考えている。
論文 参考訳（メタデータ） (2023-04-19T03:10:30Z) - 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) - Improving Generalization of Deep Reinforcement Learning-based TSP
Solvers [19.29028564568974]
本稿では,ディープラーニングアーキテクチャとDRL学習方法を含むMAGICという新しいアプローチを提案する。
マルチレイヤパーセプトロン,グラフニューラルネットワーク,アテンションモデルを統合したアーキテクチャでは,旅行セールスマンソリューションを逐次生成するポリシを定義している。
1) DRLポリシー更新をローカル検索とインターリーブし(新しいローカル検索技術を用いて)、(2) 新たなシンプルなベースラインを使用し、(3) 勾配学習を適用した。
論文 参考訳（メタデータ） (2021-10-06T15:16:19Z) - Uniform-PAC Bounds for Reinforcement Learning with Linear Function
Approximation [92.3161051419884]
線形関数近似を用いた強化学習について検討する。
既存のアルゴリズムは、高い確率的後悔と/またはおよそ正当性(PAC)サンプルの複雑さの保証しか持たない。
我々はFLUTEと呼ばれる新しいアルゴリズムを提案し、高い確率で最適ポリシーへの均一PAC収束を享受する。
論文 参考訳（メタデータ） (2021-06-22T08:48:56Z) - Online Sub-Sampling for Reinforcement Learning with General Function
Approximation [111.01990889581243]
本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。
複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。
少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
論文 参考訳（メタデータ） (2021-06-14T07:36:25Z) - Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing [49.73889315176884]
本稿では、実行時の複雑さをアクション数にサブリニアに持つ最初の証明可能なLeast-Squares Value Iteration(LSVI)アルゴリズムを提示する。
我々は, 近似最大内積探索理論と強化学習の後悔分析との関係を構築する。
論文 参考訳（メタデータ） (2021-05-18T05:23:53Z) - Learning Sampling Policy for Faster Derivative Free Optimization [100.27518340593284]
ランダムサンプリングではなく,ZO最適化における摂動を生成するためのサンプリングポリシを学習する,新たな強化学習ベースのZOアルゴリズムを提案する。
その結果,ZO-RLアルゴリズムはサンプリングポリシを学習することでZO勾配の分散を効果的に低減し,既存のZOアルゴリズムよりも高速に収束できることが示唆された。
論文 参考訳（メタデータ） (2021-04-09T14:50:59Z) - Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm
for the Traveling Salesman Problem [12.851149098610096]
VSR-LKHという可変戦略強化手法を提案する。
3つの強化学習法(q-learning, sarsa, monte carlo)とlin-kernighan-helsgaun(lkh)と呼ばれるよく知られたtspアルゴリズムを組み合わせる。
VSR-LKHはLKHの柔軟性のない操作を置き換え、強化学習によって各探索ステップで選択を学習する。
論文 参考訳（メタデータ） (2020-12-08T14:58:36Z) - SUNRISE: A Simple Unified Framework for Ensemble Learning in Deep
Reinforcement Learning [102.78958681141577]
SUNRISEは単純な統一アンサンブル法であり、様々な非政治的な深層強化学習アルゴリズムと互換性がある。
SUNRISEは, (a) アンサンブルに基づく重み付きベルマンバックアップと, (b) 最上位の自信境界を用いて行動を選択する推論手法を統合し, 効率的な探索を行う。
論文 参考訳（メタデータ） (2020-07-09T17:08:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。