A Theoretical Perspective on Why Stochastic Population Update Needs an Archive in Evolutionary Multi-objective Optimization

1 Introduction

Multi-objective optimization deals with scenarios where multiple objectives must be optimized simultaneously. They are very common in real-world applications. Since the objectives of a multi-objective optimization problem (MOP) are usually conflicting, there does not exist a single optimal solution, but instead a set of solutions which represent different optimal trade-offs between these objectives, called Pareto optimal solutions. The objective vectors of these solutions form the Pareto front. The goal of multi-objective optimization is to find the Pareto front or a good approximation of it.

Evolutionary algorithms (EAs), a kind of randomized heuristic optimization algorithms inspired by natural evolution, have been found well-suited to MOPs due to their population-based nature. Their widespread applications are across various real-world domains [Deb, 2001; Zhou et al., 2019]. Notably, there have been developed a multitude of well-established multi-objective EAs (MOEAs), including the non-dominated sorting genetic algorithm II (NSGAII) [Deb et al., 2002], multi-objective evolutionary algorithm based on decomposition (MOEA/D) [Zhang and Li, 2007], and S metric selection evolutionary multi-objective optimization algorithm (SMS-EMOA) [Beume et al., 2007].

In MOEAs, a key component is population update (aka environmental selection or population maintenance). It aims to select a set of promising solutions from the current population and newly generated solutions, which serves as a reservoir to generate high-quality solutions in subsequent generations. In most existing MOEAs, the population update is performed in a greedy and deterministic manner, with the best solutions (non-dominated solutions) always being preserved. This is based on the assumption that higher-quality solutions are more likely to generate better offspring. However, this is not always the case, particularly in rugged problem landscapes with many local optima, where solutions can easily get trapped in MOEAs. Repetitively exploring such localoptimal solutions may not help. Indeed, recent studies show that mainstream MOEAs (e.g., NSGA-II and SMS-EMOA) can easily stagnate, and even more, their population may end up in a very different area at a time [Li et al., 2023].

Very recently, Bian et al. [2025] analytically showed that introducing randomness in the population update process of MOEAs (called stochastic population update, SPU) can help the search. Specifically, the study proved that for SMS-EMOA solving the common benchmark problem OneJumpZeroJump, when k = n/2-Ω(n), using SPU can bring an acceleration of Ω(2k/2 /(√kµ2 )) = Ω(2k/2 /(√k(n-2k+ 4)2 )) on the expected running time, where n denotes the problem size, k (2 ≤ k < n/2) denotes the parameter of OneJumpZeroJump, and µ denotes the population size. Subsequently, Zheng and Doerr [2024b] extended SMS-EMOA to solve a many-objective problem, mOneJumpZeroJump, showing that the same SPU can bring an acceleration of Θ(2k /µ) = Θ(2k /(2n/m - 2k + 3)m/2 ) as well, where m is the number of objectives. These works echoed the empirical studies that show the benefit of considering non-elitism in MOEAs [Tanabe and Ishibuchi, 2019; Liang et al., 2023a].

SPU in [Bian et al., 2025; Zheng and Doerr, 2024b] introduces randomness by randomly selecting a proportion ps of the combined set of the current population and offspring solution(s) to be directly preserved into the next generation. This essentially gives a chance for inferior solutions to survive, which enables the evolutionary search to go along inferior regions which may be close to Pareto optimal regions. However, a cost of this method is that there is less space for the best solutions in the population. Some very best solutions to the problem (e.g., globally non-dominated solutions), even found by an MOEA, may be discarded during the population update process. This necessitates a large population used. Unfortunately, when the population size is large, the benefit of using SPU may vanish. This is because the benefit of SPU comes from the operation on inferior solutions while the large population size will lead to a small probability of selecting these solutions. For example, for SMS-EMOA solving OneJumpZeroJump, the acceleration of Ω(2k/2 /(√kµ2 )) brought by SPU [Bian et al., 2025] will vanish when the population size µ is exponential w.r.t. k, e.g., k = logn; for SMS-EMOA solving mOneJumpZeroJump, the acceleration of Θ(2k /(2n/m - 2k + 3)m/2 ) [Zheng and Doerr, 2024b] will vanish when the number m of objectives is large, e.g., m ≥ k, because the population size µ = (2n/m-2k+3)m/2 increases rapidly with m. This dilemma impacts both the effectiveness and practicality of using SPU in MOEAs.

