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

Sim, Kevin; Hart, Emma

Abstract

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.

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). https://doi.org/10.1145/2463372.2463555

• Conference Name: 15th annual conference on Genetic and evolutionary computation
• Start Date: Jul 6, 2013
• End Date: Jul 10, 2013
• Publication Date: Jul 6, 2013
• Deposit Date: May 28, 2013
• Publicly Available Date: Jul 6, 2013
• Publisher: Association for Computing Machinery (ACM)
• Peer Reviewed: Peer Reviewed
• Pages: 1549-1556
• Book Title: Proceedgs of GECCO 2013
• ISBN: 978-1-4503-1963-8
• DOI: https://doi.org/10.1145/2463372.2463555
• Keywords: genetic-programming; hyper-heuristics; one-dimensional bin packing; single node genetic programming
• Public URL: http://researchrepository.napier.ac.uk/id/eprint/6060
• Publisher URL: http://dx.doi.org/10.1145/2463372.2463555