Comparison of Semantic-aware Selection Methods in Genetic Programming

Abstract

This study investigates the performance of several semantic- aware selection methods for genetic programming (GP). In particular, we consider methods that do not rely on complete GP semantics (i.e., a tuple of outputs produced by a program for fitness cases (tests)), but on binary outcome vectors that only state whether a given test has been passed by a program or not. This allows us to relate to test-based problems commonly considered in the domain of coevolutionary algorithms and, in prospect, to address a wider range of practical problems, in particular the problems where desired program output is unknown (e.g., evolving GP controllers). The selection methods considered in the paper include implicit fitness sharing (ifs), discovery of derived objectives (doc), lexicase selection (lex), as well as a hybrid of the latter two. These techniques, together with a few variants, are experimentally compared to each other and to conventional GP on a battery of discrete benchmark problems. The outcomes indicate superior performance of lex and ifs, with some variants of doc showing certain potential.