Empirical analysis of algorithmic components for improved performance in a baseline genetic algorithm selection hyper-heuristic

Abstract

Selection hyper-heuristics represent high-level search algorithms that dynamically select and apply lower-level heuristics to solve various optimization problems. They encompass numerous algorithmic components such as heuristic selection, move acceptance, feedback, and parameter setting. Each of these components offers multiple implementation methods, which creates challenges for algorithm designers who must decide on the most suitable approach for their algorithms. The issue is aggravated by the absence of a definitive best method for these components. Furthermore, there is a lack of a comprehensive empirical study on the efficacy of the implementation methods of these components, where most previous studies focus on heuristic selection and move acceptance. This paper addresses this gap by presenting a comprehensive empirical analysis of seven key selection hyper-heuristic components, including search points, search phases, move acceptance, feedback, Tabu mechanism, restart mechanism, and low-level heuristic parameters, in the context of population-based Genetic Algorithm Hyper-heuristic (GAHH). Implementation methods for these components were derived from 53 algorithms implemented using the HyFlex framework, notably the 20 finalist entries in the Cross-Domain Heuristic Search Challenge 2011. An analytical method is employed to compare their performance and identify the most effective implementation method within the evaluated settings. The analysis indicated that multi-point search, iterated search phases, non-stochastic threshold move acceptance, no learning from search feedback, Tabu mechanism with visited solutions, threshold restart mechanism, and adaptive parameter control as the best-performing strategies for GAHH across a limited set of 12 HyFlex tuning instances. Notably, the performance of the no-learning approach is influenced by genetic algorithm’s evolutionary operators. The results provide valuable insights that serve as a solid foundation for future algorithm development and increase the understanding of selection hyper-heuristic components, specifically in GAHH.