In this work, a method is presented for analysis of
Markov chains modelling evolutionary algorithms through
use of a suitable quotient construction. Such a notion
of quotient of a Markov chain is frequently referred to
as ``coarse graining'' in the evolutionary computation
literature. We shall discuss the construction of a
quotient of an irreducible Markov chain with respect to
an arbitrary equivalence relation on the state space.
The stationary distribution of the quotient chain is
``coherent'' with the stationary distribution of the
original chain. Although the transition probabilities
of the quotient chain depend on the stationary
distribution of the original chain, we can still
exploit the quotient construction to deduce some
relevant properties of the stationary distribution of
the original chain. As one application, we shall
establish inequalities that describe how fast the
stationary distribution of Markov chains modeling
evolutionary algorithms concentrates on the uniform
populations as the mutation rate converges to 0.
Further applications are discussed. One of the results
related to the quotient construction method is a
significant improvement of the corresponding result of
the authors' previous conference paper Mitavskiy et
al. (2006) In: Simulated Evolution and Learning,
Proceedings of SEAL 2006, Lecture Notes in Computer
Science v. 4247, Springer Verlag, pp 726-733. This
papers implications are all strengthened accordingly.
%0 Journal Article
%1 Mitavskiy:2008:GPEM
%A Mitavskiy, Boris
%A Rowe, Jonathan E.
%A Wright, Alden
%A Schmitt, Lothar M.
%D 2008
%J Genetic Programming and Evolvable Machines
%K Asymptotics, Coarse Evolutionary Markov Mutation Quotient, Selection Stationary Uniform algorithm, algorithms, chain, distribution, genetic graining, population, pressure rate,
%N 2
%P 109--123
%R doi:10.1007/s10710-007-9038-6
%T Quotients of Markov chains and asymptotic properties
of the stationary distribution of the Markov chain
associated to an evolutionary algorithm
%V 9
%X In this work, a method is presented for analysis of
Markov chains modelling evolutionary algorithms through
use of a suitable quotient construction. Such a notion
of quotient of a Markov chain is frequently referred to
as ``coarse graining'' in the evolutionary computation
literature. We shall discuss the construction of a
quotient of an irreducible Markov chain with respect to
an arbitrary equivalence relation on the state space.
The stationary distribution of the quotient chain is
``coherent'' with the stationary distribution of the
original chain. Although the transition probabilities
of the quotient chain depend on the stationary
distribution of the original chain, we can still
exploit the quotient construction to deduce some
relevant properties of the stationary distribution of
the original chain. As one application, we shall
establish inequalities that describe how fast the
stationary distribution of Markov chains modeling
evolutionary algorithms concentrates on the uniform
populations as the mutation rate converges to 0.
Further applications are discussed. One of the results
related to the quotient construction method is a
significant improvement of the corresponding result of
the authors' previous conference paper Mitavskiy et
al. (2006) In: Simulated Evolution and Learning,
Proceedings of SEAL 2006, Lecture Notes in Computer
Science v. 4247, Springer Verlag, pp 726-733. This
papers implications are all strengthened accordingly.
@article{Mitavskiy:2008:GPEM,
abstract = {In this work, a method is presented for analysis of
Markov chains modelling evolutionary algorithms through
use of a suitable quotient construction. Such a notion
of quotient of a Markov chain is frequently referred to
as ``coarse graining'' in the evolutionary computation
literature. We shall discuss the construction of a
quotient of an irreducible Markov chain with respect to
an arbitrary equivalence relation on the state space.
The stationary distribution of the quotient chain is
``coherent'' with the stationary distribution of the
original chain. Although the transition probabilities
of the quotient chain depend on the stationary
distribution of the original chain, we can still
exploit the quotient construction to deduce some
relevant properties of the stationary distribution of
the original chain. As one application, we shall
establish inequalities that describe how fast the
stationary distribution of Markov chains modeling
evolutionary algorithms concentrates on the uniform
populations as the mutation rate converges to 0.
Further applications are discussed. One of the results
related to the quotient construction method is a
significant improvement of the corresponding result of
the authors' previous conference paper [Mitavskiy et
al. (2006) In: Simulated Evolution and Learning,
Proceedings of SEAL 2006, Lecture Notes in Computer
Science v. 4247, Springer Verlag, pp 726-733]. This
papers implications are all strengthened accordingly.},
added-at = {2008-06-19T17:35:00.000+0200},
author = {Mitavskiy, Boris and Rowe, Jonathan E. and Wright, Alden and Schmitt, Lothar M.},
biburl = {https://www.bibsonomy.org/bibtex/2383df2600991d269f01f84b349a4cdd7/brazovayeye},
doi = {doi:10.1007/s10710-007-9038-6},
interhash = {857688e5ebfc4ab733b1348944a77267},
intrahash = {383df2600991d269f01f84b349a4cdd7},
issn = {1389-2576},
journal = {Genetic Programming and Evolvable Machines},
keywords = {Asymptotics, Coarse Evolutionary Markov Mutation Quotient, Selection Stationary Uniform algorithm, algorithms, chain, distribution, genetic graining, population, pressure rate,},
month = {June},
note = {Special Issue on Theoretical foundations of
evolutionary computation},
number = 2,
pages = {109--123},
size = {25 pages},
timestamp = {2008-06-19T17:47:24.000+0200},
title = {Quotients of Markov chains and asymptotic properties
of the stationary distribution of the Markov chain
associated to an evolutionary algorithm},
volume = 9,
year = 2008
}