Equivalence of probabilistic tournament and polynomial ranking selection

Kassel Hingee, Marcus Hutter

Introduction

In the field of Evolutionary Algorithms (EAs), selection schemes are the critical mechanisms that determine which individuals in a population survive to reproduce. Historically, researchers have faced a trade-off between two dominant methods: Ranking Selection and Tournament Selection.

Ranking selection offers high flexibility by allowing selection probability to be a smooth function of an individual's rank. However, it is computationally expensive, requiring a full population sort ($O(n)$). Conversely, tournament selection is highly efficient ($O(t)$, where $t$ is small) but typically offers only discrete, "choppy" levels of selection pressure. This paper bridges this gap by proving that Probabilistic Tournament Selection is mathematically equivalent to Polynomial Ranking Selection.

Mathematical Framework and Methods

The authors define two generalized selection schemes to establish their equivalence:

  1. Polynomial $\alpha$-ranking: The probability of selecting an individual with rank $k$ is defined by a polynomial of degree $d$.
  2. Probabilistic $\alpha$-tournament: A tournament of size $t$ is held, and the $s$-th best individual in that tournament is chosen with a pre-defined probability $\alpha_s$.

To map these two worlds, the researchers employ linear algebra, specifically utilizing Vandermonde matrices, Stirling numbers of the first kind, and binomial identities. They derive two transformation matrices ($T$ and $R$) that act as "translators," mapping the coefficients of a polynomial rank scheme directly to the probability parameters of a tournament scheme.

Table of symbols and their explanations used in the mathematical derivation.

Key Insights: The Equivalence Theorem

The central contribution of this work is the Equivalence Theorem, which proves that every probabilistic tournament of size $t$ is equivalent to a unique polynomial rank scheme of degree $d = t - 1$.

This discovery allows for "the best of both worlds": an algorithm designer can define a complex, smooth selection pressure using a quadratic or cubic polynomial and then execute it with the speed of a small tournament. This effectively reduces the computational complexity from $O(n)$ to $O(t)$ without sacrificing the mathematical flexibility of ranking.

Selection probability curves for various tournament sizes t, illustrating the resulting selection pressure.

Results and Practical Utility

The authors validated their theoretical findings through numerical examples and Monte-Carlo simulations. Key results include:

  • Linear and Quadratic Coverage: For typical population sizes (e.g., $n=300$), size-2 tournaments cover nearly all linear ranking schemes, and size-3 tournaments can perfectly reproduce the most desirable (monotonic) quadratic schemes.
  • Uniqueness: The mapping between tournament configurations and polynomial curves is unique and injective.
  • Efficiency: The paper provides an explicit inverse map (Theorem 5), allowing for the instant calculation of tournament parameters from a desired polynomial selection pressure.

Limitations and Future Directions

While the equivalence is robust, a "coverage gap" exists: not every polynomial rank scheme can be represented as a tournament. A polynomial only has a tournament equivalent if the resulting tournament probabilities ($\alpha_s$) are non-negative and sum to 1. As the degree of the polynomial (and thus the tournament size $t$) increases, the percentage of representable polynomials decreases. For $t=5$, only about 2% of possible 4th-degree polynomials are representable, though the authors suggest that most "useful" monotonic schemes remain covered.

Reference: Hingee, K., & Hutter, M. (2008). Equivalence of Probabilistic Tournament and Polynomial Ranking Selection. arXiv:0803.2925v1 [cs.NE].

Summary updated

Abstract

Crucial to an evolutionary algorithm's performance is its selection scheme. We mathematically investigate the relation between polynomial rank and probabilistic tournament methods which are (respectively) generalisations of the popular linear ranking and tournament selection schemes. We show that every probabilistic tournament is equivalent to a unique polynomial rank scheme. In fact, we derived explicit operators for translating between these two types of selection. Of particular importance is that most linear and most practical quadratic rank schemes are probabilistic tournaments.
BibTeX
@inproceedings{hingee2008equivalence,
  author = {Kassel Hingee and Marcus Hutter},
  title = {{Equivalence of probabilistic tournament and polynomial ranking selection}},
  booktitle = {IEEE CEC},
  year = {2008},
  url = {https://openreview.net/forum?id=6uq1fqy7HL},
}
Figure