Strong recombination, weak selection, and mutation

摘要

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 consideredin 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.