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

arXiv: https://arxiv.org/abs/2210.03618 · HTML: https://mlsanity.com/paper/2210.03618/

## 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 (most cited first, 15 of 15)

- [Fast Genetic Algorithms](https://mlsanity.com/paper/1703.03334/) (2017)
- [Self-Adjusting Evolutionary Algorithms for Multimodal Optimization](https://mlsanity.com/paper/2004.03266/) (2020)
- [A First Runtime Analysis of the NSGA-II on a Multimodal Problem](https://mlsanity.com/paper/2204.13750/) (2022)
- [Better Runtime Guarantees Via Stochastic Domination](https://mlsanity.com/paper/1801.04487/) (2018)
- [Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives](https://mlsanity.com/paper/2012.07231/) (2020)
- [Lazy Parameter Tuning and Control: Choosing All Parameters Randomly From a Power-Law Distribution](https://mlsanity.com/paper/2104.06714/) (2021)
- [Theory of Parameter Control for Discrete Black-Box Optimization: Provable Performance Gains Through Dynamic Parameter Choices](https://mlsanity.com/paper/1804.05650/) (2018)
- [Design and Analysis of Diversity-Based Parent Selection Schemes for Speeding Up Evolutionary Multi-objective Optimisation](https://mlsanity.com/paper/1805.01221/) (2018)
- [Fixed-Target Runtime Analysis](https://mlsanity.com/paper/2004.09613/) (2020)
- [First Steps Towards a Runtime Analysis When Starting With a Good Solution](https://mlsanity.com/paper/2006.12161/) (2020)
- [A Tight Runtime Analysis for the (μ + λ) EA](https://mlsanity.com/paper/1812.11061/) (2018)
- [Runtime Analysis of the (1+(λ,λ)) Genetic Algorithm on Random Satisfiable 3-CNF Formulas](https://mlsanity.com/paper/1704.04366/) (2017)
- [Precise Runtime Analysis for Plateau Functions](https://mlsanity.com/paper/1806.01331/) (2018)
- [Running Time Analysis of the Non-dominated Sorting Genetic Algorithm II (NSGA-II) using Binary or Stochastic Tournament Selection](https://mlsanity.com/paper/2203.11550/) (2022)
- [The Efficiency Threshold for the Offspring Population Size of the (μ, λ) EA](https://mlsanity.com/paper/1904.06981/) (2019)

## Built on by (most cited first, 3 of 3)

- [The First Proven Performance Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem](https://mlsanity.com/paper/2305.13459/) (2023)
- [Many Objective Problems Where Crossover is Provably Essential](https://mlsanity.com/paper/2412.18375/) (2024)
- [Larger Offspring Populations Help the (1 + (λ, λ)) Genetic Algorithm to Overcome the Noise](https://mlsanity.com/paper/2305.04553/) (2023)

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