🚀 go-pugleaf

In article <1992Jul21.171506@trc.amoco.com> zkdc05@trc.amoco.com
(Kelly D. Crawford) writes:

> Let me offer you a summary given by Lawrence Davis at the Fourth International
> Conference on Genetic Algorithms.  It is one of the best ways I've found of
> determining when to use a GA:
>
>     When to Use Genetic Algorithms
>
>     - Problem requires good, but not optimal solution
>     - Acceptable performance measure is available
>     - Feasible to test many potential solutions
>     - Acceptable representation (of a solution) is available
>     - Size and complexity of search space preclude traditional approaches:
>          - Analytic solution
>          - Exhaustive search
>          - Hill-climbing
>          - Random search

Excuse me, but I can't imagine a problem in which the "size and complexity
of search space" preclude random search, especially methods like simulated
annealing in which the search is guided by the objective function.  How can
that be?

> Seriously, though, GAs have ample theory to suggest why they work, and
> although there is a certain degree of randomness (in fact, a LOT of
> randomness), there is a high probability that they will converge toward
> a good solution.

We just had a talk here last week that said that GAs had essentially no
theory -- the "fundamental theorem" isn't even a theorem, and so forth.
I haven't looked at the literature myself, but the speaker seemed to make
a reasonable case.  So two questions:

  1. Do GAs have any real theory?

  2. Is there any problem in which GAs beat simulated annealing?

-- 
Charles Geyer
School of Statistics
University of Minnesota
charlie@umnstat.stat.umn.edu