Together with Edgar Galvan-Lopez, Michael O'Neill and Anthony Brabazon we have published several papers examining, in particular, locality in GP.
This paper was presented at GPTP IX (2011) in Ann Arbour, Michigan, USA:
A Fine-Grained View of Phenotypes and Locality in GP (James McDermott, Edgar Galvan-Lopez, Michael O'Neill.) Slides here.
This paper was presented at PPSN XI (2010) in Krakow, Poland:
A Fine-Grained View of GP Locality with Binary Decision Diagrams as Ant Phenotypes
James McDermott, Edgar Galvan-Lopez, Michael O'Neill.
Abstract. The property that neighbouring genotypes tend to map to neighbouring phenotypes, i.e. locality, is an important criterion in the study of problem difficulty. Locality is problematic in tree-based genetic programming (GP), since typically there is no explicit phenotype. Here, we define multiple phenotypes for the artificial ant problem, and use them to describe a novel fine-grained view of GP locality. This allows us to identify the mapping from an ant's behavioural phenotype to its concrete path as being inherently non-local, and show that therefore alternative genetic encodings and operators cannot make the problem easy. We relate this to the results of evolutionary and random-search runs.
Code implementing the ant phenotypes (based on binary decision diagrams or BDDs) is available for download.