Intuitively, a possible solution to this issue is to use an archive to store the best solutions ever found. In fact, in the area of MOEAs, this approach has become a popular practice [Li et al., 2024]. Since the formalization of the archiving problem in the early 2000s [Knowles and Corne, 2003], there has been increasing interest and feasibility to use (even unbounded) archives in MOEAs, as seen in e.g. [Fieldsend et al., 2003; Krause et al., 2016; Brockhoff and Tuˇsar, 2019; Ishibuchi et al., 2020]. In this paper, we analytically show that incorporating an unbounded archive into SPU can reduce the population size and significantly enhance acceleration. Specifically, we compare the expected running time of two well-established MOEAs, SMS-EMOA and NSGA-II, with SPU for solving OneJumpZeroJump, when an archive is used or not. The results are shown in Table 1. Our contributions can be summarized as follows.

• We theoretically show that incorporating an archive mechanism with SPU can reduce the upper bound on the expected running time (even exponentially). For example, comparing Theorems 1 and 3 in Table 1, the expected running time of SMS-EMOA with SPU for solving OneJumpZeroJump, no matter whether an archive is used or not, is O(µnk · min{1, (e lnC/k)k-1 }), where C = eµ/(ps(1 - pc)). The key difference is that using an archive allows a constant population size, resulting in a significantly smaller C and thus reducing the upper bound significantly. Note that Bian et al. [2024] recently proved the effectiveness of using an archive (bringing polynomial acceleration) for MOEAs, while our analysis for MOEAs with SPU reveals that even exponential acceleration can be obtained.
• Comparing the results of Theorems 1 and 4 in Table 1, we can find that the upper bound of NSGA-II is smaller than SMS-EMOA when using SPU. Our analysis reveals that the benefit of NSGA-II is due to its (µ+µ) update mode, which selects each solution in the current population for reproduction and thus makes exploring promising dominated solutions easier.
• In addition, our derived running time bounds for MOEAs with SPU in the second column of Table 1 are significantly better than the previously known ones [Bian et al., 2025; Zheng and Doerr, 2024b]. This improvement stems from the analysis method of considering both the number and size of jumps across gap of dominated solutions. The method happens to share similarities with that of proving Lemma 12 in [Doerr and Lutzeyer, 2024]. Moreover, our running time bounds are more general, as we consider variable survival probability ps and crossover probability pc.

We also validate our theoretical findings through an empirical study on the artificial OneJumpZeroJump problem and the multi-objective travelling salesperson problem (MOTSP) [Ribeiro et al., 2002]. The results show that combining SPU with an archive leads to the best performance for both SMS-EMOA and NSGA-II. Furthermore, the results on the MOTSP show that with the SPU method, NSGA-II always performs better than SMS-EMOA. These results confirm our theoretical findings.

Finally, we give a brief overview about the running time analysis of MOEAs. Over the last decade, there has been an increasing interest for the evolutionary theory community to study MOEAs. Early theoretical works [Laumanns et al., 2004a; Laumanns et al., 2004b; Neumann, 2007; Giel and Lehre, 2010; Neumann and Theile, 2010; Doerr et al., 2013; Qian et al., 2013; Qian et al., 2016; Bian et al., 2018] mainly focus on analyzing the expected running time of a simple MOEA like GSEMO/SEMO. Recently, researchers have begun to examine practical MOEAs. Huang et al. [2021] investigated MOEA/D, assessing the effectiveness of different decomposition methods. Zheng et al. [2022] conducted the first theoretical analysis of NSGA-II. Bian et al. [2025] analyzed the running time of SMS-EMOA and showed that SPU can bring acceleration. Moreover, Wietheger and Doerr [2023] demonstrated that NSGA-III [Deb and Jain, 2014] exhibits superior performance over NSGA-II in solving the tri-objective problem 3OneMinMax. Ren et al. [2024a] analyzed the running time of SPEA2 on three m-objective problems. Some other works on well-established MOEAs include [Bian and Qian, 2022; Zheng and Doerr, 2022; Zheng and Doerr, 2024a; Cerf et al., 2023; Dang et al., 2023a; Dang et al., 2023b; Doerr and Qu, 2023b; Doerr and Qu, 2023c; Doerr et al., 2024; Doerr et al., 2025; Lu et al., 2024; Opris et al., 2024; Opris, 2025; Ren et al., 2024b].

2 Multi-objective Optimization

Multi-objective optimization aims to optimize two or more objective functions simultaneously, as shown in Definition 1. In this paper, we focus on maximization, while minimization can be defined similarly. The objectives are typically conflicting, meaning that there is no canonical complete order in the solution space X. To compare solutions, we use the domination relationship in Definition 2. A solution is Pareto optimal if no other solution in X dominates it. The set of objective vectors corresponding to all Pareto optimal solutions constitutes the Pareto front. The goal of multi-objective optimization is to find the Pareto front or its good approximation.

Definition 1 (Multi-objective Optimization). Given a feasible solution space X and objective functions f1, f2, . . . , fm, multi-objective optimization can be formulated as

Definition 2. Let f = (f1, f2, . . . , fm) : X → Rm be the objective vector. For two solutions x and y ∈ X :

• x weakly dominates y (denoted as x ⪰ y) if for any 1 ≤ i ≤ m, fi(x) ≥ fi(y);
• x dominates y (denoted as x ≻ y) if x ⪰ y and fi(x) > fi(y) for some i;

· x and y are incomparable if neither x ⪰ y nor y ⪰ x. Note that the notions of "weakly dominate" and "dominate" are also called "dominate" and "strictly dominate" in some works [Cerf et al., 2023; Wietheger and Doerr, 2023].

Next, we introduce the benchmark problem OneJumpZeroJump studied in this paper. The OneJumpZeroJump problem as presented in Definition 3 is constructed based on the Jump problem [Doerr and Neumann, 2020], and has been widely used in MOEAs' theoretical analyses [Doerr and Zheng, 2021; Doerr and Qu, 2023a; Lu et al., 2024; Ren et al., 2024b]. Its first objective is the same as the Jump problem, which aims to maximize the number of 1-bits of a solution, except for a valley around 1n (the solution with all 1-bits) where the number of 1-bits should be minimized. The second objective is isomorphic to the first, with the roles of 1bits and 0-bits reversed. The Pareto front of the OneJumpZeroJump problem is {(a, n+2k-a) | a ∈ [2k..n]∪{k, n+k}}, whose size is n-2k+3, and the Pareto optimal solution corresponding to (a, n+2k-a), a ∈ [2k..n]∪{k, n+k}, is any solution with (a - k) 1-bits. We use F ∗ I = {(a, n+2k-a) | a ∈ [2k..n]} to denote the inner part of the Pareto front.

Definition 3 (OneJumpZeroJump [Doerr and Zheng, 2021]). The OneJumpZeroJump problem is to find n bits binary strings which maximize

where k ∈ Z ∧ 2 ≤ k < n/2, and |x|1 and |x|0 denote the number of 1-bits and 0-bits in x ∈ {0, 1}n , respectively.

3 Running Time Analysis of SMS-EMOA

In this section, we prove that using an archive can bring (even exponential) speedup for the well-established MOEA, SMSEMOA [Beume et al., 2007], with stochastic population update (SPU) solving the OneJumpZeroJump problem. In Section 3.1, we first introduce SMS-EMOA with SPU, and its expected running time for solving OneJumpZeroJump, which is much tighter than the previous results [Bian et al., 2025; Zheng and Doerr, 2024b]. Then, in Section 3.2, we prove that using an archive can significantly reduce the upper bound on the expected running time. Due to space limitation, all mathematical proofs could only be sketched or had to be omitted completely. The full proof is given in the supplementary.

3.1 SMS-EMOAwith SPU

SMS-EMOA presented in Algorithm 1 is a popular MOEA, which employs non-dominated sorting and hypervolume indicator to update the population. It starts from an initial population of µ solutions (line 1). In each generation, it randomly selects a solution x from the current population (line 3) for reproduction. With probability pc, it selects another solution y and applies one-point crossover on x and y to generate an offspring solution x′ (lines 4-7); otherwise, x′ is set as the copy of x (line 9). Note that one-point crossover selects a random point i ∈ {1, 2, . . . , n} and exchanges the first i bits of

Algorithm 1 SMS-EMOA

Input: objective function f1, f2 · · · , fm, population size µ, probability pc of using crossover

• Output: µ solutions from {0, 1}n 1: P ← µ solutions uniformly and randomly selected from {0, 1}n with replacement; 2: while criterion is not met do 3: select a solution x from P uniformly at random; 4: sample u from the uniform distribution over [0, 1]; 5: if u < pc then 6: select a solution y from P uniformly at random; 7: apply one-point crossover on x and y to generate x′ 8: else 9: set x′ as the copy of x 10: end if 11: apply bit-wise mutation on x′ to generate x′′ ; 12: P ← POPULATION UPDATE(P ∪ {x′′ }) 13: end while 14: return P

