Locality in the Evolutionary Optimisation of Programs

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

  author =       "Thomas A. Seaton",
  title =        "Locality in the Evolutionary Optimisation of
  school =       "Department of Electronics, The University of York",
  year =         "2013",
  address =      "UK",
  month =        feb,
  keywords =     "genetic algorithms, genetic programming, Grammatical
                 Evolution, cartesian genetic programming, coevolution",
  URL =          "http://etheses.whiterose.ac.uk/3939/",
  URL =          "http://etheses.whiterose.ac.uk/3939/1/Thesis.zip",
  URL =          "http://etheses.whiterose.ac.uk/3939/1/Thesis.pdf",
  URL =          "http://ethos.bl.uk/OrderDetails.do?did=43&uin=uk.bl.ethos.572401",
  size =         "202 pages",
  abstract =     "The development and optimisation of programs through
                 search is a growing application area for computational
                 intelligence techniques. Evolution-inspired search
                 heuristics, such as genetic programming, provide
                 methods for autonomously generating programs within the
                 constraints of a program representation. Genetic
                 programming is a machine learning approach to producing
                 programs represented using executable or interpreted
                 structures. However, despite theoretical advances,
                 choosing a suitable representation remains a basic
                 concern for designers. Choice of representation affects
                 search space size, structure and accessible solutions,
                 as well as engineering considerations such as ease of
                 implementation. Locality is a property of evolutionary
                 search spaces derived from the representation and
                 search operators, that relates genotype and phenotype
                 distances. The interaction between search space
                 locality and search performance under different
                 representations is not well understood. The objective
                 of this thesis is to broaden the present understanding
                 of locality to encompass more complex representations,
                 for example graphs and grammars, as well as
                 non-traditional coevolutionary approaches. This thesis
                 presents four main original contributions. Firstly, a
                 statistical approach to measuring locality is defined
                 that incorporates the Mantel test, a method adapted
                 from numerical ecology. The method is assessed
                 empirically in a series of case studies over two
                 established forms of genetic programming, Grammatical
                 Evolution and Cartesian Genetic Programming. Secondly,
                 a new approach to visualising locality is provided. The
                 technique uses force-layout algorithms derived from the
                 field of graph-drawing to construct fitness landscapes
                 in genetic programming. The technique is applied to
                 produce visualisations that demonstrate structural
                 characteristics across regions of the search space.
                 Thirdly, the effect of locality on performance is
                 assessed in model co-evolutionary problems. A framework
                 to analyse performance in a coevolutionary context is
                 provided, followed by an examination of the response to
                 locality and coupled algorithm parameters. The final
                 contribution explores the interaction between locality
                 and two `pathological' dynamics in coevolutionary
                 algorithms, disengagement and cycling. The analysis
                 demonstrates that locality can influence the likelihood
                 of coevolutionary pathologies, when using executable
                 representations. Results are provided for new
                 constructed problems and a coevolutionary pursuit and
                 evasion task. In the conclusions, directions for future
                 analysis of the role of locality in evolutionary search
                 are considered, as well as the relationship between
                 these findings and other outstanding general issues in
                 the field of genetic programming.",
  notes =        "uk.bl.ethos.572401",

Genetic Programming entries for Tom Seaton