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

Doerr，Benjamin1; Lissovoi，Andrei2; Oliveto，Pietro S.3

2023-06-01

10.1016/j.artint.2023.103906

Artificial Intelligence   Impact Factor & Quartile

0004-3702

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(ℓnlog⁡n) iterations in expectation, where ℓ≥n 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(log⁡(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.

Computational complexity Genetic programming Theory

English

Corresponding

Engineering and Physical Sciences Research Council[EP/M004252/1];

COMPUTER SCIENCE

2-s2.0-85151482216

Scopus

1.Laboratoire d'Informatique (LIX),École Polytechnique,Institut Polytechnique de Paris,Palaiseau,France
2.Department of Computer Science,University of Sheffield,United Kingdom
3.Department of Computer Science and Engineering,Southern University of Science and Technology,Shenzhen,China

Doerr，Benjamin,Lissovoi，Andrei,Oliveto，Pietro S.. (1+1) genetic programming with functionally complete instruction sets can evolve Boolean conjunctions and disjunctions with arbitrarily small error[J]. Artificial Intelligence,2023,319.

Doerr，Benjamin,Lissovoi，Andrei,&Oliveto，Pietro S..(2023).(1+1) genetic programming with functionally complete instruction sets can evolve Boolean conjunctions and disjunctions with arbitrarily small error.Artificial Intelligence,319.

Doerr，Benjamin,et al."(1+1) genetic programming with functionally complete instruction sets can evolve Boolean conjunctions and disjunctions with arbitrarily small error".Artificial Intelligence 319(2023).