Runtime Analysis of Cartesian Genetic Programming in Evolving Boolean Functions

2026-06-14 · Source: Artificial Intelligence · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Mathematics & Computational Sciences · Depth: Expert, quick

Summary

A first runtime analysis of Cartesian Genetic Programming (CGP) for evolving Boolean functions using complete training sets establishes key performance bounds. For constructing a conjunction of n inputs with at most D ≥ n-1 binary gates, CGP demonstrates an asymptotic bound of O(n D^5) with strict survival selection. This bound improves to O(n D^4) when non-strict selection is employed, revealing that accepting equally good solutions, even those with non-contributing connected gates, can lead to a speedup. Conversely, the analysis proves that CGP requires exponential time to evolve an exclusive disjunction. Experimental results for conjunctions corroborate these theoretical findings, further indicating that using incomplete training sets can reduce fitness evaluations while maintaining good generalization.

Key takeaway

For research scientists optimizing Cartesian Genetic Programming performance, you should evaluate your CGP selection strategy. Non-strict survival selection can yield significant asymptotic speedups for certain functions like conjunctions, improving the bound from O(n D^5) to O(n D^4). Consider experimenting with incomplete training sets to reduce computational cost while maintaining generalization, especially when evolving conjunctions. Be aware that complex functions like exclusive disjunctions may still require exponential time.

Key insights

Non-strict selection and incomplete training sets can significantly optimize Cartesian Genetic Programming's efficiency for Boolean function evolution.

Principles

• Accepting equally good solutions can speed up CGP search.
• Non-contributing connected gates can be beneficial for CGP evolution.

In practice

• Employ non-strict selection in CGP for potential speedup.
• Consider incomplete training sets to reduce CGP fitness evaluations.

Topics

• Cartesian Genetic Programming
• Boolean Functions
• Runtime Analysis
• Evolutionary Algorithms
• Conjunctions
• Exclusive Disjunction
• Training Sets

Best for: AI Scientist, Research Scientist

Related on AIssential

• Mutation Without Variation: Convergence Dynamics in LLM-Driven Program Evolution — LLM-driven program mutation without selection pressure consistently converges to restricted structural forms, limiting diversity.
• Guiding Multi-Objective Genetic Programming with Description Length Improves Symbolic Regression Solutions — Description Length (DL) and Fractional Bayes Factor (FBF) effectively prevent overfitting and bloat in symbolic regression when used with multi-objective genetic programming.
• On the Generalization in Topology Optimization via Sensitivity-Conditioned Bernoulli Flow Matching — OOD generalization in topology optimization is maximized by conditioning on information-rich adjoint sensitivities or effective pseudo-sensitivities.
• Optimal Complexity in Byzantine-Robust Distributed Stochastic Optimization with Data Heterogeneity — Tight lower bounds for Byzantine-robust distributed stochastic optimization are established and matched by new methods.
• Evolving Features vs Evolving Entire Trees with GP for Interpretable Survival Analysis — Genetic programming can jointly optimize survival tree features and structure for improved interpretability and predictive performance.
• All Mutation Rates $c/n$ for the $(1+1)$ Evolutionary Algorithm — Optimal mutation rates for the $(1+1)$ EA are dense in $[1,\infty)$ when scaled by $1/n$.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Artificial Intelligence.