An Exploration of Grammars in Grammatical Evolution

Created by W.Langdon from gp-bibliography.bib Revision:1.4524

  author =       "Erik Anders Pieter Hemberg",
  title =        "An Exploration of Grammars in Grammatical Evolution",
  school =       "University College Dublin",
  address =      "Ireland",
  month =        "17 " # sep,
  year =         "2010",
  keywords =     "genetic algorithms, genetic programming, grammatical
  URL =          "",
  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

                 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.",

Genetic Programming entries for Erik Hemberg