two parent solutions, which actually produces two new solutions, but the algorithm only picks the one that consists of the first part of the first parent solution and the second part of the second parent solution. Afterwards, bit-wise mutation flips each bit of x′ with probability 1/n to produce an offspring x′′ (line 11). Then, the worst solution in P ∪{x′′ }, the union of the current population and offspring, is removed (line 12) using the POPULATION UPDATE OF SMS-EMOA subroutine described in Algorithm 2. The subroutine first partitions the solution set Q (where Q = P ∪{x′′ }) into non-dominated sets R1,R2, . . . ,Rv , where R1 contains all non-dominated solutions in Q, and Ri (i ≥ 2) contains all non-dominated solutions in Q \ ∪i-1 j=1Rj . A solution z ∈ Rv is then removed by minimizing ∆r(x, Rv) := HVr(Rv) - HVr(Rv \ {x}), where HVr(X) denotes the hypervolume of the solution set X with respect to a reference point r ∈ Rm (∀i, ri ≤ minx∈X fi(x)), i.e., the volume of the objective space between the reference point and the objective vectors of the solution set. A larger hypervolume indicates better approximation of the Pareto front in terms of convergence and diversity. For bi-objective problems, as defined in the original SMSEMOA [Beume et al., 2007], the algorithm omits the reference point and directly preserves the two boundary points, allowing the hypervolume to be calculated accordingly.

In [Bian et al., 2025], the SPU method is introduced and shown to be beneficial for the search of MOEAs. During population updates, SPU randomly selects a proportion ps of the current population and the offspring solution(s) to directly survive into the next generation and the removed part is selected from the rest solutions. This implies that each solution, including the worst solution in the population, has at least a probability ps of surviving to the next generation. Specifically, SPU OF SMS-EMOA as presented in Algorithm 3 is used to replace the original POPULATION UPDATE procedure in line 12 of Algorithm 1. Note that ps is set to 1/2 in [Bian et al., 2025], while we consider a general ps here.

The expected running time of SMS-EMOA with SPU for

Algorithm 2 POPULATION UPDATE OF SMS-EMOA (Q)

Input: a set Q of solutions, and a reference point r ∈ Rm Output: |Q|-1 solutions fromQ

• 1: partition Q into non-dominated sets R1,R2, . . . ,Rv;
• 2: let z = argminx∈Rv ∆r(x,Rv);
• 3: return Q\ {z}

Algorithm 3 SPU OF SMS-EMOA (Q)

Input: a set Q of solutions, and a reference point r ∈ Rm Output: |Q|-1 solutions fromQ

• 1: Q′ ← ⌊|Q| · (1-ps)⌋ solutions uniformly and randomly selected fromQwithout replacement;
• 2: partition Q′ into non-dominated sets R1,R2, . . . ,Rv;
• 3: let z = argminx∈Rv ∆r(x,Rv);
• 4: return Q\ {z}

solving OneJumpZeroJump has been proven to be O(µnk · min{1, √kµ/2k/2 }) [Bian et al., 2025], which is better than that, i.e., O(µnk ), of the original SMS-EMOA. Intuitively, by by introducing randomness into the population update, the evolutionary search has a chance to go along inferior regions which are close to Pareto optimal regions, thereby making the search easier. Here, we re-prove a tighter upper bound on the expected running time of SMS-EMOA with SPU for solving OneJumpZeroJump, as shown in Theorem 1. It is also more general, as it considers a survival probability ps ∈ [1/(µ + 1), 1 - 1/o(µ)), rather than just ps = 1/2 as in [Bian et al., 2025]. Note that the running time of EAs is often measured by the number of fitness evaluations.

Theorem 1. For SMS-EMOA solving OneJumpZeroJump with n - 2k = Ω(n), if using SPU with survival probability ps ∈ [1/(µ + 1), 1 - 1/o(µ)), the crossover probability 1 - pc = Ω(1), and the population size µ ≥ (n - 2k + 4)/(1 - ps), then the expected running time for finding the whole Pareto front is O(µnk ·min{1, (e ln C/k)k-1 }), where C = eµ/(ps(1 - pc)).

The proof of Theorem 1 needs Lemma 2, which shows that given a proper value of µ, an objective vector on the Pareto front will always be maintained once it has been found. The reason is that in Algorithm 3, the removed solution is selected from ⌊(µ + 1) · (1 - ps)⌋ ≥ n - 2k + 4 solutions in Q. For each objective vector on the Pareto front, whose size is n - 2k + 3, only one solution has positive ∆-value. This ensures that these solutions rank among the top n-2k +3 solutions, and thus will not be removed.

