Fitness-levels for non-elitist populations

Per Kristian Lehre

doi:10.1145/2001576.2001855

Fitness-levels for non-elitist populations

Per Kristian Lehre^*

^*Corresponding author for this work

Computer Science

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

50 Citations (Scopus)

Abstract

This paper introduces an easy to use technique for deriving upper bounds on the expected runtime of non-elitist population-based evolutionary algorithms (EAs). Applications of the technique show how the efficiency of EAs is critically dependant on having a sufficiently strong selective pressure. Parameter settings that ensure sufficient selective pressure on commonly considered benchmark functions are derived for the most popular selection mechanisms. Together with a recent technique for deriving lower bounds, this paper contributes to a much-needed analytical tool-box for the analysis of evolutionary algorithms with populations.

Original language	English
Title of host publication	Genetic and Evolutionary Computation Conference, GECCO'11
Pages	2075-2082
Number of pages	8
DOIs	https://doi.org/10.1145/2001576.2001855
Publication status	Published - 2011
Event	13th Annual Genetic and Evolutionary Computation Conference, GECCO'11 - Dublin, Ireland Duration: 12 Jul 2011 → 16 Jul 2011

Conference

Conference	13th Annual Genetic and Evolutionary Computation Conference, GECCO'11
Country/Territory	Ireland
City	Dublin
Period	12/07/11 → 16/07/11

Keywords

Evolutionary algorithms
Runtime analysis

ASJC Scopus subject areas

Computational Theory and Mathematics
Theoretical Computer Science

Access to Document

10.1145/2001576.2001855

Cite this

@inproceedings{50f04a09ef974107bba755ace7beeea3,

title = "Fitness-levels for non-elitist populations",

abstract = "This paper introduces an easy to use technique for deriving upper bounds on the expected runtime of non-elitist population-based evolutionary algorithms (EAs). Applications of the technique show how the efficiency of EAs is critically dependant on having a sufficiently strong selective pressure. Parameter settings that ensure sufficient selective pressure on commonly considered benchmark functions are derived for the most popular selection mechanisms. Together with a recent technique for deriving lower bounds, this paper contributes to a much-needed analytical tool-box for the analysis of evolutionary algorithms with populations.",

keywords = "Evolutionary algorithms, Runtime analysis",

author = "Lehre, {Per Kristian}",

year = "2011",

doi = "10.1145/2001576.2001855",

language = "English",

isbn = "9781450305570",

pages = "2075--2082",

booktitle = "Genetic and Evolutionary Computation Conference, GECCO'11",

note = "13th Annual Genetic and Evolutionary Computation Conference, GECCO'11 ; Conference date: 12-07-2011 Through 16-07-2011",

}

TY - GEN

T1 - Fitness-levels for non-elitist populations

AU - Lehre, Per Kristian

PY - 2011

Y1 - 2011

N2 - This paper introduces an easy to use technique for deriving upper bounds on the expected runtime of non-elitist population-based evolutionary algorithms (EAs). Applications of the technique show how the efficiency of EAs is critically dependant on having a sufficiently strong selective pressure. Parameter settings that ensure sufficient selective pressure on commonly considered benchmark functions are derived for the most popular selection mechanisms. Together with a recent technique for deriving lower bounds, this paper contributes to a much-needed analytical tool-box for the analysis of evolutionary algorithms with populations.

AB - This paper introduces an easy to use technique for deriving upper bounds on the expected runtime of non-elitist population-based evolutionary algorithms (EAs). Applications of the technique show how the efficiency of EAs is critically dependant on having a sufficiently strong selective pressure. Parameter settings that ensure sufficient selective pressure on commonly considered benchmark functions are derived for the most popular selection mechanisms. Together with a recent technique for deriving lower bounds, this paper contributes to a much-needed analytical tool-box for the analysis of evolutionary algorithms with populations.

KW - Evolutionary algorithms

KW - Runtime analysis

UR - http://www.scopus.com/inward/record.url?scp=84860420428&partnerID=8YFLogxK

U2 - 10.1145/2001576.2001855

DO - 10.1145/2001576.2001855

M3 - Conference contribution

AN - SCOPUS:84860420428

SN - 9781450305570

SP - 2075

EP - 2082

BT - Genetic and Evolutionary Computation Conference, GECCO'11

T2 - 13th Annual Genetic and Evolutionary Computation Conference, GECCO'11

Y2 - 12 July 2011 through 16 July 2011

ER -

Fitness-levels for non-elitist populations

Abstract

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this