Convergence theorem for Genetic Programming? Genetic Programming (GP) is stochastic algorithm, there has been early attempts to explain its convergence with the Schmea Theorem (Holland 1975) for Genetic Algorithm adapted for GP such as (Koza 1992) (O'Reilly 1994) (Altenberg 1994) (Rosca 1997), but I was wondering if someone could point me to the generally agreed theorem that proves GP's covergence? Does it exist?



References:


[Altenberg 1994]: Altenberg, Lee. "Emergent phenomena in genetic programming." Evolutionary Programming—
Proceedings of the Third Annual Conference. World Scientific Publishing, 1994.
[Goldberg 1989]: Goldberg, David. “Genetic Algorithms in Search, Optimization and Machine Learning.” Addison-
Wesley Professional, Reading, MA 1989.
[Koza 1992]: Koza, John R. Genetic programming: on the programming of computers by means of natural selection.
[O'reilly 1994]: O'Reilly, Una-May, and Franz Oppacher. Using Building Block Functions to Investigate a Building Block Hypothesis for Genetic. No. 94-04-020. 1994.
Vol. 1. MIT press, 1992.
[Rosca 1997]: Rosca, Justinian P. "Analysis of complexity drift in genetic programming." Genetic Programming
(1997): 286-294.
I am not sure that there is one Theorem to point to. Anyhow, you will probably be interested in the following reference, which summarizes many more recent results than those you mention in the question, e.g., for the (1+1)-EA with linear functions, quadratic functions, and monotone polynomials as objective functions (I know these are probably much simpler functions than you care about). Anyway the citations within should give you good pointers, via Google Scholar, to even newer results.

Stefan Droste, Thomas Jansen, Günter Rudolph, Hans-Paul Schwefel, Karsten Tinnefeld, and Ingo Wegener (2002): Theory of evolutionary algorithms and genetic programming.  In H.-P. Schwefel, I. Wegener, and K. Weinert (Eds.): Advances in Computational Intelligence Theory and Practice. Springer, Berlin, Germany, pages 107-144.