Level-based analysis of genetic algorithms and other search processes
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
Authors
Colleges, School and Institutes
External organisations
- University of Nottingham
- Omsk Branch of Sobolev Institute of Mathematics
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.
Details
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 |
Publication status | Published - 2014 |
Event | 13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) - - Ljublijana, Slovenia Duration: 13 Sep 2014 → 17 Sep 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 | Slovenia |
Period | 13/09/14 → 17/09/14 |