Scalable Speed-ups for the SMS-EMOA from a Simple Aging Strategy

1 Introduction

In many real-world optimization problems, several objectives have to be optimized simultaneously rather than in isolation, since improving one performance metric often leads to the degradation of another. For such multi-objective optimization problems, multi-objective evolutionary algorithms (MOEAs) have been employed with great success [Zhou et al., 2011]. For example, the famous NSGA-II algorithm [Deb et al.,

∗Corresponding author.

2002], the most widely used MOEA, has received more than 50,000 citations on Google scholar.

Interestingly, different from single-objective optimization, these MOEAs almost always select the next population in a greedy fashion. In the NSGA-II framework, for example, the parent and offspring populations are divided into several fronts by non-dominated sorting and then the first fronts are selected into the next population. As tie-breaker for the critical front, the crowding distance is used, and again the individuals with largest crowding distance survive. Similarly, the NSGA-III [Deb and Jain, 2014] and SMS-EMOA [Beume et al., 2007] extend this same two-stage, greedy method. These two algorithms greedily select according to non-dominated sorting, using references points or the hypervolume contribution as the secondary (greedy) selection criteria.

This greedy behavior in multi-objective evolutionary computation differs quite significantly from single-objective evolutionary computation, where concepts such as selection pressure are explicitly used to quantify the degree of greediness of the selection. Furthermore, classic selection operators such as tournament selection or roulette-wheel selection, are intentionally designed to be somewhat less greedy than truncation selection.

The first to substantially challenge the believe in greedy selection in multi-objective evolutionary computation were Bian et al. [2023]. In the recently very successful runtime analysis methodology [Zheng et al., 2022; Bian and Qian, 2022; Doerr and Qu, 2023a; Doerr and Qu, 2023b; Doerr and Qu, 2023c; Dang et al., 2023; Bian et al., 2023; Dinot et al., 2023; Wietheger and Doerr, 2023; Zheng and Doerr, 2023a; Zheng and Doerr, 2024a; Zheng and Doerr, 2024b; Zheng et al., 2024b; Opris et al., 2024; Ren et al., 2024; Doerr et al., 2025; Alghouass et al., 2025; Doerr et al., 2025; Deng et al., 2025; Opris, 2025a; Opris, 2025b], they designed a stochastic population update for the SMS-EMOA. Instead of performing a greedy selection over the whole combined parent and offspring population, they let (roughly) a random half of the individuals survive irrespective of their quality and conduct the usual selection of the SMS-EMOA only in the other half. With this non-greedy selection mechanism, they obtained a proven speed-up by a factor of max{1, 2k/4 /n} for the bi-objective OJZJ benchmark with problem size n and gap parameter k (this speed-up was later improved to max{1, 2k /n} in [Zheng and Doerr, 2024b]). 1

Following the exciting results on the stochastic population update of Bian et al. [2023], Zheng and Doerr [2024b] (among other results) discussed how these results extend to more than two objectives. For the m-objective mOJZJ benchmark, they proved a speed-up factor of (roughly) max{1, 2k /nm/2 }. Hence the proven speed-up from the stochastic population update vanishes for larger numbers of objectives. Till now, it remains an open question whether a non-elitist survival strategy can result in scalable speed-ups for all number of objectives.

Our contributions: In this paper, we take such an attempt and design a simple aging strategy for the population update process of the SMS-EMOA. We initialize each individual with the age limit τ. Any newly generated individual has an age of 0. Only individuals with an age of at least τ will be subject to the original survival selection of the SMS-EMOA. After the removal, all remaining individuals will increase their ages by 1 and enter into the next generation. This simple aging strategy allows any newly generated individual, irrespective of its quality, to survive for at least τ iterations.

