Another investigation on tournament selection: modelling and visualisation

ABSTRACT

Tournament selection has been widely used and studied in evolutionary algorithms. To supplement the study of tournament selection, this paper provides several models describing the probabilities that a program of a particular rank is sampled and is selected in the standard tournament selection in a simple situation and a complex situation. This paper discovers that, with the same tournament size, trends of sampling probability of a program and selection probability distributions of a population are the same regardless ofthe population size. This paper also models and investigates an alternative tournament selection method which eliminates one of the drawbacks in the standard tournament selection. Finally, this paper proposes a new fitness evaluation saving algorithm via the use of not-sampled individuals, which is a special property of tournament selection.

REFERENCES

• 1: 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
• 2: T. Blickle and L. Thiele. A comparison of selection schemes used in evolutionary algorithms. Evolutionary Computation, 4(4):361--394, 1997.
• 3: V. Filipović, J. Kratica, D. Tosić, 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.
• 4: 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
• 5: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 6: Sean Luke , Liviu Panait, Lexicographic Parsimony Pressure, Proceedings of the Genetic and Evolutionary Computation Conference, p.829-836, July 09-13, 2002
• 7: 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.
• 8: 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 ]
• 9: R. Poli. Tournament selection, iterated coupon-collection problem, and backward-chaining evolutionary algorithms. In Foundations of Genetic Algorithms, volume 3469 of Lecture Notes in Computer Science, pages 132--155. Springer-Verlag, 2005.
• 10: Riccardo Poli , William B. Langdon, Backward-chaining genetic programming, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068306]
• 11: 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]
• 12: T. Weinbrenner. GPC++ - Genetic Programming C++ Class Library, 1997.
• 13: H. Xie, M. Zhang, and P. Andreae. Population clustering in genetic programming. In Proceedings of the 9th European Conference, EuroGP 2006, volume 3905 of LNCS, pages 190--201. Springer-Verlag, 2006.

INDEX TERMS

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

General Terms:
Theory

Keywords:
modelling, tournament selection, visualisation