Hybrid meta-heuristic frameworks : a functional approach

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 \nthrough to exotic tasks such as sequence alignment in bioinformatics, the only effective approach is to use heuristic methods. In contrast to complete strategies \nthat 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 \nspecific problems, which guide the search down promising avenues. \n \nWork 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 \noften tries to combine concepts from a number of existing strategies to balance the advantages of the originals, known as hybridisation. \n \nThis 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 \nstruggled to enable hybridisation of the two major classes of metaheuristic, point based and population based, while being large and complicated to use. \n \nThis 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 \na common model, let alone one that can accommodate more esoteric optimisation techniques such as ant colony optimisation. At the same time, these implementations \ncannot ignore the fact that the development of these techniques is driven by large-scale problems, and computational efficiency cannot be ignored. Given \nthis background, this Thesis makes three substantial contributions. It decomposes metaheuristic searchmethods into a set of finer-grained concepts and tools that can \nbe 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 \nproblem in bioinformatics.