# Runtime Analyses of Multi-Objective Evolutionary Algorithms in the Presence of Noise

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

## Key facts

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

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

- [Probabilistic Tools for the Analysis of Randomized Optimization Heuristics](https://mlsanity.com/paper/1801.06733/) (2018)
- [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)
- [Analysing the Robustness of Evolutionary Algorithms to Noise: Refined Runtime Bounds and an Example Where Noise is Beneficial](https://mlsanity.com/paper/1812.00966/) (2018)
- [Analysis of Evolutionary Algorithms in Dynamic and Stochastic Environments](https://mlsanity.com/paper/1806.08547/) (2018)

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

- [Stochastic Population Update Can Provably Be Helpful in Multi-Objective Evolutionary Algorithms](https://mlsanity.com/paper/2306.02611/) (2023)
- [Many Objective Problems Where Crossover is Provably Essential](https://mlsanity.com/paper/2412.18375/) (2024)
- [Already Moderate Population Sizes Provably Yield Strong Robustness to Noise](https://mlsanity.com/paper/2404.02090/) (2024)
- [Scalable Speed-ups for the SMS-EMOA from a Simple Aging Strategy](https://mlsanity.com/paper/2505.01647/) (2025)
- [A Block-Coordinate Descent EMO Algorithm: Theoretical and Empirical Analysis](https://mlsanity.com/paper/2404.03838/) (2024)

## Abstract (arXiv)

In single-objective optimization, it is well known that evolutionary algorithms also without further adjustments can tolerate a certain amount of noise in the evaluation of the objective function. In contrast, this question is not at all understood for multi-objective optimization. In this work, we conduct the first mathematical runtime analysis of a simple multi-objective evolutionary algorithm (MOEA) on a classic benchmark in the presence of noise in the objective functions. We prove that when bit-wise prior noise with rate p ≤ α/n, α a suitable constant, is present, the simple evolutionary multi-objective optimizer (SEMO) without any adjustments to cope with noise finds the Pareto front of the OneMinMax benchmark in time O(n2log n), just as in the case without noise. Given that the problem here is to arrive at a population consisting of n+1 individuals witnessing the Pareto front, this is a surprisingly strong robustness to noise (comparably simple evolutionary algorithms cannot optimize the single-objective OneMax problem in polynomial time when p = ω(log(n)/n)). Our proofs suggest that the strong robustness of the MOEA stems from its implicit diversity mechanism designed to enable it to compute a population covering the whole Pareto front. Interestingly this result only holds when the objective value of a solution is determined only once and the algorithm from that point on works with this, possibly noisy, objective value. We prove that when all solutions are reevaluated in each iteration, then any noise rate p = ω(log(n)/n2) leads to a super-polynomial runtime. This is very different from single-objective optimization, where it is generally preferred to reevaluate solutions whenever their fitness is important and where examples are known such that not reevaluating solutions can lead to catastrophic performance losses.