Genetic Algorithms driven by MCTS
| Název práce v češtině: | Genetické algoritmy řízené MCTS |
|---|---|
| Název v anglickém jazyce: | Genetic Algorithms driven by MCTS |
| Klíčová slova: | Monte Carlo, MCTS, UCT, Evoluční algoritmy, TSP |
| Klíčová slova anglicky: | Monte Carlo, MCTS, UCT, Evolutionary algorithms, TSP |
| Akademický rok vypsání: | 2014/2015 |
| Typ práce: | diplomová práce |
| Jazyk práce: | angličtina |
| Ústav: | Katedra teoretické informatiky a matematické logiky (32-KTIML) |
| Vedoucí / školitel: | RNDr. Jan Hric |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 29.01.2015 |
| Datum zadání: | 24.03.2015 |
| Datum potvrzení stud. oddělením: | 14.04.2015 |
| Datum a čas obhajoby: | 09.02.2016 09:00 |
| Datum odevzdání elektronické podoby: | 29.11.2015 |
| Datum odevzdání tištěné podoby: | 01.12.2015 |
| Datum proběhlé obhajoby: | 09.02.2016 |
| Oponenti: | Mgr. Josef Moudřík |
| Zásady pro vypracování |
| 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). |
| Seznam odborné literatury |
| 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 |
| Předběžná náplň práce |
| 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) |