PhD

Index

Thesis Abstract

For solving combinatorial optimization problems, exact methods accurately exploit the structure of the problem but are tractable only up to a certain size; approximation or heuristic methods are tractable for very large problems but cannot always deliver a desired solution quality.  These can be combined in hybrid systems in a number of possible ways.  For the Ant Colony Optimization (ACO) metaheuristic that we use in this  thesis, these hybrid techniques have included combining ACO with approximation algorithms like Local Search or with exact algorithms such as tree search.  A question that arises is: Are there other kinds of ``exact knowledge" that can be exploited on large-scale problems by heuristic methods?  Within this thesis we present a framework that allows the exploitation of existing techniques and resources to integrate knowledge of problem structure into an ACO algorithm called Ant Colony System using the knowledge of problem structure as a kind of `template' to guide ACS to better solutions.

In this thesis we propose using the technique of kernelization from the field of parameterized complexity as the source of knowledge of problem structure.  Kernelization is a technique for reducing an optimization problem to its ``problem kernel" in polynomial time in a way that preserves the original problem's optimal solution; the kernelization rules, in a sense, embody local knowledge of the problem structure.  Kernelization has been applied to an extensive range of combinatorial optimization problems, forming a ready-made library of problem structure.  Previously kernelization has been used as a pre-processing step for other approximate or exact methods, although some algorithms have used it more extensively and integrated it into the bounded search trees algorithm.  Within this thesis we investigate ways to combine kernelization with ACS using it as a kind of template for ant organization: we propose three algorithms integrating kernelization into the pheromone system, and three others integrating kernelization into the ants' decision process.

Kernelization has been most extensively applied to the Minimum Vertex Cover Problem (MVCP), the problem of finding a subset of nodes within a graph such that every edge is covered by at least one node from this subset.  Hence we begin by investigating the usefulness of these six algorithms on this problem.  We show that all six algorithms outperform ACS on the MVCP.  We also investigate how these algorithms compare with several other techniques and find that in all cases but one they perform significantly better.

This thesis then investigates why kernelization improves ACS the way it does for each kernelization algorithm.  We find that for all algorithms, the kernelization rules we use solve structures efficiently, exactly, and deterministically which ACS could only solve heuristically.  Of particular interest is that our kernelization algorithms allow little improvement on graphs considered ``easy"; these are graphs which kernelization is able to shrink the most.  By contrast, hard graphs which kernelization is not able to shrink much at all demonstrate significant improvement.  Graphs are defined as either easy or hard depending on the relationship between their edge-to-node ratio and the Euler constant $e$ which has been found to be the transition point between easy and hard graphs for the MVCP.  We also investigate other potential kernelization rules and find that not all rules are useful for integration with ACS.

In order to illustrate the general applicability of the framework in this thesis, we also look at the Minimum Dominating Set Problem (MDSP), the problem of finding a smallest subset of nodes within a graph such that every node not in the subset is neighboring at least one node from this subset, a problem that is computationally more difficult than the MVCP.  We first develop an ACS algorithm for the MDSP.  We then devise analogous algorithms using kernelization rules for the MDSP which demonstrate an improvement over ACS, in the process showing the need to have efficient kernelization rules.  We again compare these against other algorithms; for the MDSP these kernelization algorithms outperform all others in the comparison set, demonstrating the easy and useful generalizability of the approach.

Thesis Acknowledgments

Doctoral dissertations are commonly considered an ambitious and difficult undertaking, and this has certainly been true in my experience.  However, the degree to which doing a PhD influences and affects one's entire lifestyle was a mystery to me until only recently.  It has only come into sharp focus now, as I write these acknowledgments and realize how much my PhD is a result of the support of my family and friends as it is of my professional colleagues.  Here I would like to acknowledge and thank all my friends, family, and colleagues who have helped me along the road to the completion of this doctorate.

Firstly I would like to thank Macquarie University, the Department of Computing and Division of ICS, and the CSIRO for their providing the financial means and resources that have allowed me to do this research.  This includes Bernard Mans from Macquarie University and Yusuf Pisan at the University of Technology, Sydney, for their participation in my supervision and similarly Geoff James and Mikhail Prokopenko at the CSIRO.  Thanks particularly go to Mark Dras and Bernard Mans for proof reading this dissertation.

Next I would like to thank Marco Dorigo and the IRIDIA lab in Brussels, Belgium, for allowing me to visit them and use their resources for a month in September-October 2005.  Thanks to all the members of the optimization group at IRIDIA for the discussions and friendship they provided, particularly Max Manfrin and his helpful critique of my experimental design.  On this topic he provided many useful articles for further study.

Lastly I would like to thank all those who have taken care of me over the course of my tenure.  Thanks to my flatmates Matt Roberts, Karl Grice, Mike Baines, and Kevin Woo for being more than just a flatmate but also a friend, and for putting up with my during times of difficulty.  Thanks to my Christian family at Mars Hill Anglican Church and later St Pauls Anglican Church Carlingford, and at the Christian Union at Macquarie University for their support.  The members of the Bible studies I have been involved in have been a very strong support; also Michael Kellahan, my pastor for the last four years, and to Scott Warner and Tim Bradford, workers at the Christian Union and friends.  I would also like to thank my high school friends who are particularly close to me and have had to put up with me through this whole adventure; my sister, Rachelle Gilmour, also.

However, although there are many people who have helped me in this PhD, I would not only like to thank more than anyone else, but also dedicate this PhD to five different people.  Thanks so much to my grandparents, John and Joyce Knight, who have always been my surrogate parents and have sought to take care of me in every way they could imagine.  Thanks so much to my Dad, David Gilmour, who has loved me and taken care of me all my life and has encouraged me continually in the course of my PhD, helping me to keep focused not only on the end of my PhD but also on what is important in life.  Thanks so much to Mark Dras, my friend, supervisor, and constant support throughout my PhD.  Without your help, I would never have finished.  Lastly, thanks so much to the triune God --- Father, Son, and Holy Spirit --- in whom all things exist and in whom all things hold together, including the very systems I have studied in this thesis.