 |
    |
Learning a Procedure That Can Solve Hard Bin-Packing Problems: A New GA-Based Approach to Hyper-heuristics
Peter Ross, Javier G. Marín-Blázquez, Sonia Schulenburg, and Emma Hart
School of Computing
Napier University
Edinburgh EH10 5DT
{P.Ross,S.Schulenburg,E.Hart}@napier.ac.uk
javierg@dai.ed.ac.uk
Abstract. The idea underlying hyper-heuristics is to discover some combination of familiar, straightforward heuristics that performs very well across a whole range of problems. To be worthwhile, such a combination should outperform all of the constituent heuristics. In this paper we describe a novel messy-GA-based approach that learns such a heuristic combination for solving one-dimensional bin-packing problems. When applied to a large set of benchmark problems, the learned procedure finds an optimal solution for nearly 80% of them, and for the rest produces an answer very close to optimal. When compared with its own constituent heuristics, it ranks first in 98% of the problems.
LNCS 2724, p. 1295 ff.
lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2003