Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/82823
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Journal article |
Title: | More effective crossover operators for the all-pairs shortest path problem |
Author: | Doerr, B. Johannsen, D. Kotzing, T. Neumann, F. Theile, M. |
Citation: | Theoretical Computer Science, 2013; 471:12-26 |
Publisher: | Elsevier Science BV |
Issue Date: | 2013 |
ISSN: | 0304-3975 1879-2294 |
Statement of Responsibility: | Benjamin Doerr, Daniel Johannsen, Timo Kötzing, Frank Neumann, Madeleine Theile |
Abstract: | 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 (w. r. t. the number of fitness evaluations) of Θ(n3.25( logn)0.25). In contrast to this simple algorithm, evolutionary algorithms used in practice usually employ refined recombination strategies in order to avoid the creation of infeasible offspring. We study extensions of the basic algorithm by two such concepts which are central in recombination, namely repair mechanisms and parent selection. We show that repairing infeasible offspring leads to an improved expected optimization time of O( n3.2(logn)0.2). As a second part of our study we prove that choosing parents that guarantee feasible offspring results in an optimization time of O(n3logn). Both results show that already simple adjustments of the recombination operator can asymptotically improve the runtime of evolutionary algorithms.© 2012 Elsevier B.V. All rights reserved. |
Keywords: | Running time analysis Crossover Theory Shortest paths |
Rights: | © 2013 Published by Elsevier B.V. |
DOI: | 10.1016/j.tcs.2012.10.059 |
Published version: | http://dx.doi.org/10.1016/j.tcs.2012.10.059 |
Appears in Collections: | Aurora harvest 4 Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.