Search Results

Documents authored by Mitavskiy, Boris S.

Document
DOI: 10.4230/DagSemProc.08051.4
Evaluating Stationary Distribution of the Binary GA Markov Chain in Special Cases

Authors: Boris S. Mitavskiy and Chris Cannings

Published in: Dagstuhl Seminar Proceedings, Volume 8051, Theory of Evolutionary Algorithms (2008)

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
Cite as

Boris S. Mitavskiy and Chris Cannings. Evaluating Stationary Distribution of the Binary GA Markov Chain in Special Cases. In Theory of Evolutionary Algorithms. Dagstuhl Seminar Proceedings, Volume 8051, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{mitavskiy_et_al:DagSemProc.08051.4,
  author =	{Mitavskiy, Boris S. and Cannings, Chris},
  title =	{{Evaluating Stationary Distribution of the Binary GA Markov Chain in Special Cases}},
  booktitle =	{Theory of Evolutionary Algorithms},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8051},
  editor =	{Dirk V. Arnold and Anne Auger and Jonathan E. Rowe and Carsten Witt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08051.4},
  URN =		{urn:nbn:de:0030-drops-14845},
  doi =		{10.4230/DagSemProc.08051.4},
  annote =	{Keywords: Genetic algorithms, Markov chains, stationary distribution, lumping quotient}
}
Document
DOI: 10.4230/DagSemProc.06061.5
How fast does the stationary distribution of the Markov chain modelling EAs concentrate on the homogeneous populations for small mutation rate?

Authors: Boris S. Mitavskiy and Jonathan E. Rowe

Published in: Dagstuhl Seminar Proceedings, Volume 6061, Theory of Evolutionary Algorithms (2006)

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.
Cite as

Boris S. Mitavskiy and Jonathan E. Rowe. How fast does the stationary distribution of the Markov chain modelling EAs concentrate on the homogeneous populations for small mutation rate?. In Theory of Evolutionary Algorithms. Dagstuhl Seminar Proceedings, Volume 6061, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@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/entities/document/10.4230/DagSemProc.06061.5},
  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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact