- author = "Dogan Corus and Pietro S. Oliveto",
- title = "On the Generalisation Performance of Geometric Semantic Genetic Programming for Boolean Functions: Learning Block Mutations",
- journal = "ACM Transactions on Evolutionary Learning and Optimization",
- year = "2024",
- volume = "4",
- number = "4",
- articleno = "25",
- month = dec,
- keywords = "genetic algorithms, genetic programming, Geometric Semantic Genetic Programming, Boolean functions, Runtime analysis",
- ISSN = "2688-299X",
-
DOI = "
10.1145/3677124",
- size = "33 pages",
- abstract = "...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 = "Dogan Corus PhD thesis (2018) Runtime analysis of
evolutionary algorithms with complex fitness evaluation
mechanisms. PhD thesis, University of Nottingham.
https://eprints.nottingham.ac.uk/id/eprint/48421 not on
GP?
Department of Computer Engineering, Kadir Has University, Istanbul, 34083, Turkey
https://dlnext.acm.org/journal/telo",
