The CHORDS (Computational Heuristics, Operational Research and Decision Support) research group was formed in December 2011. Its core research mission is to explore and develop computational search methodologies and models that emerge from studying the complexity and uncertainty of real world scheduling, optimisation and decision support problems. Its research agenda lies at the inter-disciplinary interface of Operational Research and Computer Science and it draws upon core application areas in search based software engineering, timetabling, manufacturing, healthcare, transportation and others.
CHORDS members have strong connections with leading UK universities (including UCL, York, Birmingham, and Nottingham) and industrial links with internationally-renowned partners (including IBM, Motorola, Microsoft, Honda, BT Labs and GCHQ).
More information can be found on the CHORDS website.
CHORDS encompasses a broad range of research interests, centred around Metaheuristic Optimization and Machine Learning.
Software maintenance dominates development cost. The Gen-O-Fix framework developed at Stirling allows a system to be continually improved (e.g. make better predictions; pass more regression tests; reduce power consumption) while it runs.
Hyper-heuristics comprise a set of approaches that are motivated (at least in part) by the goal of automating the design of heuristic methods to solve computational search problems. An underlying strategic research challenge is to develop more generally applicable search methodologies. The term hyper-heuristic is relatively new; it was first used in 2000 to describe heuristics to choose heuristics in the context of combinatorial optimisation. However, the idea of automating the design of heuristics is not new; it can be traced back to the 1960s.
The fitness landscape metaphor appears most commonly when describing the dynamics of evolutionary algorithms, and its origins are attributed to the population geneticist Sewall Wright (1932). However, the metaphor can be used for computational search in general; the search space can be regarded as a spacial structure where each point (candidate solution) has a height (objective function value) forming a landscape surface. In this scenario, the search process would be an adaptive-walk over a landscape that can range from having many peaks of high fitness boarding deep cliffs to valleys of low fitness; to being smooth, with low hills and gentle valleys.
Search and optimization problems are everywhere, and search algorithms are getting increasingly powerful. However, they are also getting increasingly complex, and only autonomous self-managed systems that provide high-level abstractions can turn search algorithms into widely used methodologies. Such systems should be able to configure themselves on the fly, automatically adapting to the changing problem conditions, based on general goals provided by their users.
Recent years have seen an increase in the use of genetic programming as a hyper-heuristic to (semi-) automate the design of heuristic algorithms. Rather than employing domain experts to hand-craft single algorithms, they are asked instead to design a framework which defines a family of algorithms, a computational search methodology such as genetic programming then takes charge of the mundane task of selecting a particular algorithm for the problem at hand. This approach has the consequence that new algorithms can be designed on-the-fly as new problems present themselves, rather than returning to the drawing board and starting the manual design process all over again.
Machine learning is the discipline of getting a machine to learn, that is improving at a given task. However, a limitation of this approach is that it does not alter the way it learns, which may or may not be suitable for the current task. One approach to avoid this shortfall is to adopt a meta-learning method, allowing the system to change the way it learns about a problem. In general this can be achieved with a two level system containing a base-level and a meta-level. There are many variations of this including multi-task learning, learning to learn and hyper-heuristics.
The gate/stand allocation problem consists of assigning a given set of flights to a set of suitable gates while making sure that certain constraints are met. The ground movement problem is the task of allocating routes and timings for aircraft to take as they proceed along the taxiways between the runways and the gates/stands, with the aim of finding a schedule that reduces delays, reduces fuel-burn associated with taxiing, and is resilient to last-minute changes. Both are challenging real-world problems and the CHORDS team are developing solutions that better reflect the reality, in collaboration with our partner airports, Manchester and Zurich. Although gate allocation has been extensively addressed in the literature, the main drawback of the current optimization models is that they do not take into account the real multi-criteria nature of this problem, and hence are inapplicable in the airport industry. For ground movement, existing work ignores or simplifies the uncertainty inherent to taxi speeds or arrival and departure times. Our work aims to address these deficiencies through the application of intelligent search approaches that provide high-quality solutions with reasonable computing effort.
This EPSRC-funded Platform project enables the CHORDS to conduct (and continue) a programme of transformative and innovative research that is not only high risk and high return, but also has a clear multi-disciplinary and industrial focus. We address a broad range of scientifically challenging problems, many of which are drawn from the real world where the complexities of the problem have not been abstracted away.
The proposed programme of research will build integrated computational models of four key airport operations: Take-off scheduling, Landing Scheduling, Gate Assignment and Baggage flow. The project will explore how to build computational models that represent the integration of these problems and it will explore how to develop effective multi-objective search methodologies which will employ the models.
The EPSRC funded £6.8M DAASE (Dynamic Adaptive Automated Software Engineering) project automates large parts of the software development process using computational search. Requirements engineering, project planning and testing would be unified into a single automated activity. DAASE places computational search at the heart of the processes and products it creates and embeds adaptivity into both. DAASE will also create an array of new processes, methods, techniques and tools for a new kind of software engineering.