- 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 = "72--110",
- month = "28 " # aug,
- keywords = "genetic algorithms, genetic programming, Evolutionary algorithms, Markov chain, Geiringer theorem, Stationary distribution, Mutation, Crossover, Fitness-proportional 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
variable-length 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 schema-based 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 'anti-communism' 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",
