Heuristic Understanding - Overview

Last Updated on Thursday, 01 July 2010 11:10

For information about this research cluster please contact Andrew J. Parkes.

The last forty years have seen a considerable research effort in the design of heuristic methods to underpin decision support system development. However, our theoretical understanding of which methods work well in which situations is close to non-existent. The area has been characterised by the “trial and error” development of algorithms with little understanding of the corresponding search space landscape. The landscape is linked to an algorithm’s ability to solve a problem but current research in this area ignores this observation. We aim to undertake a sustained effort in the mathematical analysis of fitness landscapes with the goal of better informing the design of heuristic algorithms.

Similar issues arise in the modelling, analysis and optimisation of complex stochastic systems, which are central to a wide range of applications in computer and communication networks and in manufacturing and service systems. However, stochastic (dynamic) optimisation in the context of such systems is a major technical challenge. A range of heuristic approaches have emerged (including heavy traffic, approximate dynamic programming, polyhedral methods and index policies) which have proved effective in specific contexts. However, there is as yet little underlying theory to offer deeper general insights concerning the differential effectiveness of alternative approaches.