mlsanityData to 14 Oct 2026

The (1+(λ,λ)) Global SEMO Algorithm

arXiv 2210.03618 ↗First posted 7 Oct 2022cs.NE cs.AIcited by 3

Not on the map. Why?

Abstract (arXiv)

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).

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 15 of its 59 references that are in the map. First posted on arXiv 7 Oct 2022.

Builds on

15 of 59 references.

References · 15

  1. 2017Fast Genetic Algorithmscited by 29
  2. 2020Self-Adjusting Evolutionary Algorithms for Multimodal Optimizationcited by 15
  3. 2022A First Runtime Analysis of the NSGA-II on a Multimodal Problemcited by 15
  4. 2018Better Runtime Guarantees Via Stochastic Dominationcited by 13
  5. 2020Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectivescited by 12
  6. 2021Lazy Parameter Tuning and Control: Choosing All Parameters Randomly From a Power-Law Distributioncited by 11
  7. 2018Theory of Parameter Control for Discrete Black-Box Optimization: Provable Performance Gains Through Dynamic Parameter Choicescited by 9
  8. 2018Design and Analysis of Diversity-Based Parent Selection Schemes for Speeding Up Evolutionary Multi-objective Optimisationcited by 9
  9. 2020Fixed-Target Runtime Analysiscited by 9
  10. 2020First Steps Towards a Runtime Analysis When Starting With a Good Solutioncited by 9
  11. 2018A Tight Runtime Analysis for the (μ + λ) EAcited by 8
  12. 2017Runtime Analysis of the (1+(λ,λ)) Genetic Algorithm on Random Satisfiable 3-CNF Formulascited by 7
3 more
  1. 2018Precise Runtime Analysis for Plateau Functionscited by 4
  2. 2022Running Time Analysis of the Non-dominated Sorting Genetic Algorithm II (NSGA-II) using Binary or Stochastic Tournament Selectioncited by 3
  3. 2019The Efficiency Threshold for the Offspring Population Size of the (μ, λ) EAcited by 2

Built on by

Cited by year

Citing papers per year: 2023: 2; 2024: 1.

3 papers.

  1. 2023The First Proven Performance Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problemcited by 6
  2. 2024Many Objective Problems Where Crossover is Provably Essentialcited by 3
  3. 2023Larger Offspring Populations Help the (1 + (λ, λ)) Genetic Algorithm to Overcome the Noisecited by 0