cs.LGNov 11, 2026

Runtime Analysis of Cartesian Genetic Programming on Max: A Proven Exponential Speedup

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

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

Abstract

Genetic Programming (GP) is a search paradigm inspired from natural evolution for the automated discovery of expressions, functions, and computer programs. Cartesian GP (CGP) is a flavor of GP that uses a graph-based model to encode candidate programs, as contrasted to the conventional Tree-based GP (TGP). Since its inception two decades ago, CGP has predominantly been analyzed empirically, thus little is known regarding its theoretical performance guarantees. This paper analyzes CGP for the Max problem, which has been only rigorously studied for TGP with a proven expected runtime superlinear in the optimal program length nn. We prove that the expected time for the (11+11)~CGP employing common mutation operators to evolve an equivalent optimal of the same output is polylogarithmic in nn, specifically at most O(log⁡9n)O(\log^9{n}). This is remarkable, as it shows an exponential speedup by switching to CGP. Our results shed light on the benefit and the compactness of the graph-based representation for programs, and on how CGP can navigate its search and fitness spaces efficiently. This is a first proven performance guarantee for CGP on an established benchmark problem. Experiments complement our theoretical findings.

Figures & tables

Explore similar work

CardsList
  1. Runtime Analysis of Cartesian Genetic Programming in Evolving Boolean Functions

    Jun 14, 2026Duc-Cuong Dang, Roman Kalkreuth, Andre OprisBoolean Function LearningGenetic Programming

  2. Galop: Billion-Scale Genetic Programming on a Single GPU

    Nov 10, 2026Xavier Hill Roy, Stephen KellyGenetic ProgrammingGPU Acceleration

  3. Improving Evaluation of Recombination-based Cartesian Genetic Programming

    May 27, 2026Duy Long Tran, Anja Jankovic, Marie Anastacio +2Genetic Programming