Show simple item record

dc.contributor.authorSchmitt, L.M.
dc.contributor.authorNehaniv, C.L.
dc.contributor.authorFujii, R.H.
dc.identifier.citationSchmitt , L M , Nehaniv , C L & Fujii , R H 1998 , ' Linear analysis of genetic algorithms ' , Theoretical Computer Science , vol. 200 , no. 1-2 , pp. 101-134 .
dc.identifier.otherPURE: 100983
dc.identifier.otherPURE UUID: ad5f7bbe-5097-49ad-a5a7-bd93c872e669
dc.identifier.otherdspace: 2299/3171
dc.identifier.otherScopus: 0001521166
dc.descriptionOriginal article can be found at: Copyright Elsevier B.V. DOI: 10.1016/S0304-3975(98)00004-8 [Full text of this article is not available in the UHRA]
dc.description.abstractWe represent simple and fitness-scaled genetic algorithms by Markov chains on probability distributions over the set of all possible populations of a fixed finite size. Analysis of this formulation yields new insight into the geometric properties of the three phase mutation, crossover, and fitness selection of a genetic algorithm by representing them as stochastic matrices acting on the state space. This indicates new methods using mutation and crossover as the proposal scheme for simulated annealing. We show by explicit estimates that for small mutation rates a genetic algorithm asymptotically spends most of its time in uniform populations regardless of crossover rate. The simple genetic algorithm converges in the following sense: there exists a fully positive limit probability distribution over populations. This distribution is independent of the choice of initial population. We establish strong ergodicity of the underlying inhomogeneous Markov chain for genetic algorithms that use any of a large class of fitness scaling methods including linear fitness scaling, sigma-truncation, and power law scaling. Our analysis even allows for variation in mutation and crossover rates according to a pre-determined schedule, where the mutation rate stays bounded away from zero. We show that the limit probability distribution of such a process is fully positive at all populations of uniform fitness. Consequently, genetic algorithms that use the above fitness scalings do not converge to a population containing only optimal members. This answers a question of G. Rudolph (IEEE Trans. on Neural Networks 5 (1994) 96–101).en
dc.relation.ispartofTheoretical Computer Science
dc.titleLinear analysis of genetic algorithmsen
dc.contributor.institutionSchool of Computer Science
dc.description.statusPeer reviewed
dc.relation.schoolSchool of Computer Science
rioxxterms.typeJournal Article/Review

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record