Name
Abstract | ||
|---|---|---|
Geiringer's theorem is a statement which tells us something about the limiting frequency of occurrence of a certain individual when a classical genetic algorithm is executed in the absence of selection and mutation. Recently Poll, Stephens, Wright and Rowe extended the original theorem of Geiringer to include the case of variable-length genetic algorithms and linear genetic programming. In the current paper a rather powerful finite population version of Geiringer's theorem which has been established recently by Mitavskiy is used to derive a schema-based version of the theorem for nonlinear genetic programming with homologous crossover. The theorem also applies in the presence of "node mutation". The corresponding formula in case when "node mutation" is present has been established.The limitation of the finite population Geiringer result is that it applies only in the absence of selection. In the current paper we also observe some general inequalities concerning the stationary distribution of the Markov chain associated to an evolutionary algorithm in which selection is the last (output) stage of a cycle. Moreover we prove an "anti-communism" theorem which applies to a wide class of EAs and says that for small enough mutation rate, the stationary distribution of the Markov chain modelling the EA cannot be uniform. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.tcs.2006.04.006 | Theor. Comput. Sci. |
Keywords | Field | DocType |
stationary distribution,original theorem,node mutation,mutation,fitness-proportional selection,geiringer theorem,general eas,crossover,evolutionary algorithms,classical genetic algorithm,current paper,linear genetic programming,nonlinear genetic programming,markov chain,finite population geiringer result,small enough mutation rate,evolutionary algorithm,genetic algorithm,mutation rate | Discrete mathematics,Population,Crossover,Evolutionary algorithm,Markov chain,Genetic programming,Stationary distribution,Linear genetic programming,Genetic algorithm,Mathematics | Journal |
Volume | Issue | ISSN |
361 | 1 | Theoretical Computer Science |
Citations | PageRank | References |
14 | 0.91 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Boris Mitavskiy | 1 | 109 | 11.06 |
| Jonathan Rowe | 2 | 64 | 6.04 |