Skip to main content

Research Repository

Advanced Search

Learning to solve bin packing problems with an immune inspired hyper-heuristic.

Sim, Kevin; Hart, Emma; Paechter, Ben

Authors



Contributors

Pietro Li�
Editor

Orazio Miglino
Editor

Giuseppe Nicosia
Editor

Stefano Nolfi
Editor

Mario Pavone
Editor

Abstract

Motivated by the natural immune system's ability to defend the body by generating and maintaining a repertoire of antibodies that collectively cover the potential pathogen space, we describe an artificial system that discovers and maintains a repertoire of heuristics that collectively provide methods for solving problems within a problem space. Using bin-packing as an example domain, the system continuously generates novel heuristics represented using a tree-structure. An novel affinity measure provides stimulation between heuristics that cooperate by solving problems in different parts of the space. Using a test suite comprising of 1370 problem instances, we show that the system self-organises to a minimal repertoire of heuristics that provide equivalent performance on the test set to state-of-the art methods in hyper-heuristics. Moreover, the system is shown to be highly responsive and adaptive: it rapidly incorporates new heuristics both when entirely new sets of problem instances are introduced or when the problems presented change gradually over time.

Start Date Sep 2, 2013
End Date Sep 6, 2013
Publication Date 2013
Deposit Date Aug 26, 2013
Publicly Available Date Dec 31, 2013
Peer Reviewed Peer Reviewed
Pages 856-863
Book Title Advances in Artificial Life, ECAL 2013
DOI https://doi.org/10.7551/978-0-262-31709-2-ch126
Keywords Hyper-heuristics; artificial systems; problem solving; novel affinity measure;
Public URL http://researchrepository.napier.ac.uk/id/eprint/6251
Publisher URL http://dx.doi.org/10.7551/978-0-262-31709-2-ch126
Contract Date Aug 26, 2013

Files








You might also like



Downloadable Citations