A Lifelong Learning Hyper-heuristic Method for Bin Packing

Hart, Emma; Sim, Kevin; Paechter, Ben

Abstract

We describe a novel Hyper-heuristic system which continuously learns over time to solve a combinatorial optimisation problem. 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 in- spired by methods in Artificial Immune Systems.The network is plastic in both its structure and content leading to the following properties: it exploits existing knowl- edge captured in the network to rapidly produce solutions; it can adapt to new prob- lems with widely differing characteristics; it is capable of generalising over the prob- lem space. The system is tested on a large corpus of 3968 new instances of 1D-bin packing problems as well as on 1370 existing problems from the literature; it shows excellent performance in terms of the quality of solutions obtained across the datasets and in adapting to dynamically changing sets of problem instances compared to pre- vious approaches. As the network self-adapts to sustain a minimal repertoire of both problems and heuristics that form a representative map of the problem space, the system is further shown to be computationally efficient and therefore scalable.

Citation

Hart, E., Sim, K., & Paechter, B. (2015). A Lifelong Learning Hyper-heuristic Method for Bin Packing. Evolutionary Computation, 23(1), 37-67. https://doi.org/10.1162/EVCO_a_00121

• Journal Article Type: Article
• Online Publication Date: Mar 13, 2015
• Publication Date: 2015-03
• Deposit Date: Apr 11, 2014
• Publicly Available Date: May 15, 2017
• Journal: Evolutionary Computation
• Print ISSN: 1063-6560
• Electronic ISSN: 1530-9304
• Publisher: MIT Press
• Peer Reviewed: Peer Reviewed
• Volume: 23
• Issue: 1
• Pages: 37-67
• DOI: https://doi.org/10.1162/EVCO_a_00121
• Keywords: novel Hyper-heuristic system; 1D-bin packing; scalable
• Public URL: http://researchrepository.napier.ac.uk/id/eprint/6640
• Publisher URL: http://dx.doi.org/10.1162/EVCO_a_00121