<p>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.</p>

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

CC BY-SA 3.0
2016-03-30T09:54:44.300Z
2016-03-30T15:31:47.807Z
2016-03-30T15:31:47.807Z
Rahul Savani
<p>You have an endofunction:</p>

<p>genetic :: Population -> Population</p>

<p>What are the idempotents? What are the indexes and periods?</p>

<p>Convergence means that under iteration most Populations hit upon a high fitness Population, i.e. high fitness Populations form a near dominating set over the rest of the population space if you make a graph that has edges f^i -> f.</p>

CC BY-SA 3.0
2016-03-27T18:00:43.887Z
Not sure your answer helps me understand the convergence of GPs. Also I am not convinced it is as easy to explain as you have above.
chutsu
CC BY-SA 3.0
2016-03-28T14:33:05.030Z
I am simply saying how to model the problem. Plugging in the details and verifying that your GP formulation has the property of convergence is up to you :)
Chad Brewbaker
CC BY-SA 3.0
2016-03-28T18:39:31.783Z
That really doesn't answer my question, when I'm specifically asking for a reference.
chutsu
CC BY-SA 3.0
2016-03-28T18:45:21.323Z
GPs don't always converge. Dan's book is a good reference, http://www.springerlink.com/content/978-0-387-22196-0
Chad Brewbaker
CC BY-SA 3.0
2016-03-28T19:13:35.437Z
I'm very much well aware of the property that GP does not guarantee convergence, the same can be said with many non-convex optimization methods such as Stochastic Gradient Descent, that doesn't mean they do not have a convergence theorem. My question merely asks what is the latest for GP. Which part of Dan's book answers my question?
chutsu
CC BY-SA 3.0
2016-03-26T17:20:08.977Z
2016-03-26T17:20:08.977Z
Chad Brewbaker
<p>Ricardo Poli developed a GP-specific analog of Holland's Schema Theorem:
<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.52.6955&amp;rep=rep1&amp;type=pdf" rel="nofollow">link</a></p>

CC BY-SA 3.0
2016-04-17T18:41:16.560Z
2016-04-17T18:41:16.560Z
NietzscheanAI
<p>Genetic Programming (GP) is stochastic algorithm, there has been early attempts to explain its convergence with the Schmea Theorem (Holland 1975) for Genetic <em>Algorithm</em> adapted for GP such as (Koza 1992) (O'Reilly 1994) (Altenberg 1994) (Rosca 1997), but I was wondering if someone could point me to <strong>the</strong> generally agreed theorem that proves GP's covergence? Does it exist?</p>

<hr>

<h3>References:</h3>

<ul>
<li>[Altenberg 1994]: Altenberg, Lee. "Emergent phenomena in genetic programming." Evolutionary Programming—
Proceedings of the Third Annual Conference. World Scientific Publishing, 1994.</li>
<li>[Goldberg 1989]: Goldberg, David. “Genetic Algorithms in Search, Optimization and Machine Learning.” Addison-
Wesley Professional, Reading, MA 1989.</li>
<li>[Koza 1992]: Koza, John R. Genetic programming: on the programming of computers by means of natural selection.</li>
<li>[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.</li>
<li>[Rosca 1997]: Rosca, Justinian P. "Analysis of complexity drift in genetic programming." Genetic Programming
(1997): 286-294.</li>
</ul>

CC BY-SA 3.0
2016-04-04T12:22:09.033Z
Did you see this question? http://cstheory.stackexchange.com/questions/844/provable-statements-about-genetic-algorithms/5049#5049
Lamine
CC BY-SA 3.0
2016-04-04T20:31:33.220Z
That question is more tailored towards Genetic _Algorithms_ this is more towards Genetic _Programming_ the difference is slight, but I feel the difference is significant enough to justify for its own question.
chutsu
<reference-request><genetic-algorithms><genetic-programming>
Convergence theorem for Genetic Programming?
chutsu
# Convergence theorem for Genetic Programming?

(Asked by: username_0 on 2016-03-25)

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.

**Tags:** reference-request, genetic-algorithms, genetic-programming
> **Comments:**
> **username_1**: Did you see this question? http://cstheory.stackexchange.com/questions/844/provable-statements-about-genetic-algorithms/5049#5049  
> **username_0**: That question is more tailored towards Genetic _Algorithms_ this is more towards Genetic _Programming_ the difference is slight, but I feel the difference is significant enough to justify for its own question.  

---

## 3 answers

### Answer by username_2 on 2016-03-30. Score: 3

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.


---

### Answer by username_4 on 2016-04-17. Score: 0

Ricardo Poli developed a GP-specific analog of Holland's Schema Theorem:
[link](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.52.6955&rep=rep1&type=pdf)


---

### Answer by username_3 on 2016-03-26. Score: -3

You have an endofunction:

genetic :: Population -> Population

What are the idempotents? What are the indexes and periods?

Convergence means that under iteration most Populations hit upon a high fitness Population, i.e. high fitness Populations form a near dominating set over the rest of the population space if you make a graph that has edges f^i -> f.

> **Comments:**
> **username_0**: Not sure your answer helps me understand the convergence of GPs. Also I am not convinced it is as easy to explain as you have above.  
> **username_3**: I am simply saying how to model the problem. Plugging in the details and verifying that your GP formulation has the property of convergence is up to you :)  
> **username_0**: That really doesn't answer my question, when I'm specifically asking for a reference.  
> **username_3**: GPs don't always converge. Dan's book is a good reference, http://www.springerlink.com/content/978-0-387-22196-0  
> **username_0**: I'm very much well aware of the property that GP does not guarantee convergence, the same can be said with many non-convex optimization methods such as Stochastic Gradient Descent, that doesn't mean they do not have a convergence theorem. My question merely asks what is the latest for GP. Which part of Dan's book answers my question?  

---

