cs.NEJun 14, 2026

Runtime Analysis of Cartesian Genetic Programming in Evolving Boolean Functions

Authors: Duc-Cuong Dang, Roman Kalkreuth, Andre Opris

Organizations: University of Passau, Passau, Germany · RWTH Aachen University, Aachen, Germany

Abstract

Cartesian Genetic Programming (CGP) is among the practical and popular forms of Genetic Programming as it uses a graph-based representation of programs. This paper presents a first runtime analysis of CGP in evolving Boolean functions using complete training sets. We prove an asymptotic bound O(nD5)O(n D^5) for the expected number of fitness evaluations of CGP to construct a conjunction of nn inputs using at most D≥n−1D \geq n-1 binary gates, a minimal function set, and even with a strict survival selection. When the non-strict selection is used, the bound is improved to O(nD4)O(n D^4). Our analysis reveals interesting characteristics of CGP induced search, which have been only observed empirically. In particular, enabling the acceptance of equally good solutions, including those with connected gates non-contributing to fitness, can lead to a speedup, and consequently a better asymptotic time bound. In contrast to conjunctions, we also prove a negative result which shows that CGP requires exponential time to evolve an exclusive disjunction. Experiments evolving conjunctions complement our theoretical findings. The use of incomplete training sets is found to further reduce the average number of fitness evaluations while maintaining a good level of generalisation.

Explore similar work

CardsList
May 27, 2026cs.NE

Improving Evaluation of Recombination-based Cartesian Genetic Programming

Cartesian Genetic Programming has traditionally been using mutation as its main and often sole genetic operator to drive evolutionary search. Despite advancements in recent years, recombinationbased approaches have long been avoided, due to apparent lack of performance gains. This study examines two recently suggested recombination-based operators, subgraph crossover and discrete phenotypic recombination on SRBench, a benchmarking platform for symbolic regression. Using the implementations provided in the TinyverseGP framework, we perform hyperparameter optimisation of the respective representations with these two operators. Our work demonstrates that hyperparameter optimisation can lead to improvements in performance for recombination-based Cartesian Genetic Programming.
Duy Long Tran, Anja Jankovic, Marie Anastacio +2
Genetic AlgorithmsSymbolic RegressionHyperparameter Optimization
AskPDF
May 28, 2026cs.NE

Runtime Analysis of a Compact Genetic Algorithm on a Truly Multi-valued OneMax Function

Recently, the runtime analysis of multi-valued estimation-of-distribution algorithms in the framework of Ben Jedidia et al. (TCS 2024) has made significant advancements. However, almost all existing analyses are limited to multi-valued objective functions that in each dimension only distinguish between two types, also called categories, of values and hence can be treated with similar methods as pseudo-Boolean problems. Only recently, Adak and Witt (GECCO 2025) have presented a first runtime analysis of a multi-valued compact genetic algorithm (cGA) on the multi-valued OneMax function G-OneMax ⁣:{0,…,r−1}n→N\colon \{0,\dots,r-1\}^n \to \mathbf{N} defined by G-OneMax(x1,…,xn)=∑i=1nxi(x_1,\dots,x_n)=\sum_{i=1}^n {x}_i and truly depending on all rr categories. We improve their runtime result from O(nr3log⁡2(n)log⁡(r))\textrm{O}\bigl(n r^3 \log^2( n)\log (r)\bigr) to O(nrlog⁡3(n)log⁡3(r))\textrm{O}\bigl(n r \log^3(n)\log^3(r)\bigr), both for an optimal choice of the update strength KK. Our result matches, up to polylogarithmic factors, the existing bound for the simpler rr-valued OneMax function depending essentially only on two values and analyzed in several previous works. To show the new bound, we use improved drift theorems for processes with high self-loop probabilities and specifically derived concentration inequalities to analyze how probability mass in the multi-valued cGA moves into successively smaller and smaller intervals of the rr-valued frequency matrix.
Martin S. Krejca, Carsten Witt
Genetic AlgorithmsMaximization
AskPDF
Jul 15, 2026cs.NE

Asymptotical Analysis of the (1+(λ,λ)) GA Escape Time from Local Optima on Jump Functions

The paper develops the approach to the runtime analysis of evolutionary algorithms on the basis of limit theorems from probability theory. We consider the family of Jumpk_k benchmark functions, defined on the search space of binary strings of length nn, parametrized by the integer kk, which have a plateau of multiple local optima at the Hamming distance kk from a unique global optimum. In this work, we consider the genetic algorithm (1+(λ,λ))GA(1+(λ,λ)) GA from (Doerr, Doerr and Ebel, 2015) with tunable parameters of the mutation rate pp, crossover bias cc, and two intermediate population sizes λMλ_M and λCλ_C. We study the time it escapes from the plateau of local optima and reaches the global optimum in the case of Jumpk_k fitness function and tighten the upper bounds on the expected escape time, known from the work of Antipov, Doerr and Karavaev (2022). The obtained bounds also apply to a wider range of algorithmic parameters. The main result of this work applies to the case when k→∞k\to \infty as n→∞.n \to \infty. The case of finite kk is investigated quite simply and considered tangentially.
Anton V. Eremeev, Valentin A. Topchii
Genetic AlgorithmsEscapeAsymptoticsCentral Limit Theorem
AskPDF