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.

  • Date:

    06 July 2013

  • Publication Status:

    Published

  • Publisher

    ACM

  • 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. (2013). Generating single and multiple cooperative heuristics for the one dimensional bin packing problem using a single node genetic programming island model. In E. Alba (Ed.), Proceedgs of GECCO 2013, 1549-1556. doi:10.1145/2463372.2463555

Authors

Copyright

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
GECCO’13, July 6–10, 2013, Amsterdam, The Netherlands

Keywords

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

Monthly Views:

Available Documents