Strong Recombination, Weak Selection, and Mutation

posted 11/27/06


Alden H. Wright
Computer Science Dept.  Univ. of Montana Missoula, MT 59812 USA
wright@cs.umt.edu
(406) 243-4790

J. Neal Richter
Computer Science Dept.  Montana State University, Bozeman, MT 59812 USA
Bozeman, MT 59714
richter@cs.montana.edu

Reference:  GECCO 2006 Genetic and Evolutionary Computation Conference,
Maarten Keijzer et al., editors.  Association for Computing Machinery,
2006.  Pages 1369--1376.

Abstract

We show that there are unimodal fitness functions and genetic algorithm (GA) 
parameter settings where the GA, when initialized with a random population, 
will not move close to the fitness peak in a practically useful time
period.  When the GA is initialized with a population close to the fitness 
peak, the GA will be able to stay close to the fitness peak.  Roughly
speaking, the parameter settings involve strong recombination, 
weak selection, and require mutation.  This ``bistability'' phenomenon 
has been previously investigated with needle-in-the-haystack fitness
functions, but this fitness, when used with a GA with random
initialization, requires a population size exponential
in the string length for the GA to have nontrivial behavior.
We introduce sloping-plateau fitness functions which
show the bistability phenomenon and should scale to arbitrary string 
lengths.  We introduce and use an unitation infinite population model to 
investigate the bistability phenomenon.  For the fitnesses and GAs
considered in the paper, we show that
the use of crossover moves the GA to its fixed point faster in comparison
to the same GA without crossover.