Where Genetic Algorithms excel
Authors: E. Baum, D. Boneh, and C. Garrett
Abstract:
We analyze the performance of a Genetic Algorithm (GA) we call
Culling and a variety of other algorithms on a problem we
refer to as Additive Search Problem
(ASP). ASP is closely related to several previously
well studied problems,
such as the game of Mastermind and additive fitness functions.
We show that the problem of
learning the Ising perceptron is reducible to a noisy version of ASP.
Culling is efficient on ASP, highly noise tolerant, and the best known
approach
in some regimes. Noisy ASP is the first problem we are aware of
where a Genetic Type Algorithm bests all known competitors.
Standard GA's, by contrast, perform much more poorly on ASP than
hillclimbing
and other approaches even though the Schema theorem holds for ASP.
We generalize ASP to k-ASP to study whether GA's will achieve `implicit
parallelism' in a problem with many more schemata. GA's fail to achieve
this implicit parallelism, but we describe an algorithm we call
Explicitly Parallel Search that succeeds.
We also compute the optimal culling point for
selective breeding, which turns out to be independent of the fitness
function or the population distribution. We also analyze a Mean Field
Theoretic algorithm
performing similarly to Culling on many problems. These results
provide insight into when and how GA's can beat competing methods.
Reference:
Evolutionary Computation, MIT Press, Vol. 9, No. 1, pp. 93--124, 2001
Extended abstract in proceedings of COLT 1995
Full paper: html