Speaker: Professor Emma Hart, Director of the Centre for Emergent Computing at Edinburgh Napier University.
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.
Professor Emma Hart is the Director of the Centre for Emergent Computing at Edinburgh Napier University. She gained a 1st Class Honours Degree in Chemistry from the University of Oxford, followed by an MSc in Artificial Intelligence from the University of Edinburgh. Her PhD, also from the University of Edinburgh, explored the use of immunology as an inspiration for computing, examining a range of techniques applied to optimisation and data classification problems.
She moved to Edinburgh Napier University in 2000 as a lecturer, and was promoted to a Chair in 2008 in Natural Computation. She continues to research in the area of developing novel bio-inspired techniques for solving a range of real-world optimisation and classification problems, as well as exploring the fundamental properties of immune-inspired computing through modelling and simulation.
The talk is hosted by the Automated Scheduling, Optimisation and Planning Research Group (ASAP).
Light refreshments will be available afterwards in the corridor outside the Lecture Theatre.