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

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

17 Citations (Scopus)

Résumé

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

langue originale	Anglais
titre	Parallel Problem Solving from Nature, PPSN XI - 11th International Conference, Proceedings
Editeur	Springer Verlag
Pages	184-193
Nombre de pages	10
Edition	PART 1
ISBN (imprimé)	3642158439, 9783642158438
Les DOIs	https://doi.org/10.1007/978-3-642-15844-5_19
état	Publié - 1 janv. 2010
Modification externe	Oui

Série de publications

Nom	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
nombre	PART 1
Volume	6238 LNCS
ISSN (imprimé)	0302-9743
ISSN (Electronique)	1611-3349

Accès au document

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

Contient cette citation

Doerr, B., Johannsen, D., Kötzing, T., Neumann, F., & Theile, M. (2010). More effective crossover operators for the all-pairs shortest path problem. Dans Parallel Problem Solving from Nature, PPSN XI - 11th International Conference, Proceedings (PART 1 Ed., p. 184-193). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol 6238 LNCS, Numéro 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. p. 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. Dans 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), Numéro PART 1, VOL. 6238 LNCS, Springer Verlag, p. 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, Numéro PART 1).

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

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

Résumé

Série de publications

Accès au document

Empreinte digitale

Contient cette citation