Research Output

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

  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.

  • Publication Status:

    Published

  • Publisher

    MIT Press

  • DOI:

    10.7551/978-0-262-31709-2-ch126

  • Library of Congress:

    QA75 Electronic computers. Computer science

  • Dewey Decimal Classification:

    006.3 Artificial intelligence

  • Funders:

    EPSRC grant P/J1021628/1

Citation

Sim, K., Hart, E. & Paechter, B. (2012). Learning to solve bin packing problems with an immune inspired hyper-heuristic. In Liò, P., Miglino, O., Nicosia, G., Nolfi, S. & Pavone, M. (Eds.). Advances in Artificial Life, ECAL 2013, 856-863. doi:10.7551/978-0-262-31709-2-ch126

Authors

Keywords

Hyper-heuristics; artificial systems; problem solving; novel affinity measure;

Monthly Views:

Available Documents