Fixed Parameter Evolutionary Algorithms and Maximum Leaf Spanning Trees: A Matter of Mutations

Stefan Kratsch; Per Kristian Lehre; Frank Neumann; Pietro Simone Oliveto

doi:10.1007/978-3-642-15844-5_21

Fixed Parameter Evolutionary Algorithms and Maximum Leaf Spanning Trees: A Matter of Mutations

Stefan Kratsch, Per Kristian Lehre, Frank Neumann, Pietro Simone Oliveto

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

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.

Original language	English
Title of host publication	PPSN'10 Proceedings of the 11th international conference on Parallel problem solving from nature
Volume	1
Publication date	2011
Pages	204-213
ISBN (Print)	978-3-642-15843-8
DOIs	https://doi.org/10.1007/978-3-642-15844-5_21
Publication status	Published - 2011
Event	11th International Conference on Parallel Problem Solving From Nature - Krakow, Poland Duration: 11 Sept 2010 → 15 Sept 2010 Conference number: 11 http://home.agh.edu.pl/~ppsn/

Conference

Conference	11th International Conference on Parallel Problem Solving From Nature
Number	11
Country/Territory	Poland
City	Krakow
Period	11/09/2010 → 15/09/2010
Internet address	http://home.agh.edu.pl/~ppsn/

Series	Lecture Notes in Computer Science
Number	6238

Access to Document

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

OpenUrl availability

Full text

Cite this

@inproceedings{3d54a00190f74b28878574fdc4496181,

title = "Fixed Parameter Evolutionary Algorithms and Maximum Leaf Spanning Trees: A Matter of Mutations",

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.",

author = "Stefan Kratsch and Lehre, {Per Kristian} and Frank Neumann and Oliveto, {Pietro Simone}",

year = "2011",

doi = "10.1007/978-3-642-15844-5_21",

language = "English",

isbn = "978-3-642-15843-8",

volume = "1",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

number = "6238",

pages = "204--213",

booktitle = "PPSN'10 Proceedings of the 11th international conference on Parallel problem solving from nature",

note = "11th International Conference on Parallel Problem Solving From Nature, PPSN 2010 ; Conference date: 11-09-2010 Through 15-09-2010",

url = "http://home.agh.edu.pl/~ppsn/",

}

Kratsch, S, Lehre, PK, Neumann, F & Oliveto, PS 2011, Fixed Parameter Evolutionary Algorithms and Maximum Leaf Spanning Trees: A Matter of Mutations. in PPSN'10 Proceedings of the 11th international conference on Parallel problem solving from nature. vol. 1, Lecture Notes in Computer Science, no. 6238, pp. 204-213, 11th International Conference on Parallel Problem Solving From Nature, Krakow, Poland, 11/09/2010. https://doi.org/10.1007/978-3-642-15844-5_21

Fixed Parameter Evolutionary Algorithms and Maximum Leaf Spanning Trees: A Matter of Mutations. / Kratsch, Stefan; Lehre, Per Kristian; Neumann, Frank et al.
PPSN'10 Proceedings of the 11th international conference on Parallel problem solving from nature. Vol. 1 2011. p. 204-213 (Lecture Notes in Computer Science; No. 6238).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Fixed Parameter Evolutionary Algorithms and Maximum Leaf Spanning Trees: A Matter of Mutations

AU - Kratsch, Stefan

AU - Lehre, Per Kristian

AU - Neumann, Frank

AU - Oliveto, Pietro Simone

N1 - Conference code: 11

PY - 2011

Y1 - 2011

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

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

U2 - 10.1007/978-3-642-15844-5_21

DO - 10.1007/978-3-642-15844-5_21

M3 - Article in proceedings

SN - 978-3-642-15843-8

VL - 1

T3 - Lecture Notes in Computer Science

SP - 204

EP - 213

BT - PPSN'10 Proceedings of the 11th international conference on Parallel problem solving from nature

T2 - 11th International Conference on Parallel Problem Solving From Nature

Y2 - 11 September 2010 through 15 September 2010

ER -

Fixed Parameter Evolutionary Algorithms and Maximum Leaf Spanning Trees: A Matter of Mutations

Abstract

Conference

Access to Document

OpenUrl availability

Fingerprint

Cite this