 |
    |
A Hyper-Heuristic Classifier for One Dimensional Bin Packing Problems: Improving Classification Accuracy by Attribute Evolution
Kevin Sim, Emma Hart, and Ben Paechter
Institute for Informatics and Digital Innovation, Edinburgh Napier University, Merchiston Campus, Edinburgh, EH10 5DT, UKk.sim@napier.ac.uk
e.hart@napier.ac.uk
b.paechter@napier.ac.uk
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.
Keywords: Hyper-heuristics, one dimensional bin packing, classifier systems, attribute evolution
LNCS 7492, p. 348 ff.
lncs@springer.com
© Springer-Verlag Berlin Heidelberg 2012