TY - GEN
T1 - Level-based analysis of genetic algorithms and other search processes
AU - Corus, Dogan
AU - Dang, Duc Cuong
AU - Eremeev, Anton V.
AU - Lehre, Per Kristian
PY - 2014
Y1 - 2014
N2 - The fitness-level technique is a simple and old way to derive upper bounds for the expected runtime of simple elitist evolutionary algorithms (EAs). Recently, the technique has been adapted to deduce the runtime of algorithms with non-elitist populations and unary variation operators [2,8]. In this paper, we show that the restriction to unary variation operators can be removed. This gives rise to a much more general analytical tool which is applicable to a wide range of search processes. As introductory examples, we provide simple runtime analyses of many variants of the Genetic Algorithm on well-known benchmark functions, such as OneMax, LeadingOnes, and the sorting problem.
AB - The fitness-level technique is a simple and old way to derive upper bounds for the expected runtime of simple elitist evolutionary algorithms (EAs). Recently, the technique has been adapted to deduce the runtime of algorithms with non-elitist populations and unary variation operators [2,8]. In this paper, we show that the restriction to unary variation operators can be removed. This gives rise to a much more general analytical tool which is applicable to a wide range of search processes. As introductory examples, we provide simple runtime analyses of many variants of the Genetic Algorithm on well-known benchmark functions, such as OneMax, LeadingOnes, and the sorting problem.
UR - http://www.scopus.com/inward/record.url?scp=84921717289&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-10762-2_90
DO - 10.1007/978-3-319-10762-2_90
M3 - Conference contribution
AN - SCOPUS:84921717289
SN - 978-3-319-10761-5
T3 - Lecture Notes in Computer Science
SP - 912
EP - 921
BT - Parallel Problem Solving from Nature – PPSN XIII
PB - Springer
T2 - 13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) -
Y2 - 13 September 2014 through 17 September 2014
ER -