A Dynamic Decomposition Strategy for the MOEA/D With Proven Performance Guarantees

Benjamin Doerr; Martin S. Krejca; Noé Weeks

cs.NEOct 26, 2026

A Dynamic Decomposition Strategy for the MOEA/D With Proven Performance Guarantees

Authors: Benjamin Doerr, Martin S. Krejca, Noé Weeks

Organizations: Laboratoire d’Informatique (LIX), CNRS, École Polytechnique, Institut Polytechnique de Paris, Palaiseau, France · École Normale Supérieure, Paris, France

Abstract

The MOEA/D is one of the most successful multi-objective evolutionary algorithms. It operates by decomposing the optimization problem into single-objective subproblems, which are then solved in a co-evolutionary manner. The performance of the MOEA/D depends critically on this decomposition. In this work, we propose a novel way to adjust this decomposition on the fly, for the case of discrete bi-objective optimization. Different from all previous works in this direction, we support our new algorithm with a proven performance guarantee. This is the first work that rigorously proves the runtime of a dynamic multi-objective evolutionary algorithm. For monotonic distortions of the simple LOTZ benchmark, it is known that classic decompositions leave large holes in the Pareto front, making it very hard for the MOEA/D to cover the entire Pareto front. In contrast, we prove that our self-adjusting MOEA/D solves all these LOTZ problems in an expected number of $O(n^4)$ function evaluations. This relatively low runtime as well as the details of our mathematical proof show that the dynamic decomposition strategy indeed evolves a decomposition adjusted to each of these problem instances.

Figures & tables

Panel of Figure 1 — Figure 1: A graphical sketch of the LeadingOnesTrailingZeros ( LOTZ ) [ LTZ04 ] benchmark ( Figure 1(a) ) and its monotonically distorted version [ LZZZ16 ] ( Figure 1(b) ). The details are given in Section 2 . The orange points on the outmost line denote the Pareto front of the respective benchmark. The other blue points denote other objective values that are not Pareto optima.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

$n$	metric	instance										avg
$250$	$C_{c}(s)$	$10.9602$	$11.5987$	$06.4359$	$15.2419$	$17.0742$	$12.1732$	$02.879\,12$	$16.0182$	$10.6713$	$16.8333$	$11.4503$
	$C_{s}(c)$	$59.958$	$64.3977$	$79.4427$	$55.5283$	$59.2649$	$65.2207$	$82.9415$	$66.0128$	$78.1889$	$65.2154$	$67.8839$
	$\|P_{c}\|$	$27.8$	$29.2$	$30$	$27.4$	$34.2$	$33.2$	$32$	$30.2$	$23.6$	$30.4$	$29.800\,000\,0$
	$\|P_{s}\|$	$27.2$	$24$	$27.8$	$25.2$	$26.4$	$32.4$	$26.6$	$30.6$	$23.8$	$28.2$	$27.220\,000\,0$
$500$	$C_{c}(s)$	$06.433\,33$	$06.105\,26$	$26.0417$	$0$	$05.127\,27$	$06.363\,64$	$18.303$	$0$	$16.6986$	$06.0$	$09.0$
	$C_{s}(c)$	$75.8579$	$68.4985$	$61.2468$	$90.2857$	$86.7435$	$73.6613$	$68.0849$	$80.7163$	$69.7003$	$86.4569$	$76.0$

Appendix

Table 1: The set coverage score for comparing the archives of the classic MOEA/D (

c

) and of the sMOEA/D (

s

), as well as the archive size of either algorithm at the end of each run. We report the average numbers of all

5

runs for all

10

instances for all

3

values of

n

, rounding numbers. The last column is the average of the averages reported in the

10

instances to the left, and it is computed using the original numbers and rounding afterward. We see that

s

weakly dominates far more points of

c

than the other way around. For all

3

values of

n

, these results are statistically significant, according to a one-sided Mann–Whitney

U

test on the

10

averages per instance before rounding. The final archive sizes are roughly the same between both algorithms. Please also refer to Section B.1.2 . We report on the standard deviation of these values in Table 2 .

$n$	metric	instance										avg
$250$	$C_{c}(s)$	$13.6154$	$19.2868$	$09.421\,25$	$13.603$	$19.9318$	$13.2427$	$02.852\,41$	$17.6286$	$11.6288$	$10.7548$	$13.196\,56$
	$C_{s}(c)$	$19.19$	$23.6707$	$17.2569$	$17.6453$	$21.505$	$17.6737$	$10.9134$	$28.5729$	$16.7913$	$20.5977$	$19.381\,69$
	$\|P_{c}\|$	$3.059\,41$	$2.315\,17$	$5.215\,36$	$5.004$	$5.741\,08$	$7.194\,44$	$2.097\,62$	$5.3066$	$2.870\,54$	$5.004$	$4.380\,822\,0$
	$\|P_{s}\|$	$6.939\,74$	$3.033\,15$	$2.856\,57$	$7.359\,35$	$5.535\,34$	$2.059\,13$	$4.454\,21$	$3.006\,66$	$3.815\,76$	$7.166\,59$	$4.622\,650\,0$
