Research Output

A Lifelong Learning Hyper-heuristic Method for Bin Packing.

  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.

  • Type:

    Article

  • Date:

    13 March 2015

  • Publication Status:

    Published

  • Publisher

    MIT Press Journal

  • DOI:

    10.1162/EVCO_a_00121

  • ISSN:

    1063-6560

  • Library of Congress:

    QA75 Electronic computers. Computer science

  • Dewey Decimal Classification:

    006.3 Artificial intelligence

Citation

Hart, E., Sim, K. & Paechter, B. (2015). A Lifelong Learning Hyper-heuristic Method for Bin Packing. Evolutionary Computation. 23(1), 37-67. doi:10.1162/EVCO_a_00121. ISSN 1063-6560

Authors

Keywords

novel Hyper-heuristic system; 1D-bin packing; scalable;

Monthly Views:

Available Documents