Back to search

University of York

Locality in the Evolutionary Optimisation of Programs

Abstract

dc:description.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 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.

Degree

thesis:*
Name dc:type.qualificationname
Ph.D
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of York
Year dc:date.issued
2013

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Seaton, Thomas
Advisor dc:contributor.advisor
  • Miller, Julian F.

Rights

Language dc:language.dcterms_iso639_2
eng

Identifiers

dc:identifier.*
Identifier
uk.bl.ethos.572401

Chain of custody

source
Harvested from
White Rose University Consortium
Base URL
etheses.whiterose.ac.uk/cgi/oai2
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Seaton, Thomas. Locality in the Evolutionary Optimisation of Programs. doctoral thesis, University of York, 2013.