For the SMS-EMOA with this selection strategy, we prove that the runtime for covering the full Pareto front of the biobjective OJZJ benchmark is O(nk+1 /Θ(k)k-1 ), see Theorem 5, comparing favorably with the best known guarantee of O(nk+1 ) for the classic SMS-EMOA [Bian et al., 2023]. For the m-objective version mOJZJ, we show a guarantee of O(Mkmnk /Θ(k)k ), see Theorem 10, and note that the best known upper bound for the classic SMS-EMOA is O(Mmnk ) by Wietheger and Doerr [2024], where M denotes the size of the largest set of pairwise non-dominating solutions of the problem. Hence, a speed-up factor of max{1,Θ(k)k-1 } has been obtained for the m-objective mOJZJ benchmark.

Our experimental results further support these theoretical findings, demonstrating that even for small values of k in both OJZJ and mOJZJ, the aging strategy significantly accelerates the SMS-EMOA algorithm compared to both the original version and the variant with the stochastic population update strategy.

The rest of the paper is organized as follows. Section 2 introduces the basic concept in multi-objective optimization and presents the SMS-EMOA algorithm, including its variant with the stochastic population update strategy. Section 3 introduces our simple aging strategy and gives the basic behavior of this variant when optimizing an m-objective optimization problem. In Section 4 and Section 5, we conduct the runtime analyses of the SMS-EMOA with the aging strategy on OJZJ and mOJZJ. Section 6 presents the experiments, and finally Section 7 concludes our paper.

1 Another non-elitist attempt was studied by Zheng et al. [2024b]. Inspired by the theoretical advantage of the Metropolis algorithm for the single-objective DLB benchmark [Wang et al., 2024], they discussed how to use the Metropolis algorithm for multiple objectives. While that work could detect strengths and weaknesses of different variants of the multi-objective Metropolis algorithm, compared to other MOEAs none of these variants could achieve better theoretical runtime guarantees for the bi-objective DLB benchmark.

2 Preliminaries

2.1 Multi-Objective Optimization

In multi-objective optimization, the goal is to find a set of optimal trade-off solutions that effectively balance multiple conflicting objectives, typically represented as a Pareto set. As common in the theory community, this paper considers the multi-objective pseudo-Boolean maximization problems, that is, to maximize f(x) = (f1(x), f2(x), . . . , fm(x)) subject to x ∈ {0, 1}n where m ∈ N represents the number of objectives, and n ∈ N denotes the problem size. A key concept in multi-objective optimization is Pareto dominance as not all solutions are comparable. We say that a solution x1 ∈ {0, 1}n weakly dominates another solution x2 ∈ {0, 1}n (denoted as x1 ⪰ x2) if fi(x1) ≥ fi(x2) for all i ∈ {1, . . . ,m}. In this case, x1 is at least as good as x2 in all objectives. If, in addition, x1 is strictly better than x2 in at least one objective (i.e., fi(x1) > fi(x2) for some i), then we call x1 dominates x2 (denoted as x1 ≻ x2). A solution x is called Pareto optimal if it is not dominated by any other solutions in {0, 1}n . The set of all Pareto optimal solutions is the Pareto set, and the corresponding function values form the Pareto front.

In the theory of MOEAs, the runtime is typically defined as the number of function evaluations required for the algorithm's population to fully cover the Pareto front [Auger and Doerr, 2011; Zhou et al., 2019; Doerr and Neumann, 2020]. Additionally, in this paper, we will use |x|1 to denote the exact number of ones in x, |x|0 to denote the exact number of zeros in x, and [a..b] to represent the set {a, a + 1, ..., b} for a ≤ b and a, b ∈ Z. We also use M to denote the maximum size of a set of incomparable solutions for a given optimization problem.

2.2 The SMS-EMOA and Stochastic Population Update

