skip to main content
10.1145/1389095.1389347acmconferencesArticle/Chapter ViewAbstractPublication PagesgeccoConference Proceedingsconference-collections
research-article

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

Published: 12 July 2008 Publication History

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]
T. Blickle and L. Thiele. A mathematical analysis of tournament selection. In Proceedings of the Sixth International Conference on Genetic Algorithms, pages 9--16, 1995.]]
[3]
T. Blickle and L. Thiele. A comparison of selection schemes used in evolutionary algorithms. Evolutionary Computation, 4(4):361--394, 1997.]]
[4]
J. Branke, H. C. Andersen, and H. Schmeck. Global selection methods for SIMD computers. In Proceedings of the AISB96 Workshop on Evolutionary Computing, pages 6--17, 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]
G. R. Harik. Finding multimodal solutions using restricted tournament selection. In Proceedings of the Sixth International Conference on Genetic Algorithms, pages 24--31, San Francisco, CA, 1995. Morgan Kaufmann.]]
[10]
J. R. Koza. Genetic Programming - On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, 1992.]]
[11]
S. Luke and L. Panait. Fighting bloat with nonparametric parsimony pressure. In Proceedings of Parallel Problem Solving from Nature, volume 2439 of LNCS, pages 411--421. Springer, 2002.]]
[12]
S. Luke and L. Panait. Lexicographic parsimony pressure. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 829--836, 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]
B. L. Miller and D. E. Goldberg. Genetic algorithms, selection schemes, and the varying effects of noise. Evolutionary Computation, 4(2):113--131, 1996.]]
[15]
T. Motoki. Calculating the expected loss of diversity of selection schemes. Evolutionary Computation, 10(4):397--422, 2002.]]
[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]
R. Poli and W. B. Langdon. Backward-chaining evolutionary algorithms. Artificial Intelligence, 170(11):953--982, 2006.]]
[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]
A. Sokolov and D. Whitley. Unbiased tournament selection. In Proceedings of GECCO 2005, pages 1131--1138. ACM Press, 2005.]]
[20]
H. Xie, M. Zhang, and P. Andreae. Another investigation on tournament selection: modelling and visualisation. In Proceedings of GECCO 2007, pages 1468--1475, 2007.]]

Cited By

View all
  • (2023)Genetic Programming With Lexicase Selection for Large-Scale Dynamic Flexible Job Shop SchedulingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.324460728:5(1235-1249)Online publication date: 14-Feb-2023
  • (2016)Tournament Selection Based on Statistical Test in Genetic ProgrammingParallel Problem Solving from Nature – PPSN XIV10.1007/978-3-319-45823-6_28(303-312)Online publication date: 31-Aug-2016
  • (2016)Optimization of Location Allocation of Web Services Using a Modified Non-dominated Sorting Genetic AlgorithmProceedings of the Second Australasian Conference on Artificial Life and Computational Intelligence - Volume 959210.1007/978-3-319-28270-1_21(246-257)Online publication date: 2-Feb-2016
  • Show More Cited By

Index Terms

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

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation
    July 2008
    1814 pages
    ISBN:9781605581309
    DOI:10.1145/1389095
    • Conference Chair:
    • Conor Ryan,
    • Editor:
    • Maarten Keijzer
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 12 July 2008

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. modelling
    2. multi-sampled issue
    3. simulation
    4. tournament selection

    Qualifiers

    • Research-article

    Conference

    GECCO08
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)1
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 13 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2023)Genetic Programming With Lexicase Selection for Large-Scale Dynamic Flexible Job Shop SchedulingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.324460728:5(1235-1249)Online publication date: 14-Feb-2023
    • (2016)Tournament Selection Based on Statistical Test in Genetic ProgrammingParallel Problem Solving from Nature – PPSN XIV10.1007/978-3-319-45823-6_28(303-312)Online publication date: 31-Aug-2016
    • (2016)Optimization of Location Allocation of Web Services Using a Modified Non-dominated Sorting Genetic AlgorithmProceedings of the Second Australasian Conference on Artificial Life and Computational Intelligence - Volume 959210.1007/978-3-319-28270-1_21(246-257)Online publication date: 2-Feb-2016
    • (2013)Parent Selection Pressure Auto-Tuning for Tournament Selection in Genetic ProgrammingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2011.218265217:1(1-19)Online publication date: 1-Feb-2013
    • (2010)A review of tournament selection in genetic programmingProceedings of the 5th international conference on Advances in computation and intelligence10.5555/1926680.1926703(181-192)Online publication date: 22-Oct-2010
    • (2010)A Review of Tournament Selection in Genetic ProgrammingAdvances in Computation and Intelligence10.1007/978-3-642-16493-4_19(181-192)Online publication date: 2010

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media