Lemma 2. For SMS-EMOA solving OneJumpZeroJump, if using SPU with survival probability ps ∈ [1/(µ + 1), 1 - 1/o(µ)), and the population size µ ≥ (n-2k +4)/(1-ps), then an objective vector f ∗ on the Pareto front will always be maintained once it has been found.

Proof Sketch of Theorem 1. We divide the optimization procedure into two phases: the first phase starts after initialization and finishes until the inner part F ∗ I of the Pareto front is found; the second phase starts after the first phase and finishes until the extreme Pareto optimal solution 1n is found.

Note that the analysis for finding 0n holds similarly. Since Lemma 2 ensures the maintenance of objective vectors in F ∗ I , making the first-phase analysis similar to that of Theorem 1 in [Bian et al., 2025], we can derive that the expected running time of the first phase is O(µn log n).

Next, we consider the second phase. By employing SPU, any solution (including dominated ones) can survive into the next generation with probability at least ps. This means that the population can preserve some dominated solutions to gradually reach 1n . We assume a "jump" to be an event where a solution x with |x|1 ∈ [n - k..n - 1] is selected, and a new dominated solution closer to 1n is generated and preserved. Thus, 1n can be reached more easily through multiple jumps across the gap of dominated solution set (i.e., {x | |x|1 ∈ [n- k + 1..n- 1]}). We refer to the dominated solutions along the multiple jumps as "stepping stones" and assume that 1n can be reached through M stepping stones. Then, we consider M + 1 consecutive jumps, which start from a solution x with n - k 1-bits, and continue to generate the next stepping-stone solution until finding 1n . Any failure during the intermediate jumps will result in restarting the process from the solution with n - k 1-bits. By enumerating all possible jump sizes (the sum of which is required to be k), we prove that the M+1 consecutive jumps can happen with probability at least (1-pc)(M+1)k /(eµnkCM ), where C = eµ/(ps(1 - pc)). Thus, 1n can be found after at most eµnkCM /((1 - pc)(M + 1)k ) trials in expectation. As each trial requires up to M+1 generations and 1-pc = Ω(1), the expected number of generations for finding 1n is

Finally, we minimize this upper bound by taking M = ⌈(k - 1)/ ln C -1⌉ when k > e ln C, and M = 0 when k ≤ e ln C. This leads to that the expected number of generations of the second phase is at most O(µnk · min{1, (e lnC/k)k-1 }).

As SMS-EMOA generates one solution per generation, its running time is equal to the number of generations. Combining the two phases, the total expected running time is O(µnk · min{1, (e lnC/k)k-1 }), where O(µn log n) required by the first phase is dominated, and C = eµ/(ps(1 - pc)).

Under the same conditions as the previous results O(µnk · min{1, √kµ/2k/2 }) in [Bian et al., 2025] and O(µnk · min{1, µ/2k }) in [Zheng and Doerr, 2024b], where SPU is used with ps = 1/2 and crossover probability pc = 0, our bound in Theorem 1 becomes O(µnk · (e ln(2eµ)/k)k-1 ). Since the bound in [Zheng and Doerr, 2024b] is tighter than that in [Bian et al., 2025], we focus on comparing our result only with [Zheng and Doerr, 2024b]. When k > 2e ln(2eµ), our bound O(µnk · (e ln(2eµ)/k)k-1 ) brings an improvement ratio of Θ(µ(k/(2e ln(2eµ)))k-1 ), which can be exponential when k is large, e.g., k = n/8. For a very small range logµ ≤ k < 2e ln(2eµ), our bound shows no advantage, which is because to minimize Eq. (1), we choose M = ⌈(k - 1)/ lnC - 1⌉ to round up to the nearest integer, leading to an over-relaxation. If we instead set M = 1, the same bound can be obtained. The reason of our better bound is in the second phase of finding the Pareto optimal solution

1n : 1) We consider M + 1 "jumps" across the gap between dominated solutions, and account for all possible jump sizes to find 1n ; 2) We select the optimal number of jumps, i.e., M = ⌈(k - 1)/ lnC - 1⌉. Note that Bian et al. [2025] considered only two fixed-size jumps, and although Zheng and Doerr [2024b] accounted for all possible jump sizes, they also reduced the process to two jumps.

3.2 An Archive is Provably Helpful

