Hyper-heuristics: Learning To Combine Simple Heuristics In Bin-packing Problems
Peter D. Ross, Sonia Schulenburg, Javier G. Marı́n-Blázquez, Emma Hart · Edinburgh Napier Research Repository (Edinburgh Napier University) · 2002
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. Wetry to address these concerns by using an EA, inparticular the learning classifier system XCS, tolearn a solution process rather than to solve individualproblems. 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 ofthe problems, none of the heuristics used can findan optimal answer; however, the evolved solutionprocess can find an optimal solution in over 78% of cases.