Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/67018
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Journal article |
Title: | Expected runtimes of evolutionary algorithms for the Eulerian cycle problem |
Author: | Neumann, F. |
Citation: | Computers and Operations Research, 2008; 35(9):2750-2759 |
Publisher: | Pergamon-Elsevier Science Ltd |
Issue Date: | 2008 |
ISSN: | 0305-0548 1873-765X |
Statement of Responsibility: | Frank Neumann |
Abstract: | Evolutionary algorithms are randomized search heuristics, which are applied to problems whose structure is not well understood, as well as to problems in combinatorial optimization. They have successfully been applied to different kinds of arc routing problems. To start the analysis of evolutionary algorithms with respect to the expected optimization time on these problems, we consider the Eulerian cycle problem. We show that a variant of the well-known (1 + 1) EA working on the important encoding of permutations is able to find an Eulerian tour of an Eulerian graph in expected polynomial time. Altering the operator used for mutation in the considered algorithm, the expected optimization time changes from polynomial to exponential. © 2007 Elsevier Ltd. All rights reserved. |
Keywords: | Evolutionary computations Combinatorial optimization Eulerian cycles Expected optimization time |
Rights: | Copyright © 2007 Elsevier Ltd. All rights reserved. |
DOI: | 10.1016/j.cor.2006.12.009 |
Published version: | http://dx.doi.org/10.1016/j.cor.2006.12.009 |
Appears in Collections: | Aurora harvest 5 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.