Real World Optimisation with Life-Long Learning

Lead Research Organisation: Edinburgh Napier University
Department Name: Computing

Abstract

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.

Planned Impact

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.
 
Description We have developed a novel ensemble based optimisation technique called NELLI (Network for Lifelong Learning) that uses a collective of automatically generated optimisation algorithms to solve difficult optimisation problems and continues to learn over time.

There main innovations are as follows.

The use of ensemble (collaborative) methods to tackle optimisation problems. This represents a paradigm shift from the usual approaches of focusing computational effort on developing a 'super algorithm' that solves many instances. Instead, new simple heuristics are generated using an automated programming technique requiring very little computational effort that work well on just a few instances. By combining many simple heuristics into a collective, a powerful optimizer is formed in which the collective is more powerful than any of the individual components.

The second innovation is the development of a method for solving optimisation problems that continuously learns over time, as it gains experience from solving a range of instances. The key elements of the method are a technique for continuously generating and trialling new heuristics against the current set of problems that need to be solved, while retaining a memory, storing algorithms that were useful in the past. Firstly, this enables the system to autonomously adapt to changes in problem structure, e.g. in a scheduling application, new customers orders might arrive that instances have different constraints and operation sizes to previous ones. Secondly, the memory enables the system to exploit previous knowledge in quickly determining an appropriate algorithm based on past experience. Finally, continuous adaptation mechanisms enable the current heuristics to improve over time, as they are exposed to more examples. The new approach is inspired by mechanisms observed in the natural immune system.

Results have shown the new method outperforms existing state-of-the art optimisation algorithms in a number of domains (packing, routing, scheduling). We have additionally provided the first results on lifelong learning optimisation where the instances to be solved change over time.

New insights into the composition of the ensemble have been gained. It is clear that the algorithms within the ensemble must be behaviourally diverse, in that each algorithm should operate in a different region of the problem space, i.e. solve different problemn. We have shown how a method inspired by Artificial Immune Systems enables a collection of diverse algorithms to be evolved. However, open research questions remain as to how best to measure behavioural diversity within a set of algorithms and the extent to which diversity should drive ensemble composition that should be investigated more deeply in the future.

Two new datasets that provide new benchmark resources have been created through the project. The first is a very large collection of new Rich Vehicle Routing instances that were developed as a result of collaboration with Optrak Ltd, who provided new insights into the constraints and features of real-world routing. The second is a new set of benchmark instances for job-shop scheduling. All instances are available for download.

Also noteworthy is the new collaborations and networks we have developed within the Forestry community in Europe who see significant potential for applying optimisation methods in Forestry to reduce wind-damage. Ongoing collaboration with a researcher from Institute of Mountain Science, Shinshu University (Japan) and from INRA (Bordeaux, France) is continuing to pursue this research, and we are seeking further funding.
Exploitation Route The Forestry industry are keen to use our findings to take forward new research into managing risk of damage in forests through optimisation of cutting patterns.

In the past, the use of search-based optimisation techniques to minimise damage has been hindered by the need to use computationally expensive and time consuming simulations to evaluate potential damage in a given scenario. Our findings have shown that we can replace the simulation with a computational model that accurately reflects results from the simulator, and that damage can be accurately predicted at both stand and tree level.

We are currently working with INRA (Bordeaux) to pursue further funding opportunities to take this work forward and have presented to a large workshop on Wind Damage to European Forests with practitioners and researchers from across the world.

From an academic perspective, the findings are of particular interest to the hyper-heuristic community who focus research on optimisation methods that provide fast, reliable and quality solutions. Our findings relating to *how* to generate new algorithms and how to *combine* algorithms into collaborative sets are both of interest to pushing forward research.

Finally, the new set of rich vehicle routing instances developed in conjunction with a routing company provides a new resource for researchers that brings academic and practical routing closer together, enabling researchers to tackle problems directly relevant to industry
Sectors Agriculture, Food and Drink,Digital/Communication/Information Technologies (including Software),Transport

URL http://rollproject.org
 
