Monte Carlo Tree Search algorithm for the Euclidean Steiner tree problem
Authors:
- Michał Bereta
Abstract
This study is concerned with a novel Monte Carlo Tree Search algorithm for the problem of minimal Euclidean Steiner tree on a plane. Given p points (terminals) on a plane, the goal is to find a connection of all of the points with edges of the minimum total sum of lengths, while an addition of extra points (Steiner points) is allowed. Finding minimum Steiner tree is known to be np-hard. While exact algorithms exist for this problem in 2D, their efficiency decreases when the number of terminals grows. A novel algorithm based on Upper Confidence Bound for Trees is proposed. It is adapted to the specific characteristics of the Steiner trees. A simple heuristic for fast generation of feasible solutions based on Fermat points is proposed together with a correction procedure. By combing Monte Carlo Tree Search and the proposed heuristics the proposed algorithm is shown to work better than both the greedy heuristic and pure Monte Carlo simulations. Results of numerical experiments for randomly generated and benchmark library problems (from OR-Lib) are presented and discussed.
- Record ID
- CUT579e2c3dcff3432c8eb6bacc996f5213
- Publication categories
- ;
- Author
- Journal series
- Journal of Telecommunications and Information Technology, ISSN 1509-4553, e-ISSN 1899-8852
- Issue year
- 2017
- No
- 4
- Pages
- 71-81
- Other elements of collation
- rys.; tab.; Bibliografia (na s.) - 80-81; Bibliografia (liczba pozycji) - 21; Oznaczenie streszczenia - Abstr.; Numeracja w czasopiśmie - 4
- Keywords in English
- Euclidean Steiner tree problem, MCTS, Monte Carlo Tree Search, UCT algorithm
- DOI
- DOI:10.26636/jtit.2017.122017 Opening in a new tab
- URL
- http://www.itl.waw.pl/archiwum-jtit?view=kwartalrok&rok=2017&kwartal=4 Opening in a new tab
- Language
- eng (en) English
- License
- Score (nominal)
- 12
- Additional fields
- Indeksowana w: Scopus
- Uniform Resource Identifier
- https://cris.pk.edu.pl/info/article/CUT579e2c3dcff3432c8eb6bacc996f5213/
- URN
urn:pkr-prod:CUT579e2c3dcff3432c8eb6bacc996f5213
* presented citation count is obtained through Internet information analysis, and it is close to the number calculated by the Publish or PerishOpening in a new tab system.