# Design and Analysis of Diversity-Based Parent Selection Schemes for Speeding Up Evolutionary Multi-objective Optimisation

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 May 2018.

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

- [A First Runtime Analysis of the NSGA-II on a Multimodal Problem](https://mlsanity.com/paper/2204.13750/) (2022)
- [From Understanding the Population Dynamics of the NSGA-II to the First Proven Lower Bounds](https://mlsanity.com/paper/2209.13974/) (2022)
- [Mathematical Runtime Analysis for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II)](https://mlsanity.com/paper/2112.08581/) (2021)
- [Stochastic Population Update Can Provably Be Helpful in Multi-Objective Evolutionary Algorithms](https://mlsanity.com/paper/2306.02611/) (2023)
- [Runtime Analyses of Multi-Objective Evolutionary Algorithms in the Presence of Noise](https://mlsanity.com/paper/2305.10259/) (2023)
- [The (1+(λ,λ)) Global SEMO Algorithm](https://mlsanity.com/paper/2210.03618/) (2022)
- [Many Objective Problems Where Crossover is Provably Essential](https://mlsanity.com/paper/2412.18375/) (2024)
- [Can Evolutionary Clustering Have Theoretical Guarantees?](https://mlsanity.com/paper/2212.01771/) (2022)
- [Parent Selection Mechanisms in Elitist Crossover-Based Algorithms](https://mlsanity.com/paper/2604.04083/) (2026)

## Abstract (arXiv)

Parent selection in evolutionary algorithms for multi-objective optimisation is usually performed by dominance mechanisms or indicator functions that prefer non-dominated points. We propose to refine the parent selection on evolutionary multi-objective optimisation with diversity-based metrics. The aim is to focus on individuals with a high diversity contribution located in poorly explored areas of the search space, so the chances of creating new non-dominated individuals are better than in highly populated areas. We show by means of rigorous runtime analysis that the use of diversity-based parent selection mechanisms in the Simple Evolutionary Multi-objective Optimiser (SEMO) and Global SEMO for the well known bi-objective functions rm Osmall NEMsmall INMsmall AX and rm LOTZ can significantly improve their performance. Our theoretical results are accompanied by experimental studies that show a correspondence between theory and empirical results and motivate further theoretical investigations in terms of stagnation. We show that stagnation might occur when favouring individuals with a high diversity contribution in the parent selection step and provide a discussion on which scheme to use for more complex problems based on our theoretical and experimental results.