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

1 Introduction

Many real-world optimization problems consist of multiple, often conflicting objectives. For these, a single optimal solution usually does not exist. Consequently, a common solution concept is to compute a set of solutions which cannot be improved in one objective without worsening in another one (Pareto optima) and then let a decision maker select one of these.

Due to their population-based nature, evolutionary algorithms (EAs) are an obvious heuristic approach to such problems, and in fact, such multi-objective evolutionary algorithms (MOEAs) have been successfully applied to many multi-objective problems [Coello et al., 2007; Zhou et al., 2011].

Evolutionary algorithms are known to be robust against different types of stochastic disturbances such as noise or dynamic changes of the problem instance [Jin and Branke, 2005]. Surprisingly, as regularly pointed out in the literature [Liefooghe et al., 2007; Gutjahr, 2012; Gutjahr and Pichler, 2016], only very little is known on how MOEAs cope with such stochastic optimization problems. In particular, while it is known that single-objective evolutionary algorithms without any specific adjustments can stand a certain amount of noise in the evaluation of the objective function, we are not aware of any such result in multi-objective optimization.

We approach this question via the methodology of mathematical runtime analysis [Neumann and Witt, 2010; Auger and Doerr, 2011; Jansen, 2013; Zhou et al., 2019; Doerr and Neumann, 2020]. This field, for more than twenty years, has significantly enlarged our understanding of the working principles of all kinds of randomized search heuristics, including both MOEAs [Brockhoff, 2011] and single-objective evolutionary algorithms solving stochastic optimization problems [Neumann et al., 2020]. Despite this large amount of work, there is not a single runtime analysis discussing how a standard MOEA computes or approximates the Pareto front of a multi-objective problem in the presence of noise (and this is what we shall do in the present work). The only paper that conducts a mathematical runtime analysis of a MOEA in a noisy setting analyzes a combination of the adaptive Pareto sampling frameworks with the simple evolutionary multi-objective optimizer (SEMO) [Gutjahr, 2012], so this algorithm definitely is not anymore a standard MOEA.

To start closing this gap, we conduct a runtime analysis of a simple MOEA, namely the SEMO, on the classic benchmark problem ONEMINMAX, in the presence of onebit prior noise. We prove that when the noise rate is at most

α/n, where α is a suitable constant, then the population of this MOEA, despite the noise, after an expected number of O(n2 logn) iterations witnesses the full Pareto front. This is the same bound on the runtime that is known for the setting without noise [Giel and Lehre, 2010; Covantes Osuna et al., 2020]. We note that in comparable single-objective settings, not much more noise can be tolerated. For example, only for p = O(log(log(n))/n) it could be shown in [DangNhu et al., 2018] that the (1+1) EA retains its noise-free O(n logn) runtime on the ONEMAX benchmark. Already for p = ω(log(n)/n), the runtime is super-polynomial. Considering this and taking into account that the multi-objective ONEMINMAX problem is naturally harder (we aim at a population containing exactly one solution for each Pareto optimum), our result indicates that MOEAs cope with noise surprisingly well.

However, our work also shows one important difference to the noisy optimization of single-objective problems. Our result above assumes that each solution is evaluated only once, namely when it is generated. This possibly noisy objective value is stored with the solution unless the solution is discarded at some time. This approach is natural in that it avoids costly reevaluations, but it differs from the standards in single-objective evolutionary computation. Being afraid that a faulty fitness value can negatively influence the future optimization process, almost all works there assume that each time a solution competes with others, its fitness is reevaluated. That noisy fitness values without reevaluating solutions can significantly disturb the optimization process was rigorously shown for an ant-colony optimizer [Doerr et al., 2012a].

