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.