More effective crossover operators for the all-pairs shortest path problem

Benjamin Doerr; Daniel Johannsen; Timo Kötzing; Frank Neumann; Madeleine Theile

doi:10.1007/978-3-642-15844-5_19

More effective crossover operators for the all-pairs shortest path problem

Benjamin Doerr
, Daniel Johannsen
, Timo Kötzing
, Frank Neumann
, Madeleine Theile

Max-Planck-Institut fur Informatik
Max-Planck-Institut für Informatik
TU Berlin

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

17 Citations (Scopus)

Abstract

The all-pairs problem is the first non-artificial problem for which it was shown that adding crossover can significantly speed up a mutation-only evolutionary algorithm. Recently, the analysis of this algorithm was refined and it was shown to have an expected optimization time of Θ(n ^3.25(logn)^0.25). In this work, we study two variants of the algorithm. These are based on two central concepts in recombination, repair mechanisms and parent selection. We show that repairing infeasible offspring leads to an improved expected optimization time of O(n^3.2(log n) ^0.2). Furthermore, we prove that choosing parents that guarantee feasible offspring results in an optimization time of O(n³ log n).

Original language	English
Title of host publication	Parallel Problem Solving from Nature, PPSN XI - 11th International Conference, Proceedings
Publisher	Springer Verlag
Pages	184-193
Number of pages	10
Edition	PART 1
ISBN (Print)	3642158439, 9783642158438
DOIs	https://doi.org/10.1007/978-3-642-15844-5_19
Publication status	Published - 1 Jan 2010
Externally published	Yes

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 1
Volume	6238 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Access to Document

10.1007/978-3-642-15844-5_19

Cite this

Doerr, B., Johannsen, D., Kötzing, T., Neumann, F., & Theile, M. (2010). More effective crossover operators for the all-pairs shortest path problem. In Parallel Problem Solving from Nature, PPSN XI - 11th International Conference, Proceedings (PART 1 ed., pp. 184-193). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6238 LNCS, No. PART 1). Springer Verlag. https://doi.org/10.1007/978-3-642-15844-5_19

Doerr, Benjamin ; Johannsen, Daniel ; Kötzing, Timo et al. / More effective crossover operators for the all-pairs shortest path problem. Parallel Problem Solving from Nature, PPSN XI - 11th International Conference, Proceedings. PART 1. ed. Springer Verlag, 2010. pp. 184-193 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1).

@inproceedings{c922b24998744720bfedb3dfe108ce22,

title = "More effective crossover operators for the all-pairs shortest path problem",

abstract = "The all-pairs problem is the first non-artificial problem for which it was shown that adding crossover can significantly speed up a mutation-only evolutionary algorithm. Recently, the analysis of this algorithm was refined and it was shown to have an expected optimization time of Θ(n 3.25(logn)0.25). In this work, we study two variants of the algorithm. These are based on two central concepts in recombination, repair mechanisms and parent selection. We show that repairing infeasible offspring leads to an improved expected optimization time of O(n3.2(log n) 0.2). Furthermore, we prove that choosing parents that guarantee feasible offspring results in an optimization time of O(n3 log n).",

author = "Benjamin Doerr and Daniel Johannsen and Timo K{\"o}tzing and Frank Neumann and Madeleine Theile",

year = "2010",

month = jan,

day = "1",

doi = "10.1007/978-3-642-15844-5\_19",

language = "English",

isbn = "3642158439",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

number = "PART 1",

pages = "184--193",

booktitle = "Parallel Problem Solving from Nature, PPSN XI - 11th International Conference, Proceedings",

edition = "PART 1",

}

Doerr, B, Johannsen, D, Kötzing, T, Neumann, F & Theile, M 2010, More effective crossover operators for the all-pairs shortest path problem. in Parallel Problem Solving from Nature, PPSN XI - 11th International Conference, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 6238 LNCS, Springer Verlag, pp. 184-193. https://doi.org/10.1007/978-3-642-15844-5_19

More effective crossover operators for the all-pairs shortest path problem. / Doerr, Benjamin; Johannsen, Daniel; Kötzing, Timo et al.
Parallel Problem Solving from Nature, PPSN XI - 11th International Conference, Proceedings. PART 1. ed. Springer Verlag, 2010. p. 184-193 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6238 LNCS, No. PART 1).

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

TY - GEN

T1 - More effective crossover operators for the all-pairs shortest path problem

AU - Doerr, Benjamin

AU - Johannsen, Daniel

AU - Kötzing, Timo

AU - Neumann, Frank

AU - Theile, Madeleine

PY - 2010/1/1

Y1 - 2010/1/1

N2 - The all-pairs problem is the first non-artificial problem for which it was shown that adding crossover can significantly speed up a mutation-only evolutionary algorithm. Recently, the analysis of this algorithm was refined and it was shown to have an expected optimization time of Θ(n 3.25(logn)0.25). In this work, we study two variants of the algorithm. These are based on two central concepts in recombination, repair mechanisms and parent selection. We show that repairing infeasible offspring leads to an improved expected optimization time of O(n3.2(log n) 0.2). Furthermore, we prove that choosing parents that guarantee feasible offspring results in an optimization time of O(n3 log n).

AB - The all-pairs problem is the first non-artificial problem for which it was shown that adding crossover can significantly speed up a mutation-only evolutionary algorithm. Recently, the analysis of this algorithm was refined and it was shown to have an expected optimization time of Θ(n 3.25(logn)0.25). In this work, we study two variants of the algorithm. These are based on two central concepts in recombination, repair mechanisms and parent selection. We show that repairing infeasible offspring leads to an improved expected optimization time of O(n3.2(log n) 0.2). Furthermore, we prove that choosing parents that guarantee feasible offspring results in an optimization time of O(n3 log n).

U2 - 10.1007/978-3-642-15844-5_19

DO - 10.1007/978-3-642-15844-5_19

M3 - Conference contribution

AN - SCOPUS:78149262535

SN - 3642158439

SN - 9783642158438

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 184

EP - 193

BT - Parallel Problem Solving from Nature, PPSN XI - 11th International Conference, Proceedings

PB - Springer Verlag

ER -

Doerr B, Johannsen D, Kötzing T, Neumann F, Theile M. More effective crossover operators for the all-pairs shortest path problem. In Parallel Problem Solving from Nature, PPSN XI - 11th International Conference, Proceedings. PART 1 ed. Springer Verlag. 2010. p. 184-193. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1). doi: 10.1007/978-3-642-15844-5_19

More effective crossover operators for the all-pairs shortest path problem

Abstract

Publication series

Access to Document

Fingerprint

Cite this