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

摘要

Geometric Semantic Genetic Programming (GSGP) is a recentlyudintroduced form of Genetic Programming (GP), rootedudin a geometric theory of representations, that searches directlyudthe semantic space of functions/programs, rather thanudthe space of their syntactic representations (e.g., trees) as inudtraditional GP. Remarkably, the fitness landscape seen byudGSGP is always – for any domain and for any problem –udunimodal with a linear slope by construction. This has twoudimportant consequences: (i) it makes the search for the optimumudmuch easier than for traditional GP; (ii) it opens theudway to analyse theoretically in a easy manner the optimisationudtime of GSGP in a general setting. The runtime analysisudof GP has been very hard to tackle, and only simplified formsudof GP on specific, unrealistic problems have been studied soudfar. We present a runtime analysis of GSGP with variousudtypes of mutations on the class of all Boolean functions