White Rose University Consortium logo
University of Leeds logo University of Sheffield logo York University logo

Locality in the Evolutionary Optimisation of Programs

Seaton, Thomas (2013) Locality in the Evolutionary Optimisation of Programs. PhD thesis, University of York.

[img] Archive (Zipped pdf version of thesis)
Available under License Creative Commons Attribution-Noncommercial-No Derivative Works 2.0 UK: England & Wales.

Download (6Mb)


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 coevolutionary 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.

Item Type: Thesis (PhD)
Academic Units: The University of York > Electronics (York)
Identification Number/EthosID: uk.bl.ethos.572401
Depositing User: Mr Thomas Seaton
Date Deposited: 29 May 2013 13:19
Last Modified: 08 Sep 2016 13:02
URI: http://etheses.whiterose.ac.uk/id/eprint/3939

You do not need to contact us to get a copy of this thesis. Please use the 'Download' link(s) above to get a copy.
You can contact us about this thesis. If you need to make a general enquiry, please see the Contact us page.

Actions (repository staff only: login required)