Description Scientific findings arising during the grant have led to the PI taking part in activities which will have impact outside of academia in the medium to long term. a) Farmers and growers are continuously seeking ways to reduce cost, improve quality and advance productivity. Computer science, alongside other disciplines has significant potential to shape the future of precision farming. Recognising this, the Agricultural and Horticultural Development Board (AHDB) organised a Smart Agriculture Conference to enable for scientists, researchers and engineers across multiple disciplines to build relationships that stimulate discussion and identify potential research and application opportunities that address bridge the gap between farmer need and technological development. The PI (Emma Hart) was one of three invited speakers invited to present in an Applications session, giving a talk entitled Smart Optimisation for Smart Agriculture: this was an opportunity to describe how the findings from the grant relating to development of new hyper-heuristic optimisation techniques could be applied to generate economic benefit in agriculture. This talk raised awareness of the field of hyper-heuristic based optimisation to a large audience of non-academics and actors from the Agricultural industry. Optimisation techniques are currently little used hence raising awareness of this has the potential long-term economic impact. b) Also within the agriculture domain, we have worked closely with a Forestry institute to determine how our findings can be directly used in creating economic impact in the Forestry Management in minimizing wind-damage. Wind is a major disturbance agent in forests which has important economic, environmental and social impacts. To understand forest ecosystems and to manage forests in order to mitigate the risk of wind damage, it is vital to understand the mechanisms of wind damage. However, current mechanistic models have reached their limit and a re-evaluation of the approach is required to deal with the range of spatial and temporal scales required for a comprehensive understanding. The PI was invited to attend a workshop that brought together forest wind risk modellers and experts in airflow modelling, climate modelling and engineering risk analysis from across the world. The workshop took place over two and a half days with an emphasis on discussion and debate: a report on the recommendations of participants and a joint review article on forest wind risk modelling is currently being written. This has built a new research collaboration that could lead to considerable economic benefits in the long-term. Follow-up work resulted in publication of a new method to derive features to predict wind-damage, and the work was awarded a Bronze medal in the 2018 Humies Competition at GECCO 2019 for algorithms that achieve human-competitive results on real-world problems. It also led to a further journal publication and a joint grant proposal with Forest Research (NERC) submitted January 2020 c) Our finding that effective heuristics can developed by combining a range of simple heuristics has been directly used by Pulsion Ltd, a software company based in Glasgow. Through contact made by the Business Development Manager within the School of Computing at Edinburgh Napier, we developed new software for the company to be incorporated into their product that they sell. The software enables efficient routing and scheduling of service engineers across Scotland, and therefore has direct economic benefit. We continue to have contact with Optrak one of our collaborators with ongoing discussions on how the state of the art in the field might be incorporated into their product. Finally the work has achieved a high profile within the academic community through the PI being invited to give a number of keynote talks at major international conferences on the subject
First Year Of Impact 2015
Sector Agriculture, Food and Drink,Transport
Impact Types Economic

 
Description Ensembles for Optimisation
Amount £35,000 (GBP)
Funding ID RF-2015-092 
Organisation The Leverhulme Trust 
Sector Charity/Non Profit
Country United Kingdom
Start 09/2015 
End 08/2016
 
Title Binpacking problem benchmark data set 
Description A collection of ~15000 benchmark instances of 1D bin packing problems have been developed and made available to researchers working in optimisation 
Type Of Material Database/Collection of data 
Year Produced 2013 
Provided To Others? Yes  
Impact Used within my research group 
URL http://rollproject.org/category/benchmark-problems/
 
Title Job shop scheduling dataset 
Description Collection of 700 new job shop instances 
Type Of Material Database/Collection of data 
Year Produced 2015 
Provided To Others? Yes  
Impact downloadable results available for other researchers to use as comparison 
URL http://researchrepository.napier.ac.uk/id/eprint/9364
 
