🚀 go-pugleaf

In article <1iscvrINNcp2@life.ai.mit.edu> mdlm@great-grain.ai.mit.edu (Michael De-la-Maza) writes:
>Lots of books (e.g., Goldberg's textbook and Koza's Genetic Programming)
>refer to tournament selection.  However, I have been unable to find the
>original source of the method.  Does anyone know what the original
>citation is?

There are two types of "tournament" selection...

1.  Goldberg's book talks about "stochastic tournament" as suggested by
Art Wetzel to Anne Brindle (1981).  According to Brindle's dissertation,
"The last method of selection is a ranking method proposed by Art Wetzel
(1979) which differs radically from the other selection methods.  Each
parent is selected by sampling twice from the distribution (stochastic
sampling with replacement) and using the better of the two individuals."

Of course, the "tournament size" does not have to be two. I don't have
references handy on this, but my experience has been that this method
is prone to too rapid convergence. With this method, there is also no
guarantee that the best members of the population (even the "super"
individual) will survive the current generation.

The citations are
  "Wetzel, A. 1979.  Personal communication."  (from Brindle)
  Brindle, A. (1981) Genetic Algorithms for Function Optimization, Ph.D.
    Dissertation, Technical Report TR81-2, Department of Computing Science,
    University of Alberta, Canada, January, 1981  (Goldberg lists this as
    unpublished, but I have a copy of the report; also, the date should be
    1981, not 1983 as in Goldberg.)

2.  I have no reference for the other "tournament" selection method. I
first learned about it first from the Software Technology Branch at NASA's
Johnson Space Center. It may have origninated there, but I doubt it because
I also heard about it from Rob Smith at the University of Alabama (where
Goldberg was as well). Papers that discuss it don't cite a reference.

Basically, you shuffle the population. Then take "tournament size" members
sequentially off the top of the population. Select the member with the best
fitness as a parent (i.e., hold a tournament). Keep moving this way through
the population. When you've exhausted the population, reshuffle and start
again, until the parent list is full.

This method has some nice qualities.  For one, the best member (the "super"
individual) is guarenteed to survive (i.e., built in elitism) and the best
member realizes its target mating rate.

Hope this helps.
                     __o                                          
                    ~\<,                                          
___________________()/ ()______________________________________________________
Steve Bayer                                       bayer@gothamcity.jsc.nasa.gov
The MITRE Corporation        
1120 NASA Road One, Suite 600                                    (713) 333-0978
Houston, TX  77058                                          fax: (713) 333-5147
_______________________________disclaimers ad nauseum__________________________ 

In article <1iscvrINNcp2@life.ai.mit.edu> mdlm@great-grain.ai.mit.edu (Michael De-la-Maza) writes:
>Lots of books (e.g., Goldberg's textbook and Koza's Genetic Programming)
>refer to tournament selection.  However, I have been unable to find the
>original source of the method.  Does anyone know what the original
>citation is?

According to Goldberg & Deb [1] "A form of tournament selection
attributed to unpublished work by Wetzel was studied in Brindle's
(1981) [2] dissertation..."

So it looks like the original source was: (a) before 1981, and 
(b) unpublished.


[1] Goldberg & Deb (1990) "A Comparative analysis of selection schemes
used in genetic algorithms" TCGA report No. 90007, also published in
FOGA-91, ed. G.J. Rawlins.

[2] Brindle, A (1981) "Genetic algorithms for function optimisation"
(Doctoral dissertation, Univ. of Michigan). Dissertation abstracts
international, 36(10), 5140B (University Microfilms No. 76-9381)

--

David Beasley                          (David.Beasley@cm.cf.ac.uk)    
Department of Computing Mathematics 
University of Wales College of Cardiff                          __o
PO Box 916                                                      \<,   
CARDIFF    CF2 4YN                         ___________________()/ ()___