n South African Computer Journal - A study of evolutionary algorithm selection hyper-heuristics for the one-dimensional bin-packing problem
|Article Title||A study of evolutionary algorithm selection hyper-heuristics for the one-dimensional bin-packing problem|
|© Publisher:||South African Computer Society (SAICSIT)|
|Journal||South African Computer Journal|
|Affiliations||1 University of KwaZulu-Natal|
|Publication Date||Jun 2012|
|Pages||31 - 40|
|Keyword(s)||Algorithms, Evolutionary algorithms, Hyper-heuristics, I.2. [Computing Methodologies]: Artificial Intelligence, One-dimensional bin-packing and Theory|
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.
Article metrics loading...