Towards Understanding the Effects of Locality in GP

Abstract

Locality - how well neighbouring genotypes correspond to neighbouring phenotypes - has been defined as a key element in Evolutionary Computation systems to explore and exploit the search space. Locality has been studied empirically using the typical Genetic Algorithms (GAs) representation (i.e., bitstrings), and it has been argued that locality plays an important role in the performance of evolution. To our knowledge, there are no studies of locality using the typical Genetic Programming (GP) representation (i.e., tree-like structures). The aim of this paper is to shed some light on this matter by using GP. To do so, we use three different types of mutation taken from the specialised literature. We then perform extensive experiments by comparing the difference of distances at the genotype level between parent and offspring and their corresponding fitnesses. Our findings indicate that there is low-locality in GP when using these forms of mutation on a multimodal-deceptive landscape.