The SMS-EMOA is a steady-state variant of the NSGA-II, which replaces the crowding distance by the hypervolume contribution as the secondary selection criterion. This algorithm operates with a fixed population size µ. In each iteration, a single offspring is generated and added to the combined parent and offspring population Rt. To maintain the fixed population size, one individual from Rt will be removed. It first uses the non-dominated sorting procedure to partition Rt into several fronts F1, . . . , Fi∗, where Fi contains all non-dominated individuals in Rt \ ∪i-1 j=1Fj . Within the critical front Fi∗, the individual that contributes the least to the hypervolume will be removed (broken tie randomly). The hypervolume of a set S of individuals w.r.t. reference point r is calculated as HVr(S) = L(⋃u∈S {h ∈ Rm | r ≤ h ≤ f(u)}) where L represents the Lebesgue measure. The hypervolume contribution of an individual x ∈ Fi∗ is defined by ∆r(x, F ∗ i ) := HVr(F ∗ i ) - HVr (F ∗ i \ {x}). See Algorithm 1 for the whole procedure of the classic SMS-EMOA.

The stochastic population update of the SMS-EMOA, proposed in [Bian et al., 2023], only has one change compared to the classic SMS-EMOA. It uniformly at random selects half of the combined population for the survival selection, and the

Algorithm 1: SMS-EMOA

• 1 Generate P0 by selecting µ solutions uniformly and randomly from {0, 1}n with replacement;
• 2 for t = 0, 1, 2, . . . , do
• 3 Select a solution x uniformly at random from Pt;
• 4 Generate x′ by flipping each bit of x independently with probability 1/n;
• 5 Use fast-non-dominated-sort() [Deb et al., 2002] to divide Rt = Pt ∪ {x′ } into F1, . . . , Fi∗ ;
• 6 Calculate ∆r(z, Fi∗) for all z ∈ Fi∗ and find D = arg minz∈Fi∗ ∆r(z, Fi∗ );
• 7 Uniformly at random pick z′ ∈ D and Pt+1 = Rt \ {z′ } ;

Algorithm 2: SMS-EMOA with the Stochastic Population Update

• 1 Generate P0 by selecting µ solutions uniformly and randomly from {0, 1}n with replacement;
• 2 for t = 0, 1, 2, . . . , do
• 3 Select a solution x uniformly at random from Pt;
• 4 Generate x′ by flipping each bit of x independently with probability 1/n;
• 5 Rt = ⌊Pt ∪ {x′ }/2⌋ solutions uniformly and randomly selected from Pt ∪ {x′ } without replacement;
• 6 Use fast-non-dominated-sort() [Deb et al., 2002] to divide Rt into F1, . . . , Fi∗ ;
• 7 Calculate ∆r(z, Fi∗) for all z ∈ Fi∗ and find
• D = arg minz∈Fi∗ ∆r(z, Fi∗ );
• 8 Uniformly at random pick z′ ∈ D and Pt+1 = Pt ∪ {x′ } \ {z′ };

other half directly enters into the next generation. With this strategy, the inferior solutions have the chance (like not being chosen to the survival selection) to the next generation. For a clear comparison with our proposed strategy, we also state its procedure in Algorithm 2.

As introduced before, we note here once again that a speedup by a factor of max{1, 2k/4 /n} is proven in [Bian et al., 2023] (which is subsequently proven to be max{1, 2k /n} in [Zheng and Doerr, 2024b]) for the bi-objective OJZJ benchmark. We also note here, as introduced before as well, that a speed-up factor of only Θ(1) for large m (say m > k) is proven for the m-objective mOJZJ benchmark [Zheng and Doerr, 2024b].

3 The SMS-EMOAwith the Aging Strategy

As mentioned before, the non-elitist stochastic population update cannot scale well from two objectives to more objectives. This section will introduce our non-elitist aging strategy and employ it into the SMS-EMOA for the easy comparison against the stochastic population update [Bian et al., 2023] in the later sections.

Algorithm 3: SMS-EMOA with the Aging Strategy

• 1 Initialize P0 with µ individuals chosen independently and uniformly at random from {0, 1}n with replacement and set their age to τ;
• 2 for t = 0, 1, 2, . . . , do
• 3 Select x ∈ Pt uniformly at random;
• 4 Generate y from x via standard bit-wise mutation and set its age y.age = 0;
• 5 Rt = {x | x ∈ Pt ∪ {y} and x. age ≥ τ};
• 6 Use fast-non-dominated-sort() to divide Rt into F1, . . . , Fi∗ ;
• 7 Let D = argminz∈F ∗ i ∆r(z, Fi∗);
• 8 Uniformly at random pick z′ ∈ D ;
• 9 Pt+1 = Pt ∪ {y} \ {z′ };
• 10 Raise the ages of solutions in Pt+1 by 1;

3.1 Aging Strategy

Aging has been used in different kinds of randomized search heuristics, such as in evolutionary algorithms and artificial immune systems, e.g., [Horoba et al., 2009; Jansen and Zarges, 2009; Jansen and Zarges, 2010a; Jansen and Zarges, 2010b; Jansen and Zarges, 2011b; Jansen and Zarges, 2011a; Oliveto and Sudholt, 2014; Corus et al., 2019; Corus et al., 2020]. Aging operators assign each solution in the population an individual age, which increases by 1 with each generation. Typically a maximum lifespan τ is defined, and any solution exceeding this age is removed from the population [Zarges, 2020]. We resort to this strategy but with some modifications. Instead of the immediate removal, only individuals with the age at least τ will join the survival selection and have the chance to be removed. This is the key simple aging strategy we use to let the inferior solutions have the chance to enter into the next generations, making the algorithm not shortsighted.

In this work, we choose the SMS-EMOA to equip with this strategy, since the efficiency of the SMS-EMOA with the nonelitist stochastic population update is proven for bi-objective OJZJ [Bian et al., 2023]. In detail, we first initialize µ individuals randomly, and assign all individuals with the age limit τ. In each generation, one offspring individual is generated and assigned with the age of 0. Among the µ + 1 combined parent and offspring individuals, the individuals with the age at least τ will be chosen to form the multiset Rt, to which the original survival selection will be applied. After the survival selection, the ages of all remaining individuals in the population are incremented by 1. All other procedures in the algorithm remain consistent with the original SMS-EMOA. The details are shown in Algorithm 3. Obviously, this strategy ensures that any newly generated individual, including the inferiors, can survive for at least τ generations.

3.2 Basic Behavior

The following lemma gives the basic behavior of the SMS-EMOAwith the aging strategy. That is, if the size of the population is at least the same as the size of largest set of incomparable solutions plus τ , that is, M+τ , then any individual in the current population will have future individuals that weakly dominate it. Due to the space limitation, all proofs are omitted but will be available in an arXiv preprint [Li et al., 2025].

Lemma 1. Consider any m-objective optimization problem. Consider using the SMS-EMOA with the aging strategy and with the size of the population µ ≥ M + τ to solve this problem. If Pt contains a solution x, then at any later time t′ > t, the population Pt′ will contain a solution y such that y ⪰ x. In particular, any Pareto front point once reached will be maintained in all future generations.

This important behavior of not being worse will be frequently used for the runtime analysis for the Pareto front coverage.

4 Runtime for Bi-Objective OJZJ

Recall that the stochastic population update shows a speedup by a factor of max{1, 2Θ(k) /n} for the SMS-EMOA optimizing the bi-objective OJZJ benchmark [Bian et al., 2023]. In this section, we will also show that our proposed aging strategy can speed up the SMS-EMOA by a factor of max{1,Θ(k)k-1 }, which is also faster than the one with the stochastic population update by a factor of max{1, Θ(k)k n/k}.

4.1 OJZJ

JUMP functions [Droste et al., 2002] are the most extensively studied multimodal benchmark in the theory of randomized search heuristics, particularly in evolutionary algorithms [Bambury et al., 2024]. They represent a class of problems with a tunable gap parameter k, which reflects different depths from the local optima to the global optimum. The OJZJ benchmark proposed by Doerr and Zheng [2021] is a bi-objective counterpart of the JUMP functions with problem size n and jump size k, which has been widely used to understand the theoretical behavior of the MOEAs for multimodal problems [Doerr and Qu, 2023a; Doerr and Qu, 2023b; Doerr and Qu, 2023c; Bian et al., 2023; Doerr et al., 2025]. The OJZJ benchmark involves two objectives, that is, one is the JUMP benchmark, and the other is the JUMP function applied to ¯x = 1 - x. See the formal definition in the following.

