论文证明 Cartesian 遗传编程在 Max 问题上的指数级加速：期望运行时间 O(log⁹n)

View PDF HTML (experimental)

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 $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.

Comments:	Accepted as a poster at NeurIPS 2026. To appear in the conference proceedings
Subjects:	Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Neural and Evolutionary Computing (cs.NE)
Cite as:	arXiv:2611.16013 [cs.LG]
	(or arXiv:2611.16013v1 [cs.LG] for this version)
	https://doi.org/10.48550/arXiv.2611.16013 arXiv-issued DOI via DataCite (pending registration)

Submission history

From: Roman Kalkreuth [view email]
[v1] Wed, 11 Nov 2026 21:13:49 UTC (241 KB)