Monte Carlo Tree Search Algorithm for the Euclidean Steiner Tree Problem

• Autorzy: Bereta M.

Identyfikatory

DOI

10.26636/jtit.2017.122017

• Języki publikacji: EN

Abstrakty

EN

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 p p points (terminals) on a plane, the goal is to find a connection between all the points, so that the total sum of the lengths of edges is as low as possible, while an addition of extra points (Steiner points) is allowed. Finding the 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 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.

Słowa kluczowe

EN

Euclidean Steiner tree problem; MCTS; Monte Carlo Tree Search; UCT algorithm

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2017
• Tom: nr 4
• Strony: 71--81
• Opis fizyczny: Bibliogr. 21 poz., rys., tab.

Twórcy

autor

Bereta M.

• Faculty of Physics, Mathematics and Computer Science, Tadeusz Kościuszko Cracow University of Technology, 24 Warszawska st, 31-155 Cracow, Poland

Bibliografia

• [1] D. Silver et al., “Mastering the game of Go with deep neural networks and tree search”, Nature, vol. 529, pp. 484–489, 2016.
• [2] C. Browne and E. Powley, “A survey of Monte Carlo tree search methods”, IEEE Trans. on Intell. and AI in Games, vol. 4, no. 1, pp. 1–49, 2012.
• [3] A. Auger and O. Teytaud, “Continuous lunches are free plus the design of optimal optimization algorithms”, Algorithmica, vol. 57, no. 1, pp. 121–146, 2010.
• [4] R. C. Prim, “Shortest connection networks and some generalizations”, The Bell System Tech. J., vol. 36, pp. 1389–1401, no. 6, 1957.
• [5] M. Brazil and M. Zachariasen, Optimal Interconnection Trees in the Plane. Theory, Algorithms and Applications, 1st ed. Springer, 2015.
• [6] E. Miguez, J. Cidras, E. Diaz-Dorado, and J. L. Garcia-Dornelas, “An Improved Branch Exchange Algorithm for Large Scale Distribution Network Planning”, IEEE Power Engineering Review, vol. 22, pp. 58–58, 2002.
• [7] M. M. M. Brazil, C. C. Ras, and D. D. Da Thomas, “Relay augmentation for lifetime extension of wireless sensor networks”, IET Wirel. Sensor Sys., pp. 1–29, 2013.
• [8] R. P. Mondaini and N. V. Oliveira, “Intramolecular structure of proteins as driven by Steiner optimization problems”, in Proc. 18th Int. Conf. on Syst. Engin. ICSEng 2005, Las Vegas, NV, USA, 2005, vol. 1, pp. 490–491.
• [9] Z. A. Melzak, “On the problem of Steiner”, Canadian Mathem. Bull., vol. 4, pp. 143–148, 1961.
• [10] P. Winter and M. Zachariasen, “Euclidean Steiner minimum trees: An improved exact algorithm”, Networks, vol. 30, no. 3, pp. 149–166, 1997.
• [11] D. Trietsch and F. Hwang, “An improved algorithm for Steiner trees”, SIAM J. on Appl. Mathem., vol. 50, no. 1, pp. 244–263, 1990.
• [12] W. D. Smith, “How to find Steiner minimal trees in euclideandspace”, Algorithmica, vol. 7, no. 1–6, pp. 137–177, 1992.
• [13] V. L. do Forte, F. M. T. Montenegro, J. A. de M. Brito, and N. Maculan, “Iterated local search algorithms for the Euclidean Steiner tree problem in n dimensions”, Int. Trans. in Oper. Res., vol. 23, no. 6, pp. 1185–1199, 2015.
• [14] J. Barreiros, “A hierarchic genetic algorithm for computing (near) optimal Euclidean Steiner trees”, in GECCO 2003: Proceedings of the Bird of a Feather Workshops, Genetic and Evolutionary Computation Conference, A. M. Barry, Ed. Chigaco: AAAI, 2003, pp. 56–65.
• [15] J. E. Beasley, “OR-Library: distributing test problems by electronic mail”, J. of the Oper. Res. Soc., vol. 41, no. 11, pp. 1069–1072, 1990.
• [16] B. Abramson, “Expected-outcome: A general model of static evaluation”, IEEE Trans. Pattern Anal. Mach. Intell., vol. 12, no. 2, pp. 182–193, 1990.
• [17] R. Coulom, “Efficient Selectivity and Backup Operators in MonteCarlo Tree Search”, in Computers and Games: 5th International Conference, CG 2006, Turin, Italy, May 29–31, 2006. Revised Papers, H. J. van den Herik, P. Ciancarini, and H. H. L. M. Donkers (Jeroen), Eds. Berlin Heidelberg: Springer, 2007, pp. 72–83.
• [18] P. Auer, N. Cesa-Bianchi, and P. Fischer, “Finite-time analysis of the multiarmed bandit problem”, Machine Learning, vol. 47, no. 2–3, pp. 235–256, 2002.
• [19] L. Kocsis and C. Szepesv´ ari, “Bandit based Monte-Carlo planning”, in Machine Learning: ECML 2006. 17th European Conference on Machine Learning Berlin, Germany, September 18–22, 2006 Proceedings, J. F¨ urnkranz, T. Scheffer, and M. Spiliopoulou, Eds. Berlin Heidelberg: Springer, 2006, pp. 282–293, 2006.
• [20] J. Derrac, S. Garcia, D. Molina, and F. Herrera, “A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms”, Swarm and Evol. Comput., vol. 1, no. 1, pp. 3–18, 2011.
• [21] J. Alcala-Fdez, A. Fernandez, J. Luengo, J. Derrac, S. Garcia, L. Sanchez, and F. Herrera, “KEEL data-mining software tool: Data set repository, integration of algorithms and experimental analysis framework”, J. of Multiple-Valued Logic and Soft Comput., vol. 17, no. 2–3, pp. 255–287, 2011.