- author = "Erik Anders Pieter Hemberg",
- title = "An Exploration of Grammars in Grammatical Evolution",
- year = "2010",
- school = "University College Dublin",
- address = "Ireland",
- month = "17 " # sep,
- keywords = "genetic algorithms, genetic programming, grammatical evolution",
-
URL = "
http://ncra.ucd.ie/papers/exploration_of_grammars_in_grammatical_evolution.pdf",
- size = "265 pages",
-
abstract = "The grammar in the grammar-based Genetic Programming
(GP) approach of Grammatical Evolution (GE) is
explored. The GE algorithm solves problems by using a
grammar representation and an automated and parallel
trial-and-error approach, Evolutionary Computation
(EC). The search for solutions in EC is driven by
evaluating each solution, selecting the fittest and
replacing these into a population of solutions which
are modified to further guide the search.
Representations have a strong impact on the efficiency
of search and by using a generative grammar domain
knowledge is encoded into the population of solutions.
The grammar in GE biases the search for solutions, and
in combination with a linear representation this is
what distinguishes GE from other GP-systems.
After a review of grammars in EC and a description of GE, several different constructions of grammars and operators for manipulating the grammars and the evolutionary algorithm are studied. The thesis goes on to study a meta-grammar GE, which allows a larger grammar with different bias. By adopting a divide-and-conquer strategy the goal is to investigate how a modular GE approach solves problems of increasing size and in dynamically changing environments. The results show some benefit from using meta-grammars in GE, for the meta-grammar Genetic Algorithm (mGGA) and they re-emphasise the grammar's impact on GE's performance.
In addition, GE and meta-grammars are more formally described. The bias, both declarative and search, arising from the use of a Context-Free Grammar representation and the constraints of GE and the mGGA are analysed and their implications are examined. This is done by studying the effects of the mapping and operations on the input, single and multiple changes in input, as well as the preservation of output after a change. Furthermore, a matrix view of a grammar and different suggestions for measurements of grammars are investigated, in order to allow the practitioner to get an alternative view of the mapping process and of how operations work.",
