Analysis of the Simple Genetic Algorithm on the Single-peak and Double-peak Landscapes

Alden H. Wright
Computer Science Dept.
Univ. of Montana
Missoula, MT 59812
wright@cs.umt.edu
http://www.cs.umt.edu/u/wright/wright.htm

Jonathan E. Rowe 
School of Computer Science 
The University of Birmingham  
UK
j.e.rowe@cs.bham.ac.uk 

James R. Neil
School of Computer Science 
The University of Birmingham  
UK
j.r.neil@cs.bham.ac.uk 



Abstract


We compare the behavior of a GA with and without crossover.
A simple GA with crossover can have two stable fixed points 
(bistability) on the single-peak landscapes for string lengths at 
least 8.  There are catastrophic transitions from one to two and back 
to one stable fixed point as the mutation rate increases.  Crossover 
also causes the fixed-point population distribution to change.  
For a fixed point near the peak, there are fewer copies of the 
optimum string, more copies of near-optimum strings, and less 
copies of far-from-optimum strings.  An example is given where 
average population fitness decreases to the minimum possible 
population fitness for the with-crossover GA, while the average 
population fitness increases for the without-crossover GA.  The 
primary tool in obtaining these results is the Vose dynamical system 
model.