Senington, Richard James (2013) Hybrid meta-heuristic frameworks : a functional approach. PhD thesis, University of Leeds.
Abstract
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.
Metadata
Supervisors: | Duke, D. |
---|---|
ISBN: | 978-0-85731-420-8 |
Awarding institution: | University of Leeds |
Academic Units: | The University of Leeds > Faculty of Engineering (Leeds) > School of Computing (Leeds) |
Identification Number/EthosID: | uk.bl.ethos.589235 |
Depositing User: | Repository Administrator |
Date Deposited: | 12 Dec 2013 15:07 |
Last Modified: | 07 Mar 2014 11:48 |
Download
Richard Senington's thesis
Filename: Richard Senington's thesis.pdf
Licence:
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 2.5 License
Export
Statistics
You do not need to contact us to get a copy of this thesis. Please use the 'Download' link(s) above to get a copy.
You can contact us about this thesis. If you need to make a general enquiry, please see the Contact us page.