SEQuence-Analysis Based Hyperheuristics (SEQAH) for Real-World Optimisation Problems

Selective hyperheuristics are a set of optimisation techniques that effectively optimise the search algorithm during an optimisation run by selecting combinations of lower level heuristic operations (e.g. mutation, crossover & replication). They operate at the level above metaheuristics (e.g. evolutionary algorithms) and are thus able to react to changes in the search space by modifying the heuristics that are applied to the search problem. Traditional selective hyperheuristics consider single heuristics and heuristic pair performance when determining the heuristic to select next. This project will develop new methods known as a sequence analysis based hyperheuristics (SEQAH) and will investigate the use of sequence analysis techniques, taken from other computational domains such as bioinformatics and natural-language processing, to determine heuristic selection. SEQAH methods will record the search process as a sequence of pairs of heuristic application and performance, and will process this information to inform the selection of the next heuristic to apply in the optimisation. This will allow the technique to automatically select the best heuristics to apply for a given problem - effectively tuning the algorithm to new optimisation problem types, regardless of the underlying application area. By selecting from a set of heuristics, the SEQAH techniques can combine ordinary heuristic operations (e.g. mutation and crossover) with more problem-specific heuristics such as human-designed 'rules-of-thumb' into one coherent algorithm that is able to generate near-optimal solutions in less computational time.

The developed techniques will be tested on problems from the literature and a suite of real-world problems in water distribution optimisation including the design, rehabilitation and operation of large-scale water systems. The optimisation of these systems has the potential to offer improved services in terms of reliability and water quality and to reduce the future cost and environmental impact of providing clean, safe drinking water to homes across the country. The SEQAH technique also has the potential to extend beyond the water industry and should be applicable to any number of optimisation problems in many application areas due to its ability to adapt to new problem spaces online.

Water Distribution Impact
The initial impact from this project will be wide-ranging with beneficiaries including our partners, Mouchel Ltd., their clients (large UK water companies) and ultimately the consumers that require the provision of clean, safe drinking water with minimal financial and environmental cost. The effective optimisation of the operation and design of water distribution systems in the UK is having and will have a profound effect on the socio-economic wellbeing of the UK. With an ageing infrastructure, increasing demand and regulation and the pressure exerted by climate change UK water companies are required to optimise their operations as effectively as possible. This will yield reduced bills for customers, will go some way to preserving an increasingly scarce resource and promises to reduce the environmental impact (including carbon emissions) of water supply.

Wider Impact
The wider impact of the research will be achieved through the expansion of application fields to which the hyperheuristics will be applied. Many companies that currently do not employ optimisation as they do not have the expertise to tune the algorithms will be able to apply this self-tuning technique which can incorporate problem-specific expertise in the form of heuristics. The exploration of the relationship between problem type and optimisation algorithm will provide key information as to the extent to which algorithms must be modified and tuned from one problem type to another. The results from the investigation in water distribution problems will demonstrate the variation in heuristics and their sequencing required to generate good results for a problem type in reasonable computational time. However, towards the end of the project, we fully intend to develop and test the techniques on a wider number of application areas and industry sectors using the contacts from our industrial partner.

Background
Optimisation is a key component in delivering efficiency and cost savings to businesses in many sectors and evolutionary optimisation has been shown to provide excellent results within reasonable timeframes in a wide variety of sectors. The investigators for this project have been involved in high-impact research involving industry for a number of years. Dr Keedwell has developed evolutionary algorithms for the optimisation of city-scale water distribution systems [1] and work is ongoing under the auspices of a CASE studentship to improve discolouration risk modelling in UK water companies [2]. Prof. Savic has had significant involvement with industry in the UK and further afield through a large number of EPSRC, UKWIR & FRMRC funded projects including EP/H015736/1 (start May 2010) which names some 14 industrial partners and includes both Prof. Savic (PI) and Dr Keedwell (Co-I) as investigators. This background demonstrates that the investigators have a history of working with business and achieving impact through the use of innovative computing technology and their application to problems in the water industry.

[1] Randall-Smith, M, Rogers C, Keedwell E, Diduch R, Kapelan Z, (2006) "Optimized Design of the City of Ottawa Water Network: a Genetic Algorithm Case Study" 8th Annual Water Distribution Systems Analysis Symposium pp1-20
[2] McClymont, K., Keedwell,E. Savic, D. Randall-Smith, M. (2011): "A Hyper-heuristic Approach to Water Distribution Network Design", in the Proceedings of Computing and Control in the Water Industry 2011, University of Exeter, UK