Parameterised complexity analysis of evolutionary algorithms for combinatorial optimization problems
Files
Date
2017
Authors
Pourhassan, Mojgan
Editors
Advisors
Neumann, Frank
Wagner, Markus
Wagner, Markus
Journal Title
Journal ISSN
Volume Title
Type:
Theses
Citation
Statement of Responsibility
Conference Name
Abstract
Evolutionary algorithms are general problem solvers that have been successfully used in solving combinatorial optimization problems. However, due to the great amount of randomness in these algorithms, theoretical understanding of them is quite challenging. In this thesis we analyse the parameterized complexity of evolutionary algorithms on combinatorial optimization problems. Studying the parameterized complexity of these algorithms can help us understand how different parameters of problems influence the runtime behaviour of the algorithm and consequently lead us in finding better performing algorithms. We focus on two NP-hard combinatorial optimization problems; the generalized travelling salesman problem (GTSP) and the vertex cover problem (VCP). For solving the GTSP, two hierarchical approaches with different neighbourhood structures have been proposed in the literature. In this thesis, local search algorithms and simple evolutionary algorithms based on these approaches are investigated from a theoretical perspective and complementary abilities of the two approaches are pointed out by presenting instances where they mutually outperform each other. After investigating the runtime behaviour of the mentioned randomised algorithms on GTSP, we turn our attention to the VCP. Evolutionary multi-objective optimization for the classical vertex cover problem has been previously analysed in the context of parameterized complexity analysis. We extend the analysis to the weighted version of the problem. We also examine a dynamic version of the classical problem and analyse evolutionary algorithms with respect to their ability to maintain a 2-approximation. Inspired by the concept of duality, an edge-based evolutionary algorithm for solving the VCP has been introduced in the literature. Here we show that this edge-based EA is able to maintain a 2-approximation solution in the dynamic setting. Moreover, using the dual form of the problem, we extend the edge-based approach to the weighted vertex cover problem.
School/Discipline
School of Computer Science
Dissertation Note
Thesis (Ph.D.) -- University of Adelaide, School of Computer Science, 2017.
Provenance
This electronic version is made publicly available by the University of Adelaide in accordance with its open access policy for student theses. Copyright in this thesis remains with the author. This thesis may incorporate third party material which has been used by the author pursuant to Fair Dealing exceptions. If you are the owner of any included third party copyright material you wish to be removed from this electronic version, please complete the take down form located at: http://www.adelaide.edu.au/legals