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 n. We prove that the expected time for the (1+1)~CGP employing common mutation operators to evolve an equivalent optimal of the same output is polylogarithmic in n, specifically at most O(log9n). 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
Figure 1: Example of a CGP program that computes the expression o1=(i1+i1)×i2−(i1+i1) . Node 5 is a so-called inactive node because no paths connect it to the output.
Figure 2: The optimal TGP program (right) of Max -depth- {4} - {×,+} - {t} for t∈[1,2) . Gray internal nodes are discarded when converting to an equivalent CGP program (left) by Lemma 2 .
Figure 3: A solution where at least two connection changes are required to increase the output value.
Figure 4: An example solution where j∗=3 .
Figure 5: The case analysis constituting the proof of Lemma 7 for t≥1 . From left to right, the proof is branched into smaller sublemmas based on properties of the current program x0 as described along the branching edges. Lower bounds on the probability of making a significant improvement by a factor of at least (f(x0))1/3 are written next to each sublemma.
Max param.
Setting
GP param.
Setting
Depth D
{1,…,10},{1,…,30}
Maximum iterations
2×106
Input t
1,2
Search & selection strategies
( 1 + 1 ), non-strict
Function set
{×,+} , {\logmult,\logplus}
Number of replications per D
30
Terminal set
{t} , {logt}
Mutation rate of prob. mutation
1/(3D+1)
Table 1: Configuration of GP and Max for the experiments.
Figure 6: Empirical results on Max problems comparing TGP and CGP for small D (left), and testing CGP for larger D (right). Results for too small D are dropped in the right figure to reduce noise when applying linear regression on the log-log scale to deduce the growth orders.
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) for the expected number of fitness evaluations of CGP to construct a conjunction of n inputs using at most D≥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). 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.
Duc-Cuong Dang, Roman Kalkreuth, Andre Opris
University of Passau, Passau, Germany · RWTH Aachen University, Aachen, Germany
Genetic programming (GP) evolves populations of heterogeneous programs, whereas GPUs achieve their highest throughput when groups of threads execute the same instructions. To better align GP evaluation with GPU execution, we present Galop, a hybrid CPU-GPU linear GP system that assigns one individual to each CUDA warp, a group of 32 threads that execute the same instructions across different fitness cases. We compare Galop against EvoGP, a recent high-performance GPU-based tree GP system, on data-rich symbolic regression across two unique GPUs, varying population size and fitness-case count. Galop completes evolutionary runs faster than EvoGP in 27 of the 28 main comparisons, with speedups of up to 13.6 times. Solution quality comparisons favour EvoGP overall, although Galop remains competitive on several problems. Galop also completes a full generation with 2.15 billion individuals on a single H100 GPU, approximately 4.0 times the largest population achieved by any other tested GP system. All five runs at this population complete 100 generations, with a median wall-clock time of 2.23 hours. These results make it practical to study GP populations in the billions on a single GPU. Galop's source code, experimental data, and reproducibility scripts are publicly available at https://github.com/xavierhillroy/Galop.
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
Chair for AI Methodology, RWTH Aachen University Aachen, Germany