home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / ai / genetic / 190 < prev    next >
Encoding:
Text File  |  1993-01-27  |  3.0 KB  |  59 lines
  1. Newsgroups: comp.ai.genetic
  2. Path: sparky!uunet!munnari.oz.au!sgiblab!spool.mu.edu!howland.reston.ans.net!bogus.sura.net!udel!louie!pecan.cns.udel.edu!chang
  3. From: chang@pecan.cns.udel.edu (Liang-Wen Chang)
  4. Subject: Re: GA versus Simulated Annealing
  5. Message-ID: <1993Jan27.082732.15090@udel.edu>
  6. Sender: usenet@udel.edu (USENET News Service)
  7. Nntp-Posting-Host: pecan.cns.udel.edu
  8. Organization: University of Delaware, Newark
  9. References: <1993Jan19.155159.16736@thunder.mcrcim.mcgill.edu> <2360@blue.cis.pitt.edu>
  10. Date: Wed, 27 Jan 1993 08:27:32 GMT
  11. Lines: 46
  12.  
  13. In article <2360@blue.cis.pitt.edu> genetic+@pitt.edu (Dr. Dave) writes:
  14. >
  15. >I say "should" above because, as far as I know, nobody has done a systematic
  16. >study on this.  However, it seems to be not uncommon, at least when looking at
  17. >combinatorial problems, to see cases where SA is faster, and running a lot of
  18. >different SA runs will find you solutions just as good as the best GA runs, 
  19. >but the *average* value of the GA solutions is better than the average value
  20. >of the SA solutions, and the quality of the GA is less sensitive to parameter
  21. >settings (pop size, mutation rate, encoding and operators, etc.) than the SA
  22. >is to its parameters (cooling schedule, settle time at a given temp., etc.).
  23. >
  24. >I'd be happy to be corrected about any of the above, if anyone out there has
  25. >different experience/intuition...
  26. >
  27. >Dave Tate
  28.  
  29. The GA is insensitive to encoding due to the way of crossover operation.
  30. However, we also can say it IS sensitive to encoding once the encoding
  31. method is chosen.  Because any encoding of numbers will have some
  32. bits is significant than other bits, because such inhomogeneous of
  33. bit encoding, the crossover will produce offsprings in the 'neighborhood'
  34. of the parents.  The radius of the neighborhood is random and variable
  35. depending on where the crossover points are cut.  I haven't figured
  36. out the statistic nature of such variable radius w.r.t. particular
  37. encoding.  The recent 'uniform crossover' method is more of multi-bit
  38. mutation than crossover.  
  39.  
  40. Another thought is that GA is not quite working if the error surface
  41. contains long nerrow stiff valleys.  Usually, GA will stuck, not
  42. matter how you tune the parameters(those rates and pop size).  Once,
  43. it stucks(converges prematurely), it can never get out by itself because
  44. of the similarity among pops.
  45.  
  46. SA also has the problem of stucking in some local extremes.  However,
  47. the process is dynamic due to the temperature, if let it run long enough,
  48. it 'might' be able to jump out from the stagnation point.  The difficult
  49. of SA is to determine the schedule and corresponding initial temperature
  50. for a particular problem.  The error surface with long nerrow stiff valleys
  51. , SA can perform  better than GA.  This is equivallent to say that 
  52. mutation with certain distribution is preferable than crossover with
  53. random cut to such error surfaces.  However, if the area of extremes
  54. is not narrow but stiff, GA may work better than SA.
  55.  
  56. Any comments?  I would appreciate if any.
  57.  
  58. Boris
  59.