- 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 = "
http://ncra.ucd.ie/papers/EoinMurphy_thesis.pdf",
- 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 environments.
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",
