Prof. Emma Hart gives seminar at the University of Nottingham Computer Science Visiting Speaker Series

03/02/2014 29/1/14

Prof. Emma Hart was invited to speak at the University of Nottingham Computer Science Visiting Speaker Series where she spoke about some of the work being done on the EPSRC -funded ROLL project


Title:
A lifelong Learning Method for Solving Combinatorial Optimisation Problems

Abstract

The previous two decades have seen significant advances in meta-heuristic and hyper-heuristic optimisation techniques that are able to quickly find optimal or near-optimal solutions to problem instances in many combinatorial optimisation domains. Despite many successful applications of both these approaches, they typically operate in the same manner: an algorithm is tuned to work well on a (possibly large) set of representative problems and each time a new problem instance needs to be solved, the algorithm conducts a search of either the solution space or the heuristic space to locate good solutions. Whilst this often leads to acceptable solutions, such approaches have a number of weaknesses in that if the nature of the problems to be solved changes over time, then the algorithm needs to be periodically re-tuned. Furthermore, such approaches are likely to be inefficient, failing to exploit previously learned knowledge in the search for a solution.

In contrast, in the field of machine-learning, several contemporary learning systems employ methods that use prior knowledge when learning behaviours in new, but similar tasks, leading to a recent proposal from Silver et al. (2013) that it is now appropriate for the AI community to move beyond learning algorithms to more seriously consider the nature of systems that are capable of learning over a life- time. They suggest that algorithms should be capable of learning a variety of tasks over an extended period of time such that the knowledge of the tasks is retained and can be used to improve learning in the future. They name such systems lifelong machine learning, or LML systems.

I will describe a novel Hyper-heuristic LML system which continuously learns over time to solve combinatorial optimisation problems. The system continuously generates new heuristics and samples problems from its
environment; representative problems and heuristics are incorporated into a self-sustaining network of interacting entities inspired by methods in Artificial Immune Systems.The network is plastic in both its structure and content leading to the following properties: it exploits existing knowledge captured in the network to rapidly produce solutions; it can adapt to new problems with widely differing characteristics; it is capable of generalising over the problem space. The system is tested on a large corpus of approximately 5000 1D-bin packing problems as well as on a number of job-shop scheduling problems with excellent results in terms of
effectiveness and efficiency.

 
[Read More]

Associated people

Emma Hart
Director of CEC
e.hart@napier.ac.uk
+44 131 455 2783
Real World Optimisation with Life-Long Learning (ROLL)
This project aims to improve the current state of the art in developing optimisation tools which are relevant and acceptable to industry. This will be achieved by addressing industrial current concerns regarding the ability of academic optimisation techniques to deal effectively with highly...
Bio-inspired Computing
The Bio-Inspired Algorithms group within the Centre for Algorithms, Visualisation and Evolving Systems is a large and thriving group with interests in nature-inspired computing that include Evolutionary Computing, Hyper-Heuristics, Artificial Immune Systems and Swarm Intelligence.

Resources