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

Level-based analysis of genetic algorithms and other search processes

Dogan Corus, Duc Cuong Dang, Anton V. Eremeev, Per Kristian Lehre

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

27 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	Parallel Problem Solving from Nature – PPSN XIII
Subtitle of host publication	13th International Conference, Ljubljana, Slovenia, September 13-17, 2014. Proceedings
Publisher	Springer
Pages	912-921
Number of pages	10
ISBN (Electronic)	978-3-319-10762-2
ISBN (Print)	978-3-319-10761-5
DOIs	https://doi.org/10.1007/978-3-319-10762-2_90
Publication status	Published - 2014
Event	13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) - - Ljublijana, Slovenia Duration: 13 Sept 2014 → 17 Sept 2014

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	8672
ISSN (Print)	0302-9743

Conference

Conference	13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) -
Country/Territory	Slovenia
Period	13/09/14 → 17/09/14

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-319-10762-2_90

Cite this

Corus, D., Dang, D. C., Eremeev, A. V., & Lehre, P. K. (2014). 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 (pp. 912-921). (Lecture Notes in Computer Science; Vol. 8672). Springer. https://doi.org/10.1007/978-3-319-10762-2_90

@inproceedings{92812c3b436c479fa13252c1c2e66734,

title = "Level-based analysis of genetic algorithms and other search processes",

abstract = "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.",

author = "Dogan Corus and Dang, {Duc Cuong} and Eremeev, {Anton V.} and Lehre, {Per Kristian}",

year = "2014",

doi = "10.1007/978-3-319-10762-2_90",

language = "English",

isbn = "978-3-319-10761-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "912--921",

booktitle = "Parallel Problem Solving from Nature – PPSN XIII",

note = "13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) - ; Conference date: 13-09-2014 Through 17-09-2014",

}

Corus, D, Dang, DC, Eremeev, AV & Lehre, PK 2014, 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. Lecture Notes in Computer Science, vol. 8672, Springer, pp. 912-921, 13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) - , Slovenia, 13/09/14. https://doi.org/10.1007/978-3-319-10762-2_90

Level-based analysis of genetic algorithms and other search processes. / Corus, Dogan; Dang, Duc Cuong; Eremeev, Anton V. et al.
Parallel Problem Solving from Nature – PPSN XIII: 13th International Conference, Ljubljana, Slovenia, September 13-17, 2014. Proceedings. Springer, 2014. p. 912-921 (Lecture Notes in Computer Science; Vol. 8672).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 -

Level-based analysis of genetic algorithms and other search processes

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this