Skip to main content

Research Repository

Advanced Search

A Lifelong Learning Hyper-heuristic Method for Bin Packing

Hart, Emma; Sim, Kevin; Paechter, Ben

Authors



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.

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
Contract Date May 15, 2017

Files






You might also like



Downloadable Citations