This repository is an implementation of a hyper-heuristic model based on bi-directional Long Short-Term Memory Neural Network for the 0/1 Knapsack problem.
This research work aims to show the suitability of deep learning, particularly recurrent neural networks, to provide approximate solutions to the KP. We trained a bi-directional Long Short-Term Memory (LSTM) hyper-heuristic model that searches in the space of seven greedy heuristics and decides which heuristic applies for a particular state of the problem. We trained the model with a dataset generated by a Simulated Annealing framework, characterizing each state of the problem with seven selected statistical features. To evaluate our results, we use the instances extracted from a paper published by Pisinger. The instances belong to four different groups: low-dimensional instances, uncorrelated, weakly correlated, and strongly correlated data. The Simulated Annealing framework, as well as a Random Search implementation was used along the greedy heuristics to benchmark the performance of the proposed model.
The following figure illustrates the methodology proposed in this work.
The results show that the LSTM model can be used to obtain approximate solutions for the Knapsack problem. The evaluations showed that this model could achieve high-quality results; it proved to be the second-best method for obtaining near-optimal results among seven commonly used algorithms.
This work did not find a previous study using this particular neural network architecture to solve the Knapsack Problem. We believe that by increasing the amount of data for model training and with an in-depth tuning of the parameters of the network better results can be obtained.
- Ramón Eduardo Díaz (Ramon-Diaz)
- José Manuel Tapia (jose-tapia)
- Daniela Gómez Cravioto (danisha20)