One for Exploration and Another for Exploitation: A Dual-Population MOEA Framework with Provable Benefits

1 Introduction

Multi-objective Optimization Problems (MOPs) refer to optimization scenarios involving multiple, often conflicting objectives that need to be optimized simultaneously. Unlike single-objective optimization, an MOP usually has no single optimal solution, but instead a set of Pareto optimal solutions representing different trade-offs among the objectives [Deb, 2001; Zhou et al., 2019]. The corresponding objective vectors of these Pareto optimal solutions constitute the Pareto front. The goal of a multi-objective optimizer is to find the Pareto front or approximate it as accurately as possible. Evolutionary Algorithms (EAs), inspired by natural evolution and operating with populations, are particularly well-suited to MOPs and have been widely applied in real-world domains [Deb, 2001; Zhou et al., 2019]. Over the years, numerous Multi-Objective EAs (MOEAs) have been developed, including the Non-dominated Sorting Genetic Algorithm II (NSGA-II) [Deb et al., 2002], MOEA based on Decomposition (MOEA/D) [Zhang and Li, 2007], and S-Metric Selection Evolutionary Multi-objective Optimization Algorithm (SMS-EMOA) [Beume et al., 2007].

As in many stochastic optimization processes, balancing exploration and exploitation is fundamental to the performance of MOEAs. To support effective exploration, the population in MOEAs needs to maintain a diverse set of solutions capable of guiding the search towards different regions of the search space. At the same time, effective exploitation requires the population to retain high-quality solutions found so far, enabling intensive local search for further improvement.

However, these two roles are not always fully aligned. Solutions with high exploratory potential may be of low quality - for example, they lie near the middle of multiple attraction basins. In contrast, high-quality solutions may lack the potential to guide the search toward different regions of the search space - for example, they are located in a local optimal region. As such, using a single population in MOEAs may not always help. This is echoed by recent studies showing that introducing randomness, non-elitism or aging mechanisms into population update of MOEAs (thereby allowing inferior solutions to survive longer) can benefit the search, both theoretically [Bian et al., 2025; Zheng and Doerr, 2024b; Opris, 2025a; Li et al., 2025] and empirically [Tanabe and Ishibuchi, 2019; Sanchez et al., 2023; Liang et al., 2023]. And, adding an external archive to store the non-dominated solutions (despite not being used for exploitation [Li et al., 2024b]) can further enhance exploration by freeing the evolutionary population from the role of preserving solution quality [Ishibuchi et al., 2020; Ren et al., 2025].

In this work, we propose a simple yet effective algorithmic framework that alleviates the conflict between exploration and exploitation by decoupling these two aspects, i.e., a dualpopulation MOEA with Exploration and Exploitation Decoupled (MOEA/EED). Specifically, we use a probability p to decide to exploit (select a parent solution from the exploitation population Pexploit) or explore (select a parent solution from the exploration population Pexplore). The exploitation population Pexploit stores only non-dominated solutions with unique objective vectors; the exploration population Pexplore uses an aging mechanism, meaning that solutions are preserved for a fixed duration regardless of their quality. Both populations are updated after a new solution is generated.

We analyze the expected running time of the proposed MOEA/EED on two commonly studied bi-objective problems OneJumpZeroJump [Doerr and Zheng, 2021] and biobjective RealRoyalRoad [Dang et al., 2024], and obtain a significantly better upper bound compared to previously analyzed single-population algorithms. The results are shown in Table 1. The original SMS-EMOA [Beume et al., 2007] and NSGA-II [Deb et al., 2002] serve as the baselines for comparison, as they do not incorporate any non-elitist mechanisms. Stochastic population update (stochastic method) is an approach that introduces randomness into the population update process of MOEAs (randomly selects a fraction of the current population and the offspring solution(s) to directly survive into the next generation), which has been theoretically shown to enhance the search capability [Bian et al., 2025; Zheng and Doerr, 2024b; Ren et al., 2025]. Very recently, Li et al. [2025] analytically showed that SMS-EMOA equipped with an aging method (where solutions increment their age by 1 in every generation, and are excluded from population updates until their age reaches a threshold τ) achieves greater acceleration. The main comparison results are as follows.

