research-article

The (1 + (λ, λ)) global SEMO algorithm

Authors:

Benjamin Doerr,

Adrien PinardAuthors Info & Claims

GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 520 - 528

https://doi.org/10.1145/3512290.3528868

Published: 08 July 2022 Publication History

Abstract

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(n²), whereas the best runtime guarantee for the global SEMO is only O(n² log n).

References

[1]

Denis Antipov, Maxim Buzdalov, and Benjamin Doerr. 2020. Fast mutation in crossover-based algorithms. In Genetic and Evolutionary Computation Conference, GECCO 2020. ACM, 1268--1276.

Digital Library

[2]

Denis Antipov, Maxim Buzdalov, and Benjamin Doerr. 2020. First steps towards a runtime analysis when starting with a good solution. In Parallel Problem Solving From Nature, PPSN 2020, Part II. Springer, 560--573.

[3]

Denis Antipov, Maxim Buzdalov, and Benjamin Doerr. 2021. Lazy parameter tuning and control: choosing all parameters randomly from a power-law distribution. In Genetic and Evolutionary Computation Conference, GECCO 2021. ACM, 1115--1123.

Digital Library

[4]

Denis Antipov and Benjamin Doerr. 2021. Precise runtime analysis for plateau functions. ACM Transactions on Evolutionary Learning and Optimization 1 (2021), 13:1--13:28.

Digital Library

[5]

Denis Antipov and Benjamin Doerr. 2021. A tight runtime analysis for the (μ + λ) EA. Algorithmica 83 (2021), 1054--1095.

Digital Library

[6]

Denis Antipov, Benjamin Doerr, and Vitalii Karavaev. 2019. A tight runtime analysis for the (1 + (λ, λ)) GA on LeadingOnes. In Foundations of Genetic Algorithms, FOGA 2019. ACM, 169--182.

Digital Library

[7]

Denis Antipov, Benjamin Doerr, and Vitalii Karavaev. 2020. The (1 + (λ, λ)) GA is even faster on multimodal problems. In Genetic and Evolutionary Computation Conference, GECCO 2020. ACM, 1259--1267.

Digital Library

[8]

Denis Antipov, Benjamin Doerr, and Quentin Yang. 2019. The efficiency threshold for the offspring population size of the (μ, λ) EA. In Genetic and Evolutionary Computation Conference, GECCO 2019. ACM, 1461--1469.

Digital Library

[9]

Anne Auger and Benjamin Doerr (Eds.). 2011. Theory of Randomized Search Heuristics. World Scientific Publishing.

[10]

Chao Bian and Chao Qian. 2022. Running Time Analysis of the Non-dominated Sorting Genetic Algorithm II (NSGA-II) using Binary or Stochastic Tournament Selection. CoRR abs/2203.11550 (2022).

[11]

Dimo Brockhoff, Tobias Friedrich, and Frank Neumann. 2008. Analyzing hyper-volume indicator based algorithms. In Parallel Problem Solving from Nature, PPSN 2008. Springer, 651--660.

[12]

Dirk Büche, Sibylle D. Müller, and Petros Koumoutsakos. 2003. Self-adaptation for multi-objective evolutionary algorithms. In Evolutionary Multi-Criterion Optimization, EMO 2003. Springer, 267--281.

[13]

Maxim Buzdalov and Benjamin Doerr. 2017. Runtime Analysis of the (1 + (λ, λ)) Genetic Algorithm on Random Satisfiable 3-CNF Formulas. In Genetic and Evolutionary Computation Conference, GECCO 2017. ACM, 1343--1350.

Digital Library

[14]

Luc Devroye. 1972. The compound random search. Ph.D. dissertation, Purdue Univ., West Lafayette, IN.

[15]

Benjamin Doerr. 2019. Analyzing randomized search heuristics via stochastic domination. Theoretical Computer Science 773 (2019), 115--137.

Digital Library

[16]

Benjamin Doerr and Carola Doerr. 2018. Optimal static and self-adjusting parameter choices for the (1 + (λ, λ)) genetic algorithm. Algorithmica 80 (2018), 1658--1709.

Digital Library

[17]

