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

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

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
Pages	184-193
Number of pages	10
Edition	PART 1
DOIs	https://doi.org/10.1007/978-3-642-15844-5_19
Publication status	Published - 12 Nov 2010
Externally published	Yes
Event	11th International Conference on Parallel Problem Solving from Nature, PPSN 2010 - Krakow, Poland Duration: 11 Sept 2010 → 15 Sept 2010

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

Conference

Conference	11th International Conference on Parallel Problem Solving from Nature, PPSN 2010
Country/Territory	Poland
City	Krakow
Period	11/09/10 → 15/09/10

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). 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. 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 = nov,

day = "12",

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)",

number = "PART 1",

pages = "184--193",

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

edition = "PART 1",

note = "11th International Conference on Parallel Problem Solving from Nature, PPSN 2010 ; Conference date: 11-09-2010 Through 15-09-2010",

}

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, pp. 184-193, 11th International Conference on Parallel Problem Solving from Nature, PPSN 2010, Krakow, Poland, 11/09/10. 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. 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/11/12

Y1 - 2010/11/12

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

T2 - 11th International Conference on Parallel Problem Solving from Nature, PPSN 2010

Y2 - 11 September 2010 through 15 September 2010

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. 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

Conference

Access to Document

Fingerprint

Cite this