Combining Monte Carlo Tree Search and Heuristic Search for Weighted Vertex Coloring

• URL: http://arxiv.org/abs/2304.12146v1
• Date: Mon, 24 Apr 2023 14:50:33 GMT
• Title: Combining Monte Carlo Tree Search and Heuristic Search for Weighted Vertex Coloring
• Authors: Cyril Grelier and Olivier Goudet and Jin-Kao Hao
• Abstract summary: This work investigates the Monte Carlo Tree Search (MCTS) method combined with dedicateds for solving the Weighted Vertex Coloring Problem. In addition to the basic MCTS algorithm, we study several variants where conventional random simulation is replaced by other simulation strategies. We conduct experiments on well-known benchmark instances to assess these combined MCTS variants.
• Score: 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.

Related papers

• Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
  We introduce an original variant of Monte-Carlo Tree Search (MCTS) tailored to multi-agent pathfinding. Specifically, we use individual paths to assist the agents with the the goal-reaching behavior. We also use a dedicated decomposition technique to reduce the branching factor of the tree search procedure.
  arXiv  Detail & Related papers  (2023-07-25T12:33:53Z)
• Bayesian Decision Trees Inspired from Evolutionary Algorithms [64.80360020499555]
  We propose a replacement of the Markov Chain Monte Carlo (MCMC) with an inherently parallel algorithm, the Sequential Monte Carlo (SMC) Experiments show that SMC combined with the Evolutionary Algorithms (EA) can produce more accurate results compared to MCMC in 100 times fewer iterations.
  arXiv  Detail & Related papers  (2023-05-30T06:17:35Z)
• Continuous Monte Carlo Graph Search [61.11769232283621]
  Continuous Monte Carlo Graph Search ( CMCGS) is an extension of Monte Carlo Tree Search (MCTS) to online planning. CMCGS takes advantage of the insight that, during planning, sharing the same action policy between several states can yield high performance. It can be scaled up through parallelization, and it outperforms the Cross-Entropy Method (CEM) in continuous control with learned dynamics models.
  arXiv  Detail & Related papers  (2022-10-04T07:34:06Z)
• Combining Monte-Carlo Tree Search with Proof-Number Search [5.354801701968199]
  Proof-Number Search (PNS) and Monte-Carlo Tree Search (MCTS) have been successfully applied for decision making in a range of games. This paper proposes a new approach called PN-MCTS that combines these two tree-search methods by incorporating the concept of proof and disproof numbers into the UCT formula of MCTS. Experimental results demonstrate that PN-MCTS outperforms basic MCTS in several games including Lines of Action, MiniShogi, Knightthrough, and Awari, achieving win rates up to 94.0%.
  arXiv  Detail & Related papers  (2022-06-08T15:28:42Z)
• On Monte Carlo Tree Search for Weighted Vertex Coloring [15.308312172985486]
  This work presents the first study of using the popular Monte Carlo Tree Search (MCTS) method combined with dedicateds for solving the Weighted Vertex Coloring Problem.
  arXiv  Detail & Related papers  (2022-02-03T16:27:55Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  We develop effective Monte Carlo algorithms to approximate the optimal bounds from an arbitrary combination of observational and experimental data. Our algorithms are validated extensively on synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2021-10-12T02:21:30Z)
• Monte Carlo Tree Search for high precision manufacturing [55.60116686945561]
  We make use of an expert-based simulator and adapt the MCTS default policy to deal with the manufacturing process. Common reasons for this are that there is no efficient simulator of the process available or there exist problems in applying MCTS to the complex rules of the process.
  arXiv  Detail & Related papers  (2021-07-28T14:56:17Z)
• Deterministic Gibbs Sampling via Ordinary Differential Equations [77.42706423573573]
  This paper presents a general construction of deterministic measure-preserving dynamics using autonomous ODEs and tools from differential geometry. We show how Hybrid Monte Carlo and other deterministic samplers follow as special cases of our theory.
  arXiv  Detail & Related papers  (2021-06-18T15:36:09Z)
• Monte Carlo Tree Search: A Review of Recent Modifications and Applications [0.17205106391379024]
  Monte Carlo Tree Search (MCTS) is a powerful approach to designing game-playing bots or solving sequential decision problems. The method relies on intelligent tree search that balances exploration and exploitation. The method has become a state-of-the-art technique for games, however, in more complex games.
  arXiv  Detail & Related papers  (2021-03-08T17:44:15Z)
• Monte Carlo Tree Search Based Tactical Maneuvering [1.827510863075184]
  We explore the application of simultaneous move Monte Carlo Tree Search (MCTS) based online framework for tactical maneuvering between two unmanned aircrafts. MCTS enables efficient search over long horizons and uses self-play to select best maneuver in the current state while accounting for the opponent aircraft tactics.
  arXiv  Detail & Related papers  (2020-09-13T02:03:25Z)
• Unlucky Explorer: A Complete non-Overlapping Map Exploration [0.949996206597248]
  We introduce the Maze Dash puzzle as an exploration problem where the agent must find a Hamiltonian Path visiting all the cells. An optimization has been applied to the proposed Monte-Carlo Tree Search (MCTS) algorithm to obtain a promising result. Our comparison indicates that the MCTS-based approach is an up-and-coming method that could cope with the test cases with small and medium sizes.
  arXiv  Detail & Related papers  (2020-05-28T17:19:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.