Runtime analysis of evolutionary algorithms: basic introduction
Pages 448 - 468
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.
[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.
[3]
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, pages 1--1, 2017. ISSN 1089--778X.
[4]
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.
[5]
Duc-Cuong Dang and Per Kristian Lehre. Efficient optimisation of noisy fitness functions with population-based evolutionary algorithms. In Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII, FOGA '15, pages 62--68, New York, NY, USA, 2015. ACM. ISBN 978-1-4503-3434-1. URL
[6]
Duc-Cuong Dang and Per Kristian Lehre. Runtime analysis of non-elitist populations: From classical optimisation to partial information. Algorithmica, 75(3):428--461, 2016.
[7]
Duc-Cuong Dang, Tobias Friedrich, Timo Kötzing, Martin S. Krejca, Per Kristian Lehre, Pietro Simone Oliveto, Dirk Sudholt, and Andrew M. Sutton. Escaping local optima using crossover with emergent diversity. IEEE Transactions on Evolutionary Computation, pages 1--1, 2017. ISSN 1089--778X.
[8]
Agoston E. Eiben and J. E. Smith. Introduction to Evolutionary Computing. SpringerVerlag, 2003. ISBN 3540401849.
[9]
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.
[10]
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.
[11]
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.
[12]
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.
[13]
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.
[14]
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.
[15]
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.
[16]
Pietro S. Oliveto and Carsten Witt. On the runtime analysis of the simple genetic algorithm. Theoretical Computer Science, 545:2--19, 2014.
[17]
Pietro S. Oliveto and Carsten Witt. Improved time complexity analysis of the simple genetic algorithm. Theoretical Computer Science, 605:21--41, 2015.
[18]
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.
[19]
Carsten Witt. Runtime Analysis of the (μ + 1) EA on Simple Pseudo-Boolean Functions. Evolutionary Computation, 14(1):65--86, 2006.
[20]
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
Use of the q-Gaussian mutation in evolutionary algorithms
Special issue on advances in computational intelligence and bioinformaticsThis paper proposes the use of the q-Gaussian mutation with self-adaptation of the shape of the mutation distribution in evolutionary algorithms. The shape of the q-Gaussian mutation distribution is controlled by a real parameter q. In the proposed ...
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 ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2018
1968 pages
Copyright © 2018 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: 06 July 2018
Check for updates
Qualifiers
- Tutorial
Conference
GECCO '18
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 90Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 14 Dec 2024
Other Metrics
Citations
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