(1+1) genetic programming with functionally complete instruction sets can evolve Boolean conjunctions and disjunctions with arbitrarily small error

DOI10.1016/J.ARTINT.2023.103906MaRDI QIDQ6161501zbMATH OpenFDO

Authors Benjamin Doerr, Andrei Lissovoi, Pietro S. Oliveto

Publication date 27 June 2023

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2303.07455

zbMATH Keywords

computational complexitygenetic programmingtheory

Mathematics Subject Classification ID

Artificial intelligence (68Txx)

Abstract: Recently it has been proven that simple GP systems can efficiently evolve a conjunction of $n$ variables if they are equipped with the minimal required components. In this paper, we make a considerable step forward by analysing the behaviour and performance of a GP system for evolving a Boolean conjunction or disjunction of $n$ variables using a complete function set that allows the expression of any Boolean function of up to $n$ variables. First we rigorously prove that a GP system using the complete truth table to evaluate the program quality, and equipped with both the AND and OR operators and positive literals, evolves the exact target function in $O(ellnlo{g}^{2}n)$ iterations in expectation, where $ellgeqn$ is a limit on the size of any accepted tree. Additionally, we show that when a polynomial sample of possible inputs is used to evaluate the solution quality, conjunctions or disjunctions with any polynomially small generalisation error can be evolved with probability $1-O(lo{g}^2(n)/n)$. The latter result also holds if GP uses AND, OR and positive and negated literals, thus has the power to express any Boolean function of $n$ distinct variables. To prove our results we introduce a super-multiplicative drift theorem that gives significantly stronger runtime bounds when the expected progress is only slightly super-linear in the distance from the optimum.

Cites work

• Adaptive drift analysis
• Computational complexity analysis of simple genetic programming on two problems modeling isolated program semantics
• Crossover can provably be useful in evolutionary computation
• Fixed-parameter tractability of crossover: steady-state GAs on the closest string problem
• scientific article; zbMATH DE number 795587 (Why is no real title available?)
• Multiplicative drift analysis
• On the analysis of the \((1+1)\) evolutionary algorithm
• On the benefits of populations for the exploitation speed of standard steady-state genetic algorithms
• On the Time and Space Complexity of Genetic Programming for Evolving Boolean Conjunctions
• Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
• The impact of lexicographic parsimony pressure for ORDER/MAJORITY on the run time
• The Max problem revisited: the importance of mutation in genetic programming
• Theoretical analysis of local search strategies to optimize network communication subject to preserving the total number of links
• Theory of evolutionary computation. Recent developments in discrete optimization

Cited in

(1)

• On the Time and Space Complexity of Genetic Programming for Evolving Boolean Conjunctions

This page was built for publication: (1+1) genetic programming with functionally complete instruction sets can evolve Boolean conjunctions and disjunctions with arbitrarily small error

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6161501)