Real World Optimisation with Life-Long Learning

Many practical problems arising in industrial domains concerned with operating sustainably, meeting demand and minimising costs cannot be solved exactly. Meta-heuristic optimisation techniques have been widely developed in academia to solve such problems with much success reported in the literature. However, there remains a worrying void between scientific research into optimisation techniques and those problems faced by end-users and addressed by commercial optimisation software vendors. From a commercial perspective, the problems addressed by academia are too simplistic compared to those faced in the real-world, failing to embrace many real-world constraints. From the scientific perspective, researchers have also identified a "lack of advanced metaheuristic techniques in commercial software'' which has been attributed in part to the academic community failing to demonstrate that their solutions are applicable to the needs of the commercial world, and in part to academics failing to impart their message the industrial community.

Meta-heuristic approaches can be costly to develop as they generally require human expertise to integrate specialist knowledge into an algorithm, and expertise in heuristic methods to design and tune algorithms. Recent research has therefore focused on automated algorithm design and configuration which produce tuned solvers that perform well on either individual problems or across suites of problems. One branch of this field is hyper-heuristics, which operates on a space of low-level heuristics, searching for combinations of heuristics which exploit the strength and compensate for the weaknesses of individual known heuristics. The resulting algorithms are cheap to implement, require less human expertise, have robust performance within a problem class, and are portable across problem domains. These features compensate for some reduction in solution quality compared to tailor-made approaches, while still ensuring solutions of acceptable quality. However, most automated design approaches fail to incorporate or recognise a crucial human competence; human beings continuously learn from experience - by generalising observations and feedback, they are able to update their internal problem-solving models in order to continuously improve them, and adapt to changing circumstances. The failure of computational solvers to exploit previous knowledge both wastes useful knowledge and potentially hinders the discovery of good solutions. Furthermore, if the characteristics of instances of problems in the domain change over time, solvers may need to be completely re-tuned or in the worst case redesigned periodically.

This proposal addresses these dual concerns raised above. We propose a novel lifelong-learning hyper-heuristic system which addresses current deficiencies inherent in current systems: it will exhibit short-term learning, producing fast and effective solutions to individual problems and at the same time, long-term learning processes will enable the system to autonomously adapt to new problem characteristics over time. It therefore exploits existing knowledge whilst simultaneously adapting to new information. Secondly, by working closely with two collaborators, a commercial routing software vendor and a forestry expert, our research will be directly informed by real-world problems, accounting for real constraints and performance criteria, thereby producing economic impact. Future advances in optimisation techniques will be facilitated by the development of a problem generator and a number of problem suites which reflect real-world priorities and constraints, derived from actual problem data provided through our collaborators and defined in conjunction with metrics which reflect not only economic drivers but also address environmental impact and the reduction of carbon emissions. This information database will be widely disseminated to provide an extensive platform for future research.

The proposed research has economic impact and societal impact.

From an economic perspective, there is direct economic benefit to be derived from optimising the daily activities of companies, in the domains addressed of routing, forestry management and packing but also more widely in related domains. End-users of the research - companies who need to optimise their activities - will benefit from algorithms which increase efficiency, drive-down costs and improve sustainability (in economic terms and relating to environmental impact). Crucially, the proposed methods are cheap to implement and adapt autonomously to dynamic environments, thereby reducing the need for specialist expertise to implement or ongoing maintenance costs. Users will have confidence in the developed algorithms due to the use of low-level heuristics accepted by users as opposed to black-box methods, and the rigorous performance evaluation we will conduct which places significant emphasis on calculating the worst-case performance bounds and reliability in order to address user concerns. Secondly, vendors of optimisation software will benefit from access to state-of-the-art optimisation techniques which can be integrated with confidence within existing systems, thereby having direct economic benefit. The close collaboration with commercial partners proposed in this research takes important steps towards aligning research within academia with real-world priorities, which will directly result in economic benefit in the future.

The research also has societal impact. The emphasis on sustainability as a performance criteria when optimising solutions to problems by considering carbon emissions and the environmental impact of solutions (particularly in the work in forestry management addressed) will have future benefits to society as a whole in moving towards a greener, more sustainable way of life.