Given that in single-objective evolutionary computation it is more common to assume that solutions are evaluated anew when they compete with others, we also analyzed the runtime of the SEMO on ONEMINMAX under this assumption. While this avoids sticking to faulty objective values for a long time, our mathematical runtime analysis shows that this approach can only tolerate much lower levels of noise. We can prove an O(n2 log n) runtime only for p ≤ β/n2 , β a suitable constant, and we prove that for p = ω(log(n)/n2 ) the algorithms needs super-polynomial time to compute the full Pareto front of the ONEMINMAX benchmark. So clearly, the reevaluation strategy recommended in single-objective optimization is less suitable in multi-objective optimization (in addition to the significantly higher computational cost of a single iteration).

Overall, this first runtime analysis work of a standard MOEA in a noisy environment shows that MOEAs without specific adjustments are reasonably robust to noise and that such stochastic processes can be analyzed with mathematical means, but also that insights from the single-objective setting can be fundamentally wrong in multi-objective noisy optimization.

2 Previous Work

Given the success of evolutionary algorithms both in multiobjective and in stochastic optimization, there is a large body of literature on both topics. For the general picture, we refer to the surveys [Coello et al., 2007; Zhou et al., 2011] and [Jin and Branke, 2005; Bianchi et al., 2009].

Much less understood is the intersection of both areas, that is, howMOEAs solve stochastic optimization problems, see [Gutjahr, 2011, Section 4]. Interestingly, all works described there adapt the MOEA to deal with the stochasticity of the problem. This is justified for problems that have a strong stochasticity known in advance. However, it is known that evolutionary algorithms often can tolerate a certain amount of stochastic disturbance, in particular, noisy function evaluations without any adjustments (and hence, without that the user has to be aware of this noise). In contrast to single-objective optimization, we are not aware of any such result for MOEAs.

This being a theoretical work, we now describe the mathematical runtime analyses closest to our work. The mathematical runtime analysis of MOEAs was started in [Laumanns et al., 2002a; Giel, 2003; Thierens, 2003]. These and most subsequent works regarded artificial toy algorithms like the simple evolutionary multi-objective optimizer (SEMO) or the global SEMO (GSEMO). The hope is that results proven on such basic algorithms, or at least the general insights drawn from them, extend to more realistic algorithms. That this hope is not unrealistic can be seen, e.g., from the fact that the runtimes shown for the SEMO in [Laumanns et al., 2002b; Giel and Lehre, 2010] could much later be proven also for the NSGA-II [Zheng et al., 2022; Bian and Qian, 2022; Doerr and Qu, 2023], the most prominent MOEA.

For our work, naturally, the results on the ONEMINMAX benchmark are most relevant. In [Giel and Lehre, 2010], it was proven that the SEMO finds the Pareto front of this benchmark in an expected number of O(n2 log n) iterations. A matching lower bound was proven in [Covantes Osuna et al., 2020]. The O(n2 logn) upper bound also holds for the GSEMO (never formally proven, but easy to see from the proof in [Giel and Lehre, 2010]), the hypervolume-based (µ + 1) SIBEA with suitable population size [Nguyen et al., 2015], and the NSGA-II with suitable population size [Zheng et al., 2022]. For the NSGA-III, a runtime analysis exists only for the 3-objective version of ONEMINMAX [Wietheger and Doerr, 2023], but it is obvious that this result immediately extends to an O(n2 logn) bound in the case of two objectives. The main argument in all these analyses (which is not anymore true in the noisy setting) is that Pareto points cannot be lost, that is, once the population of the algorithm contains a solution with a certain Pareto-optimal objective value, it does so forever.

Due to their randomized nature, it is not surprising that EAs can tolerate a certain amount of stochastic disturbance. In the first runtime analysis of an EA for discrete search spaces in the presence of noise [Droste, 2004], Droste investigated how the (1 + 1) EA optimizes the ONEMAX benchmark in the presence of bit-wise prior noise with noise rate p (see Section 3.2 for a precise definition of this noise model). He showed that the runtime remains polynomial (but most likely higher than the well-known O(n logn) runtime of the noiseless setting) when p = O(log(n)/n). When p = ω(log(n)/n), a super-polynomial runtime results. These bounds have been tightened and extended in the future, in particular, an O(n logn) runtime bound for noise rate p = O(log(log(n))/n) with implicit constant small enough was shown in [Dang-Nhu et al., 2018]. The level of noise an algorithm can stand depends strongly on the problem, for example, for the LEADINGONES benchmark the (1+1) EA has a polynomial runtime if and only if the noise rate is at most p = O(log(n)/n2 ) [Sudholt, 2021]. We refer to [Neumann et al., 2020] for more results.

