Prof. Emma Hart was invited to speak at the
A lifelong Learning Method for Solving Combinatorial Optimisation Problems
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.