Definition 2 ([Doerr and Zheng, 2021]). Let n ∈ N and k = [1..n]. The function OJZJn,k = (f1, f2) : {0, 1}n → R2 is defined by

Figure 1 illustrates the characteristics of the OJZJ benchmark. As proven in [Doerr and Zheng, 2021], the Pareto set is {x | |x|1 ∈ [k..n - k] ∪ {0, n}} and the Pareto front is {(a, 2k + n - a) | a ∈ [2k..n] ∪ {k, n + k}}. If k ≤ n/2, the size of the largest set of incomparable individuals, M, is n - 2k + 3. Since the objective values of OJZJ are all greater than 0, we set the reference point for the SMS-EMOA to (-1, -1). As mentioned before, we will calculate the runtime to cover the full Pareto front.

4.2 Runtime

The optimization process can be divided into two phases. The first phase ends when all inner Pareto front points {(a, 2k + n - a) | a ∈ [2k..n]} are covered. Then the second phase starts, and ends when the full Pareto front is covered for the first time. Lemma 3 considers the runtime of the first

iterations in expectation, the population will cover the inner Pareto front. The proof idea is that once the population includes at least one solution in the inner Pareto optimal set {x | |x|1 ∈ [k..n - k]}, then its Hamming neighbor belonging to the inner Pareto optima can be generated by flipping one of the 0-bits or one of the 1-bits. According to Lemma 1, any element of Pareto front will be retained. By repeating this process and selecting the appropriate individuals, the entire inner Pareto front can be covered.

Lemma 3. Let k ≤ n/2. Consider using the SMS-EMOA with the aging strategy and with the size of the population µ ≥ M + τ to optimize the OJZJ problem, then the expected number of iterations is at most O(µn logn) +

The following lemma rigorously provides the runtime analysis of the algorithm for the critical second phase, which starts with a population already covering the inner Pareto front and ends when the full Pareto front is covered. In other words, during this phase, we need to find the two extreme solutions 1n and 0n . The proof uses a waiting time argument. That is, we first calculate the probability p of generating the desired extreme solution 1n (or symmetrically 0n ) from the current boundary of the inner Pareto front, within at most kτ iterations. Subsequently we bound the expected waiting time by kτ p . More precisely, we divide kτ iterations into k steps and within each step of at most τ generation, we calculate the probability of making an improvement. Note that the aging strategy ensures that any newly generated solution survives for at least τ generations. Then we easily obtain the overall probability p via multiplying the probabilities in all steps for their independence, and thus the runtime argument is obtained.

Lemma 4. Let k ≤ n/2. Consider using the SMS-EMOA with the aging strategy and with the size of the population µ ≥ M + τ to optimize OJZJ. Assume that the current population covers all inner Pareto front points. Then the full

Pareto front will be covered in at most kτ ( e2 n (1-exp(- τµ ))k )k iterations in expectation.

Combining Lemmas 3 and 4, we derive the runtime of the SMS-EMOA with the aging strategy stated in the following theorem.

Theorem 5. Let k ≤ n/2. Consider using the SMS-EMOA with the aging strategy and with the size of the population µ ≥ M + τ to optimize OJZJ, then the expected iterations to cover the full Pareto front is at most

Note that the expected runtime of the original SMS-EMOA is O(nk+1 ) for µ = Θ(n) [Bian et al., 2023]. We set τ = Θ(n) and µ = Θ(n - 2k + 4 + τ) to also ensure µ = Θ(n). In this setting, from Theorem 5, we know that the expected iterations for the SMS-EMOA with the aging strategy to cover the full Pareto front is O(nk+1 /(Θ(k))k-1 ). Hence, we see a speed-up by a factor of max{1,Θ(k)k-1 }. Also noting O(nk+2 /2Θ(k) ) expected number of iterations for the stochastic population update [Bian et al., 2023; Zheng and Doerr, 2024b], we see our aging strategy surpasses this by a factor of max{1, Θ(k)k n/k}.

