The beta version of DROPS 2 is now publicly available! Check this page out at DROPS 2 now!


License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06061.5
URN: urn:nbn:de:0030-drops-5964
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2006/596/
Go to the corresponding Portal

Mitavskiy, Boris S. ; Rowe, Jonathan E.

How fast does the stationary distribution of the Markov chain modelling EAs concentrate on the homogeneous populations for small mutation rate?

pdf-format:
06061.MitavskiyBoris.Paper.596.pdf (0.2 MB)

Abstract

The state space of the Markov chain modelling an evolutionary algorithm
is quite large especially if the population space and the search space are
large. I shell introduce an appropriate notion of "coarse graining" for
such Markov chains. Indeed, from the mathematical point of view, this can
be called a quotient of a Markov chain by an equivalence relation over the
state space. The newly obtained Markov chain has a significantly smaller
state space and it's stationary distribution is "coherent" with the
initial large chain. Although the transition probabilities of the
coarse-grained Markov chain are defined in terms of the stationary
distribution of the original big chain, in some cases it is possible to
deduce interesting information about the stationary distribution of the
original chain in terms of the quatient chain. I will demonstrate how
this method works. I shell also present some simple results and open
questions.

BibTeX - Entry

@InProceedings{mitavskiy_et_al:DagSemProc.06061.5,
  author =	{Mitavskiy, Boris S. and Rowe, Jonathan E.},
  title =	{{How fast does the stationary distribution of the Markov chain modelling EAs concentrate on the homogeneous populations for small mutation rate?}},
  booktitle =	{Theory of Evolutionary Algorithms},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6061},
  editor =	{Dirk V. Arnold and Thomas Jansen and Michael D. Vose and Jonathan E. Rowe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2006/596},
  URN =		{urn:nbn:de:0030-drops-5964},
  doi =		{10.4230/DagSemProc.06061.5},
  annote =	{Keywords: Markov chains, Evolutionary algorithms, coarse graining quotients of irreducible Markov chains, concentration on the uniform populations}
}

Keywords: Markov chains, Evolutionary algorithms, coarse graining quotients of irreducible Markov chains, concentration on the uniform populations
Collection: 06061 - Theory of Evolutionary Algorithms
Issue Date: 2006
Date of publication: 07.07.2006

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI