Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary Algorithm

1 Introduction

Many real-world optimization problems are characterized by several, often conflicting objectives. A common solution concept for such multi-objective optimization problems is to compute a diverse set of Pareto optima (solutions which cannot be improved in one objective without compromising in another objective) and let a human decision maker select one of these. Due to their population-based nature, multi-objective evolutionary algorithms (MOEAs) are among the most prominent approaches to such problems and have found applications in numerous subfields of multi-objective optimization [Coello et al., 2007; Zhou et al., 2011].

The mathematical runtime analysis of MOEAs was started around 20 years ago [Laumanns et al., 2002; Giel, 2003; Thierens, 2003]. It has gained considerable momentum in the last years, among others, with analyses of classic algorithms such as the NSGA-II, NSGA-III, SMS-EMOA, and SPEA2 [Zheng et al., 2022; Bian and Qian, 2022; Wietheger and Doerr, 2023; Bian et al., 2023; Ren et al., 2024; Opris et al., 2024; Wietheger and Doerr, 2024; Alghouass et al., 2025; Doerr et al., 2025a; Deng et al., 2025; Li et al., 2025; Opris, 2025] or works discussing how MOEAs can solve submodular problems [Qian et al., 2019; Qian et al., 2020; Crawford, 2021; Do et al., 2023].

The by far dominant algorithm in the rigorous analysis of MOEAs is the global simple evolutionary multi-objective optimizer [Giel, 2003] (GSEMO). Due to its apparent simplicity, it was the first MOEA for which mathematical runtime analyses were conducted, and it is still often the first algorithm for which new phenomena are discovered, see, e.g., [Dinot et al., 2023; Dang et al., 2024] for recent examples. At the same time, it is a central algorithm, and many other algorithms, in particular in the area of submodular optimization, build on it. For example, algorithms such as POSS (Pareto Optimization for Subset Selection) [Qian et al., 2015], POMC (Pareto Optimization for Monotone Constraints) [Qian et al., 2017], and POMS (Pareto Optimization for Multiset Selection) [Qian et al., 2018] are all variants of the GSEMO applied to a suitable bi-objective formulation of the submodular problem of interest.

Despite this impressive body of theoretical works on the GSEMO, a real understanding of the working principles of this algorithm is still missing. This is most visible from the fact that there are almost no lower bounds matching the existing runtime guarantees (see Section 2 for a detailed discussion of this point). The reason is that for matching bounds, a deeper understanding of the population dynamics is necessary. This is particularly crucial for the GSEMO with its dynamic population size (note that the probability to choose a particular individual as parent is the reciprocal of the population size).

Our contribution: In this work, we greatly expand our understanding of the population dynamics of the GSEMO. To this end, we study how this algorithm optimizes the classic CountingOnesCountingZeros (COCZ) benchmark. For readers less familiar with the area of runtime analyses, we note that it is the established approach of this field to study how a specific randomized search heuristics solves a wellunderstood benchmark problem, and from this derive insights into the working principles of the heuristic. All runtime analysis works cited above follow this approach.

We give more details on our new understanding of the population dynamics later (Section 4) when we have made precise the GSEMO algorithm and the COCZ benchmark, and now only describe two implications. First, we indeed succeed in proving a lower bound of Ω(n2 log n) (Theorem 4), which matches the classic upper bound of [Laumanns et al., 2002; Giel, 2003]. This is the first tight lower bound for a benchmark problem in which reaching the Pareto front is non-trivial (as opposed to, e.g., the OneMinMax benchmark, where all solutions are on the Pareto front). Second, we also gain a deeper understanding on how difficult it is to reach the Pareto front. Whereas previously the time to find the first solution on the Pareto front was estimated by O(n2 logn), we prove that O(n2 ) iterations suffice with high probability to reach the Pareto front and to compute any linear fraction of it (Corollary 8).

Our results are made possible by a number of new arguments. The most interesting one is that we add dummy individuals to the population to reach a population size equal to the maximum possible size. If such a dummy individual is chosen as parent, this iteration has no effect (but is counted as iteration). This argument helps overcome the changing population size of the original GSEMO. What is interesting is that this argument, which slows down the original algorithm, can be used to prove lower bounds on the runtime. The reason is that we exploit this argument not to estimate times directly (which is not possibly due to the unclear deceleration from the dummy individuals) but only to understand the shape of the population in the objective space. We are optimistic that this argument, and our other new proof ideas, will be useful in future runtime analyses of MOEAs as well. As a first support for this claim, we show that our methods also give a tight lower bound for the runtime of the GSEMO on the OJZJk benchmark for all k (where previous works could not analyze the cases k = 2 and k = 3) and that all our results extend to the SEMO algorithm.

2 Previous Works

In the interest of space, we concentrate on the previous works most relevant for ours. For a general introduction to MOEAs and their success in applications, we refer to [Coello et al., 2007; Zhou et al., 2011].

We refer to [Neumann and Witt, 2010; Auger and Doerr, 2011; Jansen, 2013; Zhou et al., 2019; Doerr and Neumann, 2020] for introductions to mathematical runtime analyses of randomized search heuristics. We note here that the typical approach in this area is to analyze, with mathematical means, how a specific heuristic solves a particular, often artificial, problem, and to derive from this analysis a deeper understanding of the working principles of the algorithm. Such works have successfully detected strengths or weaknesses of algorithms (e.g., the NSGA-II has intrinsic difficulties with three or more objective [Zheng and Doerr, 2024]), have proposed suitable settings for parameters (e.g., the cutoff time of automated algorithm configurators [Hall et al., 2022]), or have led to the design of novel algorithms (e.g., a variant of the SMS-EMOA with stochastic selection of the next parent population [Bian et al., 2023]).

Already the first mathematical runtime analysis of a MOEA proved an O(n2 log n) runtime guarantee for the simple evolutionary multi-objective optimizer (SEMO), a predecessor of the GSEMO, on the COCZ benchmark [Laumanns et al., 2002], see [Laumanns et al., 2004] for the journal version. The same bound for the GSEMO followed a year later [Giel, 2003]. As we will see in this work, both bounds are tight. When looking at the proofs, both results estimate both the time to find the first Pareto optimum and the subsequent time to compute the full Pareto front by O(n2 log n), whereas we shall show that the Pareto front is reached, and in fact any constant fraction of it is computed, in time O(n2 ). Since then, many more upper bounds on runtimes of the (G)SEMO were shown, and later also for more complex algorithms like the NSGA-II, only very few lower bounds exist, and these only apply to very specific situations.

The first lower bound, matching their own upper bound, is that the SEMO optimizes the LOTZ benchmark in time Ω(n3 ) [Laumanns et al., 2002]. While clearly non-trivial, this result heavily exploits that the SEMO with its one-bit mutation operator cannot generate incomparable solutions until a solution on the Pareto front is found, and from that point on, the population always forms a contiguous interval of the Pareto front. With these restricted population dynamics, proving lower bounds was possible already in the first runtime analysis paper on MOEAs. For the GSEMO, the population dynamics are more complex. In particular, at any time, solutions not comparable with the parent can be generated. Consequently, despite attempts in [Doerr et al., 2013], no interesting lower bounds exist for the GSEMO on LOTZ.

The first tight lower bound for the GSEMO on a classic benchmark was given by [Doerr and Zheng, 2021], who showed that the GSEMO optimizes the OJZJk benchmark in time 32 enk+1 ± o(nk+1 ) when the gap parameter satisfies 4 ≤ k = o(n). That such a tight bound is possible builds on particular properties of this benchmark. The Pareto front of the OJZJk benchmark consists of an easy-to-explore inner part, from which two solutions are separated by difficult-tocross gap of size k. When assuming k ≥ 4 as in this result, it is easy to argue that the inner part is computed before the gaps are traversed, and hence the traversal of the gaps is slowed down by the then linear-size population. This argument breaks down for smaller values of k, and this is why no tight lower bounds existed in this case prior to this current work. The only other tight lower bound for the GSEMO on a classic benchmark we are aware of is the Ω(n2 logn) bound for the OneMinMax benchmark [Bossek and Sudholt, 2024]. This benchmark has the particularity that all solutions are Pareto optimal, hence the optimization process lacks the phase of advancing towards the Pareto front, which was the most demanding one in our work. Recently, lower bounds where proven for the runtime of the NSGA-II [Doerr and Qu, 2023], but again, these only regard the OneMinMax and OJZJk benchmarks; also, clearly, the population dynamics of the NSGA-II with its fixed population size are very different from the GSEMO. In summary, it is safe to say that there are very few interesting lower bounds for the GSEMO, and that this is caused by the difficulty of understanding the population dynamics of this algorithm.

3 Preliminaries

We now provide some general notation and definitions for multi-objective optimization, define the algorithms (Section 3.1) and benchmark functions (Section 3.2) that used in this study, and state the mathematical tools needed in our analysis (Section 3.3).

Let Z denote the integers, N := Z≥0 the natural numbers (including 0), and R the reals. For all a, b ∈ R, let [a..b] := [a, b] ∩ Z and [a] := [1..a].

We study pseudo-Boolean bi-objective maximization, that is, the maximization of objective functions f : {0, 1}n → R2 of problem size n ∈ N≥2. We call each x ∈ {0, 1}n an individual, and f(x) the objective value of x. For all i ∈ [n], we denote the value of x at position i by xi.

We compare objective values via the weak and strong dominance relationships, which are (strict) partial orders. For all objective values u, v ∈ R2 , we say that u weakly dominates v (written as u ⪰ v) if and only if u1 ≥ v1 and u2 ≥ v2. If in addition u ̸= v, then we say that u strictly dominates v (written as u ≻ v). We say that u and v are incomparable if neither weakly dominates the other. We extend this terminology to individuals, where it then refers to the individuals' objective values.

Given an objective function f, we call the set of maximal objective values (with respect to dominance) the Pareto front of f, that is, the set {f(x) | x ∈ {0, 1}n ∧ ∄y ∈ {0, 1}n : f(y) ≻ f(x)}.

3.1 The Algorithms SEMO and GSEMO

We study both the simple evolutionary multi-objective optimizer [Laumanns et al., 2002] (SEMO) and the global SEMO [Giel, 2003] (GSEMO), which only differ in how they create new solutions (Algorithm 1).

The (G)SEMO maintains a population of individuals, which will contain a maximum subset of non-dominated solutions among all solutions seen so far. This population is initialized with a single individual drawn uniformly at random from the search space. In each iteration, one individual is selected uniformly at random (the parent) and used to create a new individual (the offspring) via mutation, that is, a small random perturbation of the parent. Afterward, the algorithm removes all individuals from the population that are weakly dominated by the offspring, and the offspring is added to the population if it is not strictly dominated by a member of the population. This main loop is repeated until a user-defined termination criterion is satisfied.

The difference between the SEMO and the GSEMO is how they create the offspring y from the parent x ∈ {0, 1}n . The SEMO uses 1-bit mutation, which chooses a position i ∈ [n] uniformly at random and copies x except for position i, which is flipped to the other value. That is, for all j ∈ [n] ∖ {i}, we have yj = xj, for the i-th position we have yi = 1 - xi. The GSEMO uses standard bit mutation, which decides independently for each position whether to flip the bit (with Algorithm 1: The (G)SEMO algorithm [Laumanns et al., 2002; Giel, 2003] for maximization of a given bi-objective function f : {0, 1}n → R2 . The SEMO uses 1-bit mutation, the GSEMO standard bit mutation (see also Section 3.1).

• 10
• 1 x(0) ← an individual from {0, 1}n chosen uniformly at random; 2 P (0) = {x(0) }; 3 t ← 0; 4 while termination criterion not met do 5 choose x(t) from P (t) uniformly at random; 6 y(t) ← mutation(x(t) ); 7 Q(t) ←P (t) \ {z ∈ P (t) : f(y(t) ) ⪰ f(z)}; 8 if ̸ ∃z ∈ Q(t) : f(z) ≻ f(y(t) ) then P (t+1) ← Q(t) ∪ {y(t) }; 9 else P (t+1) ← Q(t) ; t ← t + 1;

probability 1n ) or not. That is, for all i ∈ [n] independently, we have Pr[yi = xi] = 1 - 1n and Pr[yi = 1 - xi] = 1n .

Runtime. As common in the runtime analysis of MOEAs, we define the runtime of the (G)SEMO maximizing f as the (random) number of evaluations of f until the objective values of the population contain the Pareto front of f for the first time (we say that the population covers the Pareto front). To this end, we assume that the objective value of an individual is evaluated once, namely when it is created. For our definition of runtime to make sense, we assume that the algorithm is never stopped. Since the (G)SEMO creates exactly one individual in each iteration and creates a single individual initially, the runtime is one plus the number of iterations until the population covers the Pareto front of f for the first time.

3.2 The COCZ Benchmark

The function COUNTINGONESCOUNTINGZEROS (COCZ) [Laumanns et al., 2002; Laumanns et al., 2004] is defined for even problem sizes n ∈ N≥2. For all x ∈ {0, 1}n , we have

This popular benchmark models common goals (maximizing the number of ones in the first half of the bit-string) and conflicting goals (maximizing the number of ones resp. zeros in the second half). Formally, let g1, g2 : {0, 1}n → R denote the number of ones in the first and in the second half of the bit string, respectively. Then, for all x ∈ {0, 1}n ,

With this notation, it is immediate that the objective space of the COCZ problem is COCZ({0, 1}n ) = {(i + j, i + n/2 - j) | i, j ∈ [0..n/2]}. Only the objective values with g1(x) = n/2 are Pareto optimal, that is, the Pareto front is {(n/2 + j, n - j) | j ∈ [0..n/2]} and has size n/2 + 1.

Most objective values, namely all with g1(x) ∈ [0..n/2 - 1], and hence most individuals, are not Pareto-optimal. This is a notable difference to benchmarks such as OneMinMax and OJZJ, where all or most individuals are Pareto-optimal and, in particular, random individuals with high probability lie on the Pareto front.

For COCZ, we finally note that for all i ∈ [0..n/2], individuals with exactly i ones in their first half are either incomparable or have the same objective value. We use this property in our proofs in Section 4.

3.3 Mathematical Tools

In our analysis, we are mostly concerned with bounding the tails of stopping times. To this end, we decompose a stopping time into smaller parts, each of which denotes a certain phase of the entire process. Theorem 1 provides us with strong guarantees when understanding the separate phases well.

Theorem 1 ([Witt, 2014]). Let k ∈ N≥1, and let {Di}i∈[k] be independent geometric random variables with respective positive success probabilities (pi)i∈[k]. Let T ⋆ := ∑i∈[k] Di, s := ∑i∈[k] 1 p2i , and pmin := min{pi | i ∈ [k]}. Then for all λ ∈ R≥0, we have

In order to conveniently estimate the sums appearing in applications of Theorem 1, we use the following well-known estimates.

Theorem 2 ([Cormen et al., 2001, Inequality (A.12)]). Let g : R → R be a monotonically non-increasing function, and let α, β ∈ R with α ≤ β. Then

Last, the following classic Chernoff bound is used to estimate the objective values of initial solutions.

Theorem 3 ([Chernoff, 1952]). Let k ∈ N≥1, and let {Xi}i∈[k] be independent random variables taking values in [0, 1]. Let X⋆ = ∑i∈[k] Xi and δ ∈ [0, 1]. Then

4 Runtime Analysis on COCZ

Our main result is Theorem 4 below, which proves that the (G)SEMO (Algorithm 1) optimizes the COCZ benchmark (equation (1)) with high probability and thus also in expectation in Ω(n2 logn) objective-function evaluations. This matches the O(n2 logn) upper bound by [Laumanns et al., 2004], resulting overall in a tight runtime bound of Θ(n2 log n) expected objective-function evaluations.

Theorem 4. With probability 1 - Θ(n-1 ), the (G)SEMO maximizes COCZ in at least Ω(n2 logn) objective-function evaluations.

Another interesting result of our analysis detailed in the following is that the (G)SEMO achieves a linear population size on the Pareto front of COCZ with high probability after only O(n2 ) iterations (Corollary 8). Previously, this time was estimated pessimistically only as O(n2 log n).

In order to prove Theorem 4, we need to closely follow the population size of the (G)SEMO during the run. Although the (G)SEMO only creates a single offspring each iteration (and thus only evaluates the objective function a single time), the population size and its composition affect the algorithm's runtime crucially. If the population size is large, progress is only made quickly if the probability is high to select a parent that can be likely turned into a useful offspring. This probability, in turn, relies on where the current population is. For COCZ, assume that the entire population is already on the Pareto front, that is, for each individual x in the population, we have g1(x) = n/2. If the g2-values of the population consist of a contiguous interval, that is, there is an i ∈ [n/2] such that for each j ∈ [i, n/2 - i], there is an x in the population such that g2(x) = j, then new solutions are only created likely if individuals with a g2-value close to the interval borders are chosen. 1 The situation is different if we assume that the individuals have more spread-out g2-values, that is, if there are some g2-values in the interval [i, n/2 - i] that are not covered by the current population. Then, each individual that is close to the border of some g2 interval can be useful for finding novel objective values.

A central question to proving our main result (Theorem 4) is which composition the population of the (G)SEMO has once it reaches the Pareto front (and a short time thereafter). In order to answer this question satisfactorily, we view the progress of the algorithm covering the Pareto front of COCZ in two dimensions, namely, with respect to the maximum g1value in the population and with respect to the extremal g2values in the population. The g1 quantity translates to how close the population is to reaching the Pareto front, as each individual with a g1-value of n/2 is Pareto-optimal. The g2 quantity translates to how close the population is to reaching the values in the second objective that are hardest to achieve, that is, n/2 (having only zeros in the second half) and n (having only ones in the second half).

