Research map / Learning theory and algorithms / Combinatorial and search optimization
(1+1) Genetic Programming with Functionally Complete Instruction Sets Can Evolve Boolean Conjunctions and Disjunctions with Arbitrarily Small Error
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Theoretical and experimental analysis of a (1+1)-style RLS-GP with AND/OR function set, subtree deletion and tree-size limit, proving polynomial runtime for evolving conjunctions/disjunctions with complete truth table and generalisation guarantees with polynomial training samples, plus a super-multiplicative drift theorem.
Problem
Runtime analysis of simple genetic programming on evolving Boolean conjunctions and disjunctions of n variables when the function set is complete (AND, OR) and terminals may include negated literals, with bloat control and sampled fitness.
Approach
Extends RLS-GP with a tree-size limit and an HVL-Prime variant allowing whole-subtree deletion (which avoids infinite expected runtime from leaf-only deletion), proves O(ℓ n log^2 n) runtime with the complete truth table, and shows polynomially small generalisation error with polynomial samples via a new super-multiplicative drift theorem.
Key results
- With subtree deletion and a tree-size limit, RLS-GP reaches the exact conjunction in O(ℓ n log^2 n) expected iterations under the complete truth table, with theory and experiments showing no getting stuck.
- Leaf-only deletion gets stuck on local optima with probability up to about 1.6% at n=12 with ℓ=n, and 0% for ℓ=2n and unlimited size.
- With negated literals and the complete truth table, the algorithm fails to find the optimum within 10,000 iterations for n≥8 in nearly all runs (B≈0.98–1.0), supporting the conjecture.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace leaf-only deletion with subtree deletion (ablation) | RLS-GP on AND16 with complete truth table and ℓ=n · AND16, complete truth table | iterations: 469.9 -> 544.6 | Mixed |
| replace leaf-only deletion with subtree deletion (ablation) | RLS-GP on AND16 with complete truth table and ℓ=n+1 · AND16, complete truth table | stuck-run proportion: 0.010 -> no stuck runs reported | Hurt |
| increase tree-size limit from ℓ=n to ℓ=∞ (ablation) | RLS-GP with subtree deletion on AND16 · AND16, complete truth table | iterations: 544.6 -> 221.0 | Helped |
| increase tree-size limit from ℓ=n to ℓ=∞ (ablation) | RLS-GP with subtree deletion on AND16 · AND16, complete truth table | solution size: 16.0 -> 25.2 | Hurt |
| add negated literals to the terminal set (ablation) | RLS-GP with subtree deletion on AND16 · AND16, complete truth table | stuck-run proportion: 1.000 | Hurt |
| stop at sampled error 0 rather than stopping at a positive threshold (ablation) | RLS-GP with subtree deletion and incomplete training data · AND, n=50 | iterations | Hurt |
| stop at sampled error 0 rather than stopping at a positive threshold (ablation) | RLS-GP with subtree deletion and negated literals · AND, n=50 | iterations | Hurt |
| add negated literals to the terminal set (ablation) | RLS-GP with subtree deletion and incomplete training data · AND, n=50 | iterations: 50 iterations | Helped |
Surprising findings
- Adding negated literals makes RLS-GP with the complete truth table almost always converge to a contradiction (local optimum) for n≥8, rather than the target conjunction.
- Leaf-only HVL-Prime can get permanently stuck with non-zero probability under a tree-size limit, giving infinite expected runtime.
Limitations
- Complete truth table evaluation requires exponential time in n, so the exact-solution result is only practical for modest n.
- Conjecture on negated literals with AND and OR remains unproven; formal analysis left open.
- Tree-size limit is necessary in the analysis; removing it is left as future work.
Experimental setup
Benchmarks: AND_n OR_n
Metrics: expected runtime (iterations) proportion stuck in local optimum solution size generalisation error
Baselines: HVL-Prime with leaf-only deletion RLS-GP with leaf-only deletion
Builds on: RLS-GP HVL-Prime multiplicative drift theorem dynamic subset selection
Closest papers by meaning
- Eco Search: A No-delay Best-First Search Algorithm for Program Synthesis (AAAI 2025 · similarity 0.83)
- Simple Baselines are Competitive with Code Evolution (NeurIPS 2026 · similarity 0.83)
- Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces (AAAI 2025 · similarity 0.83)
- Search Strategy Generation for Branch and Bound Using Genetic Programming (AAAI 2025 · similarity 0.83)
- Finding Simple Proofs for First-Order Optimization (NeurIPS 2026 · similarity 0.82)
- FunctionEvolve: Structure-Guided Symbolic Regression with LLMs (NeurIPS 2026 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.