論文の概要: Combining Monte Carlo Tree Search and Heuristic Search for Weighted
Vertex Coloring
- arxiv url: http://arxiv.org/abs/2304.12146v1
- Date: Mon, 24 Apr 2023 14:50:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-25 14:45:20.948431
- Title: Combining Monte Carlo Tree Search and Heuristic Search for Weighted
Vertex Coloring
- Title(参考訳): 重み付き頂点彩色におけるモンテカルロ木探索とヒューリスティック探索の組み合わせ
- Authors: Cyril Grelier and Olivier Goudet and Jin-Kao Hao
- Abstract要約: 本研究は,モンテカルロ木探索法(MCTS)と重み付き頂点色問題(Weighted Vertex Coloring Problem)の解法について検討する。
基本MCTSアルゴリズムに加えて,従来のランダムシミュレーションを他のシミュレーション手法に置き換えたいくつかの変種について検討する。
我々は、これらの組み合わせMCTSの変種を評価するために、よく知られたベンチマークインスタンスの実験を行う。
- 参考スコア(独自算出の注目度): 15.308312172985486
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This work investigates the Monte Carlo Tree Search (MCTS) method combined
with dedicated heuristics for solving the Weighted Vertex Coloring Problem. In
addition to the basic MCTS algorithm, we study several MCTS variants where the
conventional random simulation is replaced by other simulation strategies
including greedy and local search heuristics. We conduct experiments on
well-known benchmark instances to assess these combined MCTS variants. We
provide empirical evidence to shed light on the advantages and limits of each
simulation strategy. This is an extension of the work of Grelier and al.
presented at EvoCOP2022.
- Abstract(参考訳): 本研究はモンテカルロ木探索法(MCTS)と重み付き頂点色問題の解法のための専用ヒューリスティックスを組み合わせたものである。
基本MCTSアルゴリズムに加えて,従来の乱数シミュレーションをグリードや局所探索ヒューリスティックなど他のシミュレーション手法に置き換えたいくつかのMCTS変種について検討する。
我々は、これらの組み合わせMCTS変異を評価するために、よく知られたベンチマークインスタンスの実験を行う。
我々は各シミュレーション戦略の利点と限界を明らかにするための実証的な証拠を提供する。
これはevocop2022で発表されたgrelierとal.の仕事の拡張である。
関連論文リスト
- Prompt-Based Monte Carlo Tree Search for Mitigating Hallucinations in Large Models [1.4582633500696451]
本研究では,モンテカルロ木探索法(MCTS)の改良手法を提案する。
シミュレーション検索の段階では、探索パラメータの動的調整と適応選択戦略を導入し、探索と利用のバランスを改善する。
論文 参考訳(メタデータ) (2025-01-17T23:06:50Z) - Mulberry: Empowering MLLM with o1-like Reasoning and Reflection via Collective Monte Carlo Tree Search [74.46681227410038]
効率的な推論パス探索と学習のための集合モンテカルロ木探索(CoMCTS)を提案する。
我々はMulberry-260kを構築する。Mulberry-260kはマルチモーダルなデータセットで、各質問に対してリッチで明示的で明確に定義された推論ノードのツリーを持つ。
我々は、o1のようなステップバイステップ推論とリフレクション機能を備えたMLLMの一連のモデルであるMulberryを訓練するために、集合SFTを実行する。
論文 参考訳(メタデータ) (2024-12-24T10:07:51Z) - 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) - Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。
具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。
また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
論文 参考訳(メタデータ) (2023-07-25T12:33:53Z) - A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。
本稿では,差分に基づく探索法 (CombGapE) アルゴリズムを提案する。
我々は,CombGapEアルゴリズムが,合成データセットと実世界のデータセットの両方において,既存の手法を大幅に上回っていることを数値的に示す。
論文 参考訳(メタデータ) (2023-06-15T15:37:31Z) - Bayesian Decision Trees Inspired from Evolutionary Algorithms [64.80360020499555]
我々は、マルコフ連鎖モンテカルロ(MCMC)を本質的に並列なアルゴリズムであるシーケンシャルモンテカルロ(SMC)に置き換えることを提案する。
実験により、SMCと進化的アルゴリズム(EA)を組み合わせることで、MCMCの100倍のイテレーションでより正確な結果が得られることが示された。
論文 参考訳(メタデータ) (2023-05-30T06:17:35Z) - Continuous Monte Carlo Graph Search [61.11769232283621]
連続モンテカルログラフサーチ(Continuous Monte Carlo Graph Search, CMCGS)は、モンテカルログラフサーチ(MCTS)のオンラインプランニングへの拡張である。
CMCGSは、計画中、複数の州で同じ行動方針を共有することで高いパフォーマンスが得られるという洞察を生かしている。
並列化によってスケールアップすることができ、学習力学モデルによる連続制御においてクロスエントロピー法(CEM)よりも優れている。
論文 参考訳(メタデータ) (2022-10-04T07:34:06Z) - Combining Monte-Carlo Tree Search with Proof-Number Search [5.354801701968199]
Proof-Number Search (PNS) と Monte-Carlo Tree Search (MCTS) は様々なゲームにおいて意思決定に成功している。
本稿では,この2つの木探索手法を組み合わせたPN-MCTSという新しい手法を提案する。
実験の結果、PN-MCTSはLines of Action、MiniShogi、Knightthrough、Awariなどいくつかのゲームで基本MCTSを上回っ、94.0%の勝利率を記録した。
論文 参考訳(メタデータ) (2022-06-08T15:28:42Z) - On Monte Carlo Tree Search for Weighted Vertex Coloring [15.308312172985486]
本研究は,モンテカルロ木探索法(MCTS)と重み付き頂点色問題(Weighted Vertex Coloring Problem)を併用した最初の研究である。
論文 参考訳(メタデータ) (2022-02-03T16:27:55Z) - Partial Counterfactual Identification from Observational and
Experimental Data [83.798237968683]
観測データと実験データの任意の組み合わせから最適境界を近似する有効なモンテカルロアルゴリズムを開発した。
我々のアルゴリズムは、合成および実世界のデータセットに基づいて広範囲に検証されている。
論文 参考訳(メタデータ) (2021-10-12T02:21:30Z) - Monte Carlo Tree Search: A Review of Recent Modifications and
Applications [0.17205106391379024]
モンテカルロツリー検索(MCTS)は、ゲームプレイボットを設計したり、連続的な決定問題を解決するための強力なアプローチです。
この方法は、探索と搾取のバランスをとるインテリジェントな木探索に依存している。
しかし、この方法はより複雑なゲームでは最先端の技術となっている。
論文 参考訳(メタデータ) (2021-03-08T17:44:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。