🚀 go-pugleaf

Thus spake gblais@McRCIM.McGill.EDU (Gerard Blais):

>I have been using a genetic algorithm to solve a minimization
>problem.  I performed the same minimization using the "Very Fast
>Simulated Reannealing" algorithm created by Lester Ingber and
>Bruce Rosen (I got it from a friend, but I believe it's available
>from the net).  In all cases I tried, the Annealing search was
>orders of magnitude faster for converging to the global minimum
>than the GA.  

>My question is:  Are there any cases that you know of where a
>genetic algorithm would actually perform better than simulated
>annealing?  Are there any cases where simulated annealing would
>fail but not genetic algorithms?

>Any comments?


I've been waiting for someone from a more "traditional" GA background to
address this, but I haven't really seen anything yet.  I'll jump in with
both feet.

What kind of minimization problem are you doing?  Is it continuous, discrete,
or mixed?  Constrained, or unconstrained?  Unimodular, unimodular with noise,
or extremely lumpy?  

As far as I can tell, the main (potential) advantage that GA offers over SA
and its kin is in the area of robustness.  For easy problems, SA is faster
and just as good.  For hard problems, it's not so clear.  For extremely hard
problems on tricky search spaces with weird constraints, GA *should* do much
better.

I say "should" above because, as far as I know, nobody has done a systematic
study on this.  However, it seems to be not uncommon, at least when looking at
combinatorial problems, to see cases where SA is faster, and running a lot of
different SA runs will find you solutions just as good as the best GA runs, 
but the *average* value of the GA solutions is better than the average value
of the SA solutions, and the quality of the GA is less sensitive to parameter
settings (pop size, mutation rate, encoding and operators, etc.) than the SA
is to its parameters (cooling schedule, settle time at a given temp., etc.).

I'd be happy to be corrected about any of the above, if anyone out there has
different experience/intuition...

Dave Tate

-- 
       David Tate        |"Something there is that doesn't love a wall,
 dtate@unix.cis.pitt.edu | That sends the screaming liner over it 
 Prof. of Story Problems | And spills the bleacher-dwellers from their seats."
 Member ORSA, TIMS, SABR |  	"Fenway Wall", Robert Frost