Algorithms for Grammar-based Evolution

AGE is a complete opensource framework for grammatical evolution (GE) and context-free grammar genetic programming (CFG-GP) written in C++ and Lua. Its current version boasts the following features:

a clean, comprehensive implementation of standard algorithms (general evolutionary algorithms, GE mapping, CFG-GP),
modular architecture,
both user and developer documentation,
versatile output with many useful statistics,
reproducible results,
great performance.

Visualisation of the XML output via XSL (a run of the Santa Fe ant trail application).

Note to Czech-speaking visitors: You can download a Czech presentation handout (PDF, 32 slides) about grammatical evolution and AGE and the handout from my master thesis defence (PDF, 15 slides).

About grammar-based genetic programming

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 (Whigham, 1996), integration of GP and logic programming based on logic grammars (Wong and Leung, 2000), and grammatical evolution (O’Neill and Ryan, 2003).

You can learn more about grammar-based genetic programming in my master thesis (Adam Nohejl, 2011: Grammar-based genetic programming).

You can learn more about GE on a web site maintained by Michael O’Neil or in the documentation of this project.

Project goals

The project started as a tool for my successfully defended bachelor thesis (Adam Nohejl, 2009: Grammatical Evolution) and master thesis (Adam Nohejl, 2011: Grammar-based genetic programming), and I am continuing my work on it. The goal of the diploma thesis was 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 was compared in the following applications: symbolic regression (several variants, including the use of automatically defined functions), Santa Fe ant trail, and exam time tabling (a very interesting semi-real world application).

The thesis has fulfilled its goals, but there is of course plenty of room for improvement, further research, and applications. I would like to continue the development of AGE as a multi-method grammar-based evolution framework targeted at both research and practical use.

If you would like to use the software, modify it or extend it, feel free to do it. Full source code is available in the Download section. As AGE will develop I may set up a repository and a mailing list. In the meantime, you can drop me a line.

Licence

AGE is opensource and can be used for personal, academic, and commercial purposes at no cost.

AGE itself is licensed under the terms of the standard three-clause BSD licence. The distribution also includes other software distributed under the BSD licence or similarly liberal licences.