• On the OneJumpZeroJump problem, the expected running time of SMS-EMOA and NSGA-II is both O(µnk ) [Bian et al., 2025; Doerr and Qu, 2023]. SMSEMOA combined with the stochastic method achieves a speedup of Θ(max{1, (k/(e ln(2eµ)))k-1 }) [Ren et al., 2025]; when using an aging method (with τ =
• n - 2k + 4 and µ = 2τ), it further reduces the upper bound by a factor of Θ(((1-e-1/2 ) ln(2eµ)/e)k-1 ) [Li et al., 2025]. On the other hand, NSGA-II that employs the (µ+µ) update mode and the stochastic method achieves an upper bound comparable to that of the agingbased SMS-EMOA. By decoupling exploration and exploitation with two distinct populations, our proposed MOEA/EED achieves the best expected running time upper bound, faster than the stochastic NSGA-II by a factor of Θ(k · (log3e(4e))k-1 ).
• On the bi-objective RealRoyalRoad problem, the expected running time of SMS-EMOA and NSGA-II is both Ω(nn/5-1 ) [Bian et al., 2025]. SMS-EMOA combined with the stochastic method achieves a speedup of Ω(2n/10 /(µ2n3/2 )), while NSGA-II with the stochastic method further reduces the upper bound by a factor of Θ(µ(n/(20√2e2 ))n/5 ). Our proposed MOEA/EED can further reduce the upper bound of the stochastic NSGAII by a factor of Θ(µ√n(4e/ ln(3e))n/5 ).

The above proved (even exponential) speedup of MOEA/EED over the stochastic and aging-based methods stems from the fact that the latter operate in the search process of a single population. Consequently, the only way to increase the intensity of exploration in inferior, yet potentially promising regions is by increasing the proportion of non-elite solutions in the population. Although some non-elite solutions are helpful, most of them offer little exploratory value, and an excessive number of such solutions waste search resources. In contrast, MOEA/EED decouples exploration and exploitation by maintaining two distinct populations and uses a selection probability to directly determine the intensity of exploration in inferior regions. This allows it to allocate a reasonably sized non-elite population for exploration, thereby reducing the chance of selecting useless individuals and leading to a more efficient search. The advantage of MOEA/EED is also validated on well-known practical problems at the end of this paper.

The main contribution of this work is proposing the framework of MOEAs with exploration and exploitation decoupled, and showing that even a simple instantiation can work well both theoretically and empirically. Note that the use of dual-population or dual-archive mechanism (where the archive is used to generate solutions) is not uncommon in empirical studies of MOEAs (see [Li et al., 2024b] for a survey). However, existing methods do not explicitly separate exploration and exploitation by assigning each role to a dedicated population. Instead, they employ multiple populations for other purposes: for example, considering a different selection criterion each (e.g., Pareto dominance, indicator or decomposition criteria [Li et al., 2018]), or introducing an additional population to address problem-specific characteristics such as constraints [Xie et al., 2025] and multi-modality [Liu et al., 2018], alongside the main population.

Finally, we provide a brief overview of running time analyses of MOEAs, which have received growing interests over the last two decades. Early theoretical works [Laumanns et al., 2004; Neumann, 2007; Giel and Lehre, 2010; Doerr et al., 2013; Qian et al., 2013; Qian et al., 2016; Bian et al., 2018] primarily focused on simple MOEAs such as (G)SEMO, showing results on their expected running time. Recently, attention has shifted toward practical, widely used MOEAs. Huang et al. [2021] analyzed MOEA/D and evaluated the impact of different decomposition approaches. Zheng et al. [2022] conducted the first runtime analysis of NSGA-II. Bian et al. [2025] studied SMS-EMOA and showed that stochastic population update can yield significant acceleration. Wietheger and Doerr [2023] showed that NSGA-III outperforms NSGA-II on a tri-objective problem. Ren et al. [2024a] and Opris [2025b] provided a first runtime analysis of SPEA2 and PAES-25, respectively. Additional theoretical studies on established MOEAs include [Zheng and Doerr, 2024a; Bian et al., 2024; Dang et al., 2024; Doerr et al., 2025; Benjamin et al., 2025; Opris, 2025b].

