from IPython.core.display import Image, display
Table of Contents
A MCTS search utilizes tree-structure to balance between exploration and exploitation, and the algorithm consists of four key stages:
This figure highlights the difference between a discrete (left) and continuous (right) action space. For the same boundary conditions, a discrete action space has a finite number of possibilities (e.g., 361 grid points) whereas a continuous action space has infinite number of possibilites.
c-MCTS is specially designed to handle this major difference. We implemented different strategies such as range narrowing and uniqueness score to enable efficient sampling in continous high dimentional space.
c-MCTS is efficient in sampling a high dimensional continuous space. The figure below highlights the results of four 50-dimensional trail functions. c-MCTS outperforms standard optimization algorithms such as Bayesian, particle swarm, and random sampling methods both in terms of the number of iterations to reach the solution and the quality of the best solution.
Here, we compare the performance of c-MCTS with common algorithms in finding the solution for 25 different trial functions. The two performance metrics we focus on are the number of iterations (within 30000 iterations) to reach the target solution and the quality of the best solution obtained. D denotes the dimension of the trial function while the tolerance indicates the accepted error of the solution.