Abstract
Genetic algorithms (GAs) are probabilistic optimization methods based on the biological principle of natural evolution. One of the important operators in GAs is the selection strategy for obtaining better solutions. Specifically, finding a balance between the selection pressure and diversity is a critical issue in designing an efficient selection strategy. To this extent, the recently proposed real world tournament selection (RWTS) method has showed good performance in various benchmark problems. In this paper, we focus on analyzing characteristics of RWTS from the viewpoint of both the selection probabilities and stochastic sampling properties in order to provide a rational explanation for why RWTS provides improved performance. Statistical experimental results show that RWTS has a higher selection pressure with a relatively small loss of diversity and higher sampling accuracy than conventional tournament selection. The performance tests in a traveling salesman problem further confirm that the comparatively higher pressure and sampling accuracy, which are inherent in RWTS, can enhance the performance in the selection strategy.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Holland JH (1975) Adaptation in natural and artificial system. University of Michigan Press, Ann Arbor
Baker JE (1985) Adaptive selection methods for genetic algorithms. In: Proceedings of the 1st international conference on genetic algorithms and their applications, pp 101–111
Michalewicz Z (1992) Genetic algorithms + data structures = evolution programs. Springer, Berlin
Goldberg DE, Klösener KH (1991) A comparative analysis of selection schemes used in genetic algorithms. In: Rawlins G (ed) Foundation of genetic algorithms. Kaufmann, San Mateo, pp 69–93
Soak S, Corne D, Ahn B (2004) A powerful new encoding for tree-based combinatorial optimisation problems. In: Lecture notes in computer science, vol 3242, pp 430–439
Soak S, Corne D, Ahn B (2004) A new encoding for the degree constrained minimum spanning tree problem. In: Lecture notes in computer science, vol 3213, pp 952–958
Soak S, Corne D, Ahn B (2006) The edge-window-decoder representation for tree-based problem. IEEE Trans Evol Comput 10(2):124–144
Lee S, Soak S, Mahalik NP, Ahn B, Jeon M (2006) Mathematical and empirical analysis of the real world tournament selection. In: Lecture notes in artificial intelligence, vol 4215, pp 130–137
Julstrom BA (1999) It’s all the same to me: Revisiting rank-based probabilities and tournaments. In: Proceedings of the congress on evolutionary computation, pp 1501–1505
Bäck T (1996) Evolutionary algorithms in theory and practice. Oxford University Press, Oxford
Baker JE (1987) Reducting bias and inefficiency in the selection algorithm. In: Grefenstette JJ (ed). Proceedings of the second international conference on genetic algorithms. Kaufmann, San Mateo, pp 14–21
Beasley D, Bull DR, Martine RR (1993) An overview of genetic algorithms, part 1: fundamentals. University computing, the bulletin of the IUCC, vol 15, no 2, p 58
Rogers A, Bennett AP (1999) Genetic drift in genetic algorithm selection schemes. IEEE Trans Evol Comput 3(4):298–303
Schell T, Wegenkittl S (2001) Looking beyond selection probabilities: adaptation of the χ 2 measure for the performance analysis selection methods in GAs. Evol Comput 9(2):243–256
Blickle T, Thiele L (1995) A comparison of selection schemes used in genetic algorithms. Technical Report 11, Swiss Federal Institute of Technology, Zürich, Switzerland
Blickle T, Thiele L (1995) A mathematical analysis of tournament selection. In: Proceedings of the 6th international conference on genetic algorithms, pp 9–16
Bäck T (1994) Selective pressure in evolutionary algorithms: a characterization of selection mechanisms. In: Proceedings of 1st IEEE conference on evolutionary computation, pp 56–62
Papoulis A, Pillai SU (2002) Probability, random variables and stochastic processes, 4th edn. McGraw–Hill, New York, p 361
http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/index.html
Bean JC (1994) Genetics and random keys for sequencing and optimization. ORSA J Comput 6:154–160
Sywerda G (1989) Uniform crossover in genetic algorithms. In: Proceedings of the third international conference on genetic algorithms, George Mason University, USA, pp 2–9
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Lee, S., Soak, S., Kim, K. et al. Statistical properties analysis of real world tournament selection in genetic algorithms. Appl Intell 28, 195–205 (2008). https://doi.org/10.1007/s10489-007-0062-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10489-007-0062-2