2 Preliminaries

In this section, we first introduce the basic concepts of multiobjective optimization, followed by a description of the biobjective problems OneJumpZeroJump and bi-objective RealRoyalRoad, studied in this paper.

Multi-objective optimization aims to simultaneously optimize two or more typically conflicting objective functions. Without a canonical complete order in the solution space X, solutions are compared using the domination relationship in Definition 1. 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. 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.

Next, we introduce the benchmark problems OneJumpZeroJump and bi-objective RealRoyalRoad studied in this paper. The OneJumpZeroJump problem as presented in Definition 2 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, 2023; 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 one, with the roles of 1-bits and 0-bits reversed.

Definition 2 (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.

The left subfigure of Figure 1 illustrates the objective vectors of OneJumpZeroJump in the (f1, f2) objective space, where the green points represent Pareto-optimal solutions and the black points denote dominated solutions. A solution is Pareto optimal if and only if it contains (a - k) 1-bits, for a ∈ [2k..n] ∪ {k, n + k}; the corresponding objective vector is (a, n + 2k - a). Consequently, the Pareto front is given by{(a, n + 2k - a) | a ∈ [2k..n] ∪ {k, n + k}}, whose size is n - 2k + 3. We denote the inner part of the Pareto front by F ∗ I = {(a, n + 2k - a) | a ∈ [2k..n]}. As observed, the Pareto front consists of F ∗ I and two isolated extreme points corresponding to 0n and 1n . The OneJumpZeroJump problem serves as a representative benchmark where some adjacent Pareto optimal solutions in the objective space locate far away in the decision space.

The bi-objective RealRoyalRoad problem, formally defined in Definition 3, is originally proposed in [Dang et al., 2024] to evaluate the ability of MOEAs to escape from local optima. It consists of two objectives that combine the number of 1-bits with structural information captured by the number of trailing zeros (TZ) and leading zeros (LZ), where TZ(x) = ∑ni=1 ∏nj=i (1 - xj) and LZ(x) = ∑ni=1 ∏ij=1 (1 - xj). The solution space is partitioned into two special regions G and H. The set G contains all solutions with at most 3n/5 1-bits, while the set H consists of all solutions with exactly 4n/5 1-bits and satisfying LZ(x) + TZ(x) = n/5. For solutions in G or H, f1(x) is defined as the sum of n · |x|1 and the number of trailing zeros TZ(x), whereas all remaining solutions receive objective value 0. f2(x) is defined analogously, replacing TZ with LZ.

Definition 3 (Bi-objective RealRoyalRoad [Dang et al., 2024]). The bi-objective RealRoyalRoad problem is to find n bits binary strings which maximize

where n/5 ∈ Z+, G = {x | |x|1 ≤ 3n/5} and H = {x | |x|1 = 4n/5 ∧ LZ(x) + TZ(x) = n/5}. Here, |x|1, LZ(x), and TZ(x) denote the number of 1-bits, leading zeros, and trailing zeros in x ∈ {0, 1}n , respectively.

The right subfigure of Figure 1 gives an example illustration of bi-objective RealRoyalRoad in the (f1, f2) objective space, where green points denote Pareto-optimal solutions and black points denote dominated ones. The set of Pareto optimal solutions is exactly H, and the corresponding Pareto front is {(4n2 /5+a, 4n2 /5+n/5-a) | a ∈ [0..n/5]}, which has size n/5 + 1. We further denote by G′ = {x | |x|1 = 3n/5 ∧ LZ(x) + TZ(x) = 2n/5} the set of nondominated solutions located in the local region G. Thus, the bi-objective RealRoyalRoad problem simulates scenarios in which the search landscape contains structural barriers, posing significant challenges for MOEAs to transition from local to global optimality (i.e., fromG′ to H).

3 ProposedMOEAwith Exploration and Exploitation Decoupled

The proposed algorithm MOEA/EED as shown in Algorithm 1 considers two populations for exploitation and exploration (denoted as Pexploit and Pexplore), respectively. In each generation, a parent is selected for variation either from Pexploit to exploit with probability p, or from Pexplore to explore with probability 1 - p. The exploitation population retains only high-quality solutions (i.e., nondominated solutions found) for individual refinement, while the exploration population disregards solution quality and uses the age of solutions during the evolutionary process to promote the search in "under-developed" regions. Note that aging mechanisms are widely used in evolutionary algorithms and artificial immune systems [Oliveto and Sudholt, 2014;

Algorithm 1 MOEA/EED

Input: objectives f1, . . . , fm, maximum lifespan τ for the exploration population Pexplore, number of initial solutions µ and selection prob. p for the exploitation population Pexploit Output: solutions fromPexploit

• 1: Pexplore ← ∅;
• 2: Pexploit ← initialize µ solutions by uniform and random sampling from {0, 1}n , and retain the non-dominated solutions with distinct objective vectors;
• 3: while criterion is not met do

4: sample u from uniform distribution over [0, 1]; 5: if u < p or Pexplore = ∅ then 6: select a solution x from Pexploit randomly 7: else 8: select a solution x from Pexplore randomly 9: end if 10: apply bit-wise mutation on x to generate x′ ; 11: add (x′ , 0) to Pexplore; 12: if ̸ ∃z ∈ Pexploit such that z ⪰ x′ then 13: Pexploit←(Pexploit \{z ∈ Pexploit|x′ ≻ z})∪{x′ } 14: end if 15: for each (x, age) ∈ Pexplore do 16: age ← age + 1 17: end for 18: remove all (x, age) from Pexplore with age > τ 19: end while 20: return Pexploit

Stefano et al., 2016; Corus et al., 2020], and recently analyzed for their advantages in multi-objective optimization [Li et al., 2025]. In such mechanisms, each solution is assigned an age that increases by one in each generation, and solutions whose age exceeds a maximum lifespan τ are typically removed. The algorithmic procedure is as follows.

At the beginning, MOEA/EED initializes an empty population Pexplore and a population Pexploit by uniformly sampling µ solutions from {0, 1}n , and retaining the non-dominated solutions with distinct objective vectors (lines 1-2). In each generation, MOEA/EED uniformly at random selects a parent solution x from Pexploit with probability p (or from Pexploit if Pexplore = ∅), and otherwise selects a parent solution from Pexplore (lines 4-9). Then, bit-wise mutation flips each bit of x with probability 1/n to produce an offspring x′ (line 10), which is added to Pexplore directly (line 11). Afterwards, x′ will be tested if it can enter Pexploit. If there is no solution in Pexploit that weakly dominates x′ , it will be placed in Pexploit, and meanwhile those solutions dominated by the new solution will be deleted from Pexploit as the classic GSEMO/SEMO [Giel, 2003] does (lines 12-14). Afterwards, the ages of all individuals in Pexplore are increased by 1 (lines 15-17). Finally, all solutions with the age more than τ are removed (line 18).

4 Theoretical Analysis of MOEA/EED

In this section, we theoretically analyze the expected running time of MOEA/EED on the OneJumpZeroJump and biobjective RealRoyalRoad problems. We show that the expected running time is O((nk+1 /p) · min{1, (e(lnC)/k)k }) and O((5e lnC)n/5 /p), respectively, where C = e(2 - p)/(1 - p). These bounds are much better than those of the original NSGA-II [Doerr and Qu, 2023] and SMSEMOA [Bian et al., 2025] and their non-elite methods [Li et al., 2025; Ren et al., 2025]. Note that the running time of EAs is often measured by the number of fitness evaluations.

4.1 Runtime Complexity on OneJumpZeroJump

We first show that the expected running time for MOEA/EED solving OneJumpZeroJump is O((nk+1 /p) · min{C, (e(ln C)/k)k }), where C = e(2-p)/(1-p), which is better than that, i.e., O(µnk ), of the original SMS-EMOA and NSGA-II [Bian et al., 2025; Doerr and Qu, 2023], where µ = Θ(n). Intuitively, the exploration population Pexplore considers only the age of solutions but not their quality. Thus, the evolutionary search has a chance to go along inferior regions which are close to Pareto-optimal regions, making the search easier. Actually, non-elitist strategies have been shown to be effective in multi-objective optimization in prior works: Li et al. [2025] analyzed SMS-EMOA with aging mechanisms, while Bian et al. [2025] studied stochastic population updates on SMS-EMOA and NSGA-II. Compared with these strategies, our MOEA/EED framework also achieves a better upper bound due to its dual-population mechanism.

Theorem 1. For MOEA/EED solving OneJumpZeroJump with n - 2k = Ω(n), if using the maximum lifespan τ = O(n(lnC)/k), and the number of initial solutions µ = Ω(logn), then the expected running time for finding the whole Pareto front is O((nk+1 /p) · min{1, (e(lnC)/k)k }), where C = e(2 - p)/(1 - p).

Proof Sketch of Theorem 1. The optimization is split into two phases: finding the inner Pareto front F ∗ I , and then locating the extreme solutions 1n and 0n .

For the first phase, we consider the case that there is at least one initial solution x such that |x|1 ∈ [k..n - k]; otherwise, the probability of all initial solutions having at most (k - 1) or at least (n - k + 1) 1-bits is (exp(-Ω(n)))µ by Chernoff bound. Starting from x, in each generation the algorithm selects a parent (whose neighboring solution is Pareto optimal but not yet in Pexploit) from Pexploit, flips one of its 1-bits (or 0-bits), and thereby generates a new Pareto-optimal solution. By repeating this process until F ∗ I is covered, the expected running time of the first phase is O(n2 (lnn)/p).

Next, we consider the second phase. By using the agingbased population Pexplore, any newly generated solution (including dominated ones) can survive for τ generations. This allows the algorithm to gradually reach 1n through the dominated solutions x ∈ {z | |z|1 ∈ [n - k + 1..n - 1]}. A symmetric process applies for reaching 0n . Similar to the proof technic in [Doerr et al., 2023] and [Ren et al., 2025], 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 added to Pexplore. 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 jumps, which start from a solution x with n - k 1-bits, and continue to generate the next stepping-stone solution until finding 1n . We analyze the probability that the first jump succeeds within n generations and that each of the remaining jumps succeed within τ generations. If any intermediate jump fails, the process restarts from a 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 jumps can happen with probability at least p(M + 1)k /(e(1 + p)nkCM ), where C = e(2 - p)/(1 - p). Thus, 1n can be found after O(nkCM /(p(M + 1)k )) trials in expectation. As each trial requires up to n +Mτ generations, 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 running time of the second phase is at most O((nk+1 /p) ·min{1, (e(ln C)/k)k }), where C = e(2 - p)/(1 - p).

Combining the two phases, the total expected running time is O((nk+1 /p) · min{1, (e(lnC)/k)k }), where O(n2 (lnn)/p) required by the first phase is dominated.

On OneJumpZeroJump, the expected running time of SMS-EMOA and NSGA-II is both O(µnk ) [Bian et al., 2025; Doerr and Qu, 2023]. SMS-EMOA combined with the stochastic method achieves a speedup of Θ(max{1, (k/(e(ln2eµ)))k-1 }) [Ren et al., 2025]; when using an aging method (with τ = n - 2k + 4 and µ = 2τ ), it further reduces the upper bound by a factor of Θ(((1 - exp(-1/2)) ln(2eµ)/e)k-1 ) [Li et al., 2025]. The advantage stems from that under the stochastic method, a solution that is poor in objective values but beneficial for exploration can survive for about 2 generations on average, whereas the aging method guarantees its preservation for τ generations, further increasing exploration chances in promising regions. On the other hand, the NSGA-II that employs (µ+µ) update mode and the stochastic method has a high probability of exploring promising regions in each generation. As a result, it achieves an upper bound comparable to that of the aging-based SMSEMOA. Our proposed MOEA/EED further achieves a better upper bound than NSGA-II using the stochastic method by a factor of Θ(k · (log3e(4e))k-1 ) when p is commonly set to 1/2. The speedup stems from the fact that both the stochastic method and the aging-based approach are applied to a single population during the search. Consequently, the probability of selecting a solution with exploratory value in inferior regions is limited by the proportion of non-elite individuals in the population, which is at most O(1/n) per generation. In contrast, MOEA/EED structurally decouples exploration and exploitation. It uses a selection probability p to control the intensity of exploration in inferior regions, allowing it to allocate a reasonably sized non-elite population for exploration. This structural separation inherently favors newly generated ("young") individuals by preserving them in the non-elite population for exploration. Consequently, it implies a probability of (1-p)/τ to choose a solution with exploratory value in inferior regions per generation, leading to a speedup. It is also worth noting that the classic GSEMO equipped with a heavy-tailed mutation operator obtains a competitive runtime of O(nk+1k-Θ(k) ) on OneJumpZeroJump [Doerr and Zheng, 2021]. Integrating similar operators with the dual-population mechanism may yield even greater acceleration, which we leave as an interesting future work.

4.2 Runtime Complexity on Bi-objective RealRoyalRoad

We next theoretically show that the expected running time for MOEA/EED solving the bi-objective RealRoyalRoad problem is O((5e ln C)n/5 /p), where C = e(2-p)/(1-p), which is significantly better than that, i.e., Ω(nn/5-1 ), of the original SMS-EMOA and NSGA-II [Bian et al., 2025]. Thanks to the dual-population that decouples exploration and exploitation, MOEA/EED even achieves a significantly greater speedup compared to both SMS-EMOA and NSGA-II with the stochastic method.

Theorem 2. For MOEA/EED solving the bi-objective RealRoyalRoad problem, if using the maximum lifespan τ = O(lnC), and the number of initial solutions µ = Ω(logn), then the expected running time for finding the whole Pareto front is O((5e ln C)n/5 /p), where C = e(2 - p)/(1 - p).

Proof Sketch of Theorem 2. We divide the optimization process into five phases, where the first phase aims at finding a solution with 3n/5 1-bits, the second phase aims at finding a solution in G′ = {x | |x|1 = 3n/5 ∧ LZ(x) + TZ(x) = 2n/5}, the third phase aims at finding the whole G′ , the fourth phase aims at finding a solution in H (i.e., a Pareto optimal solution), and the fifth phase aims at finding all solutions in H (i.e., all Pareto optimal solutions).

For the first phase, we consider the case that there is at least one initial solution x such that |x|1 ≤ 3n/5; otherwise, the probability of all initial solutions having more than 3n/5 1-bits is (exp(-Ω(n)))µ by Chernoff bound. Note that for any two solutions x, y ∈ G with |x|1 < |y|1 ≤ 3n/5, the solution x is dominated by y. Thus, the number of 1-bits of solutions in Pexploit is non-decreasing (and increases until reaching 3n/5). In each generation, a new non-dominated solution with more 1-bits can be generated by selecting any parent from Pexploit and flipping one of its 0-bits without disturbing the others. By repeating this process until a solution with 3n/5 1-bits is found, the expected running time of the first phase is O(n(log n)/p).

Next, we consider the second phase. By selecting a solution x in Pexploit where all the solutions have 3n/5 1-bits and flipping the last 1-bit as well as one 0-bit before the last 1-bit, we keep LZ(x∗ ) and |x∗ |1 of the offspring x∗ unchanged, and increase TZ(x∗ ) by one. Then by repeating the process at most 2n/5 times, we can have a solution in G′ . Thus, the expected running time of this phase is at most O(n4 /p).

Now we consider the third phase. Suppose G′ is not fully covered; then there exists a solution y ∈ G′ \Pexploit that can be generated from some x ∈ G′ ∩ Pexploit by either flipping the first 1-bit of x together with the first 0-bit in its trailing 0-bit block, or by flipping the last 1-bit of x together with the last 0-bit in its leading 0-bit block. Intuitively, this operation shifts the position of the 1-bit block without changing its length, hence producing a non-dominated offspring that belongs to G′ . By repeating this process at most 2n/5 times, the entire G′ can be found in expected running time of O(n4 /p).

Next, we consider the fourth phase. By using the agingbased population Pexplore, any newly generated solution (including dominated ones) can survive for τ generations. This allows the algorithm to gradually reach H through the dominated solutions x ∈ {z | |z|1 ∈ [3n/5+1..4n/5-1]}. Similar to the analysis in Theorem 1, we assume a "jump" to be an event where a dominated solution is selected, and a new dominated solution closer to H is generated and added to Pexplore. Let G′′ := {0i 13n/5 0 2n/5-i | n/10 ≤ i ≤ 3n/10} denote a subset of G′ . For any x ∈ G′′ , flipping the consecutive j 0-bits before the block of 1-bits and the consecutive n/5 - j 0-bits after the block of 1-bits generates a solution in H, where the number of valid choices for j is at least n/10. That is, there are at least n/10 different ways to generate a solution in H from one solution in G′′ . To increase the success probability of reaching H, we consider M + 1 consecutive jumps, which start from a solution in G′′ , and continue to generate the next stepping-stone solution until finding a solution in H. If any intermediate jump fails, the process restarts from a solution in G′′ . By enumerating all possible jump sizes (the sum of which is required to be n/5), we prove that the M + 1 jumps can happen with probability at least p(M + 1)n/5 /(2enn/5CM ), where C = e(2-p)/(1-p). Since there are at least n/10 different ways to reach H, and each trial needs at most 1+Mτ generations, the expected number of generations for reaching H is at most (1+Mτ ) · (20enn/5-1CM /p(M +1)n/5 ). Finally, we minimize this upper bound by taking M = ⌈n/(5 ln C)-1⌉. This leads to that the expected running time of the fourth phase is at most O((5e ln C)n/5 /p), where C = e(2 - p)/(1 - p).

Finally, we consider the last phase. The proof is almost the same as that of the third phase, except that we only need to find at most n/5 remaining solutions in H. Thus, we can directly derive that the total expected number of generations of this phase is at most O(n4 /p). Combining the five phases, the total expected running time is O((5e lnC)n/5 /p).

On the bi-objective RealRoyalRoad problem, the expected running time of SMS-EMOA and NSGA-II is both Ω(nn/5-1 ) [Bian et al., 2025]. SMS-EMOA combined with the stochastic method achieves a speedup of Ω(2n/10 /(µ2n3/2 )) [Bian et al., 2025], while NSGA-II with the stochastic method further achieves an additional speedup factor of Θ(µ(n/20√2e2 )n/5 ). Yet, single-population approaches remain structurally bottlenecked. Our proposed MOEA/EED shows yet another improvement, with a speedup factor of Θ(µ√n(4e/ ln(3e))n/5 ) when p is commonly set to 1/2. As on OneJumpZeroJump, the improvement stems from decoupling exploitation and exploration through a dualpopulation mechanism. This mechanism avoids restricting the number of non-elite solutions, resulting in a higher probability, i.e., (1-p)/τ , of selecting solutions with exploration value in inferior regions and thus achieving a speedup.

Table 2: The HV (mean and standard deviation) of the NSGA-II, NSGA-II-Stochastic, SMS-EMOA, SMS-EMOA-Aging and MOEA/EED on KP, NK, TSP and QAP. The number next to each problem denotes the number of variables. The best mean is highlighted in bold.

5 Experiments

In this section, we conduct experiments on four wellknown practical problems: the multi-objective 0/1 knapsack (KP) [Teghem, 1994], travelling salesman problem (TSP) [Ribeiro et al., 2002], quadratic assignment problem (QAP) [Knowles and Corne, 2003], and NK-landscapes (NK) [Aguirre and Tanaka, 2004], following the settings in [Li et al., 2024a; Liang and Li, 2026]. These problems cover binary representation (KP, NK), order-based (TSP) and position-based (QAP) permutation representations, constraint (KP), highly rugged landscape (NK when K = 10) and relatively smooth landscapes (KP, TSP). Each problem is considered at two sizes: 100 and 200 decision variables.

We consider five algorithms: NSGA-II, the stochastic variant of NSGA-II (NSGA-II-Stochastic), SMS-EMOA, the aging variant of SMS-EMOA (SMS-EMOA-Aging) and the proposed MOEA/EED, as described in the above sections. NSGA-II, SMS-EMOA and their variants follow similar settings: 1) a population size of 200; 2) the parent selection uses uniform random selection; 3) the variation operator uses only a problem-specific mutation. Following the practice in [Li et al., 2024a], for pseudo-Boolean problems (KP, NK), we use the bit-wise mutation [Eiben and Smith, 2015] with a rate of 1/n, where n is the number of variables. For permutation problems (TSP, QAP), we use the 2-opt and 2-swap mutations [Eiben and Smith, 2015], respectively, and the mutation rate is set to 1.0. For the proposed MOEA/EED, the same problem-specific mutation is used; the maximum lifespan τ is set to 10; the number µ of initial solutions is set to 1; the probability p of selecting the exploitation population is set to 0.75. The two non-elitist variants of NSGA-II and SMSEMOA adopt this ratio, as well. For the NSGA-II-Stochastic, 1/4 of the parent ∪offspring (100 out of 400 solutions) are randomly selected to enter the next generation. For the SMSEMOA-Aging, the maximum lifespan is set to 1/4 of the population size (i.e., 50), so 1/4 of the population are preserved at each generation regardless of their quality. For all algorithms, we consider two common computational budgets: 104 and 105 evaluations; the number of independent runs is 30.

