Name
Title | ||
|---|---|---|
An extension of Geiringer's theorem for a wide class of evolutionary search algorithms. |
Abstract | ||
|---|---|---|
The frequency with which various elements of the search space of a given evolutionary algorithm are sampled is affected by the family of recombination (reproduction) operators. The original Geiringer theorem tells us the limiting frequency of occurrence of a given individual under repeated application of crossover alone for the classical genetic algorithm. Recently, Geiringer's theorem has been generalized to include the case of linear GP with homologous crossover (which can also be thought of as a variable length GA). In the current paper we prove a general theorem which tells us that under rather mild conditions on a given evolutionary algorithm, call it A, the stationary distribution of a certain Markov chain of populations in the absence of selection is unique and uniform. This theorem not only implies the already existing versions of Geiringer's theorem, but also provides a recipe of how to obtain similar facts for a rather wide class of evolutionary algorithms. The techniques which are used to prove this theorem involve a classical fact about random walks on a group and may allow us to compute and/or estimate the eigenvalues of the corresponding Markov transition matrix which is directly related to the rate of convergence towards the unique limiting distribution. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1162/evco.2006.14.1.87 | Evolutionary Computation |
Keywords | Field | DocType |
schemata,crossover,mutation,evolutionary algorithm,markov process,classical fact,station- ary distribution,wide class,certain markov chain,classical genetic algorithm,evolutionary search algorithms,random walk on a group,genetic algorithms,geiringer theorem,linear gp,evolutionary search algorithm,stationary distribution,original geiringer theorem,general theorem,corresponding markov transition matrix,current paper,rate of convergence,genetic algorithm,search algorithm,markov chain,transition matrix,search space | Search algorithm,Evolutionary algorithm,Random walk,Artificial intelligence,Genetic algorithm,Eigenvalues and eigenvectors,Discrete mathematics,Mathematical optimization,Combinatorics,Crossover,Stochastic matrix,Markov chain,Mathematics,Machine learning | Journal |
Volume | Issue | ISSN |
14 | 1 | 1063-6560 |
Citations | PageRank | References |
14 | 0.91 | 11 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Boris Mitavskiy | 1 | 109 | 11.06 |
| Jonathan Rowe | 2 | 64 | 6.04 |