License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-5964
URL: http://drops.dagstuhl.de/opus/volltexte/2006/596/

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:
Dokument 1.pdf (219 KB)


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:DSP:2006:596,
  author =	{Boris S. Mitavskiy and Jonathan E. Rowe},
  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},
  year =	{2006},
  editor =	{Dirk V. Arnold and Thomas Jansen and Michael D. Vose and Jonathan E. Rowe},
  number =	{06061},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2006/596},
  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
Seminar: 06061 - Theory of Evolutionary Algorithms
Issue date: 2006
Date of publication: 07.07.2006


DROPS-Home | Fulltext Search | Imprint Published by LZI