論文の概要: Multi-armed Bandit and Backbone boost Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problems

• arxiv url: http://arxiv.org/abs/2501.04072v1
• Date: Tue, 07 Jan 2025 16:45:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-09 14:55:21.943929
• Title: Multi-armed Bandit and Backbone boost Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problems
• Title（参考訳）: 旅行セールスマン問題に対するマルチアームバンディットとバックボーン強化Lin-Kernighan-Helsgaunアルゴリズム
• Authors: Long Wang, Jiongzhi Zheng, Zhengda Xiong, Kun He,
• Abstract要約: Lin-Kernighan-Helsguan (LKH) は、トラベリングセールスマン問題(TSP)の古典的な局所探索アルゴリズムである。 LKHは、エッジの品質を評価するために従来の距離メートル法を置き換えるために$alpha$-valueを導入した。 そこで本研究では,TSP局所探索プロセス中にバックボーン情報を抽出する手法を提案する。
• 参考スコア（独自算出の注目度）: 9.035853156510507
• License:
• Abstract: The Lin-Kernighan-Helsguan (LKH) heuristic is a classic local search algorithm for the Traveling Salesman Problem (TSP). LKH introduces an $\alpha$-value to replace the traditional distance metric for evaluating the edge quality, which leads to a significant improvement. However, we observe that the $\alpha$-value does not make full use of the historical information during the search, and single guiding information often makes LKH hard to escape from some local optima. To address the above issues, we propose a novel way to extract backbone information during the TSP local search process, which is dynamic and can be updated once a local optimal solution is found. We further propose to combine backbone information, $\alpha$-value, and distance to evaluate the edge quality so as to guide the search. Moreover, we abstract their different combinations to arms in a multi-armed bandit (MAB) and use an MAB model to help the algorithm select an appropriate evaluation metric dynamically. Both the backbone information and MAB can provide diverse guiding information and learn from the search history to suggest the best metric. We apply our methods to LKH and LKH-3, which is an extension version of LKH that can be used to solve about 40 variant problems of TSP and Vehicle Routing Problem (VRP). Extensive experiments show the excellent performance and generalization capability of our proposed method, significantly improving LKH for TSP and LKH-3 for two representative TSP and VRP variants, the Colored TSP (CTSP) and Capacitated VRP with Time Windows (CVRPTW).
• Abstract（参考訳）: Lin-Kernighan-Helsguan(LKH)ヒューリスティック(Lin-Kernighan-Helsguan)は、トラベリングセールスマン問題(TSP)の古典的な局所探索アルゴリズムである。 LKHは、エッジの品質を評価するために伝統的な距離メートル法を置き換えるために$\alpha$-valueを導入した。 しかし、$\alpha$-valueは検索中に履歴情報をフルに活用せず、単一の案内情報によってLKHがローカルなオプティマから逃れるのが困難になることが多い。 以上の課題に対処するため,TSP局所探索プロセス中にバックボーン情報を抽出する方法を提案する。 さらに,バックボーン情報と$\alpha$-value,距離を組み合わせることで,検索のガイドとしてエッジ品質を評価することを提案する。 さらに,それらの組み合わせをマルチアームバンディット(MAB)のアームに抽象化し,MABモデルを用いてアルゴリズムが適切な評価基準を動的に選択するのを支援する。 バックボーン情報とMABの両方が多様なガイド情報を提供し、検索履歴から最高の指標を提案することができる。 提案手法をLKHの拡張版であるLKHとLKH-3に適用し,約40種類のTSPおよび車両ルーティング問題(VRP)を解く。 広汎な実験により,提案手法の優れた性能と一般化能力を示し,TSPとLKH-3の2つの代表的なTSPおよびVRP(Colored TSP,CTSP)とCVRPTW(Capacitated VRP with Time Windows, CVRPTW)に対するLKHを著しく改善した。

関連論文リスト

