home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / ai / genetic / 152 < prev    next >
Encoding:
Text File  |  1993-01-21  |  2.2 KB  |  50 lines
  1. Newsgroups: comp.ai.genetic
  2. Path: sparky!uunet!peora!tarpit!cs.ucf.edu!news
  3. From: long@next1.acme.ucf.edu (Richard Long)
  4. Subject: Re: GA versus Simulated Annealing
  5. Message-ID: <1993Jan21.172459.27732@cs.ucf.edu>
  6. Sender: news@cs.ucf.edu (News system)
  7. Organization: University of Central Florida
  8. References: <1993Jan19.155159.16736@thunder.mcrcim.mcgill.edu>
  9. Date: Thu, 21 Jan 1993 17:24:59 GMT
  10. Lines: 38
  11.  
  12. In article <1993Jan19.155159.16736@thunder.mcrcim.mcgill.edu>  
  13. gblais@McRCIM.McGill.EDU (Gerard Blais) writes:
  14. > 
  15. > 
  16. > I have been using a genetic algorithm to solve a minimization
  17. > problem.  I performed the same minimization using the "Very Fast
  18. > Simulated Reannealing" algorithm created by Lester Ingber and
  19. > Bruce Rosen (I got it from a friend, but I believe it's available
  20. > from the net).  In all cases I tried, the Annealing search was
  21. > orders of magnitude faster for converging to the global minimum
  22. > than the GA.  My friend observed the same result for a different
  23. > minimization problem.
  24. > 
  25. > My question is:  Are there any cases that you know of where a
  26. > genetic algorithm would actually perform better than simulated
  27. > annealing?  Are there any cases where simulated annealing would
  28. > fail but not genetic algorithms?
  29.  
  30. One can view simulated annealing and reannealing as a GA with a mutation  
  31. rate set to non-monotonic decreasing and the crossover and inversion rates  
  32. set to zero.  From the few cases that I've read about the successes of GA,  
  33. crossover is particularly good for a problem that has a natural  
  34. hierarchical structure to the optimal solution, since crossover exploits  
  35. local fitness maxima in the construction of a global maximum.  If there is  
  36. no hierarchical structure to the optimal solution, local fitness  
  37. contributes very little to global fitness, and there is little advantage  
  38. to keeping local good solutions as crossover does.  Inversion exploits  
  39. symmetries in the problem. 
  40. Some problems that may be naturally hierarchical and symmetric, such as  
  41. image classification, may yield to GA methods more than simulated  
  42. annealing or simulated reannealing.
  43. --
  44. Richard Long
  45. Institute for Simulation and Training
  46. University of Central Florida
  47. 12424 Research Parkway, Suite 300, Orlando, FL 32826
  48. (407)658-5026, FAX: (407)658-5059
  49. long@acme.ucf.edu
  50.