Behavioral Locality in Genetic Programming

Locality is a key concept affecting exploration and exploitation in evolutionary computation systems. Genotype to phenotype mapping has locality if the neighborhood is preserved under that mapping. Unfortunately, assessment of the locality in Genetic Programming is dependent on the distance metric used to compare program trees. Furthermore, there is no distinction between genotype and phenotype in GP. As such the definition of locality in GP was studied only in the context of genotype-fitness mapping. In this work we propose a different family of similarity measures, graph kernels, as alternatives to the traditional family of distance metrics in use, that is edit distance. Traditional tree edit distance is compared to the Weisfeiler-Lehman Subtree Kernel, which is considered to be the state-of-the-art method in graph classification. Additionally, we extend the definition of the locality of GP, by studying the relationship between genotypes and behaviors. In this paper, we consider a mutation-based GP system applied to two basic benchmark problems: artificial ant (multimodal deceptive landscape) and even parity (highly neutral landscape).