The paper describes two different analyses of genetic algorithm convergence. The first examines the role of crossover in genetic algorithms. Some results from the field of population genetics are shown to have relevance for genetic algorithms and expressions are developed which illustrate how crossover improves convergence. These expressions provide a theoretical basis for the "building block" hypothesis.

The second analysis examines converge by observing the divergence of an initial population comprised of optimal solutions. Such diverging and populations were found to the optimal and stabilise. Furthermore when the genetic algorithm was started with a randomly generated initial population it converged to the same sub-optimal equilibrium state.

The divergence analysis was carried out for the standard "counting-ones" problem which is unimodal and has no epistasis. Thus the convergence behaviour observed represents an upper bound on convergence performance.

The paper also discusses mutation and concludes that the mutation rate should be related to the string length. The analysis shows that it the mutation rate is too high then a genetic algorithm will not converge fully. Thus inappropriate mutation rates can prevent adequate convergence even for unimodal problems without epistasis.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £66 +P&P)