Benjamin Doerr and Carola Doerr. 2020. Theory of parameter control for discrete black-box optimization: provable performance gains through dynamic parameter choices. In Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, Benjamin Doerr and Frank Neumann (Eds.). Springer, 271--321. Also available at https://arxiv.org/abs/1804.05650.

[18]

Benjamin Doerr, Carola Doerr, and Franziska Ebel. 2015. From black-box complexity to designing new genetic algorithms. Theoretical Computer Science 567 (2015), 87--104.

Digital Library

[19]

Benjamin Doerr, Wanru Gao, and Frank Neumann. 2016. Runtime analysis of evolutionary diversity maximization for OneMinMax. In Genetic and Evolutionary Computation Conference, GECCO 2016. ACM, 557--564.

Digital Library

[20]

Benjamin Doerr, Huu Phuoc Le, Régis Makhmara, and Ta Duy Nguyen. 2017. Fast genetic algorithms. In Genetic and Evolutionary Computation Conference, GECCO 2017. ACM, 777--784.

Digital Library

[21]

Benjamin Doerr and Frank Neumann (Eds.). 2020. Theory of Evolutionary Computation---Recent Developments in Discrete Optimization. Springer. Also available at https://cs.adelaide.edu.au/~frank/papers/TheoryBook2019-selfarchived.pdf.

[22]

Benjamin Doerr and Zhongdi Qu. 2022. A First Runtime Analysis of the NSGA-II on a Multimodal Problem. CoRR abs/2204.07637 (2022). arXiv:2204.07637

[23]

Benjamin Doerr and Weijie Zheng. 2021. Theoretical analyses of multi-objective evolutionary algorithms on multi-modal objectives. In Conference on Artificial Intelligence, AAAI 2021. AAAI Press, 12293--12301.

Digital Library

[24]

Stefan Droste, Thomas Jansen, and Ingo Wegener. 2002. On the analysis of the (1+1) evolutionary algorithm. Theoretical Computer Science 276 (2002), 51--81.

Digital Library

[25]

Stefan Droste, Thomas Jansen, and Ingo Wegener. 2006. Upper and lower bounds for randomized search heuristics in black-box optimization. Theory of Computing Systems 39 (2006), 525--544.

Digital Library

[26]

Mario Alejandro Hevia Fajardo and Dirk Sudholt. 2020. On the choice of the parameter control mechanism in the (1 + (λ, λ)) genetic algorithm. In Genetic and Evolutionary Computation Conference, GECCO 2020. ACM, 832--840.

Digital Library

[27]

Josselin Garnier, Leila Kallel, and Marc Schoenauer. 1999. Rigorous hitting times for binary mutations. Evolutionary Computation 7 (1999), 173--203.

Digital Library

[28]

Oliver Giel. 2003. Expected runtimes of a simple multi-objective evolutionary algorithm. In Congress on Evolutionary Computation, CEC 2003. IEEE, 1918--1925.

[29]

Oliver Giel and Per Kristian Lehre. 2010. On the effect of populations in evolutionary multi-objective optimisation. Evolutionary Computation 18 (2010), 335--356.

Digital Library

[30]

Zhengxin Huang and Yuren Zhou. 2020. Runtime analysis of somatic contiguous hypermutation operators in MOEA/D framework. In Conference on Artificial Intelligence, AAAI 2020. AAAI Press, 2359--2366.

[31]

Zhengxin Huang, Yuren Zhou, Zefeng Chen, and Xiaoyu He. 2019. Running time analysis of MOEA/D with crossover on discrete optimization problem. In Conference on Artificial Intelligence, AAAI 2019. AAAI Press, 2296--2303.

Digital Library

[32]

Christian Igel, Nikolaus Hansen, and Stefan Roth. 2007. Covariance matrix adaptation for multi-objective optimization. Evolutionary Computation 15 (2007), 1--28.

Digital Library

[33]

Thomas Jansen. 2013. Analyzing Evolutionary Algorithms - The Computer Science Perspective. Springer.

Digital Library

[34]

Thomas Jansen, Kenneth A. De Jong, and Ingo Wegener. 2005. On the choice of the offspring population size in evolutionary algorithms. Evolutionary Computation 13 (2005), 413--440.

Digital Library

[35]

Thomas Jansen and Christine Zarges. 2014. Performance analysis of randomised search heuristics operating with a fixed budget. Theoretical Computer Science 545 (2014), 39--58.