5 Runtime for m-Objective mOJZJ

In the previous section, we demonstrated that the SMS-EMOA with the aging strategy outperforms the original SMS-EMOA and the one with the stochastic population update strategy on the bi-objective OJZJ problem. As pointed out before, Zheng and Doerr [2024b] proved that the speed-up of the stochastic population update mechanism cannot scale well from two objectives to more objectives. In this section, we will show that our simple aging strategy performs well for many objectives, and achieves the speed-up by a factor of max{1, Θ(k)k-1 } against the original SMS-EMOA as well as the one with the stochastic population update strategy.

5.1 mOJZJ

The mOJZJ benchmark proposed by [Zheng and Doerr, 2024b] is a m-objective counterpart of the bi-objective OJZJ

benchmark [Doerr and Zheng, 2021], and is the first multimodal many-objective benchmark proposed for theoretical analysis. Zheng and Doerr [2024b] proved that the SMS-EMOA can compute the full Pareto front of this benchmark in an expected number of O(µMnk ) iterations, where M denotes the size of the Pareto front. Later, Wietheger and Doerr [2024] proved near-tight runtime guarantees for the SEMO, GSEMO, SMS-EMOA and NSGA-III algorithms on this multimodal benchmark class and other popular unimodal many-objective variants of ONEMINMAX, COCZ, and LOTZ. Zheng, Gao and Doerr [2024a] conducted the mathematical runtime analysis for the NSGA-II with their newly proposed variant of the crowding distance, showing that this algorithm can solve the mOJZJ benchmark efficiently compared with the original NSGA-II. The mOJZJ benchmark involves m objectives. The bit string of length n is divided into m/2 blocks, each of length 2n/m. For each block, a bi-objective OJZJ problem is defined. See the following definition.

Definition 6 ([Zheng and Doerr, 2024b]). Let m be the even number of objectives. Let the problem size n be a multiple of m/2. Let n′ = 2n m ∈ N and k ∈ [1..n′ ]. Let Bi := [(i - 1)n′ + 1..in′ ] for i ∈ [1..m/2] denote the i-th block of the n bit positions. Then for any x = (x1, . . . , xn), the mOJZJk = (f1(x), . . . , fm(x)) : {0, 1}n → Rm is defined by

where the OJZJ function is defined in Definition 2.

The Pareto set of mOJZJ is {x ∈ {0, 1}n | ∀i ∈ [1..m/2], |xBi |1 ∈ [k..n′ - k] ∪ {0, n′ }} and the Pareto front is {(a1, n′ + 2k - a1, . . . , am/2, n′ + 2k - am/2) | a1, . . . , am/2 ∈ [2k..n′ ] ∪ {k, n′ + k}}. Hence, the size of the Pareto front is (n′ -2k +3) m2 . Different from OJZJ, the size of the largest set of incomparable solutions is not equal to the size of the Pareto front, and a trivial upper bound of (n′ + 1) m2 is given in [Zheng and Doerr, 2023b] when k ≤ n′ /2, M ≤ (n′ + 1) m2 . Here we set the reference point to (-1, . . . , -1) with m dimensions.

5.2 Runtime

We now analyze the runtime of the SMS-EMOA with the aging strategy optimizing mOJZJ. To facilitate the proof, we resort to the technique used in [Wietheger and Doerr, 2024] which uses a union bound to establish a tail bound of the runtime. Before the analysis, we first recall several definitions from [Wietheger and Doerr, 2024]. Let m′ = m/2. The set Km,k is the set of function values of individuals in which each block has either exactly k 0-bits or k 1-bits. Formally, Km,k = {(a1, . . . , am′) | ai ∈ {k, n m′ -k} for all i ∈ [m′ ]}. Similarly, the set Cm,k is the set of function values of individuals in which each block consists either all bits being 1, all bits being 0, exactly k 0-bits, or k 1-bits. Formally, Cm,k = {(a1, . . . , am′) | ai ∈ {0, k, n m′ -k, n m′ } for all i ∈ [m′ ]}. We divide the optimization process into three phases. The first phase starts with the initialization of the algorithm and concludes when all points in Km,k are covered. The sec-

