A Lifelong Learning Hyper-heuristic Method for Bin Packing

Hart, E., Sim, K., Paechter, B. (2015). A Lifelong Learning Hyper-heuristic Method for Bin Packing. Evolutionary Computation, 23, (1), 37-67.


ISBN:
ISSN:

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 sys- tem is further shown to be computationally efficient and therefore scalable.
[Read More]

Authors

Emma Hart
Director of CEC
e.hart@napier.ac.uk
+44 131 455 2783
Kevin Sim
Lecturer
K.Sim@napier.ac.uk
+44 131 455 2497
Ben Paechter
Director of Research
b.paechter@napier.ac.uk
+44 131 455 2764

Areas of Expertise

Bio-inspired Computing
The Bio-Inspired Algorithms group within the Centre for Algorithms, Visualisation and Evolving Systems is a large and thriving group with interests in nature-inspired computing that include Evolutionary Computing, Hyper-Heuristics, Artificial Immune Systems and Swarm Intelligence.