Documentation

The whole project is thoroughly documented in the bachelor thesis Grammatical Evolution. A User Documentation chapter is also part of the thesis, which is available as a nice searchable PDF with clickable links:

Licensed under a Creative Commons Attribution 3.0 Czech Republic Licence.

New features in version 1.1 are currently documented in a separate file Documentation addendum 1.1 (PDF). Both files are also available in the project tarball download. You can find additional information about the methods used in AGE and grammar-based genetic programming in general in my master thesis below.

Master thesis

Adam Nohejl, 2011: Grammar-based genetic programming, successfully defended.

Available for download (PDF, 99 pages).

Licensed under a Creative Commons Attribution 3.0 Czech Republic Licence.

Abstract

Tree-based genetic programming (GP) has several known shortcomings: difficult adaptability to specific programming languages and environments, the problem of closure and multiple types, and the problem of declarative representation of knowledge. Most of the methods that try to solve these problems are based on formal grammars. The precise effect of their distinctive features is often difficult to analyse and a good comparison of performance in specific problems is missing. This thesis reviews three grammar-based methods: context-free grammar genetic programming (CFG-GP), including its variant GPHH recently applied to exam timetabling, grammatical evolution (GE), and LOGENPRO, it discusses how they solve the problems encountered by GP, and compares them in a series of experiments in six applications using success rates and derivation tree characteristics. The thesis demonstrates that neither GE nor LOGENPRO provide a substantial advantage over CFG-GP in any of the experiments, and analyses the differences between the effects of operators used in CFG-GP and GE. It also presents results from a highly efficient implementation of CFG-GP and GE.

Contents

1. Introduction
2. Grammar-Based Genetic Programming Methods: 1.1 Formal grammars and programming, 1.2 Genetic programming, 1.3 Grammatically biased ILP, 1.4 CFG-GP, language bias, and search bias, 1.5 Logic grammar based genetic programming: LOGENPRO, 1.6 Grammatical evolution, 1.7 Common features and shortcomings, 1.8 Implications for performance
3. Existing Applications: 2.1 Simple symbolic regression, 2.2 Artificial ant trail, 2.3 Symbolic regression with multiple types, 2.4 Boolean symbolic regression, 2.5 Hyper-heuristics, 2.6 Other applications
4. Experiments with Grammar-Based Methods: 3.1 Observed characteristics, 3.2 Setup, 3.3 Statistics, 3.4 Simple symbolic regression, 3.5 Santa Fe ant trail, 3.6 Dot product symbolic regression, 3.7 Symbolic regression with ADFs, 3.8 Boolean parity functions with ADFs, 3.9 Exam time tabling hyper-heuristics, 3.10 Conclusion
5. Implementation Notes: 4.1 Implementation of CFG-GP, 4.2 Accompanying files
6. Conclusion

Bachelor thesis

Adam Nohejl, 2009: Grammatical Evolution, successfully defended.

Available above as the main documentation of the AGE project

Licensed under a Creative Commons Attribution 3.0 Czech Republic Licence.

Abstract

Grammatical evolution (GE) is a recent grammar-based approach to genetic programming that allows development of solutions in an arbitrary programming language. Its existing implementations lack documentation and do not provide reproducible results suitable for further analysis. This thesis summarises the methods of GE and the standard methods used in evolutionary algorithms, and reviews the existing implementations, foremost the only actively developed one, GEVA. A new comprehensive software framework for GE is designed and implemented based on this review. It is modular, well-documented, portable, and gives reproducible results. It has been tested in two benchmark applications, in which it showed competitive results and outperformed GEVA 10 to 29 times in computational time. It is also shown how to further improve the performance and results by using techniques unsupported by GEVA, including new modifications to the previously published methods of bit-level mutation and “sensible” initialisation. The thesis and the software together form a solid foundation for further experiments and research.

Contents

1. Introduction
2. Introduction to Grammatical Evolution: 2.1 Genetic programming, 2.2 Fitness, a broader view, 2.3 Genotype and phenotype, 2.4 Grammatical evolution, 2.5 GE example: symbolic regression, 2.6 Search algorithm elements
3. Existing Implementations: 3.1 libGE, 3.2 GEVA, 3.3 Other implementations, 3.4 Conclusion
4. Goals: 4.1 Implementation of standard algorithms, 4.2 Modularity, 4.3 Documentation, 4.4 Output and results
5. Design Decisions: 5.1 Overall design, 5.2 Ramped initialisation, 5.3 Evaluation in C and Lua, 5.4 Mutation operators, 5.5 Portability
6. User Documentation: 6.1 Building and installation, 6.2 Command line interface, 6.3 Implemented components, 6.4 File formats, 6.5 Application programming interface, 6.6 Tutorial for application developers
7. Developer Documentation: 7.1 Selection schemes, 7.2 Fast bit-level mutation
8. Experiments: 8.1 Methodology, 8.2 Symbolic regression, 8.3 Santa Fe ant trail, 8.4 Conclusion
9. Conclusion: 9.1 Summary, 9.2 Ideas for further research