Digital Library

[36]

Marco Laumanns, Günter Rudolph, and Hans-Paul Schwefel. 2001. Mutation control and convergence in evolutionary multi-objective optimization. In Proceedings of the 7th International Mendel Conference on Soft Computing, MENDEL 2001. 24--29.

[37]

Marco Laumanns, Lothar Thiele, and Eckart Zitzler. 2004. Running time analysis of multiobjective evolutionary algorithms on pseudo-Boolean functions. IEEE Transactions on Evolutionary Computation 8 (2004), 170--182.

Digital Library

[38]

Marco Laumanns, Lothar Thiele, Eckart Zitzler, Emo Welzl, and Kalyanmoy Deb. 2002. Running time analysis of multi-objective evolutionary algorithms on a simple discrete optimization problem. In Parallel Problem Solving from Nature, PPSN 2002. Springer, 44--53.

[39]

Per Kristian Lehre and Carsten Witt. 2012. Black-Box Search by Unbiased Variation. Algorithmica 64 (2012), 623--642.

Digital Library

[40]

Yuan-Long Li, Yu-Ren Zhou, Zhi-Hui Zhan, and Jun Zhang. 2016. A primary theoretical study on decomposition-based multiobjective evolutionary algorithms. IEEE Transactions on Evolutionary Computation 20 (2016), 563--576.

Digital Library

[41]

Andrei Lissovoi, Pietro S. Oliveto, and John Alasdair Warwicker. 2019. On the time complexity of algorithm selection hyper-heuristics for multimodal optimisation. In Conference on Artificial Intelligence, AAAI 2019. AAAI Press, 2322--2329.

Digital Library

[42]

Heinz Mühlenbein. 1992. How genetic algorithms really work: mutation and hillclimbing. In Parallel Problem Solving from Nature, PPSN 1992. Elsevier, 15--26.

[43]

Frank Neumann and Carsten Witt. 2010. Bioinspired Computation in Combinatorial Optimization - Algorithms and Their Computational Complexity. Springer.

Digital Library

[44]

Phan Trung Hai Nguyen and Dirk Sudholt. 2020. Memetic algorithms outperform evolutionary algorithms in multimodal optimisation. Artificial Intelligence 287 (2020), 103345.

[45]

Edgar Covantes Osuna, Wanru Gao, Frank Neumann, and Dirk Sudholt. 2020. Design and analysis of diversity-based parent selection schemes for speeding up evolutionary multi-objective optimisation. Theoretical Computer Science 832 (2020), 123--142.

[46]

Amirhossein Rajabi and Carsten Witt. 2020. Self-adjusting evolutionary algorithms for multimodal optimization. In Genetic and Evolutionary Computation Conference, GECCO 2020. ACM, 1314--1322.

Digital Library

[47]

Ingo Rechenberg. 1973. Evolutionsstrategie. Friedrich Fromman Verlag (Günther Holzboog KG), Stuttgart.

[48]

Jonathan E. Rowe and Dirk Sudholt. 2014. The choice of the offspring population size in the (1, λ) evolutionary algorithm. Theoretical Computer Science 545 (2014), 20--38.

Digital Library

[49]

Günter Rudolph. 1997. Convergence Properties of Evolutionary Algorithms. Verlag Dr. Kovâc.

[50]

Michael A. Schumer and Kenneth Steiglitz. 1968. Adaptive step size random search. IEEE Trans. Automat. Control 13 (1968), 270--276.

[51]

Dirk Sudholt and Carsten Witt. 2019. On the choice of the update strength in estimation-of-distribution algorithms and ant colony optimization. Algorithmica 81 (2019), 1450--1489.

Digital Library

[52]

Carsten Witt. 2006. Runtime analysis of the (μ + 1) EA on simple pseudo-Boolean functions. Evolutionary Computation 14 (2006), 65--86.

Digital Library

[53]

Carsten Witt. 2013. Tight bounds on the optimization time of a randomized search heuristic on linear functions. Combinatorics, Probability & Computing 22 (2013), 294--318.

[54]

Weijie Zheng and Benjamin Doerr. 2022. Better approximation guarantees for the NSGA-II by using the current crowding distance. In Genetic and Evolutionary Computation Conference, GECCO 2022. ACM. Also available at https://arxiv.org/abs/2203.02693.

