Locality in the Evolutionary Optimisation of Programs

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.