Keep Learning

Lead Research Organisation: Edinburgh Napier University
Department Name: School of Computing

Abstract

Combinatorial problems are ubiquitous across many sectors in today's world: delivering optimised solutions can lead to considerable economic benefits in many fields such as logistics, packing, design and scheduling (of either people or processes). In a typical scenario, instances (for example, a set of goods to deliver) arrive frequently in a continual stream and a solution needs to be quickly produced. Although there are many well-known approaches to developing optimisation algorithms, most suffer from a problem that is now becoming apparent across the breadth of Artificial Intelligence: systems are limited to performing well on data that is similar to that encountered in their design process, and are unable to adapt when encountering situations outside of their original programming.


For real-world optimisation this is particularly problematic. If optimisers are trained in a one-off process then deployed, the system remains static, despite the fact that optimisation occurs in a dynamic world of changing instance characteristics, changing user-requirements and changes in operating environments that influence solution quality (e.g. breakdowns in a factory or traffic in a city). Such changes may be either gradual, or sudden. In the best case this leads to systems that deliver sub-optimal performance, while at worst, systems that are completely unfit for purpose. Moreover, a system that does not adapt wastes an obvious opportunity to improve its own performance over time as it solves more and more instances.

The targeted breakthrough of this proposal is to develop a dynamic optimisation system that continually adapts its operating mechanism and its algorithms over time to remain fit-for-purpose - a radical switch from the current one-off design and deployment approach to design of optimisers. The system will:

- Go beyond simply being reactive to being proactive in that it will predict the nature of upcoming instances and speculate about potential future scenarios. In response to these predictions, it will autonomously pre-generate and/or reconfigure suitable algorithms, followed by creation of appropriate mappings from instance to solver, in order to pre-prepare for these future scenarios. It will also respond to user requests to generate instances with specific characteristics and solvers to match them, based on the user's in-depth knowledge of their own business and sector.

- Autonomously improve its own behaviour over time, continually updating its algorithms and methods as it learns from its experience of solving more and more instances.

- Support optimisation with respect to multiple user objectives and requirements via its use of a diverse portfolios of algorithms, that range from those which generate acceptable solutions in a very short time to those that have long running time but deliver the highest possible quality.

To succeed we will make novel advances in building proactive, continually self-adapting systems and in optimisation/algorithm-selection, enhanced by integration with the latest tools from machine-learning. Benefits will be realised by any business that attempts to optimise their processes in dynamic environments, in which customer demands vary, business requirements change, and the operating environment is subject to unexpected changes. Relevant application domains include (but are not limited to) workforce scheduling, logistics and infrastructure design

Publications

10 25 50