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

Created by W.Langdon from gp-bibliography.bib Revision:1.8576

@InProceedings{corus:2025:GECCOcomp,

• author = "Dogan Corus and Pietro S. Oliveto",
• title = "On the Generalisation Performance of Geometric Semantic Genetic Programming for Boolean Functions: Learning Block Mutations",
• booktitle = "Proceedings of the 2025 Genetic and Evolutionary Computation Conference: Hot off the Press",
• year = "2025",
• editor = "Eric Medvet",
• pages = "87--88",
• address = "Malaga, Spain",
• series = "GECCO '25 Companion",
• month = "14-18 " # jul,
• organisation = "SIGEVO",
• publisher = "Association for Computing Machinery",
• publisher_address = "New York, NY, USA",
• keywords = "genetic algorithms, genetic programming, geometric semantic genetic programming, boolean functions, runtime analysis",
• isbn13 = "979-8-4007-1464-1",
• URL = "https://doi.org/10.1145/3712255.3734249",
• DOI = "doi:10.1145/3712255.3734249",
• size = "2 pages",
• 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.",
• notes = "GECCO-2025 A Recombination of the 34th International Conference on Genetic Algorithms (ICGA) and the 30th Annual Genetic Programming Conference (GP)",

}

Genetic Programming entries for Dogan Corus Pietro S Oliveto

Citations