In the last section, we have proved that for SMS-EMOA with SPU solving OneJumpZeroJump, the expected running time is O(µnk · min{1, (e ln C/k)k-1 }), where C = eµ/(ps(1 - pc)). From the analysis, we find that SPU benefits evolutionary search by exploring inferior regions that are close to Pareto optimal areas, but it also requires a larger population size µ ≥ (n-2k+4)/(1-ps) to preserve the Pareto optimal solutions discovered. The greater the randomness introduced by SPU (i.e., the larger the value of ps), the larger the population size needed. Note that a large population size may diminish the benefit of SPU, because it will lead to a very small probability of selecting specific dominated solutions for reproduction, which is required by SPU. For example, when the population size µ is exponential w.r.t. k, e.g., k = logn, the improvement by SPU will vanish, compared to the expected running time O(µnk ) without SPU [Bian et al., 2025].

In this section, we theoretically show that the limitation of SPU can be alleviated by using an archive. Once a new solution is generated, the solution will be tested if it can enter the archive. If there is no solution in the archive that dominates the new solution, then the solution will be placed in the archive, and meanwhile those solutions weakly dominated by the new solution will be deleted from the archive. Algorithmic steps incurred by adding an archive in SMS-EMOA are given as follows. In Algorithm 1, an empty set A is initialized in line 1, and the following lines are added after line 11:

The set A instead of P is returned in the last line.

We prove in Theorem 3 that if using an archive, a population size µ ≥ 3 is sufficient to guarantee the same running time bound of SMS-EMOA with SPU as Theorem 1. Note that Theorem 1 requires µ ≥ (n - 2k + 4)/(1 - ps), which implies that using an archive can allow a small population size and thus bring speedup.

Theorem 3. For SMS-EMOA solving OneJumpZeroJump with n - 2k = Ω(n), if using SPU with survival probability ps ∈ [1/(µ + 1), (µ - 2)/(µ + 1)], the crossover probability pc = Θ(1), the population size µ ≥ 3, and using an archive, then the expected running time for finding the whole Pareto front is O(µnk ·min{1, (e ln C/k)k-1 }), where C = eµ/(ps(1 - pc)).

Proof Sketch of Theorem 3. We divide the optimization procedure into three phases, where the first phase aims at finding the two boundary solutions in the inner part F ∗ I of the Pareto front (i.e., a solution with k 1-bits and a solution with n-k 1bits), the second phase aims at finding the two extreme Pareto optimal solutions 1n and 0n , and the third phase aims at finding the remaining objective vectors on the Pareto front.

A key property used in the proof is that the maximum f1 value among the Pareto optimal solutions in P ∪{x′′ } will not decrease, because the two boundary solutions in R1 (i.e., the first non-dominated set by non-dominated ranking) are prioritized for preservation into the next generation. For the first phase, we show that the expected number of generations for finding a solution with n - k 1-bits is O(µn log n), by continuously selecting the solution with the maximum f1 value in the population and flipping a 0-bit to increase the f1 value. The process for finding another boundary solution with k 1bits is symmetric. For the second phase, the analysis follows that of the second phase in Theorem 1, leading to an expected running time of O(µnk · min{1, (e lnC/k)k-1 }) for finding 1n and 0n , where C = eµ/(ps(1 - pc)). For the third phase, since 0n and 1n must be maintained in the population P, we consider the case where 0n or 1n is selected as a parent, and another solution x ∈ P is chosen as the second parent. By using one-point crossover, new points on the Pareto front can be continuously generated and added to the archive. Consequently, the expected running time of the third phase is O(µn logn). Combining the three phases, the total expected running time is O(µnk · min{1, (e lnC/k)k-1 }), where O(µn log n) required by the first phase and third phase is dominated and thus omitted.

For the case without an archive, in order to avoid losing the Pareto optimal solutions found while using SPU, the population size must be large, i.e., µ ≥ (n - 2k + 4)/(1 - ps). However, for the case with an archive, the population size only needs to be a constant. The main reasons are: 1) Using an archive that stores all the Pareto optimal solutions generated enables the algorithm not to worry about losing Pareto optimal solutions, but only endeavoring to seek new Pareto optimal solutions. 2) In the context of our analysis, a constant population size is sufficient to preserve exploration-favoring solutions, i.e., the two boundary Pareto optimal solutions.

The smaller population size allows a larger probability of selecting inferior solutions that are close to Pareto optimal areas for reproduction, thus leading to speedup. When k is limited, using only SPU may not bring acceleration. For example, when k = e ln(8en), if using SPU with ps = 1/2, µ = 2n, and pc = 1/2, the expected running time of SMS-EMOA on OneJumpZeroJump is O(µnk ·min{1, (e ln C/k)k-1 }) = O(nk+1 ) (where C = eµ/(ps(1 - pc)) = 8en), implying no acceleration compared to O(µnk ) = O(nk+1 ) without SPU [Bian et al., 2025]. However, by adding an archive and reducing the population size µ to 5, while keeping other settings unchanged, the bound reduces to O(nk · (e ln(20e)/k)k-1 ), implying a superpolynomial reduction in the upper bound as k = e ln(8en). Note that we set µ = 5 to satisfy the condition of Theorem 3, i.e., to make ps = 1/2 ∈ [1/(µ + 1), (µ - 2)/(µ + 1)]. On the other hand, when k is large, using SPU alone can lead to exponential acceleration, and the addition of an archive can further enhance this acceleration. For example, when k = n/8, if using SPU with ps = 1/2, µ = 2n, and pc = 1/2, the expected running time is O(µnk · (8e ln(8en)/n)n/8-1 ), which implies an exponential reduction in the upper bound compared to O(µnk ) without SPU. By adding an archive and setting µ to 5, the bound reduces to O(nk · (8e ln(20e)/n)n/8-1 ), resulting in an improvement ratio of Θ(n(ln(8en)/ ln(20e))n/8-1 ), i.e., an exponential reduction in the upper bound.

We also note that the recent work [Bian et al., 2024] has proven that using an archive can provide polynomial acceleration for MOEAs for the first time. For example, for SMSEMOA solving OneMinMax, the expected running time is O(µn log n) both with and without an archive, but the archive allows for a constant µ, achieving an acceleration of Θ(n). Our work gives another theoretical evidence for the effectiveness of using an archive, and further shows that superpolynomial or even exponential acceleration can be achieved. In our analysis with SPU, a sequence of M + 1 consecutive jumps are required, which implies continuously selecting specific solutions for reproduction; using an archive allows a small population size, which increases the selection probability significantly and thus leads to greater acceleration.

4 Running Time Analysis of NSGA-II

In this section, we show that an archive is also helpful for NSGA-II solving OneJumpZeroJump if using SPU. Specifically, we prove in Theorem 4 that the expected running time of NSGA-II using SPU for solving OneJumpZeroJump is O(µnk ·min{1, (e ln C/k)k-1 }), where C = e/(ps(1-pc)), and the population size µ is required to be at least 4(n-2k+ 3)/(1 - 2ps). Theorem 5 shows that using an archive with a constant population size, the same running time bound holds. Their proofs are similar to that of Theorems 1 and 3, respectively. The main difference is that in each generation, the probability of selecting a specific parent solution for reproduction is changed from 1/µ to 1 due to the (µ + µ) mode and fair selection employed by NSGA-II, making the value of C independent of µ. The introduction of NSGA-II, the corresponding SPU and archive mechanisms, and the proof details are provided in the supplementary due to space limitation.

Theorem 4. For NSGA-II solving OneJumpZeroJump with n - 2k = Ω(n), if using SPU with survival probability ps ∈ [1/(2µ), 1/2 - o(1/µ)), the crossover probability 1 - pc = Ω(1), and the population size µ ≥ 4(n - 2k + 3)/(1 - 2ps), then the expected running time for finding the whole Pareto front is O(µnk ·min{1, (e ln C/k)k-1 }), where C = e/(ps(1 - pc)).

Bian et al. [2025] analyzed NSGA-II solving OneJumpZeroJump with k > 8e2 , ps = 1/4, and pc = 0, deriving an expected running time of O(µ√k(n/2)k ). In contrast, Theorem 4 gives a tighter bound O(µnk ·(e ln(4e)/k)k-1 ), with an improvement ratio of Θ(√k(k/(2e ln(4e)))k-1 ), which can be exponential when k is large, e.g., k = n/8. Our analysis leads to improvement because, in the second phase of finding the extreme Pareto optimal solution 1n , we consider an optimal number M + 1 of jumps across the gap of the dominated solution set (i.e., {x | |x|1 ∈ [n-k+1..n-1]}), rather than a continuous sequence of k jumps from |x|1 = n - k to n in [Bian et al., 2025].

Table 2: The IGD [Coello Coello and Reyes Sierra, 2004] results (mean and standard deviation) of the four variants of NSGA-II and SMSEMOA on the 100-cities MOTSP instance clusAB from TSPLIB [Reinelt, 1991]. For each MOEA, the best mean is highlighted in bold.

Theorem 5. For NSGA-II solving OneJumpZeroJump with n - 2k = Ω(n), if using SPU with survival probability ps ∈ [1/(2µ), (µ-4)/(2µ)], the crossover probability pc = Θ(1), the population size µ ≥ 5, and using an archive, then the expected running time for finding the whole Pareto front is O(µnk ·min{1, (e ln C/k)k-1 }), where C = e/(ps(1-pc)).

