A structured-based genetic programming generation construction hyper-heuristic with transfer learning for combinatorial optimisation

Abstract

Genetic programming and variants of genetic programming such as grammar-based genetic program ming have predominately been used in generation construction hyper-heuristics (GC-HH). Previous work has also shown the effectiveness of transfer learning in genetic programming generation hyper heuristics. Structure-based genetic programming (SBGP) uses both the fitness of an individual and its structure to direct the search in a search space. This study investigates the use of a structure-based genetic programming hyper-heuristic (SBGP-HH) in generation construction hyper-heuristics. The use of SBGP-HH with transfer learning (SBGP-HH-TL) is also investigated. The proposed approaches were evaluated on the examination timetabling, one dimensional bin-packing and capacitated vehicle routing problems. SBGP-HH was found to outperform the canonical genetic programming hyper-heuristic (CGP-HH) for the selected problem domains. SBGP-HH-TL produced better results than SBGP-HH with statistical significance on most problem instances. These results were found to be statistically significant at the 90% level of confidence. SBGP-HH-TL was found to outperform CGP-HH with transfer learning (CGP-HH-TL) for the selected problem domains.