🚀 go-pugleaf

In article <Bs4pAH.2AI@research.canon.oz.au>, enzo@research.canon.oz.au (Enzo Liguori) writes:
> Does anybody know about any serious study about performances of Simulated
> Annealing (SA) compared to Genetics Algorithms (GA) ?
> Personal opinions and experience are welcome as well.
> I know that there's a book called "Simulated annealing and Genetic Algorithms"
> or something like that but I've never had any chance to read it.
> I have some experience with SA, but none with GA and the only person I know who
> tryed both is extremely pessimistic about GA.
> If there's any interest I'll summarize.
> Thanks in advance.

The book you are referring to is "Genetic Algorithms and Simulated Annealing",
edited by Lawrence Davis, published by Pitman.  I don't know how much comparison
between the two will be in there, but I do know that it is a collection of papers on
the two topics (most of which [all of which?] focus on one technique or the other).

GAs are more robust than SAs, there has been much more research done on GAs,
and there is much more software available for GAs (The robustness comment is from
a GA conference held this week.  The research and software comments are my own
observations after looking at the literature.)  Although I haven't actually coded and run
an SA, I have ran several GAs with much success.  I wouldn't call myself "extremely
pessimistic" about SAs, but I *know* GAs work well from my own experience (and others
experience as evidenced from the GA literature and personal communication).

Kelly
-- 
Kelly D. Crawford             | Amoco Production Research | These are my own
kcrawford@trc.amoco.com       | 4502 East 41st Street     | opinions, not
phone: (918) 660-4043         | Tulsa, OK  74102          | Amoco's...
          >>> *** This line intentionally left blank *** <<<

In article <1992Jul30.102118@trc.amoco.com> zkdc05@trc.amoco.com (Kelly D. Crawford) writes:
>
>GAs are more robust than SAs,

This is as far as I can tell, a commonly accepted falsehood. You can transform
any GA into SA by choosing a funny configuration space topology and annealing
schedule. You can go the other way more transparently, (by multiplexing the
search steps) so most people think that SA is properly included in GA, which I
am certain is false. GA and SA solve the same class of problems, and the optimal
GA for a problem is no better or no worse than the optimal SA for that problem.

So what's the difference? The difference is which one is more convenient for
your purposes, that is, which one is easier to think of for your problem.

The equivalence of GA and SA is much like the equivalence between space and
time averages - which obtains if the system is ergodic. Now this means that
the class of problems which are (statistically) solvable by GA and SA are the
same, however, the failure behaviors of GA and SA can be different.

>there has been much more research done on GAs,

I don't think so. I think that both GA and SA have reasonable profiles in the
literature.

Later,
Andrew Mullhaupt

andrew@rentec.com (Andrew Mullhaupt) writes:

>In article <1992Jul30.102118@trc.amoco.com> zkdc05@trc.amoco.com (Kelly D. Crawford) writes:
>>
>>GAs are more robust than SAs,

>This is as far as I can tell, a commonly accepted falsehood. You can transform
>any GA into SA by choosing a funny configuration space topology and annealing
>schedule. You can go the other way more transparently, (by multiplexing the
>search steps) so most people think that SA is properly included in GA, which I
>am certain is false. GA and SA solve the same class of problems, and the optimal
>GA for a problem is no better or no worse than the optimal SA for that problem.

I do not believe that you can make the transformations between GA's and
SA's that you indicate.  To transform the GA to an SA, you must first
note that the GA does not have an annealling aspect which forces it to
converge.  Any convergence in the GA is forced by the dynamics of
selection and cross-over.  Second, I assume that the 'funny
configuration space topology' would include the mutation and cross-over
points into the neighborhood used in SA.  Unfortunately, the
set of possible cross-over points is dependent on the current population.
There is no such dependency in SA.  In SA, the neighborhood structure
is fixed.

Performing the converse transformation is perhaps more understandable.
If you had a population of size one you wouldn't have cross-over and
would only have mutation steps, which is much like SA.  However, unless
you allow something like annealled mutation rates, you can't get a
transformation to work.

