Learning to Solve Bin Packing Problems with an Immune Inspired Hyper-heuristic

Sim, K., Hart, E., Paechter, B. (2013). Learning to Solve Bin Packing Problems with an Immune Inspired Hyper-heuristic. In: (Ed.) Proceedings of ECAL 2013 - 12th European Conference on Artificial Life, , () ( ed.). (pp. ). : . MIT Press.


ISBN:
ISSN:

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.
[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.