TY - GEN
T1 - Why Popular MOEAs Are Popular
T2 - 39th Conference on Neural Information Processing Systems, NeurIPS 2025
AU - Li, Mingfeng
AU - Zhang, Qiang
AU - Zheng, Weijie
AU - Doerr, Benjamin
N1 - Publisher Copyright:
© 2025 Neural information processing systems foundation. All rights reserved.
PY - 2025/1/1
Y1 - 2025/1/1
N2 - Recent breakthroughs in the analysis of multi-objective evolutionary algorithms (MOEAs) are mathematical runtime analyses of those algorithms which are intensively used in practice. So far, most of these results show the same performance as previously known for simpler algorithms like the GSEMO. The few results indicating advantages of the popular MOEAs share the same shortages: They only consider the problem of computing the full Pareto front, sometimes of algorithms enriched with newly invented mechanisms, and this on newly designed benchmarks. In this work, we overcome these shortcomings by analyzing how existing popular MOEAs approximate the Pareto front of the established LARGEFRONT benchmark. We prove that several popular MOEAs, including NSGA-II (with current crowding distance), NSGA-III, SMS-EMOA, and SPEA2, only need an expected time of O(n2 log n) fitness evaluations to compute an additive ω-approximation of the Pareto front of the LARGEFRONT benchmark. This contrasts with the already proven exponential runtime (with high probability) of the GSEMO on the same task. Our result is the first mathematical runtime analysis showing and explaining the superiority of popular MOEAs over simple ones like the GSEMO for the central task of computing good approximations to the Pareto front.
AB - Recent breakthroughs in the analysis of multi-objective evolutionary algorithms (MOEAs) are mathematical runtime analyses of those algorithms which are intensively used in practice. So far, most of these results show the same performance as previously known for simpler algorithms like the GSEMO. The few results indicating advantages of the popular MOEAs share the same shortages: They only consider the problem of computing the full Pareto front, sometimes of algorithms enriched with newly invented mechanisms, and this on newly designed benchmarks. In this work, we overcome these shortcomings by analyzing how existing popular MOEAs approximate the Pareto front of the established LARGEFRONT benchmark. We prove that several popular MOEAs, including NSGA-II (with current crowding distance), NSGA-III, SMS-EMOA, and SPEA2, only need an expected time of O(n2 log n) fitness evaluations to compute an additive ω-approximation of the Pareto front of the LARGEFRONT benchmark. This contrasts with the already proven exponential runtime (with high probability) of the GSEMO on the same task. Our result is the first mathematical runtime analysis showing and explaining the superiority of popular MOEAs over simple ones like the GSEMO for the central task of computing good approximations to the Pareto front.
UR - https://www.scopus.com/pages/publications/105048584582
M3 - Conference contribution
AN - SCOPUS:105048584582
T3 - Advances in Neural Information Processing Systems
SP - 134159
EP - 134178
BT - 39th Conference on Neural Information Processing Systems, NeurIPS 2025
PB - Neural information processing systems foundation
Y2 - 2 December 2025 through 7 December 2025
ER -