In our analysis, we optimistically assume, roughly, that once an individual reaches the Pareto front, all other individuals are also placed there immediately by setting their number of ones in the first half to the maximum value of n/2. 2 Thus, tracking the extremal g2-values tells us from this moment how close the algorithm is to covering the entire Pareto front. In a nutshell, we show that once the algorithm reaches the Pareto front, the extremal g2-values are still at least order √n away from the borders of the g2 interval (Lemma 9). From there on, based on a coupon collector argument, the algorithm still requires order n log n iterations with useful parents in order to cover the entire Pareto front. Since we also prove that the (G)SEMO has a population size of at least n4 once it reaches the Pareto front (Corollary 8), the probability to choose a useful parent is in the order 1n . Thus, it still takes Ω(n2 logn) iterations until the algorithm covers the entire front (Lemma 10). Reaching the Pareto front is done faster than that (Lemma 7), and thus Theorem 4 follows.

1 For the SEMO, even only the two extreme individuals with a g2-value of i or n/2 - i can create a novel objective values.

2 Actually, we place all individuals on the Pareto front after a time that is a bit longer than it takes the algorithm to reach the Pareto front, but the main idea remains the same.

A modified (G)SEMO algorithm. A main challenge in our proof strategy is to track the exact population size of the algorithm while there are individuals not on the Pareto front. This is due to such individuals being potentially dominated by better solutions and then removed. Once the entire population is on the Pareto front, this problem vanishes, as solutions either have the same objective value or are incomparable. In order to estimate the population size more easily until the Pareto front is reached, we make the following important observation: We only aim to show that the extremal g2-values are sufficiently far from n/2 and n before the (G)SEMO reaches the Pareto front. This is a relative statement, essentially comparing the progress made with the maximum g1-value in the population to the progress made with the extremal g2-values. Thus, we can arbitrarily modify the (G)SEMO as long as we make sure that this relative order is not harmed. We call the resulting algorithm the modified (G)SEMO.

The modified (G)SEMO is identical to the (G)SEMO (Algorithm 1) except for line 5, which is replaced by the following procedure, using the notation of the pseudocode. Choose a value i ∈ [0.. n2 ] uniformly at random. Check if {z ∈ P (t) | g2(z) = i} is empty. If it is, continue with the next iteration. Otherwise, note that the set contains exactly one individual x(t) , as all individuals with equal g2-value are comparable and P (t) thus contains at most one such individual. Continue with line 6 exactly seen in Algorithm 1, using x(t) . Note that the resulting modified (G)SEMO resembles a version of the original (G)SEMO that may add some pointless iterations not modifying the algorithm's state. Thus, in particular, each upper bound on the runtime of the modified (G)SEMO is also an upper bound on the runtime of the original (G)SEMO.

A key observation is that if we consider a run of the modified (G)SEMO and remove all iterations in which an index i with no corresponding individuals is chosen, the algorithm is identical of the original (G)SEMO. Thus, any statements about the states of either algorithm based on stopping times defined only on algorithm states are identical. This allows us to translate results from the modified (G)SEMO to the original one, and it addresses the challenge above of estimating the population size of the original (G)SEMO very closely. Once the modified (G)SEMO reaches the Pareto front and has a linear population size, we switch back to the original (G)SEMO in order to derive a runtime bound for this exact algorithm.

As outlined above, we compare the time it takes the modified (G)SEMO to reach the Pareto front (measured via the maximum g1-value in the population) and the time it takes to reach extremal g2-values in the order of √n. More specifically, we show that the modified (G)SEMO reaches the Pareto front with high probability in O(n2 ) iterations (Lemma 6), whereas it takes Ω(n2 logn) iterations until the g2-values progressed sufficiently far (Lemma 9). In addition, we show that once the modified (G)SEMO reaches the Pareto front, it reaches a population size linear in n within the same order of time (Lemma 7). Combining these statements, we get with high probability that the modified (G)SEMO (and thus also the original (G)SEMO) has a linear population size before the extremal g2-values are close to covering the entire interval.

We recall that all upper bounds on the iterations for the modified (G)SEMO algorithm also hold for the original (G)SEMO algorithm.

Progress of the modified (G)SEMO on the g1-values. We begin by showing that the modified (G)SEMO quickly reaches the Pareto front of COCZ and expands its population to a linear size (where we recall that for the (G)SEMO, different Pareto optima in the population necessarily have different objective values). To this end, we determine the probability to cover a fitness vector of the current best cooperative level if a linear fraction of these vectors is still uncovered. 3

Lemma 5. Let 0 < δ < 1. Consider one iteration of the modified (G)SEMO maximizing f := COCZ, and denote by Zt the number of individuals with a maximum g1-value ℓ in P (t) . Suppose that 1 ≤ Zt < δn/2. Then the probability to increase Zt by one is at least 1 n/2+1 · 1-δ 4e .

With Lemma 5, we bound the expected time to find a Pareto optimal individual in the modified (G)SEMO from above.

Lemma 6. Consider the modified (G)SEMO maximizing f := COCZ. With probability 1 - exp(-Ω(√n)), after at most O(n2 ) iterations, for every initialization of x(0) the population of the modified (G)SEMO reaches the Pareto front, i.e. P (t) contains a Pareto optimal individual x.

Once the modified (G)SEMO reaches the Pareto front, we show that it achieves a population size linear in the problem size in the same amount of time.

Lemma 7. Consider the modified (G)SEMO maximizing COCZ and suppose there is an individual on the Pareto front. Then with probability 1 - exp(-Ω(n)), after at most O(n2 ) iterations the population of the modified (G)SEMO contains at least n4 individuals on the Pareto front.

Combining Lemmas 6 and 7, we obtain that the modified (G)SEMO has a linear population size and is on the Pareto front in at most O(n2 ) iterations, with high probability.

Corollary 8. Consider the modified (G)SEMO maximizing COCZ. Then with probability 1 - exp(-Ω(√n)), after at most O(n2 ) iterations the population of the modified (G)SEMO contains at least n4 individuals on the Pareto front.

Progress of the modified (G)SEMOon the g2-values. We show that the modified (G)SEMO takes some time in order to find solutions that are close to the extremal solutions of the Pareto front. We call this value the distance to the Pareto borders. Formally, for all z ∈ {0, 1}n , let the distance of z to the Pareto borders be dPF(z) := min{g2(z), n2 - g2(z)}. Using the notation of Algorithm 1, for all t ∈ N, we define the distance of the algorithm to the Pareto borders in iteration t as dPF(P (t) ) :=minz∈P (t) dPF(z).

3 For reasons of space, most proofs had to be omitted in this extended abstract. They can be found in the long version [Doerr et al., 2025b].

Lemma 9. Consider the modified (G)SEMO maximizing COCZ. Let c ∈ R>0 be a sufficiently small constant. With probability at least 1 - Θ(n-2/5 ), for all iterations t ∈ [0..cn2 lnn], the distance of the algorithm to the Pareto borders in iteration t is at least √n.

How the original (G)SEMO computes the full Pareto front. We show that if the original (G)SEMO is started in a state that the modified (G)SEMO reaches with high probability in O(n2 ) iterations, the original (G)SEMO still requires at least order n2 lnn iterations in order to cover the Pareto front. This statement relies on the linear lower bound on the population size from Corollary 8 as well as on the distance of at least √n to the Pareto borders from Lemma 9.

Lemma 10. Consider the (G)SEMO maximizing COCZ, starting with a population size of Θ(n) on the Pareto front and a distance to the Pareto borders of at least √n. Then with probability 1-Θ(n-1 ), the algorithm covers the Pareto front after Ω(n2 log n) objective-function evaluations.

Last, we prove our main result (Theorem 4) by showing that the starting state assumed in Lemma 10 is reached with high probability, as sketched before the lemma.

Proof of Theorem 4. We only start counting function evaluations once the (G)SEMO has at least Θ(n) individuals on the Pareto front. Let T denote the first iteration in which this is the case. We proceed to argue why it has with probability 1 - Θ(n-1 ) a distance of at least √n to the Pareto borders in iteration T . By applying Lemma 10, the statement follows then and the proof is concluded.

In order to show that the (G)SEMO is in the desired state in iteration T, we consider the modified (G)SEMO instead. Recall that the original (G)SEMO changes states if and only if the modified (G)SEMO does so, albeit in potentially different iterations, and they transition into identical states. Let S denote the first iteration in which the modified (G)SEMO has at least Θ(n) individuals on the Pareto front. By Lemma 6, with probability 1 - exp(-Ω(√n)), we have that S = O(n2 ). Moreover, by Lemma 9, we have with probability 1 - Θ(n-2/5 ) that the distance of the modified (G)SEMO to the Pareto borders is at least √n. Hence, with probability 1 - Θ(n-2/5 ), the modified (G)SEMO is in the desired state in iteration S.

Since S and T refer to the same state of the respective algorithm, it follows that the original (G)SEMO is also in the desired state in iteration T with probability 1-Θ(n-1 ), concluding the proof.

5 Runtime Analysis on OMMand OJZJ

We show that our insights from Section 4 about the population dynamics on COCZ also translate to the popular biobjective benchmarks OMM [Giel and Lehre, 2010] and OJZJ [Doerr and Zheng, 2021].

The OMM benchmark aims at maximizing and minimizing the number of ones in a bit string, resulting in all individuals being Pareto-optimal. This function resembles COCZ without the cooperative part. Formally, for all x ∈ {0, 1}n ,

The Pareto front of OMM is {(i, n - i) | i ∈ [0..n]}. In particular, each individual is Pareto-optimal, different from COCZ.

The OJZJ benchmark requires a gap size k ∈ [2..⌊n/2⌋] and is structurally identical to OMM for all individuals whose number of ones is at least k at most n - k. Those individuals are all Pareto-optimal. In addition, the all-ones and the all-zeros bit string are Pareto-optimal as well. All other individuals are strictly worse. This usually requires algorithms to flip at least k bits in order to find the extremal Pareto optima. This is formally defined as for all x ∈ {0, 1}n , letting |x|1 and |x|0 denote respectively the number of ones and the number of zeros in x, let OJZJk(x) = (f1(x), f2(x)) with

The first objective is the single-objective JUMPk benchmark, which features a local optimum at n-k. The second objective is structurally identical to the first but with the roles of ones and zeros reversed. [Doerr and Zheng, 2021] showed that the Pareto front F ∗ of OJZJk is {(a, 2k+n-a) | a ∈ [2k . . . n]∪ {k, n - k}}. Note that each individual x with f(x) ∈ F ∗ strictly dominates each individual y with f(y) /∈ F ∗ since, for all j ∈ [2], we have fj(x) ≥ k but fj(y) ≤ n - (n - k + 1) = k - 1. For OMM, tight bounds are already known (see Section 5.1). Hence, our results just provide a different angle of proving them. For OJZJ, tight bounds were known for all k ∈ N≥4 (see Section 5.2), as a pessimistic bound of n for the population size is sufficient. Our result shows that this bound also holds for the cases k ∈ {2, 3}, where our insights into the population dynamics are important.

For both benchmarks, we follow a similar strategy as in Section 4. Especially, we rely again on the modified (G)SEMO. This modification needs to be slightly adjusted as follows, using the notation from its original definition: We choose a value i ∈ [0..n] uniformly at random (instead of from [0.. n2 ]) and check whether the set {z ∈ P (t) | g1(z) + g2(z) = i} is empty. That is, instead of focusing only on the number of ones in the first half, we now consider the number of ones in the entire bit string. The rest remains identical.

Progress of themodified (G)SEMO. Lemma 11 below essentially translates Corollary 8 to OMM and OJZJ and shows that the modified (G)SEMO reaches a population size of n2 in O(n2 ) iterations.

Lemma 11. Consider the modified (G)SEMO maximizing OMM or OJZJk for 1 < k ≤ n/4. With probability 1 - exp(-Ω(√n)), after at most O(n2 ) iterations, for every initialization of x(0) in case of OMM or for an initialization on the Pareto front distinct from 0n and 1n in case of OJZJk, the population of the modified (G)SEMO contains at least n/2 individuals.

Lemma 12 below translates Lemma 9 to this setting and also uses its terminology. It shows that the extremal solutions in the population are still at least √n away from the borders. We need to re-define though what these terms exactly mean in the setting of OMM and OJZJ.

The extremal solutions of the Pareto front are 1n and 0n instead of 1n and 1n/2 0n/2 for COCZ. Furthermore, for all z ∈ {0, 1}n , let the distance of z to the Pareto borders be dPF(z) := min{|z|1 , n-|z|1} which is also slightly different to the case of COCZ above. However, the distance of the algorithm to the Pareto borders in iteration t is defined as dPF(P (t) ) := minz∈P (t) dPF(z) for all t ∈ N in the same way as in Section 4.

Lemma 12. Consider the modified (G)SEMO maximizing OMM or OJZJk for 1 < k ≤ n/4. Let c ∈ R>0 be a sufficiently small constant. With probability at least 1-Θ(n-2/5 ), for all iterations t ∈ [0..cn2 lnn], the distance of the algorithm to the Pareto borders in iteration t is at least √n for OMM and at least max{√n, k} for OJZJk.

5.1 OMM

For OMM we prove a bound of Ω(n2 logn) objectivefunction evaluations, with high probability (Theorem 13). This matches the O(n2 logn) bound by [Giel and Lehre, 2010]. The tight Θ(n2 logn) runtime for the GSEMO was already proven by [Bossek and Sudholt, 2024] as a special case of the single-objective problem of quality diversity on the ONEMAX benchmark. The bound Θ(n2 logn) for the SEMO was shown by [Covantes Osuna et al., 2020].

Theorem 13. With probability 1 - Θ(n-1 ), the (G)SEMO maximizes OMM in Ω(n2 logn) objective-function evaluations.

