Fugu-MT 論文翻訳(概要): Bandit based Dynamic Candidate Edge Selection in Solving Traveling Salesman Problems

論文の概要: Bandit based Dynamic Candidate Edge Selection in Solving Traveling Salesman Problems

arxiv url: http://arxiv.org/abs/2505.15862v1
Date: Wed, 21 May 2025 06:11:00 GMT
ステータス: 翻訳完了
システム内更新日: 2025-05-23 17:12:47.820761
Title: Bandit based Dynamic Candidate Edge Selection in Solving Traveling Salesman Problems
Title（参考訳）: 旅行セールスマン問題の解決における帯域ベース動的候補エッジ選択
Authors: Long Wanga, Jiongzhi Zheng, Zhengda Xiong, ChuMin Li, Kun He,
Abstract要約: 旅行セールスマン問題(TSP)に対するLin-Kernighan-Helsgaun(LKH)アルゴリズムのバンディットに基づく手法を提案する。各イテレーションにおいて最も適したエッジを動的に選択するために、マルチアームのバンディットモデルを組み込むことで、LKHはよりスマートな選択を可能にし、改善されたソリューションへと導くことができる。
参考スコア（独自算出の注目度）: 13.219547047794912
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Algorithms designed for routing problems typically rely on high-quality candidate edges to guide their search, aiming to reduce the search space and enhance the search efficiency. However, many existing algorithms, like the classical Lin-Kernighan-Helsgaun (LKH) algorithm for the Traveling Salesman Problem (TSP), often use predetermined candidate edges that remain static throughout local searches. This rigidity could cause the algorithm to get trapped in local optima, limiting its potential to find better solutions. To address this issue, we propose expanding the candidate sets to include other promising edges, providing them an opportunity for selection. Specifically, we incorporate multi-armed bandit models to dynamically select the most suitable candidate edges in each iteration, enabling LKH to make smarter choices and lead to improved solutions. Extensive experiments on multiple TSP benchmarks show the excellent performance of our method. Moreover, we employ this bandit-based method to LKH-3, an extension of LKH tailored for solving various TSP variant problems, and our method also significantly enhances LKH-3's performance across typical TSP variants.
Abstract（参考訳）: ルーティング問題のために設計されたアルゴリズムは、探索空間を減らし、探索効率を高めることを目的として、探索をガイドする高品質な候補エッジに依存している。しかし、トラベリングセールスマン問題 (TSP) の古典的なLin-Kernighan-Helsgaun (LKH) アルゴリズムのような既存のアルゴリズムでは、ローカル検索を通して静的な候補エッジを使用することが多い。この剛性は、アルゴリズムを局所的な最適性に閉じ込められ、より良い解を見つける可能性を制限する可能性がある。この問題に対処するため、我々は候補集合を他の有望なエッジを含むように拡張し、選択の機会を与えることを提案する。具体的には、各イテレーションにおいて最も適した候補エッジを動的に選択するために、マルチアームバンディットモデルを導入し、LKHがよりスマートな選択を可能にし、ソリューションの改善につながる。複数のTSPベンチマークの大規模な実験により,本手法の優れた性能が示された。さらに,この帯域幅法をLKH-3に適用し,様々なTSP変種問題を解決するためのLKHの拡張を行い,LKH-3の典型的なTSP変種に対する性能を著しく向上させる。

関連論文リスト

Multi-armed Bandit and Backbone boost Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problems [9.035853156510507]
Lin-Kernighan-Helsguan (LKH) は、トラベリングセールスマン問題(TSP)の古典的な局所探索アルゴリズムである。 LKHは、エッジの品質を評価するために従来の距離メートル法を置き換えるために$alpha$-valueを導入した。そこで本研究では,TSP局所探索プロセス中にバックボーン情報を抽出する手法を提案する。
論文参考訳（メタデータ） (2025-01-07T16:45:41Z)
Dancing to the State of the Art? How Candidate Lists Influence LKH for Solving the Traveling Salesperson Problem [1.6874375111244329]
トラベリングセールスパーソン問題(TSP)の解決はいまだに永続的な課題である。ヒューリスティックな解法は、高品質な解を見つけるための需要を効果的に解決する。これらの解法の中で、Lin-Kernighan-Helsgaun(LKH)は遺伝的アルゴリズムの性能を補完するものとして際立っている。
論文参考訳（メタデータ） (2024-07-04T13:38:19Z)
Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
論文参考訳（メタデータ） (2024-06-21T05:57:08Z)
Stop Relying on No-Choice and Do not Repeat the Moves: Optimal, Efficient and Practical Algorithms for Assortment Optimization [38.57171985309975]
本研究では,emphPlackett Luce (PL) を用いたコンソーシアム選択問題に対する効率的なアルゴリズムを開発した。提案手法は,既存の手法の限界を無視し,実用的かつ確実に最適である。
論文参考訳（メタデータ） (2024-02-29T07:17:04Z)
Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文参考訳（メタデータ） (2023-07-17T20:11:56Z)
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)
A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文参考訳（メタデータ） (2022-03-28T21:34:16Z)
Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文参考訳（メタデータ） (2021-09-13T18:10:52Z)
Exploration in two-stage recommender systems [79.50534282841618]
2段階のレコメンデータシステムは、スケーラビリティと保守性のために業界で広く採用されている。このセットアップの鍵となる課題は、各ステージの最適性能が最適なグローバルパフォーマンスを暗示していないことである。そこで本研究では,ランクとノミネーター間の探索戦略を同期させる手法を提案する。
論文参考訳（メタデータ） (2020-09-01T16:52:51Z)
Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文参考訳（メタデータ） (2020-01-29T09:40:58Z)

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

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