We note that all these works regard the standard version of the EA without any particular adjustments to better cope with noise. It is well-studied that resampling techniques can increase the robustness to noise [Akimoto et al., 2015; Qian et al., 2018; Doerr and Sutton, 2019], however, this requires the algorithm user to be aware of the presence of noise and have an estimate of its strength.

Reevaluating solutions: When running a standard EA in a noisy environment, there is one important implementation choice, namely whether to store the possibly noisy fitness of a solution or to reevaluate the solution whenever it becomes important in the algorithm. The latter, naturally, is more costly due to the higher number of fitness evaluations, but since most EAs generate more solutions per iteration than what they take into the next generation, this often is only a constant-factor performance loss. On the other hand, sticking to the objective value seen in the first evaluation carries the risk that a single unlucky evaluation has a huge negative impact on the remaining run of the algorithm.

The question which variant to prefer has not been discussed extensively in the literature. However, starting with the first runtime analysis of an EA in a noisy environment [Droste, 2004], almost all runtime analyses of EAs in a noisy environment assume that each solution is reevaluated whenever it plays a role in the algorithm, in particular, whenever solution qualities are compared.

The only example we are aware of where this is done differently is the analysis of how an ant-colony optimizer (ACO) solves a stochastic shortest path problem in [Sudholt and Thyssen, 2012]. This work regards a variant of the Max-Min Ant System [St ¨utzle and Hoos, 2000] with best-sofar pheromone update where the best-so-far solution is kept without reevaluation. While this algorithm was provably able to solve some stochastic path problems, it was not able to solve others (except possibly in exponential time). The same algorithm, but with the best-so-far solution being reevaluated whenever it competes with a new solution, was analyzed in [Doerr et al., 2012a] and it was shown to be able to solve many problems efficiently which could not be solved by the other variant.

Noisy evolutionary multi-objective optimization: While we apparently have a good understanding on how EAs cope with noise and how they can be used to solve multi-objective problems, there has been very little research on how EAs solve multi-objective problems in the presence of noise. The only mathematical runtime analysis in this direction is [Gutjahr, 2012]. It analyzes how the adaptive Pareto sampling framework together with a variant of the SEMO (called with suitable noiseless instances) allows to solve noisy instances. So like all other non-mathematical works on noisy heuristic multi-objective optimization, e.g., [Teich, 2001; Ding et al., 2006; Liefooghe et al., 2007; Boonma and Suzuki, 2009; Fieldsend and Everson, 2015; Rakshit and Konar, 2015], this work does not analyze how a standard MOEA copes with noise, but proposes a specific way how to solve noisy multiobjective optimization problems.

3 Preliminaries: Multi-objective Optimization of the ONEMINMAX Benchmark in the Presence of Noise

3.1 The ONEMINMAX Benchmark

In multi-objective optimization over a set X using an evaluation function g : X → Rd , we say that a vector x ∈ X is a Pareto optimal solution if there is no y ∈ X with g(x) ≺ g(y). We denote as X∗ the set of Pareto optimal vectors, and define the Pareto front as g(X∗ ). Note that we will use the partial order on Rd where x ⪯ y if and only if for all i ∈ [1..d], we have xi ≤ yi. The induced strict ordering will then be defined as x ≺ y ⇐⇒ (x ⪯ y ∧ x ̸= y).

The ONEMINMAX benchmark is a bi-objective optimization problem defined over the decision space X = {0, 1}n . It was introduced in [Giel and Lehre, 2010] as a bi-objective version of the classic ONEMAX benchmark. The objective function is defined as

where the first objective f(x) = ONEMAX(x) is the number of ones in x. The goal of the algorithms analyzed in this paper is to find a minimal subset of X which has a direct image by g equal to the Pareto front of X for this benchmark. Since any solution to the ONEMINMAX benchmark is Pareto optimal, the Pareto front of this problem is X∗ = {(k, n - k) | k ∈ [0..n]}.

3.2 One-bit Noise

In this article, we consider that every evaluation of an objective vector is subject to noise. Let p ∈ [0, 1] be the noise rate in the whole article.

We define the noisy vector evaluation function ˜x as the vector x but where a random bit uniformly chosen has been flipped with probability p. Each noisy evaluation is independent from one another. This noise model is known as one-bit noise.

For any function ϕ : X → Y , we define

It is therefore possible to replace the objective function g by its noisy version ˜ g in any evaluation.

3.3 Modified SEMOAlgorithms for Optimizing Noisy Objective Functions

When running an EA on a noisy problem, one can work with the first noisy fitness value received for a solution or to reevaluate it each time it is relevant. We present two versions of the same algorithm for these two possibilities. In all our algorithms, populations Pt or P ′ t are multisets. This is necessary

Algorithm 1: SEMO without reevaluation

1 xinit is uniformly chosen from {0, 1}n 2 P0 ← {xinit} 3 W0(xinit) ← ˜ g(xinit) 4 5 for t = 0 to∞do 6 Choose xt uniformly fromPt 7 Sample x′t from xt by flipping one uniformly chosen bit in xt 8 9 w ← ˜ g(x′t ) 10 11 if there is no x ∈ Pt such that w ≺ Wt(x) then 12 Pt+1 ← {x′t } 13 Wt+1(x′t ) ←w 14 15 foreach x ∈ Pt do 16 if Wt(x) ⪯̸ w then 17 Pt+1 ← Pt+1 ∪ {x} 18 Wt+1(x) ← Wt(x) 19 else 20 Pt+1 ← Pt 21 Wt+1 ←Wt

even for a SEMO algorithm (which stores at most one solution per objective value, and hence not multiple copies of an individual) since the noise fitness may let copies of an individual appear different due to their noise fitness.

SEMO Without Reevaluation

The first algorithm is the original SEMO algorithm, but it evaluates values of an element entering the population only once and save its value as long as this element stays in the population.

In Algorithm 1, we store the noisy evaluations of elements of Pt in Wt. The function Wt can be seen as a map that associates each element of Pt with its noisy value as computed at the time of its addition.

Note that we state this algorithm in a general way to deal with any multi-objective optimization. For ONEMINMAX, this algorithm could be simplified, since the condition in line 11 is always true and the inequality in line 16 becomes an equality.

SEMO With Reevaluation

We now describe a SEMO algorithm which reevaluates each solution in each iteration. Reevaluations have been recommended in noisy settings to avoid working with the same, faulty fitness value for a long time. For the SEMO, this requires some adjustments since now it does not suffice anymore to integrate the new offspring into the existing population. Due to the changing fitness values of individuals, it may also happen that two old solutions appear equal, so one of the two has to be removed.

This algorithm uses the elim function defined below. Given a multiset E ⊂ X and a possibly random evaluation func-

Algorithm 2: SEMO with reevaluation

1 P0 ← {xinit}, where xinit is uniformly chosen from {0, 1}n 2 3 for t = 0 to∞do 4 Choose xt uniformly fromPt 5 Sample x′t from xt by flipping one uniformly chosen bit in xt 6 7 P ′ t ← Pt ∪ {x′t } 8 Pt+1 ← elim(P ′ t , ˜ g)

Algorithm 3: Elimination function elim. Inputs are the initial set E and the evaluation function h. Output is G, a minimal Pareto-dominant sub-multiset of E.

1 G← ∅ 2 Temp ← ∅ 3 4 foreach x ∈ E selected in a random order do 5 vx ← h(x) 6 7 if there is no v ∈ Temp such that vx ≺ v then 8 foreach y in G with vy ⪯ vx do 9 G ← G \ {y} 10 G ← G ∪ {x} 11 Temp ← Temp ∪{vx} 12 return G

tion h : X → Y where Y is a partially ordered set, G := elim(E, h) will be a minimal sub-multiset of E that Pareto-dominates E. Pareto-dominance meaning that for every x ∈ E, there exists y ∈ G with h(x) ⪯ h(y), and minimality meaning that for every x, y ∈ G, h(x) and h(y) are not comparable.

For ONEMINMAX, the elim function can be simplified, with the condition in line 7 being always verified and the inequality in line 8 being an equality.

4 Runtime Analysis of the SEMOWithout Reevaluation

In this section, we analyze the expected number of iterations of the main loop needed to reach the Pareto front in the SEMO without reevaluation. Our main technical tool is drift analysis, that is, a collection of mathematical tools that allow to translate estimates for the one-step change Xt+1-Xt of a random process (Xt) into estimates for hitting times of this process. See [Lengler, 2020] for a recent survey on this method. Unfortunately, for reasons of space, we cannot present the proofs of our results in full detail. They can be found in the long version [Dinot et al., 2023].

We define the total time to reach the Pareto front as a stopping time

and show that there is a constant α such that for all noise rates p ≤ αn we have E[Ttotal] = O(n2 log(n)).

4.1 Observations on the SEMOWithout Reevaluation

The function Wt is the map from the elements of Pt to their noisy evaluated value at the moment they entered the population. We call Vt the first component of Wt, that is Wt = (Vt, n - Vt). At time t, two situations can occur.

• The noisy value of the offspring x′t is not in Vt(Pt), so it is added to the population and no element is removed.
• There is an element x ∈ Pt such that Vt(x) = Vt+1(x′t ), so the value is already in the set. In that case, x will be removed from the population and x′t will be added.

From these observations, we deduce the two following lemmas.

Proof. An element is removed from the population only if the offspring has the same value.

Lemma 2. Vt is one-to-one.

Proof. It is true at time t = 0 because there is only one vector in Pt. If it is true at time t, then the only possible collision is with the offspring x′t . In that case the element of the same value will be removed from the population and the offspring will be added. Vt+1 is still one-to-one. The result is true by induction.

Another important lemma is the following.

Proof. If f(x) = k, then because of one-bit noise Vt(x) ∈ {k - 1, k, k + 1}. Since Vt is one-to-one, there are at most 3 elements of value k by f .

4.2 Time Needed to Find the Extreme Values

We define

the first time when the extreme values are noisily found.

Theorem 4. There is a constant α > 0 such that if p ≤ αn , then

Proof. We denote as jt the minimum value of Vt(Pt) and we introduce the potential function ℓt = jt - 1∃x∈Pt,Vt(x)=f(x)=jt +1. This variable equals jt+1, but with a bonus downward if the unique element x with Vt(x) = jt is correctly evaluated, that is f(x) = jt. We analyze the drift, that is the expected change of the process ℓt.

We consider first the case where f(x) = jt.

• The probability of selecting x as a parent for mutation is 1 |Pt| . The probability that its offspring has a lower value is jt n (namely, selecting a 1 in x and flipping it to a 0). The probability of correctly evaluating the offspring is 1-p. The overall probability of this event is jt(1-p) n|Pt| . In that case ℓt - ℓt+1 = 1. Therefore, when f(x) = jt, the downward component of the drift is at least jt(1-p) n|Pt| .
• For the upward component of the drift, since jt+1 ≤ jt as stated in Lemma 1, a negative shift only happens if the offspring x′t is wrongly evaluated to jt. We would have jt+1 = jt but 1∃x∈Pt+1,Vt+1(x)=f(x)=jt = 0 and ℓt - ℓt+1 = -1. Since in general Vt(x) ∈ {f(x) - 1, f(x), f(x)+1}, the value of the offspring is jt -1 or jt + 1. The mutation is also one-bit, so the parent xt at time t must be of value jt - 2, jt or jt + 2. The value jt - 2 is not an option, as the noisy value of xt would be lower than jt - 1 so strictly lower than jt, so there is at most 6 elements verifying this property according to Lemma 3. The probability of selecting one of those to create the offspring is lower than 6 |Pt| . The probability of this offspring to be wrongly evaluated to jt is lower than p.

Now consider the case where f(x) ̸= jt. In that case, ℓt - ℓt+1 ≥ 0 so the drift can only be downward. With similar arguments, we can show that in that case the drift is at least jt(1-p) n|Pt| which is greater than jt(1-p) n|Pt| - 6p |Pt| .

In both cases, the drift is greater than

This is enough to conclude by the multiplicative drift theorem [Doerr et al., 2012b] that the lowest value is reached in O(n2 log(n)) when p ≤ 1 14n . As a consequence of Lemma 1, it will remain in Vt(Pt). Symmetrically, the time to reach the highest value is identical.

4.3 Filling the Pareto Front Once the Extreme Values are Found

To derive the total time, we additionally analyze the average time to fill the full Pareto front after the extreme values are found.

Theorem 5. We consider the same algorithm, but where the extreme elements are initially in the set, that is 0, n ∈ V0(P0). We note this event Y0. Then there exists a constant α > 0 such that

Proof. The proof relies on the fact that since the extreme values have been found, we know there are elements x, y ∈ Pt verifying Vt(x) = 0, Vt(y) = n so f(x) ≤ 1 and f(y) ≥ n - 1.

Since x ∈ Pt, [0..⌊ n2 ⌋] ∩ f(Pt) is non-empty. So there is an element z ∈ Pt such that f(z) = m - 1. The probability of selecting it to generate the offspring x′t is 1 |Pt| ≥ 1 n+1 . The probability that this offspring ends up with a real value m is n-f(z) n ≥ 12 . The probability of evaluating correctly this offspring is 1 - p. A symmetrical argument can be made for [⌈ n2 ⌉..n - 1] \ f(Pt) which yields the same result.

Hence, we see that the variable counting elements in the population that are not extreme elements and are correctly evaluated features an upward drift of at least 1-p 2n . For the downward drift, observe that no more than one element is deleted at each step, and that elements that are correctly evaluated can only be lost if the offspring is miss-evaluated, which happens with probability p. Thus, the total drift on this count variable is at least 1-p 2n -p.

As for the variable counting correctly evaluated extreme elements, an argument similar to the proof of Theorem 4 shows it features a positive drift component of at least 1 n+1 1n (1 - p) and a negative drift of no more than 12p n , and so a total drift of at least 1 n+1 1n (1 - p) - 12p n .

For a well-chosen constant α > 0, if p ≤ αn then both drifts are positive. By considering a weighted sum of the two count variables, with a weight of 1 for the first and a weight of n for the second, the additive drift theorem [He and Yao, 2001] yields the desired result.

So, the total runtime of the SEMO without reevaluation is O(n2 log(n)) + O(n2 ) = O(n2 log(n)) as announced.

We observe that this second phase of the run is finished in a relatively short time. The reason for this is that once we have the extremal elements in the population, we can generate missing solutions (in particular, those which have been lost due to faulty fitness evaluations) from a neighboring solution closer to the boundaries. This is relatively easy since mutation has a constant probability to generate the desired offspring from such a parent. Here we profit from the diversity mechanism of the SEMO, which tries to keep one solution per objective value in the population. This seems to be the main reason for the relatively high robustness of the SEMO to noise, and we would speculate that other MOEAs profit from their diversity mechanisms (needed to construct the whole Pareto front) in a similar fashion.

5 Runtime Analysis of the SEMOWith Reevaluation

In this section, we analyze the expected number of iterations of the main loop needed to reach the Pareto front in the SEMO with the SEMO with reevaluation 2. We define the stopping

and show the following theorem.

Theorem. There is a constant β > 0 such that the following holds. For all noise rates p ≤ β n2 , the SEMO with reevaluations finds the complete Pareto front of the ONEMINMAX

benchmark in expected time

We will assume in the whole section that p ≤ β n2 , with β > 0 a small enough constant. We use Pt for the population at time t, P ′ t = Pt ∪ {x′t } for the population plus the mutated vector. Lt is the cardinality of f(Pt) and L′t the cardinality of P ′ t . Some of these notations are already used in the definition of Algorithm 2.

5.1 Time to Find the Extreme Values

Here, we define Tex = min{t | 0, n ∈ f(Pt)} in terms of real values. Contrary to the other algorithm, these extreme values can be lost because of the noisy reevaluations. We show that still E[Tex] = O(n2 log(n)).

To prove this result, we consider the variable dt = n + min f (Pt)-max f (Pt) and apply the multiplicative drift theorem [Doerr et al., 2012b] to it. We note that the mutation step gives a drift (towards zero) of order at least dt n2 , same as in a non-noisy setting. Different from the noiseless case, the selection can then lead to drift away from zero of order O(p). Note that in any case, dt can change by at most one. By our assumption on p the drift into the wrong direction is small compared to the drift towards zero, so asymptotically we have a "multiplicative" drift of order at least dt n2 , which allows a straight-forward application of the multiplicative drift theorem to prove the announced result.

5.2 Computing the Pareto Front Once the Extreme Values are Found

We deal with the last phase by regarding an artificially modified process of the original SEMO with reevaluation. We denote this new process as the K-extreme values keeping SEMO, K ∈ N ∪ {+∞}. This process is identical to the SEMO with reevaluation, except that it will tzappend the extreme elements to the population at the end of each iteration if they have been lost and if less than K iterations have been executed. Variables related to this new process feature a hat and a super-index K (e.g. ˆ P K t ). In the whole subsection, we will use the event Z0 = ({0, n} ⊂ f(P0)). We also define Lt as the cardinality of f(Pt).

By using the additive drift theorem [He and Yao, 2001] on the variable ˆLKt , we show the following lemma.

Lemma 6.

The following lemma shows that the two algorithms behave in the same way with high probability.

Lemma 7. For any K ∈ N, we have

Indeed, of the classical process does not lose its extreme values in the K first iterations, then it is identical to the Kextreme values keeping process.

We can finally deduce the last result.

Lemma 8. There exist constants M > 0 and µ ∈ (0, 1) such that for any n ∈ N, with t0 = Mn2 log(n) and any distribution π of the initial population P0,

This lemma states that the probability for the process, starting in any position, to end in time t0 = O(n2 log(n)) time is bounded by a constant. Therefore, the average number of phases of length t0 is constant, hence the final result.

6 Lower Bound on the SEMOWith Reevaluation

In this section, we will show that the previous β n2 bound for p for the SEMO with reevaluation to run in O(n2 log(n)) is nearly tight. Namely, if p = ω( log(n) n2 ) and for some constant λ ∈ (0, 1) we have p ≤ λn , then the runtime is superpolynomial.

Here, we will use the notation from the previous section. Our main ingredient for the proof will be the simplified drift theorem [Oliveto and Witt, 2011; Oliveto and Witt, 2012] used on the random sequence (Lt)t∈N, where Lt = |f(Pt)|.

