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

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2010

View graph of relations

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 languageEnglish
Title of host publicationPPSN'10 Proceedings of the 11th international conference on Parallel problem solving from nature
Volume1
Publication date2011
Pages204-213
ISBN (print)978-3-642-15843-8
DOIs
StatePublished

Conference

Conference11th International Conference on Parallel Problem Solving From Nature
Number11
CountryPoland
CityKrakow
Period11/09/1015/09/10
Internet addresshttp://home.agh.edu.pl/~ppsn/
NameLecture Notes in Computer Science
Number6238
CitationsWeb of Science® Times Cited: No match on DOI
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

ID: 5614805