A Study of Evolutionary Algorithm Selection Hyper-Heuristics for the One-Dimensional Bin-Packing Problem

• Published in: South African computer journal = Suid-Afrikaanse rekenaartydskrif 2012-06, Vol.48 (48)
• Main Author: Pillay, Nelishia
• Format: Article
• Language: English
• Subjects: Genetic algorithms; Heuristic; Hyper-heuristics, one-dimensional bin-packing, evolutionary algorithms; Packing problem
• ISSN: 1015-7999; 2313-7835
• DOI: 10.18489/sacj.v48i1.87

Hyper-heuristics are aimed at providing a generalized solution to optimization problems rather than producing the best result for one or more problem instances. This paper examines the use of evolutionary algorithm (EA) selection hyper-heuristics to solve the offline one-dimensional bin-packing problem. Two EA hyper-heuristics are evaluated. The first (EA-HH1) searches a heuristic space of combinations of low-level construction heuristics for bin selection. The second (EA-HH2) explores a space of combinations of both item selection and bin selection heuristic combinations. These EA hyper-heuristics use tournament selection to choose parents, and mutation and crossover with hill-climbing to create the offspring of each generation. The performance of the hyper-heuristics is compared to that of each of the low-level heuristics applied independently to solve this problem. Furthermore, the performance of both hyper-heuristics is also compared. The comparisons revealed that hyper-heuristics in general perform better than any single low-level construction heuristic in solving the problem. In addition to this it was found that the hyper-heuristic exploring a space of both item selection and bin selection heuristic combinations is more effective than the hyper-heuristic searching a space of just bin selection heuristic combinations. The performance of this hyper-heuristic was found to be comparable to other methods applied to the same benchmark sets of problems.