Some Results about the Markov Chains Associated to GPs and to General EAs
Created by W.Langdon from
gpbibliography.bib Revision:1.7630
 @Article{Mitavskiy:2006:TCS,

author = "Boris Mitavskiy and Jon Rowe",

title = "Some Results about the Markov Chains Associated to GPs
and to General EAs",

journal = "Theoretical Computer Science",

year = "2006",

volume = "361",

number = "1",

pages = "72110",

month = "28 " # aug,

keywords = "genetic algorithms, genetic programming, Evolutionary
algorithms, Markov chain, Geiringer theorem, Stationary
distribution, Mutation, Crossover, Fitnessproportional
selection",

DOI = "doi:10.1016/j.tcs.2006.04.006",

abstract = "Geiringer's theorem is a statement which tells us
something about the limiting frequency of occurrence of
a certain individual when a classical genetic algorithm
is executed in the absence of selection and mutation.
Recently Poli, Stephens, Wright and Rowe extended the
original theorem of Geiringer to include the case of
variablelength genetic algorithms and linear genetic
programming. In the current paper a rather powerful
finite population version of Geiringer's theorem which
has been established recently by previous Mitavskiy is
used to derive a schemabased version of the theorem
for nonlinear genetic programming with homologous
crossover. The theorem also applies in the presence of
'node mutation'. The corresponding formula in case when
'node mutation' is present has been established.
The limitation of the finite population Geiringer
result is that it applies only in the absence of
selection. In the current paper we also observe some
general inequalities concerning the stationary
distribution of the Markov chain associated to an
evolutionary algorithm in which selection is the last
(output) stage of a cycle. Moreover we prove an
'anticommunism' theorem which applies to a wide class
of EAs and says that for small enough mutation rate,
the stationary distribution of the Markov chain
modelling the EA cannot be uniform.",

notes = "Foundations of Genetic Algorithms",
 }
Genetic Programming entries for
Boris Mitavskiy
Jonathan E Rowe
Citations