Evolving Boolean Functions with Conjunctions and Disjunctions via Genetic Programming
This work provides theoretical runtime guarantees for genetic programming in evolving Boolean functions, which is incremental as it extends prior results on conjunctions to more complex functions.
The paper tackles the problem of evolving Boolean functions with unknown components (conjunctions and disjunctions) using genetic programming, proving that the RLS-GP system can evolve exact conjunctions in O(ℓ n log² n) iterations with a complete truth table and achieve polynomially small generalization error with high probability using polynomial samples.
Recently it has been proved that simple GP systems can efficiently evolve the 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 the GP system for evolving a Boolean function with unknown components, i.e., the function may consist of both conjunctions and disjunctions. We rigorously prove that if the target function is the conjunction of $n$ variables, then the RLS-GP using the complete truth table to evaluate program quality evolves the exact target function in $O(\ell n \log^2 n)$ iterations in expectation, where $\ell \geq n$ is a limit on the size of any accepted tree. When, as in realistic applications, only a polynomial sample of possible inputs is used to evaluate solution quality, we show how RLS-GP can evolve a conjunction with any polynomially small generalisation error with probability $1 - O(\log^2(n)/n)$. To produce 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.