Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  More Effective Crossover Operators for the All-pairs Shortest Path Problem

Doerr, B., Johannsen, D., Kötzing, T., Neumann, F., & Theile, M. (2010). More Effective Crossover Operators for the All-pairs Shortest Path Problem. In R. Schaefer, C. Cotta, J. Kolodziej, & G. Rudolph (Eds.), Parallel Problem Solving from Nature, PPSN XI (pp. 184-193). Berlin: Springer. doi:10.1007/978-3-642-15844-5_19.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-168A-7 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-2B48-F
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Doerr, Benjamin1, Autor           
Johannsen, Daniel1, Autor           
Kötzing, Timo1, Autor           
Neumann, Frank1, Autor           
Theile, Madeleine2, Autor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: The All-Pairs Shortest Path 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 $\Theta(n^{3.25}(\log n)^{0.25})$. In this work, we study two variants of the algorithm. These are based on two central concepts in recombination, \emph{repair mechanisms} and \emph{parent selection}. We show that repairing infeasible offspring leads to an improved expected optimization time of $\mathord{O}(n^{3.2}(\log n)^{0.2})$. Furthermore, we prove that choosing parents that guarantee feasible offspring results in an optimization time of $\mathord{O}(n^{3}\log n)$.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 20102010
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 536748
DOI: 10.1007/978-3-642-15844-5_19
URI: http://dx.doi.org/10.1007/978-3-642-15844-5_19
Anderer: Local-ID: C1256428004B93B8-DAF9F353F1E3426CC12577FA003CEE2F-Doe-Joh-Koe-Neu-The:c:10:APSPCrossover
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: 11th International Conference on Parallel Problem Solving from Nature
Veranstaltungsort: Krakow, Poland
Start-/Enddatum: 2010-09-11 - 2010-09-15

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Parallel Problem Solving from Nature, PPSN XI
  Untertitel : 11th International Conference, Kraków, Poland, September 11-15, 2010, Proceedings, Part I
  Kurztitel : PPSN 2010
Genre der Quelle: Konferenzband
 Urheber:
Schaefer, Robert1, Herausgeber
Cotta, Carlos1, Herausgeber
Kolodziej, Joanna1, Herausgeber
Rudolph, Günter1, Herausgeber
Affiliations:
1 External Organizations, ou_persistent22            
Ort, Verlag, Ausgabe: Berlin : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 184 - 193 Identifikator: ISBN: 978-3-642-15843-8

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
  Kurztitel : LNCS
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 6238 Artikelnummer: - Start- / Endseite: - Identifikator: -