On the Generalisation Performance of Geometric Semantic Genetic Programming for Boolean Functions: Learning Block Mutations

Abstract

In this paper we present the first rigorous theoretical analysis of the generalisation performance of a Geometric Semantic Genetic Programming (GSGP) system. More specifically, we consider a hill-climber using the GSGP Fixed Block Mutation (FBM) operator for the domain of Boolean functions. We prove that the algorithm cannot evolve Boolean conjunctions of arbitrary size that are correct on unseen inputs chosen uniformly at random from the complete truth table i.e., it generalises poorly. Two algorithms based on the Varying Block Mutation (VBM) operator are proposed and analysed to address the issue. We rigorously prove that under the uniform distribution the first one can efficiently evolve any Boolean function of constant size with respect to the number of available variables, while the second one can efficiently evolve general conjunctions or disjunctions of any size without requiring prior knowledge of the target function class. An experimental analysis confirms the theoretical insights for realistic problem sizes and indicates the superiority of the proposed operators also for small parity functions not explicitly covered by the theory.