Runtime analysis of mutation-based geometric semantic genetic programming on boolean functions.

Geometric Semantic Genetic Programming (GSGP) is a recently introduced form of Genetic Programming (GP), rooted in a geometric theory of representations, that searches directly the semantic space of functions/programs, rather than the space of their syntactic representations (e.g., trees) as in traditional GP. Remarkably, the fitness landscape seen by GSGP is always – for any domain and for any problem – unimodal with a linear slope by construction. This has two important consequences: (i) it makes the search for the optimum much easier than for traditional GP; (ii) it opens the way to analyse theoretically in a easy manner the optimisation time of GSGP in a general setting. The runtime analysis of GP has been very hard to tackle, and only simplified forms of GP on specific, unrealistic problems have been studied so far. We present a runtime analysis of GSGP with various types of mutations on the class of all Boolean functionsThe authors are grateful to Dirk Sudholt for helping check the proofs. Alberto Moraglio was supported by EPSRC grant EP/I010297/