Hyper-heuristics: learning to combine simple heuristics in bin-packing problems.

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

Abstract

Evolutionary algorithms (EAs) often appear to be a ‘black box’, neither offering worst-case bounds nor any guarantee of optimality when used to solve individual problems. They can also take much longer than non-evolutionary methods. We
try to address these concerns by using an EA, in
particular the learning classifier system XCS, to
learn a solution process rather than to solve individual
problems. The process chooses one of various simple non-evolutionary heuristics to apply to each state of a problem, gradually transforming the problem from its initial state to a solved state. We test this on a large set of one dimensional bin packing problems. For some of
the problems, none of the heuristics used can find
an optimal answer; however, the evolved solution
process can find an optimal solution in over 78% of cases.

• Conference Name: Genetic and Evolutionary Computation Conference (GECCO)
• Start Date: Jul 9, 2002
• End Date: Jul 13, 2002
• Publication Date: Jul 9, 2002
• Deposit Date: Jul 22, 2008
• Peer Reviewed: Peer Reviewed
• Pages: 942-948
• ISBN: 1558608788
• Keywords: Evolutionary algorithms; Limitations; Learning solutions;Empirical process; Systematic packing
• Public URL: http://researchrepository.napier.ac.uk/id/eprint/1843