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
 
Description The award is still active, however we have made progress in two areas: (1) in defining new methods of instance generation that enable better ML models to be trained that are able to select the best way of solving a problem. This will enable models to generalise to new types of problem that arrive in the future that have not been seen before (2) in developing a new test suite that enables new research into drifting optimisation scenarios (no such benchmark previously existed), i.e. scenarios where the characteristics of a problem solved by a company change over time, and therefore the software must first recognise the change, and then adapt to it in an autonomous manner in order to maintain performance levels
Exploitation Route The component parts of the proposed framework (generating new data examples, recognising drift, adapting to drift) can be integrated into optimisation frameworks that deal with dynamically changing data, thereby saving companies money by ensuring the software provides the best possible performance in changing environments
Sectors Digital/Communication/Information Technologies (including Software)

Healthcare

Transport