An Archive Can Bring Provable Speed-ups in Multi-Objective Evolutionary Algorithms

1 Introduction

Multi-objective optimization refers to an optimization scenario of considering multiple objectives simultaneously. Since the objectives of a multi-objective optimization problem (MOP) are usually conflicting, there does not exist a single optimal solution, but a set of trade-off solutions, called Pareto optimal solution set (or Pareto front in the objective space). Evolutionary algorithms (EAs), a kind of randomized heuristic optimization algorithms inspired by natural evolution, have been found well-suited to MOPs. Their population-based search mechanism can approximate a set of Pareto optimal solutions within one execution, with one solution representing a different trade-off between the objectives.

Over the last decades, there have been a lot of well-known multi-objective EAs (MOEAs) developed, such as the nondominated sorting genetic algorithm II (NSGA-II) [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 the MOEA area, recently there is a trend of using an archive to store non-dominated solutions generated during the search [Li et al., 2023b]. A major reason for this practice is that the population in MOEAs may fail to preserve high-quality solutions found even with elite preservation [Knowles and Corne, 2004]. During the evolutionary process, it is highly likely that there are more nondominated solutions generated than the capacity of the population. As such, a population truncation needs to take place to remove excess non-dominated solutions (e.g., on the basis of their crowdedness in the population). However, the population later may accept new solutions which are nondominated to the current population but being dominated by the ones removed previously (due to the dynamics of the evolution, for example, some area becomes sparse again). Consequently, the final population may have a large portion of dominated solutions. This applies to all practical MOEAs [Li et al., 2023b]. For example, it has been reported in [Li and Yao, 2019] that on some problems (such as DTLZ7 [Deb et al., 2005]), nearly half of the final population of NSGA-II and MOEA/D are not globally optimal (i.e., being dominated by other solutions which were discarded during their evolutionary process). This unwelcome issue has been frequently observed in various scenarios, from synthetic test suites [Laumanns et al., 2002; Fieldsend et al., 2003; Li and Yao, 2019] to real-world problems [Fieldsend, 2017; Chen et al., 2019].

An easy way to fix the above issue is to use an (unbounded) archive that stores all non-dominated solutions found, leaving the search focused on finding new non-dominated solutions. This is indeed an increasingly popular practice [Li et al., 2023b], given the capacity of today's computers that storing millions of solutions does not pose a problem. Various studies of using an unbounded archive emerged [Li et al., 2023b], including to store high-quality solutions [DuboisLacoste et al., 2015; Ishibuchi et al., 2020; Zhang et al., 2023], to incorporate it into MOEAs as an important algorithm component [Wang et al., 2019; Li et al., 2021], to benchmark different MOEAs [Tanabe and Oyama, 2017; Brockhoff and Tuˇsar, 2019], to use it to identify if the search stagnates [Li et al., 2023a], and to design efficient data structure for it [Glasmachers, 2017; Jaszkiewicz and Lust, 2018; Fieldsend, 2020; Nan et al., 2020]. An archive (even a bounded one) can significantly improve the performance of MOEAs, as shown empirically in [Bezerra et al., 2019].

In this paper, we theoretically show that using an archive can bring speed-ups for MOEAs. Specifically, we study the expected running time of two well-established MOEAs, NSGA-II and SMS-EMOA, when using an archive to store non-dominated solutions generated during the search. We consider two bi-objective optimization problems, OneMinMax and LeadingOnes-TrailingZeroes, which were commonly used in theoretical studies of MOEAs [Laumanns et al., 2004; Doerr et al., 2013; Nguyen et al., 2015; Bian and Qian, 2022; Zheng and Doerr, 2023a].

The results are given in Table 1. As can be seen in the table, using an archive allows a small constant population size, which brings an acceleration of Θ(n) on the expected running time. Note that the original algorithms without using an archive require the population size µ to be at least the same size of the problem's Pareto front (i.e., µ ≥ 2(n + 1) for NSGA-II and µ ≥ n+1 for SMS-EMOA, where n+1 is the size of the Pareto front), otherwise Pareto optimal solutions can be lost even if they have been found previously. Using an archive that stores all the Pareto optimal solutions generated enables the algorithms not to worry about losing Pareto optimal solutions, but only endeavoring to seek new Pareto optimal solutions, thus speeding up the search process.

Over the past two decades, there is a substantial number of theoretical studies in the area of MOEAs, particularly regarding their running time complexity analyses. It starts with the analysis of a simple evolutionary multi-objective optimizer (SEMO) and its global variant, GSEMO, for solving multi-objective synthetic and combinatorial optimization problems [Giel, 2003; Laumanns et al., 2004; Neumann, 2007; Giel and Lehre, 2010; Neumann and Theile, 2010; Doerr et al., 2013; Qian et al., 2013; Bian et al., 2018]. On the other side, based on SEMO and GSEMO, the effectiveness of several parent selection and reproduction methods has also been studied [Laumanns et al., 2004; Friedrich et al., 2011; Qian et al., 2013; Qian et al., 2016; Doerr and Zheng, 2021].

Recently, attention is being shifted to the analysis of practical MOEAs. The expected running time of (µ + 1) SIBEA, i.e., an MOEA using the hypervolume indicator to update the population, was analyzed on several synthetic problems [Brockhoff et al., 2008; Nguyen et al., 2015; Doerr et al., 2016]. Very recently, Zheng and Doerr [2023a] analyzed the expected running time of NSGA-II, for the first time, by considering the bi-objective OneMinMax and LeadingOnesTrailingZeroes problems. Since then, the effectiveness of different components and mechanisms in NSGA-II, e.g., crowding distance [Zheng and Doerr, 2022], stochastic tournament selection [Bian and Qian, 2022], fast mutation [Doerr and Qu, 2023a], crossover [Dang et al., 2023b; Doerr and Qu, 2023c], and diversity maintenance [Ren et al., 2024], has also been analyzed. More results on NSGA-II include [Cerf et al., 2023; Doerr and Qu, 2023a; Doerr and Qu, 2023b; Zheng and Doerr, 2023b]. Furthermore, the expected running time of other well-established MOEAs has also been analyzed, e.g., MOEA/D [Huang et al., 2019; Huang and Zhou, 2020; Huang et al., 2021], SMS-EMOA [Bian et al., 2023; Ren et al., 2024; Zheng and Doerr, 2024], and NSGA-III [Wietheger and Doerr, 2023], in addition to the analysis of them under different optimization models such as under noise [Dang et al., 2023a; Dinot et al., 2023] and the interactive model [Lu et al., 2024].

Yet, all the above work regarding practical MOEAs needs a population with a commensurable size of the problem's Pareto front. This may not be very practical since one may not be able to know the size of the problem's Pareto front before the optimization. The proposed work in this paper addresses this issue and proves that a small population, with an archive, even works better. This result not only provides a theoretical confirmation for an increasingly popular practice in the development of MOEAs, but can also be beneficial to the theory community towards studying more practical MOEAs.

2 Preliminaries

In this section, we first give basic concepts in multi-objective optimization, which is followed by the considered algorithms NSGA-II and SMS-EMOA, and the archive mechanism. Lastly, we describe the OneMinMax and LeadingOnesTrailingZeroes problems studied in this paper.

2.1 Multi-objective Optimization

Multi-objective optimization aims to optimize two or more objective functions simultaneously, as presented in Definition 1. In this paper, we considermaximization (minimization can be defined similarly), and pseudo-Boolean functions, i.e., the solution space X = {0, 1}n . Since the objectives are usually conflicting, there does not exist canonical complete order in the solution space X, and we use the domination relationship in Definition 2 to compare solutions. A solution is Pareto optimal if it is not dominated by any other solution in X, and the set of objective vectors of all the Pareto optimal solutions is called 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 (Domination). 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.

2.2 NSGA-II and SMS-EMOA

The NSGA-II algorithm [Deb et al., 2002], as presented in Algorithm 1, is a very popular MOEA which incorporates two substantial features, i.e., non-dominated sorting and crowding distance. It starts from an initial population of µ (without loss of generality, we assume that µ is even) random solutions (line 1). In each generation, NSGA-II employs binary tournament selection to select parent solutions (line 5), which picks two solutions randomly from the population P with replacement, and then selects a better one as the parent solution (ties broken uniformly). Then, onepoint crossover is performed on the two parent solutions with probability pc (lines 6-11), which selects a crossover point i ∈ {1, 2, . . . , n} uniformly at random, where n is the problem size, and then exchanges the first i bits of two solutions. The bit-wise mutation operator, which flips each bit of a solution independently with probability 1/n, is then applied to generate offspring solutions (line 12). After a set P ′ of µ offspring solutions have been generated, the solutions in the current and offspring populations are partitioned into nondominated sets R1, . . . ,Rv (line 15), where R1 contains all the non-dominated solutions in P ∪ P ′ , and Ri (i ≥ 2) contains all the non-dominated solutions in (P ∪ P ′ ) \ ∪i-1 j=1Rj . Note that a solution is said to be with rank i if it belongs to Ri. Then, the solutions in R1, . . . ,Rv are added into the next population, until the population size exceeds µ (lines 1619). For the critical set Ri whose inclusion makes the population size larger than µ, the crowding distance is computed for each of the contained solutions (line 20). Crowding distance reflects the diversity of a solution. For each objective fj, 1 ≤ j ≤ m, the solutions in Ri are sorted according to their objective values in ascending order, and we assume the sorted list is x1 , x2 , . . . , xk ; the crowding distance of the solution xl with respect to fj is set to ∞ if l ∈ {1, k}, and (fj(xl+1 ) - fj(xl-1 ))/(fj(xk ) - fj(x1 )) otherwise. The

Algorithm 1 NSGA-II [Deb et al., 2002]

Input: objective functions f1, f2 . . . , fm, population size µ, probability pc of using crossover

• 1: P ← µ solutions uniformly and randomly selected from {0,1}n with replacement;
• 2: while criterion is not met do
• 3: let P ′ = ∅, i = 0;
• 4: while i < µ/2 do
• 5: apply binary tournament selection twice to select two solutions x and y;
• 6: sample u from uniform distribution over [0, 1];
• 7: if u < pc then
• 8: apply one-point crossover on x and y to generate two solutions x′ and y′
• 9: else
• 10: set x′ and y′ as copies of x and y, respectively
• 11: end if
• 12: apply bit-wise mutation on x′ and y′ to generate x′′ and y′′ , respectively, and add them into P ′ ;
• 13: i = i +1
• 14: end while
• 15: partition P ∪P ′ into non-dominated sets R1, . . . ,Rv;
• 16: let P = ∅, i = 1;
• 17: while |P ∪Ri| < µ do
• 18: P = P ∪Ri, i = i +1
• 19: end while
• 20: assign each solution in Ri with a crowding distance;
• 21: sort the solutions inRi in ascending order by crowding distance, and add the last µ - |P | solutions into P
• 22: end while
• 23: return P

final crowding distance of a solution is the sum of the crowding distance with respect to each objective. Finally, the solutions in Ri are selected to fill the remaining population slots where the solutions with larger crowding distance are preferred (line 21). Note that when using binary tournament selection in line 5, the selection criterion is based on rank and crowding distance, that is, a solution x is superior to y if x has a smaller rank, or x and y have the same rank but x has a larger crowding distance than y. The probability pc of using crossover is set to 0.9, just as the setting in [Deb et al., 2002].

The SMS-EMOA algorithm [Beume et al., 2007] as presented in Algorithm 2 is also a popular MOEA, which employs non-dominated sorting and hypervolume indicator to update the population. Starting from an initial population of µ random solutions (line 1), in each generation, it randomly selects a parent solution x from the current population for reproduction (line 3). With probability pc (similar to NSGA-II, pc is set to 0.9), 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 actually produces two 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 is applied on x′ to generate one offspring solution (line 11). Then, similar to line 15 of Algorithm 1,

Algorithm 2 SMS-EMOA [Beume et al., 2007]

Input: objective functions f1, f2 . . . , fm, population size µ, probability pc of using crossover

• 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 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 one solution 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: partition P∪{x′′} into non-dominated sets R1, ...,Rv;
• 13: let z = arg minx∈Rv ∆r(x, Rv);
• 14: P ← (P ∪ {x′′ }) \ {z}
• 15: end while
• 16: return P

the union of the current population and the newly generated offspring solution is partitioned into non-dominated sets R1, . . . ,Rv (line 12), and one solution z ∈ Rv that minimizes∆r(x,Rv) :=HVr(Rv)-HVr(Rv\{x}) is removed (lines 13-14), where HVr(X) = Λ( ∪x∈X {f ′ ∈ Rm | ∀1 ≤ i ≤ m : ri ≤ f ′ i ≤ fi(x)}) denotes the hypervolume of a solution set X with respect to a reference point r ∈ Rm (satisfying ∀1 ≤ i ≤ m, 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, and Λ denotes the Lebesgue measure. A larger hypervolume value implies a better approximation with regards to both convergence and diversity. Note that when SMS-EMOA solves bi-objective problems, we use the original setting in [Beume et al., 2007] that the two extreme points (i.e., the objective vectors which contain the largest objective value for some fi, i ∈ {1, 2}) are always kept in the population regardless of their hypervolume loss.

2.3 NSGA-II and SMS-EMOAwith an Archive

In the original NSGA-II and SMS-EMOA, there is no archive used. As explained previously, the non-dominated solutions may lose even if they have been found once. Using an archive can easily address this issue. That is, 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. Additional algorithmic steps incurred by adding an archive in NSGA-II and SMS-EMOA are given as follows. For NSGA-II in Algorithm 1, an empty set Q is initialized in line 1, the following lines

end for

are added after line 14, and the set Q instead of P is returned in the last line. For SMS-EMOA in Algorithm 2, an empty set Q is also initialized in line 1, the following lines

are added after line 11, and the set Q instead of P is returned in the last line.

2.4 OneMinMax and LeadingOnesTrailingZeroes

Now we introduce two bi-objective problems, OneMinMax and LeadingOnesTrailingZeroes considered in this paper. Theses two problems have been widely used in MOEAs' theoretical analyses [Laumanns et al., 2004; Brockhoff et al., 2008; Doerr et al., 2013; Qian et al., 2013; Bian and Qian, 2022; Zheng and Doerr, 2023a].

The OneMinMax problem presented in Definition 3 aims to simultaneously maximize the number of 0-bits and the number of 1-bits of a binary bit string. The Pareto front is {(a, n - a) | a ∈ [0..n]}, whose size is n + 1, and the Pareto optimal solution corresponding to (a, n - a), a ∈ [0..n], is any solution with (n-a) 1-bits. Note that we use [l..r] to denote the set {l, l +1, . . . , r} of integers throughout the paper. We can see that any solution x ∈ {0, 1}n is Pareto optimal for this problem.

Definition 3 (OneMinMax [Giel and Lehre, 2010]). The OneMinMax problem of size n is to find n bits binary strings which maximize f(x) = (n - ∑ni=1 xi, ∑ni=1 xi), where xi denotes the i-th bit of x ∈ {0, 1}n .

The LeadingOnesTrailingZeroes problem presented in Definition 4 aims to simultaneously maximize the number of leading 1-bits and the number of trailing 0-bits of a binary bit string. The Pareto front is {(a, n - a) | a ∈ [0..n]}, whose size is n + 1, and the Pareto optimal solution corresponding to (a, n - a), a ∈ [0..n], is 1a 0n-a , i.e., the solution with a leading 1-bits and n - a trailing 0-bits.

Definition 4 (LeadingOnesTrailingZeroes [Laumanns et al., 2004]). The LeadingOnesTrailingZeroes problem of size n is to find n bits binary strings which maximize f(x) = (∑ni=1 ∏ij=1 xj , ∑ni=1 ∏nj=i (1-xj)), where xj denotes the j-th bit of x ∈ {0, 1}n .

3 Analysis of NSGA-II with an Archive

In this section, we analyze the expected running time of NSGA-II in Algorithm 1 using an archive. Note that the running time of an EA is usually measured by the number of fitness evaluations, which is often the most time-consuming step in the evolutionary process. We prove in Theorem 1 that the expected number of fitness evaluations of NSGA-II using an archive for solving OneMinMax is O(µn log n), where the population size µ ≥ 4. The proof idea is to divide the optimization procedure into two phases, where the first phase aims at finding the two extreme Pareto optimal solutions 1n and 0n , and the second phase aims at finding the remaining objective vectors in the Pareto front.

Theorem 1. For NSGA-II solving OneMinMax, if using an archive, and a population size µ such that µ ≥ 4, then the expected number of fitness evaluations for finding the Pareto front is O(µn logn).

Proof. We divide the running process of NSGA-II into two phases. The first phase starts after initialization and finishes until 1n and 0n are both found; the second phase starts after the first phase and finishes when the Pareto front is found.

For the first phase, we will prove that the expected number of generations for finding 0n is O(n logn), and then the same bound holds for finding 1n analogously. We first show that the maximal f1 value of the solutions in the population P, i.e., maxx∈P |x|0, will not decrease, where |x|0 denotes the number of 0-bits in x. Let C denote the set of solutions in P ∪ P ′ with the maximal f1 value, where P ′ denotes the offspring population. Because of P ⊆ P ∪ P ′ and the definition of C, we have for any x ∈ C, |x|0 ≥ maxx∈P |x|0. Thus, we only need to show that one solution in C will be maintained in the next population. Because all the solutions in C have the maximal f1 value and the same f2 value, they cannot be dominated by any solution in P ∪P ′ , implying that they all have rank 1, i.e., belong to R1 in the non-dominated sorting procedure. If |R1| ≤ µ, all the solutions in C will be maintained in the next population. If |R1| > µ, the crowding distance of the solutions in R1 needs to be computed. When the solutions in R1 are sorted according to f1 in ascending order, one solution in C (denoted as x∗ ) must be put in the last position and thus has infinite crowding distance. Note that only solutions in the first and the last positions can have infinite crowding distance. As OneMinMax has two objectives, at most four solutions in R1 can have infinite crowding distance. Thus, x∗ is among the best four solutions in R1 and must be included in the next population (note that µ ≥ 4), implying that the maximal f1 value will not decrease.

Next, we analyze the increase of the maximal f1 value. Assume that currently the maximal f1 value is i (i < n), i.e., maxx∈P |x|0 = i. When using binary tournament selection to select a parent solution, the competition between the two randomly selected solutions is based on rank and crowding distance (note that the rank and crowding distance here are computed based on the current population P instead of the union of the current population and the offspring population) with ties broken uniformly. As analyzed in the last paragraph, a solution x ∈ P with |x|0 = i must have rank 1 and infinite crowding distance. Once x is selected for competition (whose probability is 1/µ), it will always win, if the other solution selected for competition has larger rank or finite crowding distance; or win with probability 1/2, if the other solution has the same rank and crowding distance as x, resulting in a tie which is broken uniformly at random. Thus, x can be selected as a parent solution with probability at least 1/(2µ). In the reproduction procedure, a solution with more 0-bits can be generated from x if crossover is not performed (whose probability is 1 - 0.9 = 0.1) and only one of the 1-bits in x is flipped by bit-wise mutation (whose probability is ((n - |x|0)/n) · (1-1/n)n-1 ). Thus, the probability of generating a solution with more than i 0-bits is at least

Because in each generation, µ/2 pairs of parent solutions will be selected for reproduction, the probability of generating a solution with more than i 0-bits is at least

where the inequalities hold by 1 + a ≤ ea for any a ∈ R. Because the solution with the most number of 0-bits will be maintained in the population, the expected number of generations for increasing the maximal f1 value to n, i.e., finding 0n , is at most ∑n-1 i=0 O(n/(n-i)) = O(n log n). That is, the expected number of generations of the first phase is O(n log n).

Now we consider the second phase, and will show that NSGA-II can find the whole Pareto front in O(n logn) expected numbers of generations. Note that after phase 1, 0n and 1n must be maintained in the population P. Let D = {j | ∃x ∈ Q, |x|0 = j}, where Q denotes the archive, and we suppose |D| = i, i.e., i points in the Pareto front has been found in the archive. Note that i ≥ 2 as 0n and 1n have been found. Next, we consider two cases.

(1) The number of 1n or the number of 0n in the current population P is at least µ/4. Without loss of generality, we assume that the number of 0n is at least µ/4. Then, the probability of selecting 0n as a parent solution is at least (1/4)2 = 1/16, because it is sufficient to select 0n twice in binary tournament selection. According to the analysis in the paragraph above Eq. (1), the probability of selecting 1n as the other parent solution is at least 1/(2µ). After exchanging the first k (k ∈ [0..n] \ D) bits of 0n and 1n by one-point crossover (the probability is 0.9 · (1/n)), a solution with k 0-bits can be generated, which can keep unchanged after bit-wise mutation if none of the bits is flipped (the probability is (1 - 1/n)n ). Thus, the probability of generating a new point in the Pareto front is at least

where the term n+1-i is because there are |[0..n]\D| = n+ 1-i points in the Pareto front to be found, the first inequality holds by (1 - 1/n)n-1 ≥ 1/e, and the second inequality holds for n ≥ 3.

(2) The number of 1n and the number of 0n in the current population P are both less than µ/4. Then, in one binary tournament selection procedure, the probability of selecting two solutions with the number of 0-bits in [1..n - 1] is at least (µ - µ/4 - µ/4)2 /µ2 = 1/4, and we assume that the winning solution x has j (j ∈ [1..n- 1]) 0-bits. If the other selected parent solution is 0n , then for any k ∈ [j +1..n] \D, there must exist a crossover point k′ such that exchanging the first k′ bits of x and 0n can generate a solution with k 0bits. If the other selected parent solution is 1n , then for any k ∈ [0..j - 1] \ D, there must exist a crossover point k′ such that exchanging the first k′ bits of x and 1n can generate a solution with k 0-bits. The newly generated solution can keep unchanged by flipping no bits in bit-wise mutation. Note that the probability of selecting 1n (or 0n ) as a parent solution is at least 1/(2µ). Thus, similar to Eq. (2), the probability of generating a new point in the Pareto front is at least

By taking the smaller one between Eqs. (2) and (3), and using the fact that NSGA-II produces µ/2 pairs of offspring solutions in each generation, the probability of generating a new point in the Pareto front in each generation is at least

Then, we can derive that the expected number of generations of the second phase (i.e., for finding the whole Pareto front) is at most ∑ni=2 O(n/(n + 1 - i)) = O(n log n).

Combining the two phases, the total expected number of generations is O(n log n), implying that the expected number of fitness evaluations is O(µn log n), because each generation of NSGA-II requires to evaluate µ offspring solutions. Thus, the theorem holds.

We prove in Theorem 2 that the expected number of fitness evaluations of NSGA-II using an archive for solving LeadingOnesTrailingZeroes is O(µn2 + µ2n log n), where the population size µ ≥ 4. As the proof of Theorem 1, we divide the optimization procedure into two phases, that is to find the extreme solutions 1n and 0n , and to find the whole Pareto front, respectively. But due to the fact that only solutions with the form 1j 0n-j are Pareto optimal for LeadingOnesTrailingZeroes while any solution is Pareto optimal for OneMinMax, their analyses of increasing the maximal f1 value in the first phase as well as generating new Pareto optimal solutions in the second phase are different. The detailed proof of Theorem 2 is given in the supplementary due to space limitation.

Theorem 2. For NSGA-II solving LeadingOnesTrailingZeroes, if using an archive, and a population size µ such that µ ≥ 4, then the expected number of fitness evaluations for finding the Pareto front is O(µn2 + µ2n log n).

The expected number of fitness evaluations of the original NSGA-II (without using an archive) for solving OneMinMax and LeadingOnesTrailingZeroes has been shown to be O(µn log n) and O(µn2 ), respectively, where the population size µ ≥ 2(n + 1) [Bian and Qian, 2022]. Thus, our results in Theorems 1 and 2 show that if a constant population size is used for NSGA-II having an archive, the expected running time can be reduced by a factor of Θ(n). The main reason for the acceleration is that the archive can preserve all the non-dominated solutions generated so far, which enables NSGA-II to discard solutions that are not critical for finding the Pareto front, and thus to use a small population bringing more efficient exploration of the search space.

4 Analysis of SMS-EMOAwith an Archive

In this section, we consider SMS-EMOA in Algorithm 2 using an archive. We prove in Theorems 3 and 4 that the expected number of fitness evaluations of SMS-EMOA using an archive for solving OneMinMax and LeadingOnesTrailingZeroes is O(µn logn) and O(µn2 + µ2n logn), respectively, where the population size µ ≥ 2. Their proofs are similar to that of Theorems 1 and 2, respectively. That is, we divide the optimization procedure into two phases, where the first phase aims at finding 1n and 0n , and the second phase aims at finding the whole Pareto front. The main difference of the proofs is led by that 1) during the population update procedure, SMS-EMOA directly preserves two boundary objective vectors which contain the largest objective value for f1 or f2, and 2) during the reproduction procedure, it uses uniform parent selection and generates only one offspring solution in each generation. The detailed proof of Theorem 4 is given in the supplementary due to space limitation.

