Unbiased tournament selection

ABSTRACT

Tournament selection is a popular form of selection which is commonly used with genetic algorithms, genetic programming and evolutionary programming. However, tournament selection introduces a sampling bias into the selection process. We review analytic results and present empirical evidence that shows this bias has a significant impact on search performance. We introduce two new forms of unbiased tournament selection that remove or reduce sampling bias in tournament selection.

REFERENCES

• 1: Thomas Bäck , Hans-Paul Schwefel, An overview of evolutionary algorithms for parameter optimization, Evolutionary Computation, v.1 n.1, p.1-23, Spring 1993
• 2: James E. Baker, Reducing bias and inefficiency in the selection algorithm, Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, p.14-21, October 1987, Cambridge, Massachusetts, United States
• 3: Blickle T. and L. Thiele. "A Comparison of Selection Schemes used in Genetic Algorithms". TIK Report No. 11, Computer Engineering and Communication Networks Lab (TIK), Swiss Federal Institute of Technology (ETH) Zurich, Switzerland, December 1995.
• 4: Blickle T. and L. Thiele. "A Comparison of selection schemes used in evolutionary algorithms". Evolutionary Computation, 4(4): 361--394, 1997.
• 5: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 6: Goldberg D. and K. Deb. "A Comparative Analysis of Selection Schemes Used in Genetic Algorithms". In Rawlins, G.J.E., editor, Foundations of Genetic Algorithms, pages 69--93, Morgan Kaufmann, San Mateo, California, 1991.
• 7: Tatsuya Motoki, Calculating the expected loss of diversity of selection schemes, Evolutionary Computation, v.10 n.4, p.397-422, December 2002 [doi>10.1162/106365602760972776]
• 8: Poli R. "Tournament Selection, Iterated Coupon-collection Problem, and Backward-chaining Evolutionary Algorithms". Proceedings of the Foundations of Genetic Algorithms Workshop (FOGA 8), Springer 2005.
• 9: Schwefel H.-P. "Evolution and Optimum Seeking", p.328. Wiley, New York, 1995.
• 10: David E. Smith , Jeremy Frank , Ari K. Jónsson, Bridging the gap between planning and scheduling, The Knowledge Engineering Review, v.15 n.1, p.47-83, March 2000 [doi>10.1017/S0269888900001089]
• 11: Syswerda G. "Schedule Optimization Using Genetic Algorithms". In L. Davis, ed., Handbook of Genetic Algorithms, 332--349, Van Nostrand Reinhold, New York, 1991.
• 12: Whitley D. "A Genetic Algorithm Tutorial", Statistics and Computing (4):65--85, 1994.
• 13: Darrell Whitley , Soraya Rana , John Dzubera , Keith E. Mathias, Evaluating evolutionary algorithms, Artificial Intelligence, v.85 n.1-2, p.245-276, Aug. 1996 [doi>10.1016/0004-3702(95)00124-7]
• 14: Darrell Whitley, The GENITOR algorithm and selection pressure: why rank-based allocation of reproductive trials is best, Proceedings of the third international conference on Genetic algorithms, p.116-121, December 1989, George Mason University, United States
• 15: Whitley D., M. Lunacek, J. Knight. "Ruffled by Ridges: How Evolutionary Algorithms Can Fail". In K. Deb, ed., GECCO (2) 2004: 294--306. Springer-Verlag.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global optimization

Keywords:
evolutionary computation, genetic algorithms, loss of diversity, tournament selection