A Hyper-Heuristic classifier for one dimensional bin packing problems: Improving classification accuracy by attribute evolution.

Sim, Kevin; Hart, Emma; Paechter, Ben

Abstract

A hyper-heuristic for the one dimensional bin packing problem is presented that uses an Evolutionary Algorithm (EA) to evolve a set of attributes that characterise a problem instance. The EA evolves divisions of variable quantity and dimension that represent ranges of a bin’s capacity and are used to train a k-nearest neighbour algorithm. Once trained the classifier selects a single deterministic heuristic to solve each one of a large set of unseen problem instances. The evolved classifier is shown to achieve results significantly better than are obtained by any of the constituent heuristics when used in isolation

Citation

Sim, K., Hart, E., & Paechter, B. (2012). A Hyper-Heuristic classifier for one dimensional bin packing problems: Improving classification accuracy by attribute evolution. In Parallel Problem Solving from Nature: PPSN XII (348-357). https://doi.org/10.1007/978-3-642-32964-7_35

• Conference Name: International Conference on Parallel Problem Solving from Nature
• Start Date: Sep 1, 2012
• End Date: Sep 5, 2012
• Publication Date: 2012
• Deposit Date: Nov 2, 2012
• Publicly Available Date: May 16, 2017
• Peer Reviewed: Peer Reviewed
• Volume: 7492
• Pages: 348-357
• Series Title: Lecture Notes in Computer Science
• Series ISSN: 0302-9743
• Book Title: Parallel Problem Solving from Nature: PPSN XII
• ISBN: 978-3-642-32963-0
• DOI: https://doi.org/10.1007/978-3-642-32964-7_35
• Keywords: Hyper-heuristics; one dimensional bin packing; classifier systems; attribute evolution
• Public URL: http://researchrepository.napier.ac.uk/id/eprint/5698
• Publisher URL: http://dx.doi.org/10.1007/978-3-642-32964-7_35