An Exploration of Tree-Adjoining Grammars for Grammatical Evolution

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

  author =       "Eoin Murphy",
  title =        "An Exploration of Tree-Adjoining Grammars for
                 Grammatical Evolution",
  school =       "University College Dublin",
  year =         "2014",
  address =      "Ireland",
  month =        "6 " # dec,
  keywords =     "genetic algorithms, genetic programming, Grammatical
                 Evolution, TAG",
  URL =          "",
  size =         "302 pages",
  abstract =     "Grammars are an important tool for Evolutionary
                 Computation (EC). Grammars offer a flexible means of
                 search space restriction, and provide a mechanism for
                 imposing language and search biases. This thesis
                 explores the use of a particular grammar type,
                 Tree-Adjoining Grammars (TAGs) for use with Grammatical
                 Evolution (GE), a grammar-based EC algorithm. To date,
                 much of the work on GE has used Context-Free Grammars
                 (CFGs). TAGs have been shown to be more powerful than
                 CFGs and can generate some context-sensitive languages.
                 TAGs also exhibit interesting properties, such as, each
                 intermediate stage of TAG derivation being a fully
                 structured feasible sentence from the language.

                 The focus of this thesis is to explore the use of TAGs
                 for representation in GE. A definition of TAGs is given
                 and a comprehensive survey of TAGs in EC is presented.
                 Following this, a novel representation and mapping
                 process is developed which combines the linear
                 chromosome used by GE with TAGs. This extension of GE,
                 called Tree-Adjoining Grammatical Evolution (TAGE), is
                 compared with canonical GE on a number of benchmark
                 problems. TAGE demonstrates a performance benefit over
                 GE. Further study of the two representations is
                 presented, which identifies core representational
                 differences, such as, invalid individuals and neutral
                 crossover operations, both of which do not occur in
                 TAGE. These differences are shown to account for some
                 of improved performance of TAGE.

                 Subsequent to this, a novel method of rendering search
                 landscapes is presented. Single mutation event
                 landscapes are generated for GE and TAGE for a number
                 of common grammars. It is shown that TAGE search spaces
                 are much more densely connected than those of GE,
                 affording TAGE greater opportunities to move about the
                 search space.

                 Further representational differences in the form of
                 preferential language biases are discovered when
                 developing methods of generating similar initial
                 populations for both TAGE and GE. Two main biases are
                 identified, adjunction constraints and grammar
                 transformation biases. These biases affect the
                 distributions of tree structures generated by TAGE.
                 Methods of mitigating these biases are presented and it
                 is shown that these biases can provide problem
                 dependent performance benefits.

                 The developmental nature of the feasibility property of
                 TAGs is exploited by integrating an on line artificial
                 gene regulatory network (GRN) model with TAGE in the
                 form of Developmental TAGE (DTAGE). DTAGE is shown to
                 improve the usability of this GRN model by facilitating
                 it with the use of the TAGE mapping process. DTAGE is
                 demonstrated to be capable of evolving GRNs whose
                 output, when provided with feedback in the form of
                 state information from dynamic problem environments,
                 maps to phenotypes that can survive in those

                 In summary, this thesis explores the utility and
                 capability of TAGs for representation in GE.
                 Differences in representation between TAGs and CFGs for
                 use with GE are identified and studied in terms of
                 performance. TAGs are then exploited in the development
                 of a novel evolutionary developmental system combining
                 TAGs, GE and a GRN model.",
  notes =        "Supervisor: Michael O'Neill",

Genetic Programming entries for Eoin Murphy