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

Andrei Lissovoi, Pietro S. OlivetoAAAI 2018 · DOI

Introduction

Genetic Programming (GP) has demonstrated significant practical success in evolving computer programs through bio-inspired mechanisms. However, a rigorous theoretical foundation for its performance remains underdeveloped. Most existing GP theory focuses on the structural evolution of program trees rather than their functional convergence. This research addresses this gap by analyzing the time and space complexity of GP when evolving Boolean conjunctions (e.g., $x_1 \wedge x_2 \wedge \dots \wedge x_n$). The study investigates the efficiency of finding perfect solutions, the generalization capabilities when trained on sparse data, and the robustness of GP in the presence of noise or extended operator sets.

Methods and Algorithmic Framework

The authors analyze four primary variants of simple GP algorithms, focusing on Random Local Search (RLS-GP) and (1+1) GP. RLS-GP performs local modifications (addition, deletion, or substitution of a single node), while (1+1) GP allows for more global search by performing a variable number of modifications per step, typically sampled from a Poisson distribution.

Algorithmic framework for the GP variants analyzed, including RLS-GP and (1+1) GP.

A critical component of the analysis is the selection mechanism. The researchers compare "non-strict" selection, which accepts new programs that are at least as good as the current one, against "strict" selection, which requires a strict improvement. The analysis utilizes Drift Analysis to bound the expected time to reach a target state and space complexity analysis to monitor tree size.

The training environments range from complete truth tables ($2^n$ rows) to static polynomial-sized subsets, dynamic training sets (resampled every iteration), and minimal training sets of only $n$ or $n+1$ rows.

Key Theoretical Insights

The Role of Neutrality

A significant finding is the importance of "neutrality" in the search process. In environments with irrelevant variables (the $AND_{n,m}$ problem), non-strict selection allows the algorithm to accept mutations that do not immediately improve fitness. This flexibility enables the GP to navigate the search space and prune redundant variables. Conversely, strict selection often leads to "bloat," where the algorithm becomes trapped with sub-optimal, oversized programs.

Natural Bloat Control and Generalization

While bloat is a common challenge in GP, this study shows that training on small datasets naturally encourages the evolution of smaller trees. The algorithms tend to produce trees of size $O(\log n)$, which is optimal for generalization. Furthermore, while adding negations (NOT gates) can create "trap points" that make reaching a perfect solution harder on the full training set, the resulting "trapped" solutions still exhibit high generalization performance.

Results

The theoretical analysis yields several key performance bounds:

  • Runtime Efficiency: For the standard $AND_n$ problem, both RLS-GP and (1+1) GP achieve the exact solution in $\Theta(n \log n)$ iterations.
  • Generalization: With polynomial-sized training sets, GP constructs solutions with a generalization error of at most $n^{-c}$ within $O(\log n)$ iterations.
  • Selection Impact: In the $AND_{n,m}$ setting, non-strict RLS-GP succeeds in $O(n \log n)$, whereas strict selection fails with high probability.
Expected error of RLS-GP variants over training iterations.

The study also proves that a carefully selected training set of only $n+1$ rows is sufficient to evolve a program with 100% accuracy across all $2^n$ possible inputs, even when negations are permitted.

Conclusion and Future Work

This work provides a "mathematical laboratory" for understanding GP through the lens of Boolean conjunctions. While these structures are simpler than real-world programs, the insights into neutrality, bloat control, and selection mechanisms are foundational. Future research directions include extending these analyses to more complex functions, investigating population-based GP with crossover, and exploring non-uniform data distributions where trap dynamics may differ.

Summary updated

BibTeX
@inproceedings{lissovoi2018time,
  author = {Andrei Lissovoi and Pietro S. Oliveto},
  title = {{On the Time and Space Complexity of Genetic Programming for Evolving Boolean Conjunctions}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.11517},
}
Figure