Problems requiring combinatorial optimisation are routinely encountered in research and applied computing. Though polynomial-time algorithms are known for certain problems, formany practical problems, frommundane tasks in scheduling
through to exotic tasks such as sequence alignment in bioinformatics, the only effective approach is to use heuristic methods. In contrast to complete strategies
that locate globally optimal solutions through (in the worst case) the enumeration of all solutions to a problem, heuristics are based upon rules of thumb about
specific problems, which guide the search down promising avenues.
Work in the field of Operations Research has gone further, developing generic metaheuristics, abstract templates which may be adapted to tackle many different problems. Metaheuristic researchers have created a variety of algorithms, each with their own strengths and weaknesses, and development of metaheuristics now
often tries to combine concepts from a number of existing strategies to balance the advantages of the originals, known as hybridisation.
This interest in hybridisation has led to the creation of a number of frameworks in imperative languages to assist programmers in the rapid creation and experimentation upon the algorithms. However these existing frameworks have
struggled to enable hybridisation of the two major classes of metaheuristic, point based and population based, while being large and complicated to use.
This Thesis investigates a functional approach to hybridisation. Despite superficial analogies between hybridisation and function composition, there are substantial challenges: unlike global search methods that can be explained elegantly in terms of graph traversal, prior work on local search has struggled to articulate
a common model, let alone one that can accommodate more esoteric optimisation techniques such as ant colony optimisation. At the same time, these implementations
cannot ignore the fact that the development of these techniques is driven by large-scale problems, and computational efficiency cannot be ignored. Given
this background, this Thesis makes three substantial contributions. It decomposes metaheuristic searchmethods into a set of finer-grained concepts and tools that can
be reassembled to describe both standard search strategies and more specialised approaches. It resolves problems found in implementing these abstractions in the widely used language Haskell, developing a novel approach based on dataflow networks. The value of functional abstraction in the practice of metaheuristic development and tuning is demonstrated through case studies, including a substantial
problem in bioinformatics.
Altmetric
Altmetric