# On Steady-State Evolutionary Algorithms and Selective Pressure: Why Inverse Rank-Based Allocation of Reproductive Trials is Best

arXiv: https://arxiv.org/abs/2103.10394 · HTML: https://mlsanity.com/paper/2103.10394/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 46 references that are in the map.
- First posted on arXiv 18 Mar 2021.

## Builds on (most cited first, 8 of 8)

- [Fast Genetic Algorithms](https://mlsanity.com/paper/1703.03334/) (2017)
- [Level-based Analysis of Genetic Algorithms and other Search Processes](https://mlsanity.com/paper/1407.7663/) (2014)
- [Fast Artificial Immune Systems](https://mlsanity.com/paper/1806.00299/) (2018)
- [Standard Steady State Genetic Algorithms Can Hillclimb Faster than Mutation-only Evolutionary Algorithms](https://mlsanity.com/paper/1708.01571/) (2017)
- [On the Benefits of Populations on the Exploitation Speed of Standard Steady-State Genetic Algorithms](https://mlsanity.com/paper/1903.10976/) (2019)
- [The Benefits of Population Diversity in Evolutionary Algorithms: A Survey of Rigorous Runtime Analyses](https://mlsanity.com/paper/1801.10087/) (2018)
- [Artificial Immune Systems Can Find Arbitrarily Good Approximations for the NP-Hard Number Partitioning Problem](https://mlsanity.com/paper/1806.00300/) (2018)
- [A General Dichotomy of Evolutionary Algorithms on Monotone Functions](https://mlsanity.com/paper/1803.09227/) (2018)

## Built on by (most cited first, 3 of 3)

- [(1+1) Genetic Programming With Functionally Complete Instruction Sets Can Evolve Boolean Conjunctions and Disjunctions with Arbitrarily Small Error](https://mlsanity.com/paper/2303.07455/) (2023)
- [Frequency Fitness Assignment: Optimization without Bias for Good Solutions can be Efficient](https://mlsanity.com/paper/2112.00229/) (2021)
- [Parent Selection Mechanisms in Elitist Crossover-Based Algorithms](https://mlsanity.com/paper/2604.04083/) (2026)

## Abstract (arXiv)

We analyse the impact of the selective pressure for the global optimisation capabilities of steady-state EAs. For the standard bimodal benchmark function twomax we rigorously prove that using uniform parent selection leads to exponential runtimes with high probability to locate both optima for the standard (μ+1)~EA and (μ+1)~RLS with any polynomial population sizes. On the other hand, we prove that selecting the worst individual as parent leads to efficient global optimisation with overwhelming probability for reasonable population sizes. Since always selecting the worst individual may have detrimental effects for escaping from local optima, we consider the performance of stochastic parent selection operators with low selective pressure for a function class called textscTruncatedTwoMax where one slope is shorter than the other. An experimental analysis shows that the EAs equipped with inverse tournament selection, where the loser is selected for reproduction and small tournament sizes, globally optimise textscTwoMax efficiently and effectively escape from local optima of textscTruncatedTwoMax with high probability. Thus they identify both optima efficiently while uniform (or stronger) selection fails in theory and in practice. We then show the power of inverse selection on function classes from the literature where populations are essential by providing rigorous proofs or experimental evidence that it outperforms uniform selection equipped with or without a restart strategy. We conclude the paper by confirming our theoretical insights with an empirical analysis of the different selective pressures on standard benchmarks of the classical MaxSat and Multidimensional Knapsack Problems.