論文の概要: 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.の仕事の拡張である。
関連論文リスト
- Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。
具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。
また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
論文 参考訳(メタデータ) (2023-07-25T12:33:53Z) - 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 for high precision manufacturing [55.60116686945561]
我々は、専門家ベースのシミュレータを使用し、MCTSのデフォルトポリシーを適用して製造プロセスに対処する。
一般的な理由は、プロセスの効率的なシミュレータが存在しないことや、MCTSをプロセスの複雑な規則に適用する際の問題があることである。
論文 参考訳(メタデータ) (2021-07-28T14:56:17Z) - Deterministic Gibbs Sampling via Ordinary Differential Equations [77.42706423573573]
本稿では,自律的ODEとツールを用いた決定論的測度保存ダイナミクスの一般構築について述べる。
我々は、ハイブリッドモンテカルロや他の決定論的サンプルが、我々の理論の特別な場合としてどのように従うかを示す。
論文 参考訳(メタデータ) (2021-06-18T15:36:09Z) - Monte Carlo Tree Search: A Review of Recent Modifications and
Applications [0.17205106391379024]
モンテカルロツリー検索(MCTS)は、ゲームプレイボットを設計したり、連続的な決定問題を解決するための強力なアプローチです。
この方法は、探索と搾取のバランスをとるインテリジェントな木探索に依存している。
しかし、この方法はより複雑なゲームでは最先端の技術となっている。
論文 参考訳(メタデータ) (2021-03-08T17:44:15Z) - Monte Carlo Tree Search Based Tactical Maneuvering [1.827510863075184]
モンテカルロ・ツリー・サーチ(MCTS)をベースとしたオンライン・フレームワークによる2機の無人航空機間の戦術的操作の同時移動について検討する。
MCTSは長い地平線を効率的に探索し、対戦機戦術を考慮しつつ、現在の状態における最良の操縦を選択するためにセルフプレイを使用する。
論文 参考訳(メタデータ) (2020-09-13T02:03:25Z) - Unlucky Explorer: A Complete non-Overlapping Map Exploration [0.949996206597248]
エージェントがすべてのセルを訪問するハミルトニアンパスを見つけなければならない探索問題として,Maze Dashパズルを紹介した。
提案したモンテカルロ木探索(MCTS)アルゴリズムに最適化を適用し,有望な結果を得た。
比較の結果,MCTSをベースとしたアプローチは,テストケースの小型化と中型化を両立させる手法であることがわかった。
論文 参考訳(メタデータ) (2020-05-28T17:19:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。