Fugu-MT 論文翻訳(概要): Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problem

論文の概要: Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problem

arxiv url: http://arxiv.org/abs/2012.04461v6
Date: Wed, 17 Mar 2021 08:02:11 GMT
ステータス: 処理完了
システム内更新日: 2021-05-17 05:15:27.296362
Title: Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problem
Title（参考訳）: トラベルセールスマン問題の強化学習とlin-kernighan-helsgaunアルゴリズムの併用
Authors: Jiongzhi Zheng and Kun He and Jianrong Zhou and Yan Jin and Chu-Min Li
Abstract要約: VSR-LKHという可変戦略強化手法を提案する。 3つの強化学習法(q-learning, sarsa, monte carlo)とlin-kernighan-helsgaun(lkh)と呼ばれるよく知られたtspアルゴリズムを組み合わせる。 VSR-LKHはLKHの柔軟性のない操作を置き換え、強化学習によって各探索ステップで選択を学習する。
参考スコア（独自算出の注目度）: 12.851149098610096
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We address the Traveling Salesman Problem (TSP), a famous NP-hard combinatorial optimization problem. And we propose a variable strategy reinforced approach, denoted as VSR-LKH, which combines three reinforcement learning methods (Q-learning, Sarsa and Monte Carlo) with the well-known TSP algorithm, called Lin-Kernighan-Helsgaun (LKH). VSR-LKH replaces the inflexible traversal operation in LKH, and lets the program learn to make choice at each search step by reinforcement learning. Experimental results on 111 TSP benchmarks from the TSPLIB with up to 85,900 cities demonstrate the excellent performance of the proposed method.
Abstract（参考訳）: 本稿では,NP-hard組合せ最適化問題であるトラベリングセールスマン問題(TSP)に対処する。本稿では,3つの強化学習手法(Q-learning,Sarsa,Monte Carlo)と,Lin-Kernighan-Helsgaun (LKH) と呼ばれるTSPアルゴリズムを組み合わせた可変戦略強化手法を提案する。 VSR-LKHは、LKHの非フレキシブルトラバース操作を置き換え、強化学習によって各探索ステップで選択を学習する。最大85,900都市でのTSPLIBによる111TSPベンチマーク実験の結果,提案手法の優れた性能を示した。

関連論文リスト

Hint-before-Solving Prompting: Guiding LLMs to Effectively Utilize Encoded Knowledge [85.17343729885003]
我々は,Hint-before-Solving Prompting (HSP)を導入し,その問題を解くためのヒントを生成する。 HSPは推論タスクの精度を効果的に向上させることができる。我々はHSPと細調整されたLlemma-7Bに基づいてHSPMATHデータセットを構築し、64.3精度を達成した。
論文参考訳（メタデータ） (2024-02-22T05:58:03Z)
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)
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)
Reinforced Lin-Kernighan-Helsgaun Algorithms for the Traveling Salesman Problems [17.564543997481508]
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)アルゴリズムを提案する。
論文参考訳（メタデータ） (2022-07-08T13:03:29Z)
Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
機械学習は分岐のための有望なパラダイムとして登場した。分岐のための単純かつ効果的なRLアプローチであるレトロ分岐を提案する。我々は現在最先端のRL分岐アルゴリズムを3～5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドの性能の20%以内である。
論文参考訳（メタデータ） (2022-05-28T06:08:07Z)
NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem [14.605192361813454]
我々は、Lin-Kernighan-Helsgaun(LKH)とディープラーニングを組み合わせた新しいアルゴリズムNeuroLKHを提案する。具体的には、エッジスコアの教師付き学習とノードペナルティの教師なし学習を併用したスパースグラフネットワーク(SGN)を訓練する。幅広い問題サイズで1つのモデルをトレーニングすることで、NeuroLKHはLKHを大幅に上回り、はるかに大きなサイズで一般化する。
論文参考訳（メタデータ） (2021-10-15T10:14:27Z)
Reinforced Hybrid Genetic Algorithm for the Traveling Salesman Problem [4.92025078254413]
有名なNPハードトラベリングセールスマン問題(TSP)に対する強力な強化ハイブリッド遺伝的アルゴリズム(RHGA)を提案する。 RHGAは強化学習技術と有名なエッジアセンブリクロスオーバー遺伝的アルゴリズム(EAX-GA)とLin-Kernighan-Helsgaun局所探索を組み合わせた。都市数は1,000, 85,900都市で, 良く知られた, 広く利用されているベンチマーク138都市を対象に, 提案手法の優れた性能を実証した。
論文参考訳（メタデータ） (2021-07-09T07:36:12Z)
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)
Evolving Reinforcement Learning Algorithms [186.62294652057062]
メタラーニング強化学習アルゴリズムの手法を提案する。学習アルゴリズムはドメインに依存しないため、トレーニング中に見えない新しい環境に一般化することができる。従来の制御タスク、gridworld型タスク、atariゲームよりも優れた一般化性能を得る2つの学習アルゴリズムに注目した。
論文参考訳（メタデータ） (2021-01-08T18:55:07Z)
Reinforcement Learning for Combinatorial Optimization: A Survey [12.323976053967066]
最適化問題を解決する多くの伝統的なアルゴリズムは、解決を逐次構築する手工芸品を使用する。強化学習(Reinforcement Learning, RL)は、エージェントを監督的または自己監督的な方法で訓練することにより、これらの検索を自動化する優れた代替手段を提案する。
論文参考訳（メタデータ） (2020-03-07T16:19:45Z)

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