home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / ai / genetic / 168 < prev    next >
Encoding:
Internet Message Format  |  1993-01-23  |  2.7 KB
  1. Path: sparky!uunet!gatech!pitt.edu!genetic
  2. From: genetic+@pitt.edu (Dr. Dave)
  3. Newsgroups: comp.ai.genetic
  4. Subject: Re: GA versus Simulated Annealing
  5. Message-ID: <2360@blue.cis.pitt.edu>
  6. Date: 22 Jan 93 21:57:06 GMT
  7. References: <1993Jan19.155159.16736@thunder.mcrcim.mcgill.edu>
  8. Sender: news+@pitt.edu
  9. Organization: Department of Industrial Engineering
  10. Lines: 51
  11.  
  12. Thus spake gblais@McRCIM.McGill.EDU (Gerard Blais):
  13.  
  14. >I have been using a genetic algorithm to solve a minimization
  15. >problem.  I performed the same minimization using the "Very Fast
  16. >Simulated Reannealing" algorithm created by Lester Ingber and
  17. >Bruce Rosen (I got it from a friend, but I believe it's available
  18. >from the net).  In all cases I tried, the Annealing search was
  19. >orders of magnitude faster for converging to the global minimum
  20. >than the GA.  
  21.  
  22. >My question is:  Are there any cases that you know of where a
  23. >genetic algorithm would actually perform better than simulated
  24. >annealing?  Are there any cases where simulated annealing would
  25. >fail but not genetic algorithms?
  26.  
  27. >Any comments?
  28.  
  29.  
  30. I've been waiting for someone from a more "traditional" GA background to
  31. address this, but I haven't really seen anything yet.  I'll jump in with
  32. both feet.
  33.  
  34. What kind of minimization problem are you doing?  Is it continuous, discrete,
  35. or mixed?  Constrained, or unconstrained?  Unimodular, unimodular with noise,
  36. or extremely lumpy?  
  37.  
  38. As far as I can tell, the main (potential) advantage that GA offers over SA
  39. and its kin is in the area of robustness.  For easy problems, SA is faster
  40. and just as good.  For hard problems, it's not so clear.  For extremely hard
  41. problems on tricky search spaces with weird constraints, GA *should* do much
  42. better.
  43.  
  44. I say "should" above because, as far as I know, nobody has done a systematic
  45. study on this.  However, it seems to be not uncommon, at least when looking at
  46. combinatorial problems, to see cases where SA is faster, and running a lot of
  47. different SA runs will find you solutions just as good as the best GA runs, 
  48. but the *average* value of the GA solutions is better than the average value
  49. of the SA solutions, and the quality of the GA is less sensitive to parameter
  50. settings (pop size, mutation rate, encoding and operators, etc.) than the SA
  51. is to its parameters (cooling schedule, settle time at a given temp., etc.).
  52.  
  53. I'd be happy to be corrected about any of the above, if anyone out there has
  54. different experience/intuition...
  55.  
  56. Dave Tate
  57.  
  58. -- 
  59.        David Tate        |"Something there is that doesn't love a wall,
  60.  dtate@unix.cis.pitt.edu | That sends the screaming liner over it 
  61.  Prof. of Story Problems | And spills the bleacher-dwellers from their seats."
  62.  Member ORSA, TIMS, SABR |      "Fenway Wall", Robert Frost          
  63.