Cited By
View all- Ma YBai Y(2020)A multi-population differential evolution with best-random mutation strategy for large-scale global optimizationApplied Intelligence10.1007/s10489-019-01613-2Online publication date: 25-Jan-2020
Runtime Analysis of Population-based Evolutionary Algorithms
Pages 435 - 462
References
[1]
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. 10.1109/TSMCB.2008.2012167.
[2]
Dogan Corus, Duc-Cuong Dang, Anton V. Eremeev, and Per Kristian Lehre. Level-based analysis of genetic algorithms and other search processes. In Parallel Problem Solving from Nature - PPSN XIII - 13th International Conference, Ljubljana, Slovenia, September 13-17, 2014. Proceedings, pages 912--921, 2014. 10.1007/978-3-319-10762-2_90. URL http://dx.doi.org/10.1007/978-3-319-10762-2_90.
[3]
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. 10.1145/2576768.2598374.
[4]
Agoston E. Eiben and J. E. Smith. Introduction to Evolutionary Computing. SpringerVerlag, 2003. ISBN 3540401849.
[5]
David E. Goldberg and Kalyanmoy Deb. A comparative analysis of selection schemes used in genetic algorithms. In Foundations of Genetic Algorithms, pages 69--93. Morgan Kaufmann, 1991.
[6]
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.
[7]
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. 10.1162/106365605774666921.
[8]
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, 2011.
[9]
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, 2011. ACM. ISBN 978-1-4503-0557-0.
[10]
Per Kristian Lehre and Xin Yao. On the impact of mutation-selection balance on the runtime of evolutionary algorithms. Evolutionary Computation, IEEE Transactions on, 16 (2): 225 --241, April 2012. ISSN 1089-778X. 10.1109/TEVC.2011.2112665.
[11]
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. http://doi.acm.org/10.1145/1569901.1570016.
[12]
Pietro S. Oliveto and Carsten Witt. On the runtime analysis of the simple genetic algorithm. Theoretical Computer Science, 545: 2--19, 2014.
[13]
Pietro S. Oliveto and Carsten Witt. Improved time complexity analysis of the simple genetic algorithm. Theoretical Computer Science, 605: 21--41, 2015.
[14]
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.
[15]
Carsten Witt. Runtime Analysis of the (μ 1) EA on Simple Pseudo-Boolean Functions. Evolutionary Computation, 14 (1): 65--86, 2006.
[16]
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. http://doi.acm.org/10.1145/1527125.1527132.
Index Terms
- Runtime Analysis of Population-based Evolutionary Algorithms
Recommendations
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 ...
Towards a Runtime Comparison of Natural and Artificial Evolution
Evolutionary algorithms (EAs) form a popular optimisation paradigm inspired by natural evolution. In recent years the field of evolutionary computation has developed a rigorous analytical theory to analyse the runtimes of EAs on many illustrative ...
The choice of the offspring population size in the (1,λ) EA
GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computationWe extend the theory of non-elitist evolutionary algorithms (EAs) by considering the offspring population size in the (1,λ) EA. We establish a sharp threshold at λ = log{\frac{e}{e-1}} n ≈5 log10 n between exponential and polynomial running times on ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2016
1510 pages
ISBN:9781450343237
DOI:10.1145/2908961
- Editor:
- Tobias Friedrich,
- General Chair:
- Frank Neumann,
- Program Chair:
- Andrew M. Sutton
Copyright © 2016 Owner/Author.
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 20 July 2016
Check for updates
Author Tags
Qualifiers
- Tutorial
Funding Sources
Conference
GECCO '16
Sponsor:
Acceptance Rates
GECCO '16 Companion Paper Acceptance Rate 137 of 381 submissions, 36%;
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 81Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 14 Dec 2024
Other Metrics
Citations
Cited By
View all- Ma YBai Y(2020)A multi-population differential evolution with best-random mutation strategy for large-scale global optimizationApplied Intelligence10.1007/s10489-019-01613-2Online publication date: 25-Jan-2020
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in