Theorem 3. For SMS-EMOA solving OneMinMax, if using an archive, and a population size µ such that µ ≥ 2, then the expected number of fitness evaluations for finding the Pareto front is O(µn logn).

Proof. For the first phase, the maximal f1 value will not decrease because SMS-EMOA directly keeps the two boundary points in the population update procedure. Now, we consider the increase of the maximal f1 value. Note that SMS-EMOA in Algorithm 2 selects a parent solution uniformly at random, instead of using binary tournament selection; thus, the probability of selecting any specific solution in the population is 1/µ. Eq. (1) changes to

Different from NSGA-II which produces µ/2 pairs of offspring solutions in each generation, SMS-EMOA only reproduces one solution in each generation. Thus, the expected number of generations for increasing the maximal f1 value to n, i.e., finding 0n , is at most ∑n-1 i=0 10eµn/(n - i) = O(µn logn). That is, the expected number of generations of the first phase is O(µn log n).

For the second phase, by considering the difference between uniform parent selection employed by SMS-EMOA and binary tournament selection employed by NSGA-II, Eq. (2) changes to

and Eq. (3) changes to

Thus, the expected number of generations of the second phase (i.e., for finding the whole Pareto front) is at most ∑ni=2 8eµn/(n + 1 - i) = O(µn log n).

