TY - GEN
T1 - The (1 + (?, ?)) global SEMO algorithm
AU - Doerr, Benjamin
AU - Hadri, Omar El
AU - Pinard, Adrien
N1 - Publisher Copyright:
© 2022 ACM.
PY - 2022/7/8
Y1 - 2022/7/8
N2 - The (1 + (?, ?)) genetic algorithm is a recently proposed single-objective evolutionary algorithm with several interesting properties. We show that its main working principle, mutation with a high rate and crossover as repair mechanism, can be transported also to multi-objective evolutionary computation. We define the (1 + (?, ?)) global SEMO algorithm, a variant of the classic global SEMO algorithm, and prove that it optimizes the OneMinMax benchmark asymptotically faster than the global SEMO. Following the single-objective example, we design a one-fifth rule inspired dynamic parameter setting (to the best of our knowledge for the first time in discrete multi-objective optimization) and prove that it further improves the runtime to O(n2), whereas the best runtime guarantee for the global SEMO is only O(n2 log n).
AB - The (1 + (?, ?)) genetic algorithm is a recently proposed single-objective evolutionary algorithm with several interesting properties. We show that its main working principle, mutation with a high rate and crossover as repair mechanism, can be transported also to multi-objective evolutionary computation. We define the (1 + (?, ?)) global SEMO algorithm, a variant of the classic global SEMO algorithm, and prove that it optimizes the OneMinMax benchmark asymptotically faster than the global SEMO. Following the single-objective example, we design a one-fifth rule inspired dynamic parameter setting (to the best of our knowledge for the first time in discrete multi-objective optimization) and prove that it further improves the runtime to O(n2), whereas the best runtime guarantee for the global SEMO is only O(n2 log n).
KW - Runtime analysis
KW - dynamic parameter setting
KW - multi-objective optimization
KW - mutation operator
KW - one-fifth success rule
U2 - 10.1145/3512290.3528868
DO - 10.1145/3512290.3528868
M3 - Conference contribution
AN - SCOPUS:85135218889
T3 - GECCO 2022 - Proceedings of the 2022 Genetic and Evolutionary Computation Conference
SP - 520
EP - 528
BT - GECCO 2022 - Proceedings of the 2022 Genetic and Evolutionary Computation Conference
PB - Association for Computing Machinery, Inc
T2 - 2022 Genetic and Evolutionary Computation Conference, GECCO 2022
Y2 - 9 July 2022 through 13 July 2022
ER -