home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / ai / genetic / 44 < prev    next >
Encoding:
Text File  |  1993-01-12  |  3.4 KB  |  67 lines
  1. Newsgroups: comp.ai.genetic
  2. Path: sparky!uunet!think.com!linus!linus.mitre.org!mwunix!m16532
  3. From: m16532@mwunix (Steven Bayer)
  4. Subject: Re: Tournament selection
  5. Message-ID: <1993Jan12.154359.13650@linus.mitre.org>
  6. Sender: news@linus.mitre.org (News Service)
  7. Nntp-Posting-Host: mwunix.mitre.org
  8. Organization: MITRE Corporation, Houston, TX
  9. References: <1iscvrINNcp2@life.ai.mit.edu>
  10. Date: Tue, 12 Jan 1993 15:43:59 GMT
  11. Lines: 54
  12.  
  13. In article <1iscvrINNcp2@life.ai.mit.edu> mdlm@great-grain.ai.mit.edu (Michael De-la-Maza) writes:
  14. >Lots of books (e.g., Goldberg's textbook and Koza's Genetic Programming)
  15. >refer to tournament selection.  However, I have been unable to find the
  16. >original source of the method.  Does anyone know what the original
  17. >citation is?
  18.  
  19. There are two types of "tournament" selection...
  20.  
  21. 1.  Goldberg's book talks about "stochastic tournament" as suggested by
  22. Art Wetzel to Anne Brindle (1981).  According to Brindle's dissertation,
  23. "The last method of selection is a ranking method proposed by Art Wetzel
  24. (1979) which differs radically from the other selection methods.  Each
  25. parent is selected by sampling twice from the distribution (stochastic
  26. sampling with replacement) and using the better of the two individuals."
  27.  
  28. Of course, the "tournament size" does not have to be two. I don't have
  29. references handy on this, but my experience has been that this method
  30. is prone to too rapid convergence. With this method, there is also no
  31. guarantee that the best members of the population (even the "super"
  32. individual) will survive the current generation.
  33.  
  34. The citations are
  35.   "Wetzel, A. 1979.  Personal communication."  (from Brindle)
  36.   Brindle, A. (1981) Genetic Algorithms for Function Optimization, Ph.D.
  37.     Dissertation, Technical Report TR81-2, Department of Computing Science,
  38.     University of Alberta, Canada, January, 1981  (Goldberg lists this as
  39.     unpublished, but I have a copy of the report; also, the date should be
  40.     1981, not 1983 as in Goldberg.)
  41.  
  42. 2.  I have no reference for the other "tournament" selection method. I
  43. first learned about it first from the Software Technology Branch at NASA's
  44. Johnson Space Center. It may have origninated there, but I doubt it because
  45. I also heard about it from Rob Smith at the University of Alabama (where
  46. Goldberg was as well). Papers that discuss it don't cite a reference.
  47.  
  48. Basically, you shuffle the population. Then take "tournament size" members
  49. sequentially off the top of the population. Select the member with the best
  50. fitness as a parent (i.e., hold a tournament). Keep moving this way through
  51. the population. When you've exhausted the population, reshuffle and start
  52. again, until the parent list is full.
  53.  
  54. This method has some nice qualities.  For one, the best member (the "super"
  55. individual) is guarenteed to survive (i.e., built in elitism) and the best
  56. member realizes its target mating rate.
  57.  
  58. Hope this helps.
  59.                      __o                                          
  60.                     ~\<,                                          
  61. ___________________()/ ()______________________________________________________
  62. Steve Bayer                                       bayer@gothamcity.jsc.nasa.gov
  63. The MITRE Corporation        
  64. 1120 NASA Road One, Suite 600                                    (713) 333-0978
  65. Houston, TX  77058                                          fax: (713) 333-5147
  66. _______________________________disclaimers ad nauseum__________________________ 
  67.