An Extension of Geiringer's Theorem for a Wide Class of Evolutionary Search Algorithms

Created by W.Langdon from gp-bibliography.bib Revision:1.4420

  title =        "An Extension of Geiringer's Theorem for a Wide Class
                 of Evolutionary Search Algorithms",
  author =       "Boris Mitavskiy and Jonathan Rowe",
  journal =      "Evolutionary Computation",
  year =         "2006",
  volume =       "14",
  number =       "1",
  pages =        "87--118",
  month =        "Spring",
  keywords =     "genetic algorithms, genetic programming, crossover,
                 schemata, Geiringer theorem, Markov process, stationary
                 distribution, random walk on a group, mutation",
  URL =          "",
  DOI =          "doi:10.1162/evco.2006.14.1.87",
  size =         "32 pages",
  abstract =     "he frequency with which various elements of the search
                 space of a given evolutionary algorithm are sampled is
                 affected by the family of recombination (reproduction)
                 operators. The original Geiringer theorem tells us the
                 limiting frequency of occurrence of a given individual
                 under repeated application of crossover alone for the
                 classical genetic algorithm. Recently, Geiringer's
                 theorem has been generalised to include the case of
                 linear GP with homologous crossover (which can also be
                 thought of as a variable length GA). In the current
                 paper we prove a general theorem which tells us that
                 under rather mild conditions on a given evolutionary
                 algorithm, call it A, the stationary distribution of a
                 certain Markov chain of populations in the absence of
                 selection is unique and uniform. This theorem not only
                 implies the already existing versions of Geiringer's
                 theorem, but also provides a recipe of how to obtain
                 similar facts for a rather wide class of evolutionary
                 algorithms. The techniques which are used to prove this
                 theorem involve a classical fact about random walks on
                 a group and may allow us to compute and/or estimate the
                 eigenvalues of the corresponding Markov transition
                 matrix which is directly related to the rate of
                 convergence towards the unique limiting distribution.",

Genetic Programming entries for Boris Mitavskiy Jonathan E Rowe