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

DOI10.1016/j.artint.2023.103906arXiv2303.07455MaRDI QIDQ6161501

Andrei Lissovoi, Pietro S. Oliveto, Benjamin Doerr

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)

Cites Work

• Unnamed Item
• Crossover can provably be useful in evolutionary computation
• Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
• On the analysis of the \((1+1)\) evolutionary algorithm
• Adaptive drift analysis
• Multiplicative drift analysis
• On the benefits of populations for the exploitation speed of standard steady-state genetic algorithms
• The Max problem revisited: the importance of mutation in genetic programming
• The impact of lexicographic parsimony pressure for ORDER/MAJORITY on the run time
• Analyzing randomized search heuristics via stochastic domination
• Fixed-parameter tractability of crossover: steady-state GAs on the closest string problem
• Theoretical analysis of local search strategies to optimize network communication subject to preserving the total number of links
• On the Time and Space Complexity of Genetic Programming for Evolving Boolean Conjunctions
• Theory of Evolutionary Computation
• Computational complexity analysis of simple genetic programming on two problems modeling isolated program semantics

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