Non-elitist evolutionary algorithms excel in fitness landscapes with sparse deceptive regions and dense valleys

Duc-Cuong Dang; Anton Eremeev; Per Kristian Lehre

doi:10.1145/3449639.3459398

Non-elitist evolutionary algorithms excel in fitness landscapes with sparse deceptive regions and dense valleys

Duc-Cuong Dang, Anton Eremeev, Per Kristian Lehre

Computer Science

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

224 Downloads (Pure)

Abstract

It is largely unknown how the runtime of evolutionary algorithms depends on fitness landscape characteristics for broad classes of problems. Runtime guarantees for complex and multi-modal problems where EAs are typically applied are rarely available.

We present a parameterised problem class SparseLocalOpt_α,ε where the class with parameters α, ϵ ∈ [0, 1] contains all fitness landscapes with deceptive regions of sparsity ε and fitness valleys of density α. We study how the runtime of EAs depends on these fitness landscape parameters.

We find that for any constant density and sparsity α, ε ∈ (0, 1), SparseLocalOpt_α,ε has exponential elitist (μ + λ) black-box complexity, implying that a wide range of elitist EAs fail even for mildly deceptive and multi-modal landscapes. In contrast, we derive a set of sufficient conditions for non-elitist EAs to optimise any problem in SparseLocalOpt_α,ε in expected polynomial time for broad values of α and ε. These conditions can be satisfied for tournament selection and linear ranking selection, but not for (μ, λ)-selection.

Original language	English
Title of host publication	GECCO '21
Subtitle of host publication	Proceedings of the Genetic and Evolutionary Computation Conference
Editors	Francisco Chicano
Place of Publication	New York
Publisher	Association for Computing Machinery (ACM)
Pages	1133–1141
Number of pages	9
ISBN (Electronic)	9781450383509
DOIs	https://doi.org/10.1145/3449639.3459398
Publication status	Published - 26 Jun 2021
Event	2021 Genetic and Evolutionary Computation Conference, GECCO 2021 - Virtual, Online, France Duration: 10 Jul 2021 → 14 Jul 2021

Publication series

Name	Genetic and Evolutionary Computation Conference (GECCO)
Publisher	ACM

Conference

Conference	2021 Genetic and Evolutionary Computation Conference, GECCO 2021
Country/Territory	France
City	Virtual, Online
Period	10/07/21 → 14/07/21

Bibliographical note

Funding Information:
Eremeev was supported by the Russian Science Foundation grant 17-18-01536. Lehre was supported by a Turing AI Fellowship (EPSRC grant ref EP/V025562/1).

Publisher Copyright:
© 2021 ACM.

Keywords

Elitism
Fitness landscape analysis
Runtime analysis

ASJC Scopus subject areas

Genetics
Computational Mathematics

Access to Document

10.1145/3449639.3459398

DangDC2021Nonelitist
This is the authors accepted manuscript (AAM) for a forthcoming publication in GECCO '21: Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion, published by Association for Computing Machinery (ACM).
Accepted author manuscript, 459 KBLicence: None: All rights reserved
dangd2021corrigendumOther version, 157 KBLicence: None: All rights reserved

Cite this

Dang, D.-C., Eremeev, A., & Lehre, P. K. (2021). Non-elitist evolutionary algorithms excel in fitness landscapes with sparse deceptive regions and dense valleys. In F. Chicano (Ed.), GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference (pp. 1133–1141). (Genetic and Evolutionary Computation Conference (GECCO)). Association for Computing Machinery (ACM). https://doi.org/10.1145/3449639.3459398

Dang, Duc-Cuong ; Eremeev, Anton ; Lehre, Per Kristian. / Non-elitist evolutionary algorithms excel in fitness landscapes with sparse deceptive regions and dense valleys. GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference. editor / Francisco Chicano. New York : Association for Computing Machinery (ACM), 2021. pp. 1133–1141 (Genetic and Evolutionary Computation Conference (GECCO)).

@inproceedings{2950b9f4d0104f8ea9efdffc62e07059,

title = "Non-elitist evolutionary algorithms excel in fitness landscapes with sparse deceptive regions and dense valleys",

abstract = "It is largely unknown how the runtime of evolutionary algorithms depends on fitness landscape characteristics for broad classes of problems. Runtime guarantees for complex and multi-modal problems where EAs are typically applied are rarely available.We present a parameterised problem class SparseLocalOptα,ε where the class with parameters α, ϵ ∈ [0, 1] contains all fitness landscapes with deceptive regions of sparsity ε and fitness valleys of density α. We study how the runtime of EAs depends on these fitness landscape parameters.We find that for any constant density and sparsity α, ε ∈ (0, 1), SparseLocalOptα,ε has exponential elitist (μ + λ) black-box complexity, implying that a wide range of elitist EAs fail even for mildly deceptive and multi-modal landscapes. In contrast, we derive a set of sufficient conditions for non-elitist EAs to optimise any problem in SparseLocalOptα,ε in expected polynomial time for broad values of α and ε. These conditions can be satisfied for tournament selection and linear ranking selection, but not for (μ, λ)-selection.",

keywords = "Elitism, Fitness landscape analysis, Runtime analysis",

author = "Duc-Cuong Dang and Anton Eremeev and Lehre, {Per Kristian}",

note = "Funding Information: Eremeev was supported by the Russian Science Foundation grant 17-18-01536. Lehre was supported by a Turing AI Fellowship (EPSRC grant ref EP/V025562/1). Publisher Copyright: {\textcopyright} 2021 ACM.; 2021 Genetic and Evolutionary Computation Conference, GECCO 2021 ; Conference date: 10-07-2021 Through 14-07-2021",

year = "2021",

month = jun,

day = "26",

doi = "10.1145/3449639.3459398",

language = "English",

series = "Genetic and Evolutionary Computation Conference (GECCO)",

publisher = "Association for Computing Machinery (ACM)",

pages = "1133–1141",

editor = "Chicano, {Francisco }",

booktitle = "GECCO '21",

address = "United States",

}

Dang, D-C, Eremeev, A & Lehre, PK 2021, Non-elitist evolutionary algorithms excel in fitness landscapes with sparse deceptive regions and dense valleys. in F Chicano (ed.), GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference. Genetic and Evolutionary Computation Conference (GECCO), Association for Computing Machinery (ACM), New York, pp. 1133–1141, 2021 Genetic and Evolutionary Computation Conference, GECCO 2021, Virtual, Online, France, 10/07/21. https://doi.org/10.1145/3449639.3459398

Non-elitist evolutionary algorithms excel in fitness landscapes with sparse deceptive regions and dense valleys. / Dang, Duc-Cuong; Eremeev, Anton; Lehre, Per Kristian.
GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference. ed. / Francisco Chicano. New York: Association for Computing Machinery (ACM), 2021. p. 1133–1141 (Genetic and Evolutionary Computation Conference (GECCO)).

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

TY - GEN

T1 - Non-elitist evolutionary algorithms excel in fitness landscapes with sparse deceptive regions and dense valleys

AU - Dang, Duc-Cuong

AU - Eremeev, Anton

AU - Lehre, Per Kristian

N1 - Funding Information: Eremeev was supported by the Russian Science Foundation grant 17-18-01536. Lehre was supported by a Turing AI Fellowship (EPSRC grant ref EP/V025562/1). Publisher Copyright: © 2021 ACM.

PY - 2021/6/26

Y1 - 2021/6/26

N2 - It is largely unknown how the runtime of evolutionary algorithms depends on fitness landscape characteristics for broad classes of problems. Runtime guarantees for complex and multi-modal problems where EAs are typically applied are rarely available.We present a parameterised problem class SparseLocalOptα,ε where the class with parameters α, ϵ ∈ [0, 1] contains all fitness landscapes with deceptive regions of sparsity ε and fitness valleys of density α. We study how the runtime of EAs depends on these fitness landscape parameters.We find that for any constant density and sparsity α, ε ∈ (0, 1), SparseLocalOptα,ε has exponential elitist (μ + λ) black-box complexity, implying that a wide range of elitist EAs fail even for mildly deceptive and multi-modal landscapes. In contrast, we derive a set of sufficient conditions for non-elitist EAs to optimise any problem in SparseLocalOptα,ε in expected polynomial time for broad values of α and ε. These conditions can be satisfied for tournament selection and linear ranking selection, but not for (μ, λ)-selection.

AB - It is largely unknown how the runtime of evolutionary algorithms depends on fitness landscape characteristics for broad classes of problems. Runtime guarantees for complex and multi-modal problems where EAs are typically applied are rarely available.We present a parameterised problem class SparseLocalOptα,ε where the class with parameters α, ϵ ∈ [0, 1] contains all fitness landscapes with deceptive regions of sparsity ε and fitness valleys of density α. We study how the runtime of EAs depends on these fitness landscape parameters.We find that for any constant density and sparsity α, ε ∈ (0, 1), SparseLocalOptα,ε has exponential elitist (μ + λ) black-box complexity, implying that a wide range of elitist EAs fail even for mildly deceptive and multi-modal landscapes. In contrast, we derive a set of sufficient conditions for non-elitist EAs to optimise any problem in SparseLocalOptα,ε in expected polynomial time for broad values of α and ε. These conditions can be satisfied for tournament selection and linear ranking selection, but not for (μ, λ)-selection.

KW - Elitism

KW - Fitness landscape analysis

KW - Runtime analysis

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

U2 - 10.1145/3449639.3459398

DO - 10.1145/3449639.3459398

M3 - Conference contribution

T3 - Genetic and Evolutionary Computation Conference (GECCO)

SP - 1133

EP - 1141

BT - GECCO '21

A2 - Chicano, Francisco

PB - Association for Computing Machinery (ACM)

CY - New York

T2 - 2021 Genetic and Evolutionary Computation Conference, GECCO 2021

Y2 - 10 July 2021 through 14 July 2021

ER -

Dang DC, Eremeev A, Lehre PK. Non-elitist evolutionary algorithms excel in fitness landscapes with sparse deceptive regions and dense valleys. In Chicano F, editor, GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference. New York: Association for Computing Machinery (ACM). 2021. p. 1133–1141. (Genetic and Evolutionary Computation Conference (GECCO)). doi: 10.1145/3449639.3459398

Non-elitist evolutionary algorithms excel in fitness landscapes with sparse deceptive regions and dense valleys

Abstract

Publication series

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this