Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/66265
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | Fixed parameter evolutionary algorithms and maximum leaf spanning trees: a matter of mutation |
Author: | Kratsch, S. Lehre, P. Neumann, F. Oliveto, P. |
Citation: | Parallel Problem Solving from Nature – PPSN XI: 11th International Conference, Kraków, Poland, September 11-15, 2010, Proceedings, Part I / Robert Schaefer, Carlos Cotta, Joanna Kołodziej and Günter Rudolph (eds.): pp.204-213 |
Publisher: | Springer-Verlag |
Publisher Place: | Berlin |
Issue Date: | 2010 |
Series/Report no.: | Lecture Notes in Computer Science ; 6238 |
ISBN: | 3642158439 9783642158438 |
ISSN: | 0302-9743 1611-3349 |
Conference Name: | International Conference on Parallel Problem Solving from Nature (11th : 2010 : Krakow, Poland) |
Editor: | Schaefer, R. Cotta, C. Kolodziej, J. Rudolph, G. |
Statement of Responsibility: | Stefan Kratsch, Per Kristian Lehre, Frank Neumann and Pietro Simone Oliveto |
Abstract: | Evolutionary algorithms have been shown to be very successful for a wide range of NP-hard combinatorial optimization problems. We investigate the NP-hard problem of computing a spanning tree that has a maximal number of leaves by evolutionary algorithms in the context of fixed parameter tractability (FPT) where the maximum number of leaves is the parameter under consideration. Our results show that simple evolutionary algorithms working with an edge-set encoding are confronted with local optima whose size of the inferior neighborhood grows with the value of an optimal solution. Investigating two common mutation operators, we show that an operator related to spanning tree problems leads to an FPT running time in contrast to a general mutation operator that does not have this property. |
Rights: | © Springer-Verlag Berlin Heidelberg 2010 |
DOI: | 10.1007/978-3-642-15844-5_21 |
Published version: | http://dx.doi.org/10.1007/978-3-642-15844-5_21 |
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.