7
$\begingroup$

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.
$\endgroup$
2
  • $\begingroup$ Did you see this question? cstheory.stackexchange.com/questions/844/… $\endgroup$
    – Lamine
    Apr 4, 2016 at 12:22
  • $\begingroup$ 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. $\endgroup$
    – chutsu
    Apr 4, 2016 at 20:31

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

Ricardo Poli developed a GP-specific analog of Holland's Schema Theorem: link

$\endgroup$
-3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – chutsu
    Mar 27, 2016 at 18:00
  • $\begingroup$ 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 :) $\endgroup$ Mar 28, 2016 at 14:33
  • $\begingroup$ That really doesn't answer my question, when I'm specifically asking for a reference. $\endgroup$
    – chutsu
    Mar 28, 2016 at 18:39
  • $\begingroup$ GPs don't always converge. Dan's book is a good reference, springerlink.com/content/978-0-387-22196-0 $\endgroup$ Mar 28, 2016 at 18:45
  • $\begingroup$ 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? $\endgroup$
    – chutsu
    Mar 28, 2016 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.