論文の概要: Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problems
- arxiv url: http://arxiv.org/abs/2406.03503v1
- Date: Sun, 2 Jun 2024 16:11:38 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-07 19:34:24.438462
- Title: Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problems
- Title（参考訳）: 位置:大規模トラベリングセールスマン問題の解決のためのポストホック検索に基づくニューラルアプローチの再考
- Authors: Yifan Xia, Xianliang Yang, Zichuan Liu, Zhihao Liu, Lei Song, Jiang Bian,
- Abstract要約: 大規模旅行セールスマン問題の解決における最近の進歩は、ヒートマップ誘導モンテカルロ木探索(MCTS)パラダイムを利用している。
簡単なベースライン法は,ヒートマップ生成における複雑なML手法より優れていることを示す。
本研究は,問題固有の手作り戦略に依存しているにもかかわらず,LKH-3に対するパラダイムの劣りを示すものである。
- 参考スコア（独自算出の注目度）: 14.277867417951347
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent advancements in solving large-scale traveling salesman problems (TSP) utilize the heatmap-guided Monte Carlo tree search (MCTS) paradigm, where machine learning (ML) models generate heatmaps, indicating the probability distribution of each edge being part of the optimal solution, to guide MCTS in solution finding. However, our theoretical and experimental analysis raises doubts about the effectiveness of ML-based heatmap generation. In support of this, we demonstrate that a simple baseline method can outperform complex ML approaches in heatmap generation. Furthermore, we question the practical value of the heatmap-guided MCTS paradigm. To substantiate this, our findings show its inferiority to the LKH-3 heuristic despite the paradigm's reliance on problem-specific, hand-crafted strategies. For the future, we suggest research directions focused on developing more theoretically sound heatmap generation methods and exploring autonomous, generalizable ML approaches for combinatorial problems. The code is available for review: https://github.com/xyfffff/rethink_mcts_for_tsp.
- Abstract（参考訳）: 大規模旅行セールスマン問題(TSP)の解決における最近の進歩は、機械学習(ML)モデルがヒートマップを生成し、各エッジの確率分布が最適解の一部であることを示す、ヒートマップ誘導モンテカルロ木探索(MCTS)パラダイムを用いて解を見つける。
しかし,我々の理論的および実験的分析は,MLに基づくヒートマップ生成の有効性に疑問を呈する。
これを支持するために、簡単なベースライン法が、ヒートマップ生成における複雑なMLアプローチより優れていることを示す。
さらに,熱マップ誘導MCTSパラダイムの実用的価値を疑問視する。
本研究は,問題固有の手作り戦略に依存しているにもかかわらず,LKH-3ヒューリスティックに劣ることを示すものである。
将来的には,より理論的に健全な熱マップ生成手法の開発と,組合せ問題に対する自律的で一般化可能なMLアプローチの探求に焦点をあてる研究の方向性を提案する。
コードは https://github.com/xyfffff/rethink_mcts_for_tsp でレビューすることができる。
関連論文リスト
- Rethinking the "Heatmap + Monte Carlo Tree Search" Paradigm for Solving Large Scale TSP [11.388824026057735]
heatmap + Monte Carlo Tree Search (MCTS)"パラダイムは、最近、学習ベースのソリューションで注目を集めています。
本稿では,近年,学習型ソリューションの注目を集めている"ヒートマップ+モンテカルロ木探索(MCTS)"のパラダイムを再考する。
本研究は,トラベリングセールスマン問題の本質的な$k$-nearest性から導かれる初歩的かつパラメータフリーなヒートマップが,複雑なヒートマップの性能に匹敵するか,あるいは超えることを示した。
論文 参考訳（メタデータ） (2024-11-14T07:13:08Z) - 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) - Disentangled Representation Learning with the Gromov-Monge Gap [65.73194652234848]
乱れのないデータから歪んだ表現を学習することは、機械学習における根本的な課題である。
本稿では,2次最適輸送に基づく非交叉表現学習手法を提案する。
提案手法の有効性を4つの標準ベンチマークで示す。
論文 参考訳（メタデータ） (2024-07-10T16:51:32Z) - 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) - Model-Based Reparameterization Policy Gradient Methods: Theory and
Practical Algorithms [88.74308282658133]
Reization (RP) Policy Gradient Methods (PGM) は、ロボット工学やコンピュータグラフィックスにおける連続的な制御タスクに広く採用されている。
近年の研究では、長期強化学習問題に適用した場合、モデルベースRP PGMはカオス的かつ非滑らかな最適化環境を経験する可能性があることが示されている。
本稿では,長期モデルアンロールによる爆発的分散問題を緩和するスペクトル正規化法を提案する。
論文 参考訳（メタデータ） (2023-10-30T18:43:21Z) - Lightweight Super-Resolution Head for Human Pose Estimation [42.51588635059534]
ヒートマップに基づく手法がポーズ推定の主流となっている。
しかし、ヒートマップに基づくアプローチは、ダウンスケールのヒートマップを持つ重要な量子化誤差に悩まされる。
本稿では,SRPoseによる量子化誤差の低減と処理後処理への依存性について述べる。
論文 参考訳（メタデータ） (2023-07-31T15:35:34Z) - Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo [104.9535542833054]
我々は、強化学習のためのトンプソンサンプリングに基づくスケーラブルで効果的な探索戦略を提案する。
代わりに、Langevin Monte Carlo を用いて、Q 関数をその後部分布から直接サンプリングする。
提案手法は,Atari57スイートからのいくつかの挑戦的な探索課題において,最先端の深部RLアルゴリズムと比較して,より優れた,あるいは類似した結果が得られる。
論文 参考訳（メタデータ） (2023-05-29T17:11:28Z) - Minimizing Entropy to Discover Good Solutions to Recurrent Mixed Integer
Programs [0.0]
混合整数プログラミング(MIP)問題に対する現在の解法は、幅広い問題に対して良好に動作するように設計されている。
近年の研究では、機械学習(ML)をMIPソルバと統合してドメイン知識を注入し、最適性ギャップを効率的に閉じることが示されている。
本稿では、エントロピーの概念を用いて、最小限のトレーニングデータとチューニングで効率的にモデルを構築するオンラインソルバを提案する。
論文 参考訳（メタデータ） (2022-02-07T18:52:56Z) - Pretrained Cost Model for Distributed Constraint Optimization Problems [37.79733538931925]
分散制約最適化問題(DCOP)は、最適化問題の重要なサブクラスである。
本稿では,DCOPのための新しい非巡回グラフスキーマ表現を提案し,グラフ表現を組み込むためにグラフ注意ネットワーク(GAT)を利用する。
我々のモデルであるGAT-PCMは、幅広いDCOPアルゴリズムを向上するために、オフラインで最適なラベル付きデータで事前訓練される。
論文 参考訳（メタデータ） (2021-12-08T09:24:10Z) - Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances [55.64521598173897]
本稿では,旅行セールスマン問題(TSP)のヒートマップ構築に繰り返し使用可能な,小規模モデルのトレーニングを試みる。
ヒートマップは強化学習アプローチ(モンテカルロツリーサーチ)に供給され、高品質のソリューションの検索を案内します。
実験結果によると、この新しいアプローチは、既存の機械学習ベースのTSPアルゴリズムを明らかに上回る。
論文 参考訳（メタデータ） (2020-12-19T11:06:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。