On the Equivalence Between Stochastic Tournament and Power-Law Ranking Selection and How to Implement Them Efficiently

Tournament selection is a popular parent selection mechanism in evolutionary algorithms. Bian and Qian (PPSN 2022) proved that choosing the tournament size uniformly at random, called stochastic tournament selection, in combination with crossover significantly improves the performance of NSGA-II on some benchmark functions. We show that this selection mechanism is asymptotically equivalent to the power-law ranking selection proposed in Covantes Osuna et al. (Theor. Comput. Sci. 832, 2020) with the exponent of 2. Thus asymptotic runtime bounds proven for one operator also hold when one operator is replaced with the other. We also investigate how to implement these operators efficiently for NSGA-II on the problems considered in the previous papers. We propose to implement the stochastic tournament with a pre-computed selection distribution to save on random numbers. Experiments on high dimensional problems demonstrate the superiority of this method compared to the standard implementation. Overall, the power-law ranking selection is the most efficient selection mechanism for the studied problems. Remarkably, we also find that the way ties are broken between equally fit solutions can make the difference between the best and the worst approach, especially when crossover is involved.