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(\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.
This paper investigates the role of dynamic population sizes in evolutionary multi-objective optimization. Although such approaches are widely used in practice, their benefits remain poorly understood, and rigorous runtime analyses explaining when and why they help are still scarce. To address this, we introduce the bi-objective problem class $\text{CLIMB}$, where the parameter $\ell$ determines the size of the Pareto front. On this problem class, we analyze the runtime of GSEMO and the widely used NSGA-II. Our results show that allowing a dynamic population size for NSGA-II can lead to a moderate improvement, yielding a super-constant speedup for $\ell \in ω(\log(n)) \cap o(\sqrt{n \log(n)})$ in terms of fitness evaluations. In particular, we prove that GSEMO and NSGA-II-DYN, a version of NSGA-II with dynamic population sizes that we propose in this paper, can cover the Pareto front of $\text{CLIMB}$ in expected $O(n \log(n) + \ell^2 \log(en/(n-2\ell+3)))$ evaluations, and that this bound is tight for $\ell = O(\sqrt{n \log(n)})$. In contrast, NSGA-II with a fixed population size of at least $4\ell$ requires expected $O(n\ell + n\log(n) + \ell^2 \log(en/(n-2\ell+3)))$ evaluations to cover the entire Pareto front of $\text{CLIMB}$, while still requiring expected $Ω(\ell n)$ evaluations to even find a Pareto-optimal search point. To the best of our knowledge, this is the first rigorous runtime analysis in bi-objective optimization that demonstrates a super-constant speedup of GSEMO over NSGA-II. Our analysis builds on concepts from single-objective optimization, such as the evolution of population diversity over time, and employs the well-known family-tree method to prove the lower bound.