Genetic Algorithms driven by MCTS

• Thesis title in Czech: Genetické algoritmy řízené MCTS
• Thesis title in English: Genetic Algorithms driven by MCTS
• Key words: Monte Carlo, MCTS, UCT, Evoluční algoritmy, TSP
• English key words: Monte Carlo, MCTS, UCT, Evolutionary algorithms, TSP
• Academic year of topic announcement: 2014/2015
• Thesis type: diploma thesis
• Thesis language: angličtina
• Department: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
• Supervisor: RNDr. Jan Hric
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 29.01.2015
• Date of assignment: 24.03.2015
• Confirmed by Study dept. on: 14.04.2015
• Date and time of defence: 09.02.2016 09:00
• Date of electronic submission: 29.11.2015
• Date of submission of printed version: 01.12.2015
• Date of proceeded defence: 09.02.2016
• Opponents: Mgr. Josef Moudřík

Guidelines

This proposed thesis should find possibilities for an integration of genetic algorithms (GA) with a Monte Carlo Tree Search (MCTS) method.
Genetic algorithms search a parameter space of a problem. Then a tree is built from the searched solutions using appropriate methods. Next candidate solution (or a generation) is generated from the tree using MCTS-like methods.

For instance, the MCTS trees can select independent alleles, alleles depending on previously chosen
alleles, or build trees for succesfull sequences (schemas).

A goal of the thesis is to develop various techniques for a tree building, a selection, and combining of
individuals, and eventually an integration of heuristics. The results of a development will be
implemented and measured on some optimization problem(s).

References

P. Norvig, S. Russell, Artificial Intelligence - A Modern Approach, Prentice Hall, 2003

Sylvain Gelly, David Silver, Combining online and offline knowledge in UCT. In: ICML'07: Proceedings of the 24th International Conference on Machine Learning, New York, USA, ACM 2007, pp. 273-280

Guillaume Chaslot, Mark Winands, Jaap H. van den Herik, Jos Uiterwijk, Bruno Bouzy, Progressive strategies for Monte-Carlo tree search.
In: Joint Conference on Information Sciences, Salt Lake City, USA, 2007.

C. Browne, E. Powley, D. Whitehouse et. al., A Survey of Monte Carlo Tree Search Methods. IEEE Transactions on Computational Intelligence and AI in Games, IEEE, vol. 4, No. 1, 2012

Preliminary scope of work

Práce má prozkoumat možnosti integrace genetických algoritmů (GA) a Monte Carlo Tree Search (MCTS).
Genetické algoritmy prohledávají prostor parametrů nějakého problému.
Z dosud prohledaných řešení se postaví vhodným způsobem
strom a další řešení (nebo generace) je navrženo ze stromu pomocí MCTS metod.

Například MCTS-stromy můžou vybírat jednotlivé alely nezávisle, podmíněně podle předchozích vybraných alel anebo budovat stromy odpovídající úspěšným úsekům (schématům).

Cílem práce je prozkoumat různé způsoby stavby stromu, ohodnocování, výběru a kombinování
jedinců, případně integraci heuristik. Výsledky návrhu diplomant implementuje a změří na vybrané optimalizační úloze nebo úlohách.

(Lze navrhnout několik prací na související (pod)témy a přesněji určit zaměření konkrétní práce)