Research Output

Generating single and multiple cooperative heuristics for the one dimensional bin packing problem using a single node genetic programming island model.

  Novel deterministic heuristics are generated using Single Node Genetic Programming for application to the One Dimensional Bin Packing Problem. First a single deterministic heuristic was evolved that minimised the total number of bins used when applied to a set of 685 training instances. Following this, a set of heuristics were evolved using a form of cooperative co-evolution that collectively minimise the number of bins used across the same set of problems. Results on an unseen test set comprising a further 685 problem instances show that the single evolved heuristic out- performs existing deterministic heuristics described in the literature. The collection of heuristics evolved by cooperative co-evolution outperforms any of the single heuristics, including the newly generated ones.

  • Type:

    Book Chapter

  • Date:

    30 November 2012

  • Publication Status:

    Published

  • Publisher

    ACM SIGEVO

  • DOI:

    10.1145/2463372.2463555

  • Library of Congress:

    QA75 Electronic computers. Computer science

  • Dewey Decimal Classification:

    006.3 Artificial intelligence

Citation

Sim, K. & Hart, E. (2012). Generating single and multiple cooperative heuristics for the one dimensional bin packing problem using a single node genetic programming island model. In Alba, E. (Ed.). Proceedgs of GECCO 2013, 1549-1556. ACM SIGEVO. doi:10.1145/2463372.2463555. ISBN 978-1-4503-1963-8

Authors

Keywords

genetic-programming; hyper-heuristics; one-dimensional bin packing; single node genetic programming;

Monthly Views:

Available Documents