Digital Library

[55]

Weijie Zheng, Yufei Liu, and Benjamin Doerr. 2022. A first mathematical run-time analysis of the Non-Dominated Sorting Genetic Algorithm II (NSGA-II). In Conference on Artificial Intelligence, AAAI 2022. AAAI Press. Preprint at https://arxiv.org/abs/2112.08581.

Cited By

Ye FNeumann Fde Nobel JNeumann ABäck TLi XHandl J(2024)What Performance Indicators to Use for Self-Adaptation in Multi-Objective Evolutionary AlgorithmsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654073(787-795)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654073
Doerr CJanett DLengler J(2024)Tight Runtime Bounds for Static Unary Unbiased Evolutionary Algorithms on Linear FunctionsAlgorithmica10.1007/s00453-024-01258-986:10(3115-3152)Online publication date: 22-Jul-2024
https://doi.org/10.1007/s00453-024-01258-9
Zheng WDoerr B(2023)Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives*Evolutionary Computation10.1162/evco_a_0032831:4(337-373)Online publication date: 1-Dec-2023
https://doi.org/10.1162/evco_a_00328
Show More Cited By

Index Terms

The (1 + (λ, λ)) global SEMO algorithm
1. Theory of computation
  1. Theory and algorithms for application domains
    1. Theory of randomized search heuristics

Recommendations

The ($$1+\lambda $$1+ý) Evolutionary Algorithm with Self-Adjusting Mutation Rate

We propose a new way to self-adjust the mutation rate in population-based evolutionary algorithms in discrete search spaces. Roughly speaking, it consists of creating half the offspring with a mutation rate that is twice the current mutation rate and ...
The choice of the offspring population size in the (1,λ) evolutionary algorithm

We extend the theory of non-elitist evolutionary algorithms (EAs) by considering the offspring population size in the (1,@l) EA. We establish a sharp threshold at @l=log"e"e"-"1n~5log"1"0n between exponential and polynomial running times on OneMax. For ...
The (1+λ) evolutionary algorithm with self-adjusting mutation rate
GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference

We propose a new way to self-adjust the mutation rate in population-based evolutionary algorithms. Roughly speaking, it consists of creating half the offspring with a mutation rate that is twice the current mutation rate and the other half with half the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference

July 2022

1472 pages

ISBN:9781450392372

DOI:10.1145/3512290

Editor:
Jonathan E. Fieldsend
University of Exeter
,
General Chair:
Markus Wagner
The University of Adelaide

Copyright © 2022 ACM.

Publication rights licensed to ACM. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Agence Nationale de la Recherche

Conference

GECCO '22

Sponsor:

SIGEVO

GECCO '22: Genetic and Evolutionary Computation Conference

July 9 - 13, 2022

Massachusetts, Boston

Acceptance Rates

Overall Acceptance Rate 1,532 of 4,029 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
150
Total Downloads

Downloads (Last 12 months)18
Downloads (Last 6 weeks)5

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ye FNeumann Fde Nobel JNeumann ABäck TLi XHandl J(2024)What Performance Indicators to Use for Self-Adaptation in Multi-Objective Evolutionary AlgorithmsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654073(787-795)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654073
Doerr CJanett DLengler J(2024)Tight Runtime Bounds for Static Unary Unbiased Evolutionary Algorithms on Linear FunctionsAlgorithmica10.1007/s00453-024-01258-986:10(3115-3152)Online publication date: 22-Jul-2024
https://doi.org/10.1007/s00453-024-01258-9
Zheng WDoerr B(2023)Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives*Evolutionary Computation10.1162/evco_a_0032831:4(337-373)Online publication date: 1-Dec-2023
https://doi.org/10.1162/evco_a_00328
Ivanova AAntipov DDoerr BSilva SPaquete L(2023)Larger Offspring Populations Help the (1 + (λ, λ)) Genetic Algorithm to Overcome the NoiseProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590514(919-928)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590514
Doerr CJanett DLengler JSilva SPaquete L(2023)Tight Runtime Bounds for Static Unary Unbiased Evolutionary Algorithms on Linear FunctionsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590482(1565-1574)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590482

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents