The $(1+(\lambda ,\lambda ))$ Global SEMO Algorithm

Abstract

The $(1+(\lambda ,\lambda ))$ 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+(\lambda ,\lambda ))$ 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(n^2)$, whereas the best runtime guarantee for the global SEMO is only $O(n^2\log n)$.

arXiv commentAuthor generated version of a paper at GECCO 2022

References in corpus (5)

• Better Runtime Guarantees Via Stochastic Domination
• Runtime Analysis of the $(1+(\lambda ,\lambda ))$ Genetic Algorithm on Random Satisfiable 3-CNF Formulas
• Self-Adjusting Evolutionary Algorithms for Multimodal Optimization
• Design and Analysis of Diversity-Based Parent Selection Schemes for Speeding Up Evolutionary Multi-objective Optimisation
• Precise Runtime Analysis for Plateau Functions

Cited by in corpus (1)

• Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives