A Parameterised Complexity Analysis of Bi-level Optimisation with Evolutionary Algorithms

Simple item page
dc.contributor.authorCorus, D.
dc.contributor.authorLehre, P.
dc.contributor.authorNeumann, F.
dc.contributor.authorPourhassan, M.
dc.date.issued2016
dc.description.abstractBi-level optimisation problems have gained increasing interest in the field of combinatorial optimisation in recent years. In this paper, we analyse the runtime of some evolutionary algorithms for bi-level optimisation problems. We examine two NP-hard problems, the generalised minimum spanning tree problem and the generalised travelling salesperson problem in the context of parameterised complexity. For the generalised minimum spanning tree problem, we analyse the two approaches presented by Hu and Raidl ( 2012 ) with respect to the number of clusters that distinguish each other by the chosen representation of possible solutions. Our results show that a (1+1) evolutionary algorithm working with the spanning nodes representation is not a fixed-parameter evolutionary algorithm for the problem, whereas the problem can be solved in fixed-parameter time with the global structure representation. We present hard instances for each approach and show that the two approaches are highly complementary by proving that they solve each other's hard instances very efficiently. For the generalised travelling salesperson problem, we analyse the problem with respect to the number of clusters in the problem instance. Our results show that a (1+1) evolutionary algorithm working with the global structure representation is a fixed-parameter evolutionary algorithm for the problem.
dc.description.statementofresponsibilityDogan Corus, Per Kristian Lehre, Frank Neumann, Mojgan Pourhassan
dc.identifier.citationEvolutionary Computation, 2016; 24(1):183-203
dc.identifier.doi10.1162/EVCO_a_00147
dc.identifier.issn1063-6560
dc.identifier.issn1530-9304
dc.identifier.orcidNeumann, F. [0000-0002-2721-3618]
dc.identifier.urihttp://hdl.handle.net/2440/99626
dc.language.isoen
dc.publisherMIT Press Journals
dc.relation.granthttp://purl.org/au-research/grants/arc/DP130104395
dc.relation.granthttp://purl.org/au-research/grants/arc/DP140103400
dc.rights© 2016 Massachusetts Institute of Technology
dc.source.urihttps://doi.org/10.1162/evco_a_00147
dc.subjectBi-level optimisation
dc.subjectevolutionary algorithms
dc.subjectcombinatorial optimisation
dc.titleA Parameterised Complexity Analysis of Bi-level Optimisation with Evolutionary Algorithms
dc.typeJournal article
pubs.publication-statusPublished

Files

Collections

Computer Science publications