Combining the two phases, the total expected number of generations is O(µn logn). Since SMS-EMOA only generates one solution in generation, the expected number of fitness evaluations is also O(µn log n).

Theorem 4. For SMS-EMOA solving LeadingOnesTrailingZeroes, if using an archive, and a population size µ such that µ ≥ 2, then the expected number of fitness evaluations for finding the Pareto front is O(µn2 + µ2n log n).

The expected number of fitness evaluations of the original SMS-EMOA (without crossover) solving OneMinMax and LeadingOnesTrailingZeroes has been shown to be O(µn log n) and O(µn2 ), respectively, where the population size µ ≥ n+1 [Zheng and Doerr, 2024]. Though their analysis does not consider crossover, the running time bounds still hold asymptotically here as the crossover operator is not performed with a constant probability 0.1 in Algorithm 2. Note that the size of the Pareto front is n+1, thus when µ < n+1, the whole Pareto front cannot be covered. Therefore, our results in Theorems 3 and 4 show that if a constant population size is used for SMS-EMOA having an archive, the expected running time can be accelerated by a factor of Θ(n). The main reason for the acceleration is similar to that of NSGAII. That is, introducing the archive enables SMS-EMOA to only preserve essential solutions for locating the Pareto front, and thus makes the exploration more efficient.

