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.