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

Mitavskiy, Boris S. ; Cannings, Chris

Evaluating Stationary Distribution of the Binary GA Markov Chain in Special Cases

pdf-format:
Dokument 1.pdf (305 KB)


Abstract

The evolutionary algorithm stochastic process is well-known to be Markovian. These have been under investigation in much of the theoretical evolutionary computing research. When mutation rate is positive, the Markov chain modeling an evolutionary algorithm is irreducible and, therefore, has a unique stationary distribution, yet, rather little is known about the stationary distribution. On the other hand, knowing the stationary distribution may provide some information about the expected times to hit optimum, assessment of the biases due to recombination and is of importance in population genetics to assess what's called a ``genetic load" (see the introduction for more details). In this talk I will show how the quotient construction method can be exploited to derive rather explicit bounds on the ratios of the stationary distribution values of various subsets of the state space. In fact, some of the bounds obtained in the current work are expressed in terms of the parameters involved in all the three main stages of an evolutionary algorithm: namely selection, recombination and mutation. I will also discuss the newest developments which may allow for further improvements of the bounds

BibTeX - Entry

@InProceedings{mitavskiy_et_al:DSP:2008:1484,
  author =	{Boris S. Mitavskiy and Chris Cannings},
  title =	{Evaluating Stationary Distribution of the Binary GA Markov Chain in Special Cases},
  booktitle =	{Theory of Evolutionary Algorithms},
  year =	{2008},
  editor =	{Dirk V. Arnold and Anne Auger and Jonathan E. Rowe and Carsten Witt},
  number =	{08051},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1484},
  annote =	{Keywords: Genetic algorithms, Markov chains, stationary distribution, lumping quotient}
}

Keywords: Genetic algorithms, Markov chains, stationary distribution, lumping quotient
Seminar: 08051 - Theory of Evolutionary Algorithms
Issue date: 2008
Date of publication: 06.05.2008


DROPS-Home | Fulltext Search | Imprint Published by LZI