Grammar-based genetic programming

• Název práce v češtině: Grammar-based genetic programming
• Název v anglickém jazyce: Grammar-based genetic programming
• Klíčová slova: genetické programování, formální gramatika, evoluční algoritmy, gramatická evoluce
• Klíčová slova anglicky: genetic programming, formal grammar, evolutionary algorithms, grammatical evolution
• Akademický rok vypsání: 2009/2010
• Typ práce: diplomová práce
• Jazyk práce: angličtina
• Ústav: Katedra softwaru a výuky informatiky (32-KSVI)
• Vedoucí / školitel: RNDr. František Mráz, CSc.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 08.03.2010
• Datum zadání: 08.03.2010
• Datum a čas obhajoby: 05.09.2011 11:00
• Datum odevzdání elektronické podoby: 07.09.2011
• Datum odevzdání tištěné podoby: 05.08.2011
• Datum proběhlé obhajoby: 05.09.2011
• Oponenti: RNDr. Jiří Iša

Zásady pro vypracování

There have been a number of attempts at grammar-based genetic programming (GP). The several approaches have tried to complement, constrain, or supplant the explicit tree structures traditionally used in GP with derivations based on formal grammars. Formal grammars are a flexible tool for adapting GP to a specific problem, yet their integration with evolutionary algorithms raises a number of issues concerning the encoding of individuals, and design of operators. The proposed methods include introduction of bias in GP using context-free grammars, integration of GP and logic programming based on logic grammars, and Grammatical Evolution.

The goal of the thesis is to

(1) describe the problems arising from integration of grammars and genetic programming or evolutionary algorithms,

(2) compare the approaches of existing methods, and

(3) analyse their shortcomings and attempt to improve on them.

Appropriateness and performance will be compared on some benchmark problems like symbolic regression, Santa Fe ant trail, and exam time tabling.

Seznam odborné literatury

P. A. Whigham. Search bias, language bias, and genetic programming. In: J. R. Koza, et al., editors, Genetic Programming 1996: Proceedings of the First Annual Conference, Stanford University, CA, USA, MIT Press, 1996, 230-237.

M. L. Wong and K. S. Leung. Data Mining Using Grammar-Based Genetic Programming and Applications. Kluwer Academic Publishers, 2000.

M. O'Neill and C. Ryan. Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language. Springer, 2003.

M. B. B. El-Den, R. Poli, and S. Fatima. Evolving timetabling heuristics using a grammar-based genetic programming hyper-heuristic framework. In: Memetic Computing, Vol. 1, Nr. 3 (2009) 205-219.