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 proceedingArticle in proceedingsResearchpeer-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 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
    Publication statusPublished - 2011
    Event11th International Conference on Parallel Problem Solving From Nature - Krakow, Poland
    Duration: 11 Sep 201015 Sep 2010
    Conference number: 11
    http://home.agh.edu.pl/~ppsn/

    Conference

    Conference11th International Conference on Parallel Problem Solving From Nature
    Number11
    CountryPoland
    CityKrakow
    Period11/09/201015/09/2010
    Internet address
    SeriesLecture Notes in Computer Science
    Number6238

    Fingerprint Dive into the research topics of 'Fixed Parameter Evolutionary Algorithms and Maximum Leaf Spanning Trees: A Matter of Mutations'. Together they form a unique fingerprint.

    Cite this