Towards an understanding of locality in genetic programming

Locality – how well neighbouring genotypes correspond to neighbouring phenotypes – has been defined as a key ele-ment affecting how Evolutionary Computation systems ex-plore and exploit the search space. Locality has been studied empirically using the typical Genetic Algorithm (GA) rep-resentation (i.e., bitstrings), and it has been argued that locality plays an important role in EC performance. To our knowledge, there are few explicit studies of locality using the typical Genetic Programming (GP) representation (i.e., tree-like structures). The aim of this paper is to address this important research gap. We extend the genotype-phenotype definition of locality to GP by studying the relationship be-tween genotypes and fitness. We consider a mutation-based GP system applied to two problems which are highly diffi-cult to solve by GP (a multimodal deceptive landscape and a highly neutral landscape). To analyse in detail the locality in these instances, we adopt three popular mutation opera-tors. We analyse the operators ’ genotypic step sizes in terms of three distance measures taken from the specialised liter-ature and in terms of corresponding fitness values. We also analyse the frequencies of different sizes of fitness change