TY - GEN
T1 - Hot off the Press
T2 - 2023 Genetic and Evolutionary Computation Conference Companion, GECCO 2023 Companion
AU - Doerr, Benjamin
AU - Qu, Zhondi
N1 - Publisher Copyright:
© 2023 Copyright held by the owner/author(s).
PY - 2023/7/15
Y1 - 2023/7/15
N2 - Very recently, the first mathematical runtime analyses for the NSGA-II, the most common multi-objective evolutionary algorithm, have been conducted. Continuing this research direction, we prove that the NSGA-II optimizes the OneJumpZeroJump benchmark asymptotically faster when crossover is employed. Together with a parallel independent work by Dang, Opris, Salehi, and Sudholt (also at AAAI 2023), this is the first time such an advantage of crossover is proven for the NSGA-II. Our arguments can be transferred to single-objective optimization. They then prove that crossover can speed up the (μ + 1) genetic algorithm in a different way and more pronounced than known before. Our experiments confirm the added value of crossover and show that the observed advantages are even larger than what our proofs can guarantee. This paper for the Hot-off-the-Press track at GECCO 2023 summarizes the work Benjamin Doerr, Zhongdi Qu. Runtime analysis for the NSGA-II: Provable speed-ups from crossover, Conference on Artificial Intelligence, AAAI 2023. AAAI Press, to appear. [13].
AB - Very recently, the first mathematical runtime analyses for the NSGA-II, the most common multi-objective evolutionary algorithm, have been conducted. Continuing this research direction, we prove that the NSGA-II optimizes the OneJumpZeroJump benchmark asymptotically faster when crossover is employed. Together with a parallel independent work by Dang, Opris, Salehi, and Sudholt (also at AAAI 2023), this is the first time such an advantage of crossover is proven for the NSGA-II. Our arguments can be transferred to single-objective optimization. They then prove that crossover can speed up the (μ + 1) genetic algorithm in a different way and more pronounced than known before. Our experiments confirm the added value of crossover and show that the observed advantages are even larger than what our proofs can guarantee. This paper for the Hot-off-the-Press track at GECCO 2023 summarizes the work Benjamin Doerr, Zhongdi Qu. Runtime analysis for the NSGA-II: Provable speed-ups from crossover, Conference on Artificial Intelligence, AAAI 2023. AAAI Press, to appear. [13].
KW - NSGA-II
KW - multi-objective optimization
KW - multimodal problems
KW - runtime analysis
KW - theory
U2 - 10.1145/3583133.3595845
DO - 10.1145/3583133.3595845
M3 - Conference contribution
AN - SCOPUS:85169005013
T3 - GECCO 2023 Companion - Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion
SP - 19
EP - 20
BT - GECCO 2023 Companion - Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion
PB - Association for Computing Machinery, Inc
Y2 - 15 July 2023 through 19 July 2023
ER -