Level-Based Analysis of Genetic Algorithms and Other Search Processes
作者： Dogan Corus , Duc-Cuong Dang , Anton V. Eremeev , Per Kristian Lehre
DOI: 10.1007/978-3-319-10762-2_90
关键词: Theoretical computer science 、 Range (mathematics) 、 Genetic algorithm 、 Sorting problem 、 Unary operation 、 Computer science 、 Variation (game tree) 、 Evolutionary algorithm 、 Simple (abstract algebra) 、 Benchmark (computing)
摘要: The fitness-level technique is a simple and old way to derive upper bounds for the expected runtime of elitist evolutionary algorithms (EAs). Recently, has been adapted deduce with non-elitist populations unary variation operators [2,8]. In this paper, we show that restriction can be removed. This gives rise much more general analytical tool which applicable wide range search processes. As introductory examples, provide analyses many variants Genetic Algorithm on well-known benchmark functions, such as OneMax, LeadingOnes, sorting problem.
springer.com
sci-hub.st 参考文章(21)
Per Kristian Lehre, Negative drift in populations parallel problem solving from nature. pp. 244- 253 ,(2010) , 10.1007/978-3-642-15844-5_25
Ingo Wegener, Methods for the Analysis of Evolutionary Algorithms on Pseudo-Boolean Functions Springer, Boston, MA. pp. 349- 369 ,(2003) , 10.1007/0-306-48041-7_14
Michael D. Vose, The Simple Genetic Algorithm: Foundations and Theory ,(1999)
Dirk Sudholt, A New Method for Lower Bounds on the Running Time of Evolutionary Algorithms IEEE Transactions on Evolutionary Computation. ,vol. 17, pp. 418- 435 ,(2013) , 10.1109/TEVC.2012.2202241
Per Kristian Lehre, Xin Yao, Crossover can be constructive when computing unique input–output sequences Soft Computing. ,vol. 15, pp. 1675- 1687 ,(2011) , 10.1007/S00500-010-0610-2
Jens Scharnow, Karsten Tinnefeld, Ingo Wegener, The analysis of evolutionary algorithms on sorting and shortest paths problems Journal of Mathematical Modelling and Algorithms. ,vol. 3, pp. 349- 366 ,(2004) , 10.1007/S10852-005-2584-0
Devdatt P. Dubhashi, Alessandro Panconesi, Concentration of Measure for the Analysis of Randomized Algorithms ,(2012)
Per Kristian Lehre, Fitness-levels for non-elitist populations Proceedings of the 13th annual conference on Genetic and evolutionary computation - GECCO '11. pp. 2075- 2082 ,(2011) , 10.1145/2001576.2001855
Benjamin Doerr, Carola Doerr, Franziska Ebel, Lessons from the black-box: fast crossover-based genetic algorithms genetic and evolutionary computation conference. pp. 781- 788 ,(2013) , 10.1145/2463372.2463480
Chao Qian, Yang Yu, Zhi-Hua Zhou, An analysis on recombination in multi-objective evolutionary optimization Artificial Intelligence. ,vol. 204, pp. 99- 119 ,(2013) , 10.1016/J.ARTINT.2013.09.002