The proof of Theorem 13 is very similar to that of Theorem 4. We use Lemmas 11 and 12 for OMM from above.

Lemma 14. Consider the (G)SEMO maximizing OMM, starting with a population size of Θ(n) on the Pareto front and the distance to the Pareto borders is at least √n. Then with probability 1-Θ(n-1 ), the algorithm covers the Pareto front after Ω(n2 log n) objective-function evaluations.

By combining Lemmas 11, 12, and 14, we obtain the proof for Theorem 13 in a similar way as the proof of Theorem 4.

5.2 OJZJ

For OJZJ, we only consider the GSEMO, as the SEMO does not cover the Pareto front with high probability ([Doerr and Zheng, 2021]), due to the deceptive nature of the benchmark and the 1-bit mutation being incapable of creating the extremal Pareto optima from non-extremal Pareto optima. For gap size k ∈ [2.. n4 ], we prove a bound of Ω(nk+1 ) objectivefunction evaluations, with high probability (Theorem 15). This matches the bound O(nk+1 ) for all of these values of k by [Doerr and Zheng, 2021]. Moreover, for k ∈ [4.. n2 - 1], [Doerr and Zheng, 2021] proved already a matching bound of Ω((n-2k)nk ). However, for k ∈ {2, 3}, our results are new.

Theorem 15. In expectation, the GSEMOmaximizes OJZJk for k ∈ [2.. n4 ] in Ω(nk+1 ) objective-function evaluations.

The proof of Theorem 15 makes use of Lemma 16 below, which shows that it takes the GSEMO a lot of time to find the all-ones and all-zeros bit string.

Lemma 16. Consider the GSEMO maximizing OJZJk for 1 < k ≤ n/4, starting with a population size of Θ(n) on the Pareto front, but neither 0n nor 1n are in the population. Then the algorithm covers the Pareto front in expectation after Ω(nk+1 ) objective-function evaluations.

Theorem 15 can be proven in a similar way to Theorems 4 and 13 by using Lemmas 11 and 12 for OJZJk when 1 < k ≤ n/4 and then following Lemma 16.

6 Conclusion

We studied the population dynamics of the (G)SEMO, that is, the size and shape of its population over time. For the COCZ benchmark, we proved that the algorithm has a population size linear in the size of the Pareto front (Corollary 8) while it is still sufficiently far away from covering the entire Pareto front (Lemma 9). Covering these remaining solutions takes at least Ω(n2 log n) iterations (Theorem 4). Since a matching upper bound exists, this result is tight.

Our proof strategy relies on defining a modified process that allows an easier estimate of the probability to select a useful parent for making progress. This modification affects the absolute number of iterations but not the relative order of state changes. Thus, insights into state behavior for the modification also translate directly back to the original (G)SEMO.

We show that our insights for COCZ also transfer to OMM and OJZJ, where we derive lower bounds that match known upper bounds. Although most of these lower bounds were already known, our proof strategy provides a different angle for deriving them. Moreover, our lower bounds for gap sizes k ∈ {2, 3} for OJZJk are new. Since we prove a general lower bound for a large range of k, all of which are tight, our method captures the true nature of the (G)SEMO well.

Our analysis shows that the GSEMO is hampered by exploiting easy parts of the search space too quickly. This lets the population grow quickly, slowing down the selection required for exploring harder-to-reach parts of the search space.

For future work, it would be interesting to derive lower bounds for the population size while the (G)SEMO is approaching the Pareto front. In this article, we only derive upper bounds for this time (Corollary 8). Lower bounds would give us a clearer picture how wasteful the algorithm is in terms of function evaluations before reaching the Pareto front.

Another interesting open problem is to derive tight lower bounds of the GSEMO for the LEADINGONESTRAILINGZEROS (LOTZ) benchmark. For this setting, so far, only the bound O(n3 ) [Giel, 2003] exists (but a Θ(n3 ) bound for the SEMO). In contrast to the setting in this article, for LOTZ, it is far more likely for the GSEMO to get closer to the Pareto front than to create an incomparable offspring. Only once the Pareto front is reached, these two probabilities are in the same order. Hence, the dynamics seem to be different from here.

Our result can also serve as a stepping stone towards the deeper understanding of the population dynamics of other MOEAs, like the NSGA-II. However, since the NSGA-II has a fixed population size, parts of the analysis need to focus on how duplicate entries in the population are treated, which is a separate topic and thus left for future work.

Acknowledgments

• This research benefited from the support of the FMJH Program PGMO.

This paper significantly profited from discussions at the Dagstuhl Seminars 23361 Multiobjective Optimization on a Budget and 24271 Theory of Randomized Optimization Heuristics.