An analysis of multi-sampled issue and no-replacement tournament selection

ABSTRACT

Standard tournament selection samples individuals with replacement. The sampling-with-replacement strategy has its advantages but also has issues. One of the commonly recognised issues is that it is possible to have the same individual sampled multiple times in a tournament. Although the impact of this multi-sampled issue on genetic programming is not clear, some researchers believe that it may lower the probability of some good individuals being sampled or selected. One solution is to use an alternative tournament selection (no-replacement tournament selection), which samples individuals in a tournament without replacement. This paper analyses no-replacement tournament selection to investigate the impact of the scheme and the importance of the issue. Theoretical simulations show that when common tournament sizes and population sizes are used, no-replacement tournament selection does not make the selection behaviour significantly different from that in the standard one and that the multi-sampled issue seldom occurs. In general, the issue is not crucial to the selection behaviour of standard tournament selection.

REFERENCES

• 1: T. Bäck. Selective pressure in evolutionary algorithms: A characterization of selection mechanisms. In Proceedings of the First IEEE Conference on Evolutionary Computation., pages 57--62, 1994.
• 2: Tobias Blickle , Lothar Thiele, A Mathematical Analysis of Tournament Selection, Proceedings of the 6th International Conference on Genetic Algorithms, p.9-16, July 15-19, 1995
• 3: Tobias Blickle , Lothar Thiele, A comparison of selection schemes used in evolutionary algorithms, Evolutionary Computation, v.4 n.4, p.361-394, Winter 1996 [doi>10.1162/evco.1996.4.4.361]
• 4: Jürgen Branke , Hans Christian Andersen , Hartmut Schmeck, Global Selection Methods for Massively Parallel Computers, Selected Papers from AISB Workshop on Evolutionary Computing, p.175-188, April 01-02, 1996
• 5: A. Brindle. Genetic algorithms for function optimisation. PhD thesis, Deptartment of Computing Science, University of Alberta, 1981.
• 6: M. Bulmer. The Mathematical Theory of Quantitative Genetics. Oxford University Press, Oxford, UK, 1980.
• 7: V. Filipović, J. Kratica, D. Tošić, and I. Ljubić. Fine grained tournament selection for the simple plant location problem. In 5th Online World Conference on Soft Computing Methods in Industrial Applications, pages 152--158, 2000.
• 8: D. E. Goldberg and K. Deb. A comparative analysis of selection schemes used in genetic algorithms. Foundations of Genetic Algorithms, pages 69--93, 1991.
• 9: Georges R. Harik, Finding Multimodal Solutions Using Restricted Tournament Selection, Proceedings of the 6th International Conference on Genetic Algorithms, p.24-31, July 15-19, 1995
• 10: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 11: Sean Luke , Liviu Panait, Fighting Bloat with Nonparametric Parsimony Pressure, Proceedings of the 7th International Conference on Parallel Problem Solving from Nature, p.411-421, September 07-11, 2002
• 12: Sean Luke , Liviu Panait, Lexicographic Parsimony Pressure, Proceedings of the Genetic and Evolutionary Computation Conference, p.829-836, July 09-13, 2002
• 13: B. L. Miller and D. E. Goldberg. Genetic algorithms, tournament selection, and the effects of noise. Technical Report 95006, University of Illinois at Urbana-Champaign, July 1995.
• 14: Brad L. Miller , David E. Goldberg, Genetic algorithms, selection schemes, and the varying effects of noise, Evolutionary Computation, v.4 n.2, p.113-131, Summer 1996 [doi>10.1162/evco.1996.4.2.113]
• 15: 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]
• 16: H. Muhlenbein and D. Schlierkamp-Voosen. Predictive models for the breeder genetic algorithm, I: continuous parameter optimization. Evolutionary Computation, 1(1):25--49, 1993.
• 17: Riccardo Poli , William B. Langdon, Backward-chaining evolutionary algorithms, Artificial Intelligence, v.170 n.11, p.953-982, August 2006 [doi>10.1016/j.artint.2006.04.003]
• 18: E. Popovici and K. D. Jong. Understanding EA dynamics via population fitness distributions. In Proceedings of the Genetic and Evolutionary Computation Conference 2003, pages 1604--1605, 2003.
• 19: Artem Sokolov , Darrell Whitley, Unbiased tournament selection, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068198]
• 20: Huayang Xie , Mengjie Zhang , Peter Andreae, Another investigation on tournament selection: modelling and visualisation, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277226]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Theory

Keywords:
modelling, multi-sampled issue, simulation, tournament selection