Crossover can provably be useful in evolutionary computation

Benjamin Doerr; Edda Happ; Christian Klein

doi:10.1016/j.tcs.2010.10.035

Crossover can provably be useful in evolutionary computation

Benjamin Doerr
, Edda Happ
, Christian Klein

Max-Planck-Institut fur Informatik

Research output: Contribution to journal › Article › peer-review

96 Citations (Scopus)

Abstract

We show that a natural evolutionary algorithm for the all-pairs shortest path problem is significantly faster with a crossover operator than without. This is the first theoretical analysis proving the usefulness of crossover for a non-artificial problem.

Original language	English
Pages (from-to)	17-33
Number of pages	17
Journal	Theoretical Computer Science
Volume	425
DOIs	https://doi.org/10.1016/j.tcs.2010.10.035
Publication status	Published - 30 Mar 2012
Externally published	Yes

Keywords

Crossover
Runtime analysis
Shortest path

Access to Document

10.1016/j.tcs.2010.10.035

Cite this

@article{dccbe6e1d48349569036a978a6bfec4b,

title = "Crossover can provably be useful in evolutionary computation",

abstract = "We show that a natural evolutionary algorithm for the all-pairs shortest path problem is significantly faster with a crossover operator than without. This is the first theoretical analysis proving the usefulness of crossover for a non-artificial problem.",

keywords = "Crossover, Runtime analysis, Shortest path",

author = "Benjamin Doerr and Edda Happ and Christian Klein",

year = "2012",

month = mar,

day = "30",

doi = "10.1016/j.tcs.2010.10.035",

language = "English",

volume = "425",

pages = "17--33",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Crossover can provably be useful in evolutionary computation

AU - Doerr, Benjamin

AU - Happ, Edda

AU - Klein, Christian

PY - 2012/3/30

Y1 - 2012/3/30

N2 - We show that a natural evolutionary algorithm for the all-pairs shortest path problem is significantly faster with a crossover operator than without. This is the first theoretical analysis proving the usefulness of crossover for a non-artificial problem.

AB - We show that a natural evolutionary algorithm for the all-pairs shortest path problem is significantly faster with a crossover operator than without. This is the first theoretical analysis proving the usefulness of crossover for a non-artificial problem.

KW - Crossover

KW - Runtime analysis

KW - Shortest path

U2 - 10.1016/j.tcs.2010.10.035

DO - 10.1016/j.tcs.2010.10.035

M3 - Article

AN - SCOPUS:84857916849

SN - 0304-3975

VL - 425

SP - 17

EP - 33

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Crossover can provably be useful in evolutionary computation

Abstract

Keywords

Access to Document

Fingerprint

Cite this