Next Generation Decision Support: Automating the Heuristic Design Process

Lead Research Organisation: University of Nottingham
Department Name: School of Computer Science

Abstract

The current state of the art in decision support and search methodologies tends to focus on bespoke problem specific systems. Indeed, there are many examples of powerful and innovative search methodologies which have been tailored for specific applications and which underpin highly effective decision support systems. Over the last 20 years or so, there has been significant scientific progress in building search methodologies and in tailoring those methodologies (usually through hybridisation with problem specific methods and information) for a very wide range of application areas. Such methodologies can be extremely effective in the hands of an expert but they require specialist human knowledge to be applied effectively in complex real world problem solving environments. The goal of developing automated systems to replace the human expert in this role is only just beginning to be seriously addressed by the scientific community. The challenge of developing systems to intelligently select, evolve and develop search methods is an extremely ambitious and demanding research goal. The level of adventure should not be underestimated. The goal of exploring the boundaries between what is possible and what is not (with respect to the automation of the heuristic design process) represents one of the most important current research challenges to face the search and decision support community. The main aim of this major and far reaching programme of research is to address this challenge by investigating a wide range of promising and adventurous research directions in an integrated and co-ordinated manner. The successful development of automated systems to generate heuristic methods would underpin the next generation of search/optimisation systems that would be able to operate at a fundamentally more general level than current understanding can support. The aim is to develop systems which can operate upon a wider range of problems and problem instances than is possible with today's technology by automatically tailoring heuristics to particular problems and problem instances. Today, this process can only be effectively carried out by human experts.Of course, we know (from the No Free Lunch theorem and related work) that it will not be possible to build a completely general search method. However, we also know (from work carried out by ourselves and others) that it is possible to generate methods that are more general than the current state of the art. The question of how general we can make search systems is very much an open question and it is one that we will explore in this research programme. The emphasis will not follow conventional current thinking by concentrating on the development of systems to solve particular search/optimisation problems. Instead this major scientific undertaking will investigate the possibility of developing adaptive systems which can react to the conditions and the environment of the particular decision support problem in hand. The potential benefits of success in such a radical undertaking are enormous and permeate not only the disciplines of Artificial Intelligence and Operational Research but also the various disciplines that draw on and contribute to them. These include Computer Science, Mathematics, Business, Engineering, Computational Chemistry, Medicine, Architecture (space planning), Bioinformatics, Manufacturing and all areas of Management. The research will also impact upon automated heuristic selection and design across many diverse applications such as scheduling, timetabling, cutting/packing, protein folding, catalyst optimisation, medical decision making and others. This research initiative will enable us to explore risky and unconventional ideas across a range of disciplines and research council remits in a way that is not possible with standard grants and it will allow us to flexibly redirect our efforts across application areas as well as disciplines to explore ideas as they emerge.

Publications

10 25 50
publication icon
A.Liefooghe (2008) Springer Lecture Notes in Computer Science Volume 4972 in Metaheuristics for the Bi-objective Ring Star Problem

publication icon
Brucker P (2012) A branch and bound algorithm for the cyclic job-shop problem with transportation in Computers & Operations Research

publication icon
Burke E (2017) Progress control in iterated local search for nurse rostering in Journal of the Operational Research Society

publication icon
Burke E (2017) The late acceptance Hill-Climbing heuristic in European Journal of Operational Research

publication icon
Burke E (2012) Grammatical Evolution of Local Search Heuristics in IEEE Transactions on Evolutionary Computation

publication icon
Burke E (2011) A squeaky wheel optimisation methodology for two-dimensional strip packing in Computers & Operations Research

publication icon
Burke E (2009) A Pareto-based search methodology for multi-objective nurse scheduling in Annals of Operations Research

 
Description Heuristic search methods have been successful in solving difficult real-world optimisation problems. Diverse methodologies have been proposed in Computer Science, Artificial Intelligence, and Operational Research, ranging from bio-inspired approaches to the randomisation of complete methods. However, successful heuristics need to be crafted anew for each new problem, or even just for a new instance of the same problem. The goal of this project was to reduce the role of the human expert in designing effective search algorithms. By using machine learning or meta-level search, we have proposed methodologies that can adapt to different environments without a need to manually customise the search for each particular problem domain.

In addressing this challenge, we have identified two main lines of research: heuristic selection, and heuristic generation. In heuristic selection, the idea is to automatically combine pre-defined heuristics or neighbourhood structures to solve the problem at hand from a fixed set, whereas heuristic generation aims to automatically create new heuristics (or heuristic components). An example of heuristic generation is the evolution of flexible packing heuristics that can generalise from one-dimensional to three-dimensional problems by using genetic programming.
Exploitation Route The potential benefits from undertaking this far reaching scientific programme are enormous. Obviously the main deliverable of this challenging and demanding research initiative will be the novel reusable technologies that will underpin future research into automated decision support and heuristic search strategies.
The main beneficiaries are as follows:
1) The International Scientific Research Community: This research lies at the multi-disciplinary interface of Operational Research (OR) and Artificial Intelligence (AI) and impacts upon many other disciplines and upon a broad range of decision support problem domains. The primary aim of this exciting initiative will facilitate the creation of systems which are fundamentally more applicable across a wider range of problems than is possible today. These advances will be of interest not only to the OR and AI communities, but also to the wider scientific communities that carry out fundamental research in these areas, including those in Computer Science, Mathematics and Engineering, and those disciplines which exploit such technologies such as Business, Computational Chemistry, Medicine, Bioinformatics to name but a few. The enormous impact that this initiative will have on all of the disciplines within the international decision support community is impossible to quantify. This programme has the potential to change the way in which decision support research is undertaken and the way in which it is implemented and exploited.
2) The User Community: A key goal of this research initiative is to underpin decision support and search technologies in order to enable systems that utilise these technologies to address a far wider range of application areas than is possible today.
Sectors Digital/Communication/Information Technologies (including Software),Healthcare,Manufacturing, including Industrial Biotechology,Transport,Other

 
Description DAASE: Dynamic Adaptive Automated Software Engineering
Amount £6,834,903 (GBP)
Funding ID EP/J017515/1 
Organisation Engineering and Physical Sciences Research Council (EPSRC) 
Sector Academic/University
Country United Kingdom
Start 06/2012 
End 11/2018
 
Description The LANCS (Lancaster, Nottingham, Cardiff and Southampton) Initiative in Foundational Operational Research: Building Theory for Practice
Amount £1,914,106 (GBP)
Funding ID EP/F033214/1 
Organisation Engineering and Physical Sciences Research Council (EPSRC) 
Sector Academic/University
Country United Kingdom
Start 09/2008 
End 05/2014