論文の概要: Dancing to the State of the Art? How Candidate Lists Influence LKH for Solving the Traveling Salesperson Problem

• arxiv url: http://arxiv.org/abs/2407.03927v1
• Date: Thu, 4 Jul 2024 13:38:19 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-08 17:53:13.164655
• Title: Dancing to the State of the Art? How Candidate Lists Influence LKH for Solving the Traveling Salesperson Problem
• Title（参考訳）: 最先端への道のり : トラベリングセールスパーソン問題の解決における候補リストがLKHにどのように影響するか
• Authors: Jonathan Heins, Lennart Schäpermeier, Pascal Kerschke, Darrell Whitley,
• Abstract要約: トラベリングセールスパーソン問題(TSP)の解決はいまだに永続的な課題である。 ヒューリスティックな解法は、高品質な解を見つけるための需要を効果的に解決する。 これらの解法の中で、Lin-Kernighan-Helsgaun(LKH)は遺伝的アルゴリズムの性能を補完するものとして際立っている。
• 参考スコア（独自算出の注目度）: 1.6874375111244329
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Solving the Traveling Salesperson Problem (TSP) remains a persistent challenge, despite its fundamental role in numerous generalized applications in modern contexts. Heuristic solvers address the demand for finding high-quality solutions efficiently. Among these solvers, the Lin-Kernighan-Helsgaun (LKH) heuristic stands out, as it complements the performance of genetic algorithms across a diverse range of problem instances. However, frequent timeouts on challenging instances hinder the practical applicability of the solver. Within this work, we investigate a previously overlooked factor contributing to many timeouts: The use of a fixed candidate set based on a tree structure. Our investigations reveal that candidate sets based on Hamiltonian circuits contain more optimal edges. We thus propose to integrate this promising initialization strategy, in the form of POPMUSIC, within an efficient restart version of LKH. As confirmed by our experimental studies, this refined TSP heuristic is much more efficient - causing fewer timeouts and improving the performance (in terms of penalized average runtime) by an order of magnitude - and thereby challenges the state of the art in TSP solving.
• Abstract（参考訳）: トラベリングセールスパーソン問題 (TSP) の解決は、現代の状況において多くの一般化された応用において基礎的な役割を担っているにもかかわらず、依然として永続的な課題である。 ヒューリスティックな解法は、高品質な解を見つけるための需要を効果的に解決する。 これらの解法の中で、Lin-Kernighan-Helsgaun(LKH)のヒューリスティックは、多様な問題インスタンスにおける遺伝的アルゴリズムのパフォーマンスを補完するものとして際立っている。 しかし、挑戦するインスタンスに対する頻繁なタイムアウトは、解法の適用性を妨げている。 本研究では,木構造に基づく固定された候補セットの利用について,これまで見過ごされてきた要因について検討する。 我々の研究により、ハミルトニアン回路に基づく候補集合はより最適なエッジを含むことが明らかとなった。 そこで我々は,この有望な初期化戦略であるPOPMUSICを,LKHの効率的な再起動バージョンに統合することを提案する。 実験によって確認されたように、この改良されたTSPヒューリスティックはより効率的であり、タイムアウトが少なくなり、(ペナル化平均ランタイムの観点から)パフォーマンスが桁違いに向上する。

関連論文リスト

• LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
  このフレームワークはMonte Carlo Tree Search (MCTS)と反復的なSelf-Refineを組み合わせて推論パスを最適化する。 このフレームワークは、一般的なベンチマークと高度なベンチマークでテストされており、探索効率と問題解決能力の点で優れた性能を示している。
  論文  参考訳（メタデータ） (2024-10-03T18:12:29Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing Problem [0.0]
  我々は、キャパシタントカー問題(CVRP)またはその減量版であるトラベリングセールスパーソン問題(TSP)について議論する。 今日の最も強力な古典的アルゴリズムでさえ、CVRPは古典的解決が難しい。 量子コンピューティングは、ソリューションの時間を改善する手段を提供するかもしれない。
  論文  参考訳（メタデータ） (2023-04-19T13:03:50Z)
• Rolling Horizon based Temporal Decomposition for the Offline Pickup and Delivery Problem with Time Windows [5.818566833386833]
  オフラインPDPTWのクラスを解くための新しい時間分解方式を提案する。 私たちのフレームワークはよりスケーラブルで、さまざまな難易度の問題インスタンスに対して優れたソリューションを提供することができます。
  論文  参考訳（メタデータ） (2023-03-06T20:07:05Z)
• A Reinforcement Learning Approach for Scheduling Problems With Improved Generalization Through Order Swapping [0.0]
  JSSP は NP-hard COP のカテゴリに分類される。 近年,COPの解法にDRLを用いる研究が注目され,解の質や計算効率の面で有望な結果が示されている。 特に、制約されたジョブのディスパッチにおいてよく機能すると考えられるポリシ・グラディエントパラダイムを採用するPPOアルゴリズムを採用する。
  論文  参考訳（メタデータ） (2023-02-27T16:45:04Z)
• MAP-Elites based Hyper-Heuristic for the Resource Constrained Project Scheduling Problem [0.3359875577705538]
  資源制約型プロジェクトスケジューリング問題(RCPSP)はNP-Hard最適化問題である。 本稿では, MAP-Elites を用いたハイパーヒューリスティック (MEHH) を用いて, RCPSP の効率的な優先ルールの自動発見を行う。
  論文  参考訳（メタデータ） (2022-04-24T01:49:59Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。 これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。 本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:59:20Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• Instance-Dependent Confidence and Early Stopping for Reinforcement Learning [99.57168572237421]
  強化学習(RL)のための様々なアルゴリズムは、その収束率の劇的な変動を問題構造の関数として示している。 この研究は、観察されたパフォーマンスの違いについて、textitexを説明する保証を提供する。 次の自然なステップは、これらの理論的保証を実際に有用なガイドラインに変換することです。
  論文  参考訳（メタデータ） (2022-01-21T04:25:35Z)
• Learning to Schedule Heuristics in Branch-and-Bound [25.79025327341732]
  現実世界のアプリケーションは通常、迅速な意思決定を可能にするために、検索の早い段階で優れたソリューションを見つける必要があります。 正確なMIPソルバにおけるスケジューリングのための最初のデータ駆動フレームワークを提案する。 最先端の学術MIPソルバーのデフォルト設定と比較して、挑戦的なインスタンスのクラスで平均プライマリ積分を最大49%削減することができます。
  論文  参考訳（メタデータ） (2021-03-18T14:49:52Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

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

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