🚀 go-pugleaf

From: nagle@well.UUCP (John Nagle)
To: comp.ai
Date: 4 Jul 89 17:00:41 GMT
Subject: Genetic algorithms don't seem to work
Keywords: genetics results

mod-ki message 0272
************************************************************************
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
inversions, 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

[Diesen Text habe ich aus der Newsgroup comp.ai kopiert. Es ist wichtig,
neue Methoden gleich auch kritisch zu durchleuchten. Was angesichts  des
laufenden Neuronale-Netze-etc-Goldrauschs eilig auf den  Markt  geknallt
und ungeprueft  rezipiert  wird,  kann  unmoeglich  alles  experimentell
verifiziert  sein.  Und  wie  sollte  man  hochparallele  Methoden  wohl
verifizieren, ausser experimentell? CAVE PROPHETIS. hwh]
************************************************************************