Name
Abstract | ||
|---|---|---|
The evolutionary algorithm stochastic process is well-known to be Markovian. These have been under investigation in much of the theoretical evo- lutionary computing research. When mutation rate is positive, the Markov chain modeling an evolutionary algorithm is irreducible and, therefore, has a unique stationary distribution. Rather little is known about the stationary distribution. In fact, the only quantitative facts established so far, tell us that the stationary distributions of Markov chains modeling evolutionary algorithms concentrate on the uniform populations (i.e. these populations consisting of the repeated copy of the same individual). At the same time, knowing the stationary distribution may provide some information about the expected time it takes for the algorithm to reach a certain solution, assessment of the biases due to recombination and selec- tion and is of importance in population genetics to assess what's called a "genetic load" (see the introduction for more details). In the recent joint works of the first author, some bounds have been established on the rates at which the stationary distribution concentrates on the uniform populations. The primary tool used in these papers is the "quotient construction" method. It turns out that the "quo- tient construction" method can be significantly strengthen to yield much more informative results. In the current paper we present a couple of examples where we compute the stationary distribution of a GA Markov chain using the quotient construction method. Furthermore, we show another important asymptotic result which we hope will be of technical importance in the future applications. |
Year | Venue | Field |
|---|---|---|
2008 | Theory of Evolutionary Algorithms | Applied mathematics,Mathematical optimization,Markov process,Evolutionary algorithm,Coupling from the past,Markov chain,Evolutionary computation,Stochastic process,Stationary distribution,Stationary sequence,Mathematics |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
20 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Boris Mitavskiy | 1 | 109 | 11.06 |
| Chris Cannings | 2 | 37 | 4.96 |