Description Forest Research 
Organisation French National Institute of Agricultural Research
Country France 
Sector Academic/University 
PI Contribution Using data collected from several forests in the South West of France provided byINRA, the research team has used a suite of machine-learning methods in order to predict tree damage and estimate critical wind speeds, replacing the need for a complex physics simulator. The techniques have obtained superior results than the methods they have used in the past. The results have also given new insights in to the relative importance of a range of factors that contribute to wind damage in forests. The team has also engaged in knowledge transfer with the partner, hosting visit by an RA from INRA to explain the use of the techniques and tools required
Collaborator Contribution The partner has provided real-world data from several forests in France for us to work with They have used their own funding to visit us at Edinburgh Napier at least twice a year to jointly discuss results we have provided and discuss next steps They are currently participating in writing a joint publication on the results obtained (2 members of staff from INRA, PI, RA from Napier) They have indicated a wish to extend the collaboration beyond the project end and have a arrange a 3-day visit in February 2016 (for 2 researchers from INRA) to discuss follow on work
Impact K Sim : workshop in Bordeaux (January 2015): Presentation: E Hart: attendance at invitation only workshop Mathematical Modelling of Wind Damage Risk to Forests (October 2015) Joint journal paper submitted for review (J. Forest and Ecology Management, 2016)
Start Year 2013
 
Description Optrak 
Organisation Optrak Distribution Software Limited
Country United Kingdom 
Sector Private 
PI Contribution We have discussed with the collaborator the potential for using heuristic methods in the software they develop
Collaborator Contribution Optrak have engaged in a number of discussion which have clearly identified the real world constraints faced by logistics companies that are not accounted for in academic vehicle routing research. Based on these constraints, we have developed a new benchmark suite of rich vehicle routing problems that are made freely available to researchers and academics. Optrak have contributed to a publications on which the collaborator is a named author. In addition, Tim Pidgen gave an invited talk at a workshop at GECCO 2013, in which he described to the audience some of the real challenges faced by logistics operators and suggested directions for future research.
Impact Sim, K., Hart, E., Urquhart, N., Pigden, T. (2015). A new rich vehicle routing problem model and benchmark resource. In: Proceedings of the The 11th edition of the International Conference on Evolutionary and Deterministic Methods for Design, Optimization and Control with Applications to Industrial and Societal Problems (EUROGEN 2015). Vehicle Routing Benchmark Dataset http://www.rollproject.org/vehicle-routing/
Start Year 2013
 
Description Pulsion 
Organisation Pulsion Technology
Country United Kingdom 
Sector Private 
PI Contribution We developed a piece of software for the company to integrate into a product that uses the heuristic methods developed in our research to optimise scheduling of a home-based workforce to service jobs across Scotland.
Collaborator Contribution The company provided data and insights that enabled us to tailor our heuristic methods to real-world problems. Based on these discussions, we further developed a demo based on the company's requirements for disseminating our research more widely. The company contributed to the writing and publication of a workshop paper presented at GECCO 2014.
Impact 1. Demo - available from www.rollproject.org 2. Paper published at GECCO 2014: Sim, Kevin, Hart, Emma, Urquhart Neil. A Real-World Employee Scheduling and Routing Application
Start Year 2014
 
Description AHDB Conference (Birmingham) 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? Yes
Geographic Reach National
Primary Audience Professional Practitioners
Results and Impact AHDB's Smart Agriculture Conference is an opportunity for scientists, researchers and engineers across multiple disciplines to build relationships that stimulate discussion and identify potential research and application opportunities that address bridge the gap between farmer need and technological development.
The talk sparked discussion regarding how to 'sell' optimisation technologies to farmers and potential benefits

Contact made with Dr. Charles Elworthy Head of Research, Map of Agriculture regarding plans for future involvement

Video of presentation and slides available from http://www.smartag.ahdb.org.uk/video-gallery/
Year(s) Of Engagement Activity 2015
URL http://www.smartag.ahdb.org.uk
 
Description COW Workshop (University College London) 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other academic audiences (collaborators, peers etc.)
Results and Impact The talk sparked a number of discussions regarding the use of hyper heuristics that can continue to learn in the field of Search Based Software Engineering

Online Videos available from the talk
Audience noted potential for learning from techniques represented

Request for collaboration from researcher at University of Cardiff
Year(s) Of Engagement Activity 2015
URL http://crest.cs.ucl.ac.uk/index.php?id=7831
 
Description Invited Talk (University of Aberystwyth) 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach Local
Primary Audience Other audiences
Results and Impact discussion following talk relating to benefits of hyper-heuristic methods

raised awareness of new research in field of artificial immune systems
Year(s) Of Engagement Activity 2015
 
