論文の概要: Rethinking the "Heatmap + Monte Carlo Tree Search" Paradigm for Solving Large Scale TSP

• arxiv url: http://arxiv.org/abs/2411.09238v1
• Date: Thu, 14 Nov 2024 07:13:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-15 15:24:05.838969
• Title: Rethinking the "Heatmap + Monte Carlo Tree Search" Paradigm for Solving Large Scale TSP
• Title（参考訳）: 大規模TSP解決のための"ヒートマップ+モンテカルロ木探索"パラダイムの再考
• Authors: Xuanhao Pan, Chenguang Wang, Chaolong Ying, Ye Xue, Tianshu Yu,
• Abstract要約: heatmap + Monte Carlo Tree Search (MCTS)"パラダイムは、最近、学習ベースのソリューションで注目を集めています。 本稿では,近年,学習型ソリューションの注目を集めている"ヒートマップ+モンテカルロ木探索(MCTS)"のパラダイムを再考する。 本研究は,トラベリングセールスマン問題の本質的な$k$-nearest性から導かれる初歩的かつパラメータフリーなヒートマップが,複雑なヒートマップの性能に匹敵するか,あるいは超えることを示した。
• 参考スコア（独自算出の注目度）: 11.388824026057735
• License:
• Abstract: The Travelling Salesman Problem (TSP) remains a fundamental challenge in combinatorial optimization, inspiring diverse algorithmic strategies. This paper revisits the "heatmap + Monte Carlo Tree Search (MCTS)" paradigm that has recently gained traction for learning-based TSP solutions. Within this framework, heatmaps encode the likelihood of edges forming part of the optimal tour, and MCTS refines this probabilistic guidance to discover optimal solutions. Contemporary approaches have predominantly emphasized the refinement of heatmap generation through sophisticated learning models, inadvertently sidelining the critical role of MCTS. Our extensive empirical analysis reveals two pivotal insights: 1) The configuration of MCTS strategies profoundly influences the solution quality, demanding meticulous tuning to leverage their full potential; 2) Our findings demonstrate that a rudimentary and parameter-free heatmap, derived from the intrinsic $k$-nearest nature of TSP, can rival or even surpass the performance of complicated heatmaps, with strong generalizability across various scales. Empirical evaluations across various TSP scales underscore the efficacy of our approach, achieving competitive results. These observations challenge the prevailing focus on heatmap sophistication, advocating a reevaluation of the paradigm to harness both components synergistically. Our code is available at: https://github.com/LOGO-CUHKSZ/rethink_mcts_tsp.
• Abstract（参考訳）: トラベリングセールスマン問題(TSP)は、様々なアルゴリズム戦略を刺激する組合せ最適化における根本的な課題である。 本稿では,近年,学習型 TSP ソリューションの注目を集めている "heatmap + Monte Carlo Tree Search (MCTS)" パラダイムを再検討する。 この枠組みの中で、ヒートマップは最適ツアーの一部を構成するエッジの確率を符号化し、MCTSはこの確率的ガイダンスを洗練して最適解を発見する。 現代のアプローチは、MCTSの重要な役割を必然的に脇に置いて、洗練された学習モデルによるヒートマップ生成の洗練を主に強調してきた。 私たちの広範な経験分析は、2つの重要な洞察を明らかにします。 1)MCTS戦略の設定は,ソリューションの品質に大きく影響し,その潜在能力を最大限活用するために精巧なチューニングを要求する。 2) TSPの本質的な$k$-nearest特性から導かれる初歩的かつパラメータフリーなヒートマップは,様々なスケールで高い一般化性を持つ複雑なヒートマップの性能に匹敵する,あるいは超えうることを示した。 各種TSP尺度における実証的評価は, 提案手法の有効性を裏付け, 競争結果の達成に寄与する。 これらの観察は、両方のコンポーネントを相乗的に活用するパラダイムの再評価を提唱し、熱マップの高度化に重点を置いている。 私たちのコードは、https://github.com/LOGO-CUHKSZ/rethink_mcts_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)
• Optimized Monte Carlo Tree Search for Enhanced Decision Making in the FrozenLake Environment [0.0]
  Monte Carlo Tree Search (MCTS) は複雑な意思決定問題を解決する強力なアルゴリズムである。 本稿では,古典的強化学習課題であるFrozenLake環境に適用したMCTS実装を提案する。
  論文  参考訳（メタデータ） (2024-09-25T05:04:53Z)
• Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problems [14.277867417951347]
  大規模旅行セールスマン問題の解決における最近の進歩は、ヒートマップ誘導モンテカルロ木探索(MCTS)パラダイムを利用している。 簡単なベースライン法は,ヒートマップ生成における複雑なML手法より優れていることを示す。 本研究は,問題固有の手作り戦略に依存しているにもかかわらず,LKH-3に対するパラダイムの劣りを示すものである。
  論文  参考訳（メタデータ） (2024-06-02T16:11:38Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。 我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。 本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
  論文  参考訳（メタデータ） (2023-10-08T23:39:38Z)
• 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)
• Generalized Parametric Contrastive Learning [60.62901294843829]
  一般化パラメトリックコントラスト学習(GPaCo/PaCo)は、不均衡データとバランスデータの両方でうまく機能する。 長い尾のベンチマークの実験は、長い尾の認識のための新しい最先端を示す。
  論文  参考訳（メタデータ） (2022-09-26T03:49:28Z)
• Embed to Control Partially Observed Systems: Representation Learning with Provable Sample Efficiency [105.17746223041954]
  部分的に観察されたマルコフ決定過程(POMDP)における強化学習は2つの課題に直面している。 しばしば、未来を予測するのに完全な歴史を要し、地平線と指数関数的にスケールするサンプルの複雑さを誘導する。 本稿では,2段階の表現を最適化しながら学習するETC(Embed to Control)という強化学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-26T16:34:46Z)
• A Unified Perspective on Value Backup and Exploration in Monte-Carlo Tree Search [41.11958980731047]
  本稿では,新たに導入されたバックアップ演算子とエントロピー正規化に基づく収束率と探索率を改善する2つの手法を提案する。 この理論的な定式化は、我々が新たに導入したものも含めて、同じ数学的枠組みの下で異なるアプローチを統一することを示します。 実際には、我々の統合された視点は、目の前の問題に応じて単一の$alpha$パラメータをチューニングすることで、探索と搾取のバランスをとる柔軟な方法を提供する。
  論文  参考訳（メタデータ） (2022-02-11T15:30:08Z)
• Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances [55.64521598173897]
  本稿では,旅行セールスマン問題(TSP)のヒートマップ構築に繰り返し使用可能な,小規模モデルのトレーニングを試みる。 ヒートマップは強化学習アプローチ(モンテカルロツリーサーチ)に供給され、高品質のソリューションの検索を案内します。 実験結果によると、この新しいアプローチは、既存の機械学習ベースのTSPアルゴリズムを明らかに上回る。
  論文  参考訳（メタデータ） (2020-12-19T11:06:30Z)

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

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