A Neural Approach to Generation of Constructive Heuristics

Alissa, Mohamad; Sim, Kevin; Hart, Emma

Abstract

Both algorithm-selection methods and hyper-heuristic methods rely on a pool of complementary heuristics. Improving the pool with new heuristics can improve performance, however, designing new heuristics can be challenging. Methods such as genetic programming have proved successful in automating this process in the past. Typically, these make use of problem state-information and existing heuristics as components. Here we propose a novel neural approach for generating constructive heuristics, in which a neural network acts as a heuristic by generating decisions. We evaluate two architectures, an Encoder-Decoder LSTM and a Feed-Forward Neural Network. Both are trained using the decisions output from existing heuristics on a large set of instances. We consider streaming instances of bin-packing problems in a continual stream that must be packed immediately in strict order and using a limited number of resources. We show that the new heuristics generated are capable of solving a subset of instances better than the well-known heuristics forming the original pool, and hence the overall value of the pool is improved w.r.t. both Falkenauer's performance metric and the number of bins used.

Citation

Alissa, M., Sim, K., & Hart, E. (2021). A Neural Approach to Generation of Constructive Heuristics. In 2021 IEEE Congress on Evolutionary Computation (CEC) (1147-1154). https://doi.org/10.1109/CEC45853.2021.9504989

• Conference Name: IEEE Congress on Evolutionary Computation 2021
• Conference Location: Kraków, Poland (online)
• Start Date: Jun 28, 2021
• End Date: Jul 1, 2021
• Acceptance Date: Apr 7, 2021
• Online Publication Date: Aug 9, 2021
• Publication Date: 2021
• Deposit Date: Jul 5, 2021
• Publicly Available Date: Jul 5, 2021
• Publisher: Institute of Electrical and Electronics Engineers
• Pages: 1147-1154
• Book Title: 2021 IEEE Congress on Evolutionary Computation (CEC)
• DOI: https://doi.org/10.1109/CEC45853.2021.9504989
• Keywords: Automatic Heuristics Generation; Hyper-Heuristics; Encoder-Decoder LSTM; Streaming Bin-packing
• Public URL: http://researchrepository.napier.ac.uk/Output/2784773