$500$	$C_{c}(s)$	$10.9034$	$08.055\,21$	$32.0996$	$0$	$06.300\,89$	$12.7273$	$28.4019$	$0$	$31.1741$	$12.0$	$14.166\,24$
	$C_{s}(c)$	$16.2787$	$19.4605$	$27.5696$	$08.005\,67$	$12.2303$	$18.5534$	$21.3893$	$16.26$	$34.5437$	$17.4816$	$19.177\,28$

Appendix

Table 2: The standard deviation of the values from Table 1 . Each value below is the average of the

5

standard deviations of the

5

runs per instance. We only report rounded values. We see that the average difference of the archive sizes seen in Table 1 is within one (average) standard deviation, which means that they are likely due to random variances.

Panel of Figure 2 — Figure 2: The number of subproblems per iteration of the sMOEA/D on two random instances of the stated size. The number is initially small, resulting only in a few FEs, and it grows in later iterations, allowing the algorithm to explore the Pareto front more thoroughly. Please also refer to Section B.1.2 .

Multi-Objective Evolutionary Optimization

Multi-Objective Evolutionary Optimization uses population-based search to find diverse Pareto-optimal solutions when objectives conflict.

See all 85 papers

Understanding the Co-evolutionary Solution Exchange of the MOEA/D: Already the Smallest Communication Radius Gives the Best-Possible Speed-Up
Oct 26, 2026Benjamin Doerr, Moaad Elmoutassim, Martin S. Krejca +1Multi-Objective Evolutionary Optimization Evolutionary Optimization
Laboratoire d’Informatique (LIX), CNRS, École Polytechnique, Institut Polytechnique de Paris, Palaiseau, France · École Polytechnique, Institut Polytechnique de Paris, Palaiseau, France
First Mathematical Runtime Analyses of Multi-Objective Evolutionary Algorithms for Multi-Valued Decision Variables
May 14, 2026Mingfeng Li, Zheng Cheng, Weijie Zheng +1Evolutionary Optimization Multi-Objective Evolutionary Optimization
School of Computer Science and Technology, National Key Laboratory of Smart Farm Technologies and Systems, International Research Institute for Artiﬁcial Intelligence, Harbin Institute of Technology, Shenzhen · 2Pengcheng Laboratory, Shenzhen, China · 3Laboratoire d’Informatique (LIX), CNRS, ´Ecole Polytechnique, Institut Polytechnique de Paris, Palaiseau, France
Training-Free Diffusion-Driven Modeling of Pareto Set Evolution for Dynamic Multiobjective Optimization
Mar 23, 2026Jian Guan, Huolong Wu, Zhenzhong Wang +2Multi-Objective Optimization Multi-Objective Evolutionary Optimization
Institute of Artificial Intelligence, Xiamen University, Xiamen, 361005, China · Department of Artificial Intelligence, School of Informatics, Xiamen University; the Key Laboratory of Multimedia Trusted Perception and Efficient Computing, Ministry of Education; and the Key Laboratory of Digital Protection and Intelligent Processing of Intangible Cultural Heritage of Fujian and Taiwan, Ministry of Culture and Tourism, Xiamen, 361005, China · Department of Artificial Intelligence, Sichuan University, Chengdu, 610065, China

Oct 26, 2026J/K move · Enter open · S save

Understanding the Co-evolutionary Solution Exchange of the MOEA/D: Already the Smallest Communication Radius Gives the Best-Possible Speed-Up

Benjamin Doerr, Moaad Elmoutassim, Martin S. Krejca, Guy Mushiata Kibulu

Laboratoire d’Informatique (LIX), CNRS, École Polytechnique, Institut Polytechnique de Paris, Palaiseau, France · École Polytechnique, Institut Polytechnique de Paris, Palaiseau, France

Multi-Objective Evolutionary Optimization Evolutionary Optimization Runtime Analysis of Evolutionary Algorithms

Open paper AskPDF arXiv

Besides domination-based algorithms such as the NSGA-II, the decomposition-based MOEA/D is one of the most popular and successful optimization heuristic for multi-objective problems. It decomposes the problem into several, single-objective subproblems. By solving these in a co-evolutionary manner and archiving non-dominated solutions, it approximates or computes the Pareto front. Interestingly, so far no advantages from the co-evolutionary communication of subproblem solutions were proven. In this first mathematical runtime analysis addressing this research question, we investigate how the mutation-based MOEA/D solves the classic OneMinMax benchmark when solutions are exchanged among subproblems in different distances

r

. We show, for the first time, that the MOEA/D profits from an exchange of solutions, and that already very small communication radii

r

are sufficient to maximally profit from this feature of the algorithm. More precisely, for all values

r \ge 1

we prove a tight runtime guarantee of

Θ(n^2)

, where

n

is the problem size. This is asymptotically faster than the known bound of

O(n^2 \log n)

guarantee for

r=0

, which we complement with a matching bound of

Ω(n^2 \log n)

Abstract

Multi-Objective Evolutionary Optimization

Explore similar work

Understanding the Co-evolutionary Solution Exchange of the MOEA/D: Already the Smallest Communication Radius Gives the Best-Possible Speed-Up

First Mathematical Runtime Analyses of Multi-Objective Evolutionary Algorithms for Multi-Valued Decision Variables

Training-Free Diffusion-Driven Modeling of Pareto Set Evolution for Dynamic Multiobjective Optimization