ond phase begins thereafter and ends when all points in Cm,k are covered. The final phase ends when the remaining Pareto front is covered.

For the first phase and the final phase, we apply Lemma A1 and Lemma A3 from [Wietheger and Doerr, 2024], which provide the runtime analyses of the GSEMO on mOJZJ. These results can be adapted to the SMS-EMOA with the aging strategy when the size of the population µ ≥ M + τ . The reason is that Section 5 of [Wietheger and Doerr, 2024] outlines three sufficient properties to prove such upper bounds. The survival guarantee provided by Lemma 1 satisfies the first one for not losing already made progress. As for the remaining two properties, the probability of selecting an individual from the population for mutation is 1/µ and standard bit-wise mutation is employed. Therefore, we obtain the following lemmas for the runtime of the first and final phases.

Lemma 7. Let k ≤ n′ /2. Consider the SMS-EMOA with the aging strategy and with the size of the population µ ≥ M +τ to optimize mOJZJ. Let T denote the number of iterations until the population covers Km,k and let

Then T ≤ t with probability at least 1 - 1n .

Lemma 8. Let k ≤ n′ /2. Consider the SMS-EMOA with the aging strategy and with population size µ ≥ M+τ optimizing mOJZJ starting with a population that covers Cm,k. Let T denote the number of iterations until the population covers the entire Pareto front and let

Then T ≤ ⌈t⌉ with probability at least 1 - 1n .

Now we consider the second phase that begins when all points in Km,k are covered and ends when all points in Cm,k are covered. From the analysis of Lemma 4, we know that the aging strategy helps to remain the inferior individuals, thereby increasing the probability of generating individuals with all 1-bits or all 0-bits. The following lemma shows that it continues to provide advantages in traversing fitness valleys for many-objective optimization. We first use the same approach to Lemma 4, calculating the probability of changing a block with n′ - k 1-bits (or 0-bits) to the extreme block 1n′ (or 0n′ ) within at most kτ iterations. Then based on this, we calculate the tail bound for the time required to find the extreme solution 1n which has m′ extreme blocks. A union bound is further used over the tail bounds to bound the time required to cover Cm,k.

Lemma 9. Let k ≤ n′ /2. Consider the SMS-EMOA with the aging strategy and with population size µ ≥ M+τ optimizing mOJZJ starting with a population that covers Km,k. Let T denote the number of iterations until the population covers Cm,k and let

Then T ≤ t with probability at least 1 - 1n . Further,

Combining Lemmas 7 to 9, similarly using a simple restart argument to obtain the expected value for the first and final phase, we can easily derive the runtime of the SMS-EMOA with the aging strategy in the following theorem.

Theorem 10. Let k ≤ n′ /2. Consider the SMS-EMOA with the aging strategy that µ ≥ M + τ to optimize mOJZJ. Let T denote the number of iterations until the population covers the Pareto front and let

Then T ≤ t with high probability. Further,

With τ = Θ(M) and population size µ = Θ(M + τ), the SMS-EMOA with the aging strategy requires O(Mkm(n/Θ(k))k ) iterations in expectation to cover the full Pareto front of mOJZJ. Compared to the runtime guarantee O(Mmnk ) proved in [Wietheger and Doerr, 2024] for the original SMS-EMOA, the aging strategy achieves a speedup by a factor of max{1,Θ(k)k-1 }. Together with Theorem 5 for bi-objective OJZJ, we see that our aging strategy achieves a scalable speed-up factor of max{1, Θ(k)k-1 } for all number of objectives. It is a nice property that the stochastic population update strategy doesn't have (Note the speed-up reduces significantly for increasing the number of objectives, as mentioned before). Besides, a speed-up factor of max{1,Θ(k)k-1 } for our aging strategy is also obtained compared to the stochastic population update.

6 Experiments

This section conducts experiments to intuitively see the efficiency of the aging strategy for two and more objectives. For comparison, we also include experiments for the original SMS-EMOA and the one with the stochastic population update.

For the bi-objective problem, we chose OJZJ as characterized in Theorem 5. We set the size of the problem n ∈ {10, 15, 20, 25, 30} and fix the gap parameter at k = 4 in order to see whether the proven asymptotic runtime advantages hold for small and medium problem sizes. We set the age limit τ = µ/2 and the size of the population to 2(n-2k+4), which yields the optimal asymptotic bounds established in Theorem 5.

Each algorithm was tested with 50 independent runs, and terminated when the full Pareto front was covered for the first time. Figure 2 illustrates the mean (with standard deviations) number of iterations for each algorithm to cover the full Pareto front for the first time. From Figure 2, we can easily see a notable speed-up of about 7 of the aging strategy compared to the original SMS-EMOA, as well as a speed-up of around 5 compared to the stochastic population update strategy. These results clearly indicate that the superiority of the aging strategy already appears for small problem sizes and small gap size .

For many-objective optimization, we chose mOJZJ as in Theorem 10, and we fixed the number of objectives to m = 4. We do not set larger numbers of objectives, since (i) experiments with m = 4 finished in a reasonable time and (ii) with m = 4 we intend to see whether our aging strategy can result in a good speed-up even for small number of objectives. We set the problem size n ∈ {12, 16, 20, 24, 28} and gap size k = 3 to see whether the asymptotic results hold for small and medium problem sizes. The age limit τ was still set to µ/2 and the population size was set to 2((n′ +1)m/2 +1) for the best asymptotic runtime in Theorem 10. Due to the large number of fitness evaluations, each algorithm was tested with 20 independent runs, which we consider also sufficient for a reliable performance comparison, and terminated when the full Pareto front was covered for the first time. From Figure 3, we easily see the clear superiority of the SMS-EMOA with the aging strategy against the original one and the one with the stochastic population update. Note that the theoretical speed-up factor against the other two is Θ(k)k-1 from Theorem 10. For this setting, kk-1 = 32 = 9. From the plot, we know such speed-up factor is around 3 compared to the original SMS-EMOA and is around 2 compared to the one with the stochastic population update strategy, which means that the theoretical speed-up is already witnessed for small problem sizes, small gap size, and small number of objectives.

7 Conclusion

In this paper, to tackle the quest for a scalably efficient nonelitist selection strategy for MOEAs, we proposed a simple aging strategy, essentially giving each new individual τ iterations to develop before being prone to removal, and added it to the SMS-EMOA. A speed-up of max{1,Θ(k)k-1 } compared to the original SMS-EMOA (and also the one with the stochastic population update) is proven for the m-objective JUMP benchmark for all even m. This is the first non-elitist strategy for which a speed-up not vanishing for larger numbers of objectives is proven.

Also for the bi-objective JUMP benchmark, our speed-up of max{1, Θ(k)k-1 } compares favorably with the previously shown speed-up of max{1, 2k /n} by the stochastic population update strategy, and in particular means that a positive speed-up is seen for small values of k, which are most relevant (only constant k give a polynomial runtime). Our experiments support the above findings.

From our understanding of the mathematical proofs, we conjecture that our simple non-elitist aging strategy can be effective in other MOEAs as well, and list this as our most interesting future work.

Acknowledgments

This work was supported by National Natural Science Foundation of China (Grant No. 62306086, 62350710797), Science, Technology and Innovation Commission of Shenzhen Municipality (Grant No. GXWD20220818191018001), and Guangdong Basic and Applied Basic Research Foundation (Grant No. 2025A1515011936). This research benefited from the support of the FMJH Program PGMO. This work has profited from many fruitful discussions at the Dagstuhl Seminars 23361 Multiobjective Optimization on a Budget and 24271 Theory of Randomized Optimization Heuristics.