Comparing Theorems 4 and 5, we find that if using SPU, the expected running time for NSGA-II solving OneJumpZeroJump with or without an archive is both O(µnk · (e lnC/k)k-1 ), where C = e/(ps(1 - pc)). The difference is that using an archive allows for a small constant population size µ, which can bring an acceleration factor of Θ(n/(1 - 2ps)), as µ is required to be at least 4(n-2k+3)/(1-2ps) if not using an archive. Compared to SMS-EMOA, using an archive does not lead to an exponential reduction in the upper bound for NSGA-II. The reason is that NSGA-II employs the (µ + µ) update mode and fair selection, allowing it to select and explore all solutions in each generation, thereby alleviating selection pressure. This results in a smaller constant C = e/(ps(1 - pc)) independent of µ in Theorems 4 and 5, compared to C = eµ/(ps(1 - pc)) in Theorems 1 and 3. This also implies that NSGA-II achieves a smaller expected running time than SMS-EMOA, suggesting that the (µ + µ) mode may be more suitable for SPU than the (µ + 1) mode.

5 Experiments

In this section, we conduct experiments on OneJumpZeroJump and the well-known multi-objective travelling salesman problem (MOTSP) [Ribeiro et al., 2002]. Table 3 presents the results of NSGA-II solving the OneJumpZeroJump problem with size n ∈ {10, 15, 20, 25, 30} and k = 3. The settings are: population size µ = 8 with an archive, and µ = 8(n - 2k + 3) without; survival probability ps = 1/2 when using SPU; and crossover probability pc = 1/2. We present the average number of fitness evaluations over 200 runs for three configurations: SPU only, archive only, and SPU + archive. Results show that using SPU+archive significantly reduces running time compared to using only SPU, and using only archive. We have similar results on SMS-EMOA in the supplementary.

For the MOTSP, the Pareto front size |PF| is known, allowing us to set commensurable population sizes µ for the compared MOEAs. We conduct experiments on two 100cities instances (i.e., clusAB and kroAB) of MOTSP 1 using NSGA-II and SMS-EMOA under four scenarios with varying population sizes: 1) the original algorithms, 2) using only SPU, 3) using only an archive, and 4) using SPU and an archive. For a fair comparison, each scenario used 1, 000, 000 fitness evaluations over 30 runs. Table 2 presents the results of a widely-used quality indicator, Inverted Generational Distance (IGD) [Coello Coello and Reyes Sierra, 2004] on the instance clusAB. We used IGD since it can measure how well the obtained solution set represents the Pareto front [Li et al., 2020]. Table 2 shows that using SPU and an archive simultaneously can lead to the smallest value of IGD for both SMSEMOA and NSGA-II, and statistically outperforms the other three scenarios. Moreover, with the SPU method, NSGA-II always achieves smaller IGD values than SMS-EMOA. Similar results can be observed on the kroAB instance, along with additional experiments using smaller population sizes (µ = |PF|/6, |PF|/8, and |PF|/10). These findings further validate our theoretical analysis, with full experimental details available in the supplementary.

1 https://webia.lip6.fr/∼lustt/Research.html

6 Conclusion

This paper analytically shows that SPU in MOEAs needs an archive to better leverage its exploration ability. We prove that for NSGA-II and SMS-EMOA solving OneJumpZeroJump, introducing an archive for SPU can address the dilemma of large population size and may provide an extra exponential speedup. The reason is that SPU requires a large population to preserve the best solutions found, while an archive enables a small population size, increasing the chance of selecting inferior but undeveloped solutions. We also find that the (µ + µ) update mode may be more suitable for SPU than the (µ + 1) update mode. Another contribution lies in improving the running time bounds for SMS-EMOA and NSGA-II solving OneJumpZeroJump using SPU. These theoretical findings are empirically validated on OneJumpZeroJump and the MOTSP. We hope our work may provide some theoretical evidence for the attempts of designing new MOEAs that separate the exploration (via the evolutionary population) and elitist solution preservation (via an external archive), such as in non-elitist or less elitist MOEAs [Tanabe and Ishibuchi, 2019; Liang et al., 2023b].

Acknowledgements

This work was supported by the National Science and Technology Major Project (2022ZD0116600), the National Science Foundation of China (62276124), and the Fundamental Research Funds for the Central Universities (14380020). Chao Qian is the corresponding author. The supplementary is available at arXiv.