Learning a procedure that can solve hard bin-packing problems: a new GA-based approach to hyperheuristics.

Ross, Peter; Marin-Blazquez, Javier G; Schulenburg, Sonia; Hart, Emma

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 heuris-
tic 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.

• Conference Name: Genetic and Evolutionary Computation Conference (GECCO) 2003
• Start Date: Jul 12, 2003
• End Date: Jul 16, 2003
• Publication Date: Jul 12, 2003
• Deposit Date: Jun 2, 2008
• Peer Reviewed: Peer Reviewed
• Pages: 1295-1306
• Keywords: Computer programming; Problem solving; Hyper-heuristics; Genetic algorithms; Bin-packing; Unidimensional
• Public URL: http://researchrepository.napier.ac.uk/id/eprint/1844