In the whole proof, we will assume that p = ω( log(n) n2 ) and that there exists a constant λ ∈]0, 1[ such that p ≤ λn .

Lemma 9. We denote an = max(n + 1 - βpn2 , 3n 4 ), with β > 0 to be determined. There exists a constant δ > 0 such that E[Lt - Lt+1 | Lt, Lt ≥ an] ≥ δnp.

This lemma indicates the presence of a negative drift of Lt. Indeed, when that variable is close to n, each wrong evaluation will cause on average a deletion. This effect will dominate the gains from the mutation if the noise rate is big enough. We then show that

These are the two hypotheses for the Simplified Drift Theorem, as stated in [Oliveto and Witt, 2012]. The theorem implies the existence of a constant B > 0 such that Pr[Ttotal ≤ 2Bpn2 ] ≤ 2-Ω(pn2 ) . As pn2 = ω(log(n)), this yields the final result.

7 Conclusion

We conducted the first mathematical runtime analysis, and to the best of our knowledge also the first analysis at all, aimed at understanding how MOEAs without particular adjustments behave in the presence of noise. Taking the SEMO algorithm and the ONEMINMAX benchmark with one-bit noise as an example simple enough to admit a mathematical analysis, we show that noise rates up to p = O(1/n) can be tolerated without suffering from an asymptotic increase of the expected runtime (whereas runtime we regard the time it takes until for the first time the population of the algorithm witnesses the full Pareto front). This robustness is very close to the p = O(log(log(n))/n) noise tolerance known for the much simpler single-objective ONEMAX problem and suggests that MOEAs, despite the more complex problem of finding the whole Pareto front, can stand similar noise levels as singleobjective EAs.

Interestingly, our result only holds when solutions are evaluated only once and the algorithm then continues with this, possibly faulty, objective value. If solutions are reevaluated whenever they are compared to other solutions (here in each iteration), then any noise rate p = ω(log(n)/n2 ) leads to a super-polynomial runtime. This is in drastic contrast to single-objective evolutionary computation, where the general recommendation (backed up by an analysis of an ant colony optimizer) is to reevaluate each solution when its fitness is relevant so that a single faulty fitness evaluation cannot harm the future optimization process for a long time.

From the proofs of our results we are optimistic that our general finding that MOEAs without particular adjustments are robust to a moderate amount of noise is not restricted to the particular setting we analyzed, but holds for a broad range of algorithms and benchmarks. A reasonable next step to support this belief would be to regard the global SEMO algorithm (using bit-wise mutation instead of one-bit flips) and a bit-wise noise model (where the fitness observed for x is the fitness of a search point obtained from x by flipping each bit independently with probability q = p/n). With this scaling, we would expect very similar results to hold as shown in this work. We note that this appears to be a problem very close to ours, but past research has shown that both global mutation in MOEAs and bit-wise noise can render mathematical analyses much harder (different from the SEMO, there is no good lower bound for the global SEMO on the LOTZ benchmark [Doerr et al., 2013]; the first mathematical runtime analysis in the presence of noise [Droste, 2004], namely one-bit noise, was extended to bit-wise noise only more than ten years later [Gießen and K¨otzing, 2016] and with much deeper methods).

A second interesting direction to extend this work would be by regarding other problems. The ONEMINMAX problem has the particular properties that all solutions lie on the Pareto front and the one-bit flips are sufficient to explore the whole front. Hence analyses for the COCZ or LOTZ benchmarks having non-Pareto optimal solutions [Laumanns et al., 2004] or the ONEJUMPZEROJUMP benchmark having larger gaps in the Pareto front [Doerr and Zheng, 2021] would be very interesting. Understanding how existing analyses for combinatorial optimization problems such as [Neumann, 2007; Cerf et al., 2023] extend to the noisy setting could be a subsequent step.

A third interesting direction for future research would be to regard posterior noise models (where the noisy objective value of a search point is its true objective value modified in some stochastic way, e.g., by adding Gaussian noise). For single-objective evolutionary algorithms, often comparable results could be obtained with similar arguments [Gießen and K¨otzing, 2016; Dang-Nhu et al., 2018]. Since posterior noise can lead to objective values that cannot be obtained as noiseless fitness values, we have some doubts that our results extend to posterior noise as well. In particular, we would speculate that for posterior noise, different from what our result suggests for prior noise, reevaluating search points is the better strategy as otherwise it is not clear how to remove a noisy objective value that cannot occur as noiseless one.

Acknowledgments

This work was supported by a public grant as part of the Investissements d'avenir project, reference ANR-11-LABX0056-LMH, LabEx LMH and a fellowship via the International Exchange Program of ´Ecole Polytechnique.