Neural Network Based Heuristic Selection for Selection Hyper-Heuristics

OpenAlex · English

The present study utilizes neural network to perform heuristic selection in selection hyper-heuristics. Selection hyper-heuristics are problem-independent solvers, preferably benefited for tackling a wide range of search and optimization problems. Unlike traditional algorithms, selection hyper-heuristics operate across a heuristic set to solve a given problem instance rather than directly solving it. The idea, in that sense, is to manage a particular heuristic set provided for a specific problem. One critical component to properly utilize a heuristic set is a heuristic selection method. This method, essentially, identifies one or more heuristics to use at each decision step. The goal is to solve a given problem instance cooperatively by taking advantage of the underlying heuristics' strengths. Accommodating a learning-based selection approach is quite common since a heuristic selection policy appropriate for one case might be inferior for other cases. This work employs neural network to realize heuristic selection. Namely, two architectures of a single hidden-layer Long Short-Term Memory (LSTM) and a deep Temporal Convolutional Network (TCN) have been used to realize the selection task, formed as a sequence prediction problem. The training process of those architectures is achieved by using heuristic sequences derived from 20 existing selection hyper-heuristics. The resulting models are combined with a simple move acceptance criterion and tested on the 1-dimensional Bin Packing problem. The corresponding empirical analysis revealed that neural network is able to capture the heuristic selection decisions coming from different selection hyper-heuristics, under a single selection system.