Problems requiring combinatorial optimisation are routinely encountered in research and applied computing. Though polynomial-time algorithms are known for certain problems, for many practical problems, from mundane 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.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:589235 |
| Date | January 2013 |
| Creators | Senington, Richard James |
| Contributors | Duke, D. |
| Publisher | University of Leeds |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | http://etheses.whiterose.ac.uk/4847/ |
Page generated in 0.0025 seconds