Please use this identifier to cite or link to this item:
Scopus Web of ScienceĀ® Altmetric
Type: Theses
Title: Diversity optimization and parameterized analysis of heuristic search methods for combinatorial optimization problems
Author: Gao, Wanru
Issue Date: 2016
School/Discipline: School of Computer Science
Abstract: Heuristic search algorithms belong to the most successful approaches for many combinatorial optimization problems which have wide real world applications in various areas. The heuristic algorithms usually provide solutions with acceptable quality in reasonable timeframe which is different from exact algorithms. Fixed-parameter approach provides a way for understanding how and why heuristic methods perform well for prominent combinatorial optimization problems. In this thesis, there are two main topics discussed. Firstly, we integrate the well-known branching approach for the classical combinatorial optimization problem, namely minimum vertex cover problem, to a local search algorithm and compare its performance with the core component of the state-of-the-art algorithm. After that, we investigate how well-performing local search algorithms for small or medium size instances can be scaled up to solve massive input instances. A parallel kernelization technique is proposed which is motivated by the assumption that huge graphs are composed of several easy to solve components while the overall problem is hard to solve. Using evolutionary algorithms to generate a diverse set of solutions where all of them meet certain quality criteria has gained increasing interests in recent years. As the second section, we put forward an evolutionary algorithm which allows us to maximize the diversity over a set of solutions with good quality and then focus on the theoretical analysis of the algorithm to provide understanding of how evolutionary algorithms maximize the diversity of a population and guarantee the quality of all solutions at the same time. Then the idea is extended to evolving hard/easy optimization problem instances with diverse feature values. The feature-based analysis of heuristic search algorithms plays an important role in understanding the behaviour of the algorithm and our results show good classification of the problem instances in terms of hardness based on different combinations of feature values.
Advisor: Neumann, Frank
Wagner, Markus
Dissertation Note: Thesis (Ph.D.) -- University of Adelaide, School of Computer Science, 2016.
Keywords: combinatorial optimization
diversity maximization
evolutionary computation
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:
DOI: 10.4225/55/58c1f2171a1ba
Appears in Collections:Research Theses

Files in This Item:
File Description SizeFormat 
01front.pdf216.63 kBAdobe PDFView/Open
02whole.pdf2.32 MBAdobe PDFView/Open
  Restricted Access
Library staff access only211.36 kBAdobe PDFView/Open
  Restricted Access
Library staff access only2.28 MBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.