We use the hypervolume (HV) [Zitzler and Thiele, 1999] to compare the performance of the algorithms. According to [Li et al., 2022], the reference point of HV is set to nadir-0.1× (ideal - nadir) for maximization problems (KP, NK), and to nadir + 0.1 × (nadir - ideal) for minimization problems (TSP, QAP), where the ideal/nadir point is computed from the non-dominated set of all algorithms at 104 evaluations.

Table 2 gives the HV results of the five algorithms on the four practical problems. The proposed MOEA/EED achieves the best HV across all problem instances and budgets, with statistically significant differences over the others in almost all cases. The difference is substantial (one to two orders of magnitude in HV) in some instances under the small budget. This indicates that MOEA/EED gains advantages quickly, particularly for larger problem instances (e.g., QAP-200). Indeed, for some large instances (KP-200 and TSP-200), the solutions obtained by the other four competitors after 104 evaluations fail to match the nadir point of the non-dominated set obtained by MOEA/EED, resulting in a HV value of zero.

6 Conclusion

In this paper, we propose a dual-population MOEA with Exploration and Exploitation Decoupled (MOEA/EED): the exploration population uses a simple aging mechanism, and the exploitation population stores only non-dominated solutions. Exploration and exploitation are regulated by a probability p instead of the proportion of non-elite populations. We theoretically show that MOEA/EED achieves significantly better expected running time bounds on the OneJumpZeroJump and bi-objective RealRoyalRoad problems than SMS-EMOA, NSGA-II, and their non-elitist variants. Finally, the theoretical benefits are empirically validated on a range of practical optimization problems.

Acknowledgments

This work was supported by the National Science and Technology Major Project (2022ZD0116600), the NSFC (62276124), the Fundamental Research Funds for the Central Universities (14380020), the Fundamental and Interdisciplinary Disciplines Breakthrough Plan of the Ministry of Education of China (JYB2025XDXM118), and the "111 Center" (B26023). Chao Qian is the corresponding author.