# Stochastic Population Update Can Provably Be Helpful in Multi-Objective Evolutionary Algorithms

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 85 references that are in the map.
- First posted on arXiv 5 Jun 2023.

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

- [Maximizing Submodular or Monotone Approximately Submodular Functions by Multi-objective Evolutionary Algorithms](https://mlsanity.com/paper/1711.07214/) (2017)
- [Pareto Optimization for Subset Selection with Dynamic Cost Constraints](https://mlsanity.com/paper/1811.07806/) (2018)
- [A First Runtime Analysis of the NSGA-II on a Multimodal Problem](https://mlsanity.com/paper/2204.13750/) (2022)
- [Runtime Analysis for the NSGA-II: Provable Speed-Ups From Crossover](https://mlsanity.com/paper/2208.08759/) (2022)
- [Reducing Idleness in Financial Cloud Services via Multi-objective Evolutionary Reinforcement Learning based Load Balancer](https://mlsanity.com/paper/2305.03463/) (2023)
- [From Understanding the Population Dynamics of the NSGA-II to the First Proven Lower Bounds](https://mlsanity.com/paper/2209.13974/) (2022)
- [Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives](https://mlsanity.com/paper/2012.07231/) (2020)
- [A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III)](https://mlsanity.com/paper/2211.08202/) (2022)
- [Design and Analysis of Diversity-Based Parent Selection Schemes for Speeding Up Evolutionary Multi-objective Optimisation](https://mlsanity.com/paper/1805.01221/) (2018)
- [Mathematical Runtime Analysis for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II)](https://mlsanity.com/paper/2112.08581/) (2021)
- [Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectives](https://mlsanity.com/paper/2211.13084/) (2022)
- [Crossover Can Guarantee Exponential Speed-Ups in Evolutionary Multi-Objective Optimisation](https://mlsanity.com/paper/2301.13687/) (2023)
- [The First Proven Performance Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem](https://mlsanity.com/paper/2305.13459/) (2023)
- [Runtime Analyses of Multi-Objective Evolutionary Algorithms in the Presence of Noise](https://mlsanity.com/paper/2305.10259/) (2023)
- [Lower Bounds for Non-Elitist Evolutionary Algorithms via Negative Multiplicative Drift](https://mlsanity.com/paper/2005.00853/) (2020)
- [Exponential Upper Bounds for the Runtime of Randomized Search Heuristics](https://mlsanity.com/paper/2004.05733/) (2020)
- [Non-Elitist Evolutionary Multi-Objective Optimisation: Proof-of-Principle Results](https://mlsanity.com/paper/2305.16870/) (2023)

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

- [Offline Multi-Objective Optimization](https://mlsanity.com/paper/2406.03722/) (2024)
- [Many Objective Problems Where Crossover is Provably Essential](https://mlsanity.com/paper/2412.18375/) (2024)
- [A Crowding Distance That Provably Solves the Difficulties of the NSGA-II in Many-Objective Optimization](https://mlsanity.com/paper/2407.17687/) (2024)
- [Scalable Speed-ups for the SMS-EMOA from a Simple Aging Strategy](https://mlsanity.com/paper/2505.01647/) (2025)
- [Surrogate-Assisted Evolutionary Reinforcement Learning Based on Autoencoder and Hyperbolic Neural Network](https://mlsanity.com/paper/2505.19423/) (2025)
- [A Block-Coordinate Descent EMO Algorithm: Theoretical and Empirical Analysis](https://mlsanity.com/paper/2404.03838/) (2024)
- [From Observations to Parameters: Detecting Changepoint in Nonlinear Dynamics with Simulation-based Inference](https://mlsanity.com/paper/2510.17933/) (2025)
- [SPEA2^+: Improved Density Estimation in SPEA2 with Provable Runtime Guarantees](https://mlsanity.com/paper/2606.12382/) (2026)

## Abstract (arXiv)

Evolutionary algorithms (EAs) have been widely and successfully applied to solve multi-objective optimization problems, due to their nature of population-based search. Population update, a key component in multi-objective EAs (MOEAs), is usually performed in a greedy, deterministic manner. That is, the next-generation population is formed by selecting the best solutions from the current population and newly-generated solutions (irrespective of the selection criteria used such as Pareto dominance, crowdedness and indicators). In this paper, we analytically present that stochastic population update can be beneficial for the search of MOEAs. Specifically, we prove that the expected running time of two well-established MOEAs, SMS-EMOA and NSGA-II, for solving two bi-objective problems, OneJumpZeroJump and bi-objective RealRoyalRoad, can be exponentially decreased if replacing its deterministic population update mechanism by a stochastic one. Empirical studies also verify the effectiveness of the proposed population update method. This work is an attempt to show the benefit of introducing randomness into the population update of MOEAs. Its positive results, which might hold more generally, should encourage the exploration of developing new MOEAs in the area.