• Exploring Knowledge Boundaries in Large Language Models for Retrieval Judgment [56.87031484108484]
  大規模言語モデル(LLM)は、その実践的応用でますます認識されている。 Retrieval-Augmented Generation (RAG)はこの課題に取り組み、LLMに大きな影響を与えている。 中立あるいは有害な結果をもたらす検索要求を最小化することにより、時間と計算コストの両方を効果的に削減できる。
  論文  参考訳（メタデータ） (2024-11-09T15:12:28Z)
• Rethinking Optimal Transport in Offline Reinforcement Learning [64.56896902186126]
  オフラインの強化学習では、データはさまざまな専門家によって提供され、一部は準最適である。 効率的なポリシを抽出するには、データセットから最高の振る舞いを強調する必要がある。 本稿では,各状態に対する最善の専門家行動の公平な分布に状態をマッピングするポリシーを見つけることを目的としたアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-10-17T22:36:43Z)
• Research on Travel Route Planing Problems Based on Greedy Algorithm [0.0]
  欲求アルゴリズムに基づく経路計画問題は、与えられた開始点と終了点の間の最適経路またはほぼ最適経路を特定する方法を表す。 本稿では,まず都市評価指標をダウンスケールし,主要な主要成分を抽出し,データをダウンスケールするためにPCA法を用いる。 旅行者のニーズに応じて個別にルートをカスタマイズする,欲求に基づく経路計画アルゴリズムが提案され,最適化されている。
  論文  参考訳（メタデータ） (2024-10-17T05:17:01Z)
• CAGES: Cost-Aware Gradient Entropy Search for Efficient Local Multi-Fidelity Bayesian Optimization [0.0]
  我々は,多要素ブラックボックス関数の局所BOのための新しいアルゴリズムであるCost-Aware Gradient Entropy Search (CAGES)を提案する。 我々は,CAGESが様々な合成およびベンチマークRL問題において,他の最先端手法と比較して,大幅な性能向上を達成できることを実証した。
  論文  参考訳（メタデータ） (2024-05-13T14:00:02Z)
• Multimodal Learned Sparse Retrieval with Probabilistic Expansion Control [66.78146440275093]
  学習検索(LSR)は、クエリとドキュメントを疎語彙ベクトルにエンコードするニューラルネットワークのファミリーである。 テキスト画像検索に焦点をあて,マルチモーダル領域へのLSRの適用について検討する。 LexLIPやSTAIRのような現在のアプローチでは、大規模なデータセットで複雑なマルチステップのトレーニングが必要です。 提案手法は, 密度ベクトルを凍結密度モデルからスパース語彙ベクトルへ効率的に変換する。
  論文  参考訳（メタデータ） (2024-02-27T14:21:56Z)
• 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)
• 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)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。 複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。 少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
  論文  参考訳（メタデータ） (2021-06-14T07:36:25Z)
• Information Directed Reward Learning for Reinforcement Learning [64.33774245655401]
  我々は、標準rlアルゴリズムが可能な限り少数の専門家クエリで高い期待値を達成することができる報酬関数のモデルを学ぶ。 特定のタイプのクエリ用に設計された以前のアクティブな報酬学習方法とは対照的に、IDRLは自然に異なるクエリタイプに対応します。 我々は,複数の環境における広範囲な評価と,異なるタイプのクエリでこの結果を支持する。
  論文  参考訳（メタデータ） (2021-02-24T18:46:42Z)
• 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)
• Learning the Step-size Policy for the Limited-Memory Broyden-Fletcher-Goldfarb-Shanno Algorithm [3.7470451129384825]
  本稿では,L-BFGSアルゴリズムのステップサイズポリシの学習方法について考察する。 入力として電流勾配の局所的な情報を用いたニューラルネットワークアーキテクチャを提案する。 ステップ長ポリシは、同様の最適化問題のデータから学習され、目的関数のさらなる評価を回避し、出力ステップが予め定義された間隔内に留まることを保証します。
  論文  参考訳（メタデータ） (2020-10-03T09:34:03Z)

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

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