It is not clear to me that GA and SA solve the same class of problems.
Would you explain your reasoning?  The comparisons I have seen between
GA's and SA's have shown different relative performances on different
problems. 

--Bill

In article <1136@kepler1.rentec.com>, andrew@rentec.com (Andrew Mullhaupt) writes:
> In article <1992Jul30.102118@trc.amoco.com> zkdc05@trc.amoco.com (Kelly D. Crawford) writes:
> >
> >GAs are more robust than SAs,
> 
> This is as far as I can tell, a commonly accepted falsehood. You can transform
> any GA into SA by choosing a funny configuration space topology and annealing
> schedule. You can go the other way more transparently, (by multiplexing the
...
> 
> >there has been much more research done on GAs,
> 
> I don't think so. I think that both GA and SA have reasonable profiles in the
> literature.
> 
> Later,
> Andrew Mullhaupt
Well stated.

My feeling is that at the current time there are more successful
SA real codes (consider VLSI layout and routing) than GA. In applications
where the points in the configuration space are huge it is more of a
"challange" to get a GA to run.

The newer GA literature is catching up in volume and it is usually
easier to manage the massive parallelization of GA code over SA code.

john
-- 
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
John A. Kapenga                   Department of Computer Science
Ma Bell:  (616)387-5657           Western Michigan University
Internet: john@cs.wmich.edu       Kalamazoo, MI 49008

In article <1136@kepler1.rentec.com>, andrew@rentec.com (Andrew Mullhaupt) writes:
> [stuff deleted in a discussion on SA vs GA] 
>
> So what's the difference? The difference is which one is more convenient for
> your purposes, that is, which one is easier to think of for your problem.
>
> [more stuff deleted]

This is probably the best comment I've seen so far on any of this stuff.  It tends to
apply to almost any such debate (like Fortran vs C, etc, etc, etc...)

There is one comment that I have seen throughout this thread, however, that is
completely false (not by the above writer, but by some others I have seen responding).
I keep seeing the statement that GAs are nice toys, but there are very few practical
applications.  This couldn't be further from the truth.  Let me list a *sampling* of the
successful applications in the area.

Bin packing
Job shop scheduling
Vehicle routing with time windows
Gas pipeline optimization
VLSI circuit layout
VLSI layout compaction
Keyboard configuration
Aircraft landing strut weight optimization
Communications network link size optimization
Classroom scheduling (via SA with metalevel GA - hybrid of the two techniques)
Recursive adaptive filter design
Traveling salesman problem
Selection of detectors for binary pattern recognition
Image registration
Nonlinear equation solving
Constrained optimization problems (linear programming, etc)
Prisoner's dilemma
Database query optimization
Clustering
Criminal identification (face matching)
Pattern recognition
Music composition
Partitioning problems
Adaptive fuzzy logic controller design
Task allocation in multicomputers
Process control
1-D fractal inverse problem
Resource scheduling
Fuzzy logic synthesis
Context free grammar induction
Various NP problems (SAT, Hamiltonian circuit problem, n-queens, etc)
Chemometrics
Parametric design of aircraft
Configuration of stack filters
Steiner tree optimization
(apologies if I have duplicated anything in this list...I did it rather quickly)

I could go on.  This list was compiled in a few minutes by browsing Goldberg ("Genetic
Algorithms in Search, Optimization & Machine Learning", Addison-Wesley, 1989) and
the proceedings of the 3rd and 4th International Conference on Genetic Algorithms.
While not *everything* in the above list would fall under *practical*, most would.
The literature bears clear witness that GAs fall well within the bounds of practicality.
I can provide more detailed references if anyone is interested in a particular topic.

Kelly
-- 
Kelly D. Crawford             | Amoco Production Research | These are my own
kcrawford@trc.amoco.com       | 4502 East 41st Street     | opinions, not
phone: (918) 660-4043         | Tulsa, OK  74102          | Amoco's...
          >>> *** This line intentionally left blank *** <<<