Description Invited Talk: Lifelong Learning in Autonomous Systems 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Postgraduate students
Results and Impact Invited talk at the Technical University of Vienna : attended by ~20 staff and students
Year(s) Of Engagement Activity 2018
 
Description Invited talk (University of Nottingham) 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach Local
Primary Audience Other academic audiences (collaborators, peers etc.)
Results and Impact Talk sparked questions and discussion: was particularly useful in informing future research directions given expertise at the University of Nottingham in both Hyper Heuristic methods and immune inspired computing

talk resulted in ongoing discussions with researchers from Nottingham
Year(s) Of Engagement Activity 2013
 
Description Invited talk (University of Stirling) 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach Local
Primary Audience Other academic audiences (collaborators, peers etc.)
Results and Impact sparked much discussion .
Resulted in ongoing collaboration with two staff members from University of Stirling to develop an International Vehicle Routing Competition

International Vehicle Routing competition developed jointly to be launched January 2016

New collaboration with staff member initiated, currently writing joint grant proposal
Year(s) Of Engagement Activity 2014
 
Description Keynote (IJCCI, Madeira) 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Postgraduate students
Results and Impact Keynote on Lifelong Learning at the International Joint Conference on Computational Intelligence, attended by researchers from across Europe.
Year(s) Of Engagement Activity 2017
URL http://www.ijcci.org/KeynoteSpeakers.aspx?y=2017
 
Description Keynote EURO 2016 28th European Conference on Operational Research 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other audiences
Results and Impact I gave an invited keynote at EURO OR - the 28th European Conference on Operational Research. The conference is attended by around 2000 people including academics and practitioners.
The keynote I presented was based on the work conducted during this project. The keynote was streamed live and is available as video on the conference website.
As a result, I was invited to write a tutorial article for the international IFORS magazine
Year(s) Of Engagement Activity 2016
URL http://www.euro2016.poznan.pl/emma-hart/
 
Description Participant in invitation only Symposium with Russian scientists 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? Yes
Geographic Reach International
Primary Audience Other academic audiences (collaborators, peers etc.)
Results and Impact session sparked questions and discussion with both UK and Russian scientists


Have made contact with other scientists in UK working in similar areas
Year(s) Of Engagement Activity 2013
URL https://royalsociety.org/policy/publications/2013/russia-frontiers-science/
 
Description Real World Applications Workshop (GECCO 2013, GECCO 2014) 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other academic audiences (collaborators, peers etc.)
Results and Impact Workshop on Real World Problems at leading international optimisation conference. Included invited speaker from industry and speakers who had worked directly on real-world problems with industrial partners :

Speakers from :
Slovenia (2013) Bogdan Filipic
UK Tim Pigden (2014) Industry
US Darrel Whitley (2014) Academia
Spain Anna Esparcia-Alcazar (2014) Industry

Workshop ran in for 2nd year following success of 1st.
Discussions with other academics on pitfalls of working with real problems informed thinking
Year(s) Of Engagement Activity 2013,2014
URL http://rollproject.org/category/events/
 
Description SICSA Technology Showcase (Glasgow) 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach Regional
Primary Audience Professional Practitioners
Results and Impact DEMOfest is an annual technology showcase of leading Informatics and Computer Science research from Scottish Universities and creates an environment for industry partners and academics to come together to create opportunities for collaborative innovation.

Discussed concept of life-long learning with a number of academic and industrialists who were interested in the potential of the technique

developed concepts for incorporating into new algorithms
Year(s) Of Engagement Activity 2013
URL http://www.sicsa.ac.uk/knowledge-exchange/industry-collaboration/demofest/
 
Description Wind Damage Workshop (Arcachon) 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other academic audiences (collaborators, peers etc.)
Results and Impact The workshop brought together forest wind risk modellers from around the world along with experts in subjects required to improve the models (e.g. meso-scale airflow modellers, wind climate scientists, risk analysis engineers, etc.), but who have to date not always been actively involved in forest wind damage risk modelling.
As the only representative from the optimisation/learning community the talk sparked discussion regarding the potential application of techniques to new real data gathered from forests around the world.

- potential follow up work with research from Japan relating to data collected from Forests in Aquitaine region of France
- potential follow up work with researcher from Netherlands applied to real data collected during storm damage in 2009
Year(s) Of Engagement Activity 2015