A Parameterized Complexity Analysis of Bi-level Optimisation with Evolutionary Algorithms
Bi-level optimisation problems have gained increasing interest in the field of combinatorial optimisation in recent years. With this paper, we start the runtime analysis of evolutionary algorithms for bi-level optimisation problems. We examine two NP-hard problems, the generalised minimum spanning tree problem (GMST), and the generalised travelling salesman problem (GTSP) 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) EA working with the spanning nodes representation is not a fixed-parameter evolutionary algorithm for the problem, whereas the global structure representation enables to solve the problem in fixed-parameter time. 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 salesman problem, we analyse the problem with respect to the number of clusters in the problem instance. Our results show that a (1+1) EA working with the global structure representation is a fixed-parameter evolutionary algorithm for the problem.
Code (0)
등록된 구현이 없습니다.
Tasks
Evolutionary AlgorithmsSimilar Papers 제목 키워드 기반
Parameterized Analysis of Multi-objective Evolutionary Algorithms and the Weighted Vertex Cover Problem
A rigorous runtime analysis of evolutionary multi-objective optimization for the classical vertex cover problem in the context of parameterized complexity analysis has been presented by Kratsch and Neumann (2013). In thi…
DiversityEvolutionary AlgorithmsParameterized Complexity Analysis of Randomized Search Heuristics
This chapter compiles a number of results that apply the theory of parameterized algorithmics to the running-time analysis of randomized search heuristics such as evolutionary algorithms. The parameterized approach artic…
Combinatorial OptimizationEvolutionary AlgorithmsAnalysis of Solution Quality of a Multiobjective Optimization-based Evolutionary Algorithm for Knapsack Problem
Multi-objective optimisation is regarded as one of the most promising ways for dealing with constrained optimisation problems in evolutionary optimisation. This paper presents a theoretical investigation of a multi-objec…
Multiobjective OptimizationTheoretical Analysis of Stochastic Search Algorithms
Theoretical analyses of stochastic search algorithms, albeit few, have always existed since these algorithms became popular. Starting in the nineties a systematic approach to analyse the performance of stochastic search …
Evolutionary AlgorithmsLevel-based Analysis of Genetic Algorithms and other Search Processes
Understanding how the time-complexity of evolutionary algorithms (EAs) depend on their parameter settings and characteristics of fitness landscapes is a fundamental problem in evolutionary computation. Most rigorous resu…
Evolutionary Algorithms