5 Experiments

In the previous sections, we have proved that when an archive is used in NSGA-II and SMS-EMOA, the expected number of fitness evaluations for solving OneMinMax and LeadingOnesTrailingZeroes can be reduced by a factor of Θ(n). However, as only upper bounds on the running time of the original NSGA-II and SMS-EMOA have been derived, we conduct experiments to examine their actual performance to complement the theoretical results.

Specifically, we set the problem size n from 10 to 50, with a step of 10. For NSGA-II and SMS-EMOA using an archive, the population size µ is set to 4 and 2, respectively, as suggested in Theorems 1-4. For the original NSGAII and SMS-EMOA without an archive, we test three values of µ, i.e., n + 1, 2(n + 1), and 4(n + 1), as suggested by [Bian and Qian, 2022; Zheng and Doerr, 2023a; Zheng and Doerr, 2024]. Note that n + 1 is the size of the Pareto front of OneMinMax and LeadingOnesTrailingZeroes. If using a population size µ < n + 1, the original algorithms without archive obviously cannot find the Pareto front. For each n, we run an algorithm 1000 times independently, and record the average number of fitness evaluations until the Pareto front is found. In case where the Pareto front cannot be found in acceptable running time, we set the maximum number of fitness evaluations to 5×104 for OneMinMax and 2×105 for LeadingOnesTrailingZeroes. We can observe from Figure 1 that using an archive brings a clear acceleration.

We can also observe that when using a population size of n+1, SMS-EMOA performs much better than NSGA-II. The main reason is that for NSGA-II, when two Pareto optimal solutions corresponding to one objective vector (e.g., two solutions corresponding to one boundary point in the Pareto front) have been found, they both can have fairly large crowding distance, and thus occupy two slots in the population. Then, the population size of n+ 1 is not sufficient to ensure the preservation of objective vectors in the Pareto front. However, for SMS-EMOA, these duplicate Pareto optimal solutions have a zero hypervolume contribution, and thus are less preferred, implying that they will not affect the preservation of other objective vectors in the Pareto front. Meanwhile, since SMSEMOA only removes one solution in each generation, the objective vector corresponding to these duplicate solutions will also be preserved. Thus, a population size of n+1 is sufficient for SMS-EMOA to preserve the whole Pareto front.

6 Conclusion

In this paper, we perform a first theoretical study for MOEAs with an archive, an increasingly popular practice in the design of MOEAs. Through rigorous running time analysis for NSGA-II and SMS-EMOA solving two commonly studied bi-objective problems, OneMinMax and LeadingOnesTrailingZeroes, we prove that using an archive can allow a constant population size, bringing an acceleration of factor Θ(n). This is also verified by the experiments. Our results provide theoretical confirmation for the benefit of using an archive to store non-dominated solutions generated during the search process of MOEAs, which has frequently been observed empirically [Fieldsend et al., 2003; Bezerra et al., 2019]. In the future, it would be interesting to derive the lower bounds of NSGA-II and SMS-EMOA without using an archive to make the comparison strict. Another interesting direction is studying real-world problems, e.g., multi-objective combinatorial optimization problems.

Acknowledgements

This work was supported by the National Science and Technology Major Project (2022ZD0116600) and National Science Foundation of China (62276124). Chao Qian is the corresponding author. The supplementary is available at arXiv.