Runtime Analysis of Population-based Evolutionary Algorithms - Part I: Steady State EAs
References
[1]
Brendan Case and Per Kristian Lehre. Self-adaptation in non-Elitist Evolutionary Algorithms on Discrete Problems with Unknown Structure. IEEE Transactions on Evolutionary Computation, pages 1--1, 2020a. ISSN 1941--0026. Conference Name: IEEE Transactions on Evolutionary Computation.
[2]
Brendan Case and Per Kristian Lehre. Self-Adaptation in Nonelitist Evolutionary Algorithms on Discrete Problems With Unknown Structure. IEEE Transactions on Evolutionary Computation, 24(4):650--663, August 2020b. ISSN 1941--0026. Conference Name: IEEE Transactions on Evolutionary Computation
[3]
Stephan Cathabard, Per Kristian Lehre, and Xin Yao. Non-uniform mutation rates for problems with unknown solution lengths. In Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms, (FOGA 2011), pages 173--180, New York, NY, USA, 2011. ACM.
[4]
Tianshi Chen, Jun He, Guangzhong Sun, Guoliang Chen, and Xin Yao. A new approach for analyzing average time complexity of population-based evolutionary algorithms on unimodal problems. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, 39(5):1092--1106, Oct. 2009. ISSN 1083--4419.
[5]
Dogan Corus and Pietro S. Oliveto. Standard steady state genetic algorithms can hillclimb faster than mutation-only evolutionary algorithms. IEEE Transactions on Evolutionary Computation, pages 1--1, 2017.
[6]
Dogan Corus, Duc-Cuong Dang, Anton V. Eremeev, and Per Kristian Lehre. Level-Based Analysis of Genetic Algorithms and Other Search Processes. IEEE Transactions on Evolutionary Computation, 22(5):707--719, October 2018a. ISSN 1941--0026.
[7]
Dogan Corus, Duc-Cuong Dang, Anton V. Eremeev, and Per Kristian Lehre. Level-Based Analysis of Genetic Algorithms and Other Search Processes. IEEE Transactions on Evolutionary Computation, 22(5):707--719, October 2018b. ISSN 1089-778X, 1089-778X, 1941--0026. URL https://ieeexplore.ieee.org/document/8039236/.
[8]
Duc-Cuong Dang and Per Kristian Lehre. Refined Upper Bounds on the Expected Runtime of Non-elitist Populations from Fitness-Levels. In Proceedings of the 16th Annual Conference on Genetic and Evolutionary Computation Conference (GECCO 2014), pages 1367--1374, 2014. ISBN 9781450326629.
[9]
Duc-Cuong Dang and Per Kristian Lehre. Runtime Analysis of Non-elitist Populations: From Classical Optimisation to Partial Information. Algorithmica, 75(3):428--461, July 2016a. ISSN 1432--0541.
[10]
Duc-Cuong Dang and Per Kristian Lehre. Self-adaptation of Mutation Rates in Non-elitist Populations. In Julia Handl, Emma Hart, Peter R. Lewis, Manuel Lopez-Ibanez, Gabriela Ochoa, and Ben Paechter, editors, Parallel Problem Solving from Nature - PPSN XIV, volume 9921, pages 803--813. Springer International Publishing, Cham, 2016b. ISBN 978-3-319-45822-9 978-3-319-45823-6. URL http://link.springer.com/10.1007/978-3-319-45823-6_75.
[11]
Duc-Cuong Dang and Per Kristian Lehre. Self-adaptation of Mutation Rates in Non-elitist Populations. In Parallel Problem Solving from Nature - PPSN XIV, Lecture Notes in Computer Science, pages 803--813. Springer, Cham, September 2016c. ISBN 978-3-319-45822-9 978-3-319-45823-6. URL https://link.springer.com/chapter/10.1007/978-3-319-45823-6_75.
[12]
Duc-Cuong Dang, Thomas Jansen, and Per Kristian Lehre. Populations Can Be Essential in Tracking Dynamic Optima. Algorithmica, 78 (2):660--680, June 2017. ISSN 1432--0541.
[13]
Duc-Cuong Dang, Anton Eremeev, and Per Kristian Lehre. Non-elitist evolutionary algorithms excel in fitness landscapes with sparse deceptive regions and dense valleys. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '21, pages 1133--1141, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450383509.
[14]
Benjamin Doerr. Analyzing randomized search heuristics via stochastic domination. Theoretical Computer Science, 773:115--137, June 2019. ISSN 0304--3975. URL https://www.sciencedirect.com/science/article/pii/S0304397518305954.
[15]
Benjamin Doerr. Lower Bounds for Non-Elitist Evolutionary Algorithms via Negative Multiplicative Drift. Evolutionary Computation, pages 1--25, November 2020. ISSN 1063--6560, 1530--9304. URL https://www.mitpressjournals.org/doi/abs/10.1162/evco_a_00283.
[16]
Benjamin Doerr and Timo Kötzing. Multiplicative Up-Drift. Algorithmica, October 2020. ISSN 1432--0541.
[17]
Benjamin Doerr and Frank Neumann. A Survey on Recent Progress in the Theory of Evolutionary Algorithms for Discrete Optimization. ACM Transactions on Evolutionary Learning and Optimization, 1(4):16:1--16:43, October 2021. ISSN 2688-299X.
[18]
Benjamin Doerr, Carola Doerr, and Timo Kötzing. Solving Problems with Unknown Solution Length at Almost No Extra Cost | SpringerLink. Algorithmica, (81):703--748, 2019. URL https://link.springer.com/article/10.1007/s00453-018-0477-7.
[19]
Carola Doerr and Johannes Lengler. Introducing Elitist Black-Box Models: When Does Elitist Behavior Weaken the Performance of Evolutionary Algorithms? Evolutionary Computation, 25(4):587--606, October 2016. ISSN 1063--6560. Publisher: MIT Press.
[20]
Stefan Droste, Thomas Jansen, and Ingo Wegener. On the analysis of the (1+1) Evolutionary Algorithm. Theoretical Computer Science, 276:51--81, 2002.
[21]
A. E. Eiben, Zbigniew Michalewicz, Marc Schoenauer, and James E. Smith. Parameter control in evolutionary algorithms. In Parameter Setting in Evolutionary Algorithms, pages 19--46. Springer, 2007.
[22]
Hafsteinn Einarsson, Johannes Lengler, Marcelo Matheus Gauy, Florian Meier, Asier Mujika, Angelika Steger, and Felix Weissenberger. The Linear Hidden Subset Problem for the (1 + 1) EA with Scheduled and Adaptive Mutation Rates. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '18, pages 1491--1498, New York, NY, USA, 2018. ACM. ISBN 978-1-4503-5618-3. URL http://doi.acm.org/10.1145/3205455.3205519.
[23]
Jun He and Xin Yao. Towards an analytic framework for analysing the computation time of evolutionary algorithms. Artificial Intelligence, 145(1-2):59--97, 2003.
[24]
Thomas Jansen, Kenneth A. De Jong, and Ingo Wegener. On the choice of the offspring population size in evolutionary algorithms. Evolutionary Computation, 13(4):413--440, 2005.
[25]
Per Kristian Lehre. Negative drift in populations. In Proceedings of Parallel Problem Solving from Nature - (PPSN XI), volume 6238 of LNCS, pages 244--253. Springer Berlin / Heidelberg, 2011a.
[26]
Per Kristian Lehre. Fitness-levels for non-elitist populations. In Proceedings of the 13th annual conference on Genetic and evolutionary computation, (GECCO 2011), pages 2075--2082, New York, NY, USA, 2011b. ACM. ISBN 978-1-4503-0557-0.
[27]
Per Kristian Lehre and Xiaoyu Qin. More precise runtime analyses of non-elitist EAs in uncertain environments. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '21, pages 1160--1168, New York, NY, USA, June 2021. Association for Computing Machinery. ISBN 978-1-4503-8350-9.
[28]
Per Kristian Lehre and Xin Yao. On the impact of mutation-selection balance on the runtime of evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 16(2):225--241, April 2012. ISSN 1089-778X.
[29]
Frank Neumann, Pietro Simone Oliveto, and Carsten Witt. Theoretical analysis of fitness-proportional selection: landscapes and efficiency. In Proceedings of the 11th Annual conference on Genetic and evolutionary computation (GECCO 2009), pages 835--842, New York, NY, USA, 2009. ACM. ISBN 978-1-60558-325-9.
[30]
Pietro S. Oliveto and Carsten Witt. On the runtime analysis of the simple genetic algorithm. Theoretical Computer Science, 545:2--19, 2014.
[31]
Pietro S. Oliveto and Carsten Witt. Improved time complexity analysis of the simple genetic algorithm. Theoretical Computer Science, 605:21--41, 2015.
[32]
Pietro S. Oliveto, Jun He, and Xin Yao. Time complexity of evolutionary algorithms for combinatorial optimization: A decade of results. International Journal of Automation and Computing, 4(3):281--293, July 2007. ISSN 1751--8520.
[33]
Jonathan E. Rowe and Dirk Sudholt. The choice of the offspring population size in the (1,λ) ea. In Proceedings of the fourteenth international conference on Genetic and evolutionary computation conference, GECCO '12, pages 1349--1356, New York, NY, USA, 2012. ACM. ISBN 978-1-4503-1177-9.
[34]
Dirk Sudholt. A New Method for Lower Bounds on the Running Time of Evolutionary Algorithms. IEEE Transactions on Evolutionary Computation, 17(3):418--435, June 2013. ISSN 1941--0026.
[35]
Carsten Witt. Runtime Analysis of the (μ + 1) EA on Simple Pseudo-Boolean Functions. Evolutionary Computation, 14(1):65--86, 2006.
[36]
Andrew C. Yao. Probabilistic computations: Toward a unified measure of complexity. In 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), pages 222--227, October 1977. ISSN: 0272--5428.
[37]
Christine Zarges. On the utility of the population size for inversely fitness proportional mutation rates. In FOGA 09: Proceedings of the tenth ACM SIGEVO workshop on Foundations of genetic algorithms, pages 39--46, New York, NY, USA, 2009. ACM. ISBN 978-1-60558-414-0.
Recommendations
Population size versus runtime of a simple evolutionary algorithm
Evolutionary algorithms (EAs) find numerous applications, and practical knowledge on EAs is immense. In practice, sophisticated population-based EAs employing selection, mutation and crossover are applied. In contrast, theoretical analysis of EAs often ...
Standard Steady State Genetic Algorithms Can Hillclimb Faster Than Mutation-Only Evolutionary Algorithms
Explaining to what extent the real power of genetic algorithms (GAs) lies in the ability of crossover to recombine individuals into higher quality solutions is an important problem in evolutionary computation. In this paper we show how the interplay ...
Terminating evolutionary algorithms at their steady state
Assessing the reliability of termination conditions for evolutionary algorithms (EAs) is of prime importance. An erroneous or weak stop criterion can negatively affect both the computational effort and the final result. We introduce a statistical ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2023
2519 pages
Copyright © 2023 Owner/Author(s).
This work is licensed under a Creative Commons Attribution International 4.0 License.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 24 July 2023
Check for updates
Qualifiers
- Tutorial
Conference
GECCO '23 Companion
Sponsor:
GECCO '23 Companion: Companion Conference on Genetic and Evolutionary Computation
July 15 - 19, 2023
Lisbon, Portugal
Acceptance Rates
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 110Total Downloads
- Downloads (Last 12 months)89
- Downloads (Last 6 weeks)18
Reflects downloads up to 30 Sep 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in