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

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

96 Citations (Scopus)

Résumé

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.

langue originale	Anglais
Pages (de - à)	17-33
Nombre de pages	17
journal	Theoretical Computer Science
Volume	425
Les DOIs	https://doi.org/10.1016/j.tcs.2010.10.035
état	Publié - 30 mars 2012
Modification externe	Oui

Accès au document

10.1016/j.tcs.2010.10.035

Contient cette citation

@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

Résumé

Accès au document

Empreinte digitale

Contient cette citation