Published on Thu Jan 09 2014

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

Dogan Corus, Per Kristian Lehre, Frank Neumann, Mojgan Pourhassan

Bi-level optimisation problems have gained increasing interest in the field of combinatorial optimisation in recent years. We examine two NP-hard problems, the generalised minimum spanning tree problem (GMST) and the generalised travelling salesman problem (GTSP) We show that the two

0
0
0
Abstract

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.

Wed Feb 07 2018
Artificial Intelligence
Evolutionary Computation plus Dynamic Programming for the Bi-Objective Travelling Thief Problem
Research proposes a novel indicator-based hybrid evolutionary approach that combines approximate and exact algorithms. The approach is capable to outperform the state-of-the-art results for the single-objective case of the problem.
0
0
0
Wed Apr 06 2016
Neural Networks
Parameterized Analysis of Multi-objective Evolutionary Algorithms and the Weighted Vertex Cover Problem
A rigorous runtime analysis of evolutionary multi-objective optimization has been presented by Kratsch and Neumann (2013) In this paper, we extend the analysis to the weighted vertex cover problem and provide a fixed parameter evolutionary algorithm with respect to OPT, the cost of the the optimal solution.
0
0
0
Wed Feb 13 2019
Neural Networks
Analysis of Baseline Evolutionary Algorithms for the Packing While Travelling Problem
Packing While Travelling (PWT) is also known as the non-linear knapsack problem. PWT is an attempt to analyse the behaviour of Evolutionary Algorithms on non- linear problems from theoretical perspective.
0
0
0
Fri Feb 12 2021
Neural Networks
A bi-level encoding scheme for the clustered shortest-path tree problem in multifactorial optimization
0
0
0
Mon Apr 27 2020
Neural Networks
Evolutionary Multi-Objective Optimization for the Dynamic Knapsack Problem
Evolutionary algorithms are bio-inspired algorithms that can easily adapt to changing environments. In this paper, we study single- and multi-objective evolutionary algorithms for the classical knapsack problem where the capacity of the knapsacks varies over time.
0
0
0
Wed Sep 03 2014
Neural Networks
Performance Analysis on Evolutionary Algorithms for the Minimum Label Spanning Tree Problem
evolutionary algorithms (EAs) are efficient for the minimum label spanning tree (MLST) problem. We show that the (1+1) EA and GSEMO outperform local search algorithms on three instances of the MLST problem.
0
0
0