Crossover can provably be useful in evolutionary computation

Benjamin Doerr; Edda Happ; Christian Klein

doi:10.1145/1389095.1389202

Crossover can provably be useful in evolutionary computation

Benjamin Doerr
, Edda Happ
, Christian Klein

Max-Planck-Institut fur Informatik

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

Abstract

We show that the 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
Title of host publication	GECCO'08
Subtitle of host publication	Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation 2008
Publisher	Association for Computing Machinery (ACM)
Pages	539-546
Number of pages	8
ISBN (Print)	9781605581309
DOIs	https://doi.org/10.1145/1389095.1389202
Publication status	Published - 1 Jan 2008
Externally published	Yes
Event	10th Annual Genetic and Evolutionary Computation Conference, GECCO 2008 - Atlanta, GA, United States Duration: 12 Jul 2008 → 16 Jul 2008

Publication series

Name	GECCO'08: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation 2008

Conference

Conference	10th Annual Genetic and Evolutionary Computation Conference, GECCO 2008
Country/Territory	United States
City	Atlanta, GA
Period	12/07/08 → 16/07/08

Keywords

Analysis
Combinatorial optimization
Crossover
Evolutionary computation

Access to Document

10.1145/1389095.1389202

Cite this

Doerr, B., Happ, E., & Klein, C. (2008). Crossover can provably be useful in evolutionary computation. In GECCO'08: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation 2008 (pp. 539-546). (GECCO'08: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation 2008). Association for Computing Machinery (ACM). https://doi.org/10.1145/1389095.1389202

Doerr, Benjamin ; Happ, Edda ; Klein, Christian. / Crossover can provably be useful in evolutionary computation. GECCO'08: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation 2008. Association for Computing Machinery (ACM), 2008. pp. 539-546 (GECCO'08: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation 2008).

@inproceedings{e05ca62597414fa6a360330768320d8e,

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

abstract = "We show that the 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 = "Analysis, Combinatorial optimization, Crossover, Evolutionary computation",

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

year = "2008",

month = jan,

day = "1",

doi = "10.1145/1389095.1389202",

language = "English",

isbn = "9781605581309",

series = "GECCO'08: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation 2008",

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

pages = "539--546",

booktitle = "GECCO'08",

note = "10th Annual Genetic and Evolutionary Computation Conference, GECCO 2008 ; Conference date: 12-07-2008 Through 16-07-2008",

}

Doerr, B, Happ, E & Klein, C 2008, Crossover can provably be useful in evolutionary computation. in GECCO'08: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation 2008. GECCO'08: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation 2008, Association for Computing Machinery (ACM), pp. 539-546, 10th Annual Genetic and Evolutionary Computation Conference, GECCO 2008, Atlanta, GA, United States, 12/07/08. https://doi.org/10.1145/1389095.1389202

Crossover can provably be useful in evolutionary computation. / Doerr, Benjamin; Happ, Edda; Klein, Christian.
GECCO'08: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation 2008. Association for Computing Machinery (ACM), 2008. p. 539-546 (GECCO'08: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation 2008).

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

TY - GEN

T1 - Crossover can provably be useful in evolutionary computation

AU - Doerr, Benjamin

AU - Happ, Edda

AU - Klein, Christian

PY - 2008/1/1

Y1 - 2008/1/1

N2 - We show that the 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 the 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 - Analysis

KW - Combinatorial optimization

KW - Crossover

KW - Evolutionary computation

UR - https://www.scopus.com/pages/publications/57349134448

U2 - 10.1145/1389095.1389202

DO - 10.1145/1389095.1389202

M3 - Conference contribution

AN - SCOPUS:57349134448

SN - 9781605581309

T3 - GECCO'08: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation 2008

SP - 539

EP - 546

BT - GECCO'08

PB - Association for Computing Machinery (ACM)

T2 - 10th Annual Genetic and Evolutionary Computation Conference, GECCO 2008

Y2 - 12 July 2008 through 16 July 2008

ER -

Doerr B, Happ E, Klein C. Crossover can provably be useful in evolutionary computation. In GECCO'08: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation 2008. Association for Computing Machinery (ACM). 2008. p. 539-546. (GECCO'08: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation 2008). doi: 10.1145/1389095.1389202

Crossover can provably be useful in evolutionary computation

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this