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



Pietro Li�

Orazio Miglino

Giuseppe Nicosia

Stefano Nolfi

Mario Pavone


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
Keywords Hyper-heuristics; artificial systems; problem solving; novel affinity measure;
Public URL
Publisher URL
Contract Date Aug 26, 2013


You might also like

Downloadable Citations