TY - GEN
T1 - Near-Tight Runtime Guarantees for Many-Objective Evolutionary Algorithms
AU - Wietheger, Simon
AU - Doerr, Benjamin
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
PY - 2024/1/1
Y1 - 2024/1/1
N2 - Despite significant progress in the field of mathematical runtime analysis of multi-objective evolutionary algorithms (MOEAs), the performance of MOEAs on discrete many-objective problems is little understood. In particular, the few existing bounds for the SEMO, global SEMO, and SMS-EMOA algorithms on classic benchmarks are all roughly quadratic in the size of the Pareto front. In this work, we prove near-tight runtime guarantees for these three algorithms on the four most common benchmark problems OneMinMax, CountingOnesCountingZeros, LeadingOnesTrailingZeros, and OneJumpZeroJump, and this for arbitrary numbers of objectives. Our bounds depend only linearly on the Pareto front size, showing that these MOEAs on these benchmarks cope much better with many objectives than what previous works suggested. Our bounds are tight apart from small polynomial factors in the number of objectives and length of bitstrings. This is the first time that such tight bounds are proven for many-objective uses of these MOEAs. While it is known that such results cannot hold for the NSGA-II, we do show that our bounds, via a recent structural result, transfer to the NSGA-III algorithm.
AB - Despite significant progress in the field of mathematical runtime analysis of multi-objective evolutionary algorithms (MOEAs), the performance of MOEAs on discrete many-objective problems is little understood. In particular, the few existing bounds for the SEMO, global SEMO, and SMS-EMOA algorithms on classic benchmarks are all roughly quadratic in the size of the Pareto front. In this work, we prove near-tight runtime guarantees for these three algorithms on the four most common benchmark problems OneMinMax, CountingOnesCountingZeros, LeadingOnesTrailingZeros, and OneJumpZeroJump, and this for arbitrary numbers of objectives. Our bounds depend only linearly on the Pareto front size, showing that these MOEAs on these benchmarks cope much better with many objectives than what previous works suggested. Our bounds are tight apart from small polynomial factors in the number of objectives and length of bitstrings. This is the first time that such tight bounds are proven for many-objective uses of these MOEAs. While it is known that such results cannot hold for the NSGA-II, we do show that our bounds, via a recent structural result, transfer to the NSGA-III algorithm.
KW - NSGA
KW - SMS-EMOA
KW - evolutionary multi-objective optimization
KW - runtime analysis
KW - theory
U2 - 10.1007/978-3-031-70085-9_10
DO - 10.1007/978-3-031-70085-9_10
M3 - Conference contribution
AN - SCOPUS:85204522682
SN - 9783031700842
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 153
EP - 168
BT - Parallel Problem Solving from Nature – PPSN XVIII - 18th International Conference, PPSN 2024, Proceedings
A2 - Affenzeller, Michael
A2 - Winkler, Stephan M.
A2 - Kononova, Anna V.
A2 - Bäck, Thomas
A2 - Trautmann, Heike
A2 - Tušar, Tea
A2 - Machado, Penousal
PB - Springer Science and Business Media Deutschland GmbH
T2 - 18th International Conference on Parallel Problem Solving from Nature, PPSN 2024
Y2 - 14 September 2024 through 18 September 2024
ER -