Path: utzoo!attcan!uunet!cs.utexas.edu!usc!apple!well!nagle
From: nagle@well.UUCP (John Nagle)
Newsgroups: comp.ai
Subject: Genetic algorithms don't seem to work
Keywords: genetics results
Message-ID: <12553@well.UUCP>
Date: 4 Jul 89 17:00:41 GMT
Distribution: comp
Lines: 23


      David Goldberg's "Genetic Algorithms" offers a good overview of the
field, along with some sample programs.  The interesting thing is that
the sample programs, which work fine on trivial functions, don't do well
on complex ones.  In particular, it is claimed that genetic algorithms
do well in searching for maxima in hill-climbing problems dominated by
local maxima.  (Goldberg, p. 4, esp. figure 1.3).  But this does not
seem to be the case in practice.  What seems to happen is that as soon
as any individual in the population finds a good spot with a high fitness,
it reproduces rapidly and takes over the population.  The resulting
population is homogeneous, so crossover does nothing, and only mutation
can bring further progress.  Since mutation progresses by single-bit 
invrersions, the space that can be explored by mutation has only as many
positions as there are bits in the chromosone.  Unless one of these few
positions is better than the good spot already found, which is unlikely
for many interesting functions, no further exploration of the space will
ever take place, and the algorithm remains stuck in a local maximum.
In any case, exploration by mutation is extremely inefficient.

      So where do people get the idea that this works as an optimization
technique for hill-climbing problems dominated by local maxima?

     					John Nagle