A Parameter-Based Analysis of Ant-Based Generation Hyper-Heuristics

Recently, ant algorithms have been employed by generation constructive and generation perturbative hyper-heuristics. However, no research has been conducted to study these algorithms in terms of their parameters and the heuristics that they generate. This paper presents a study of ant-based generation hyper-heuristics that examines the effect of different parameters for achieving good performance for three different assessment criteria namely, generality, optimality and computational effort. This is done via an elementary effects analysis to assess the importance of the different parameters in producing good performance for the different assessment criteria. The paper also presents an analysis of generated heuristics, assessed via three metrics that define a compactness criterion, to assess the potential of bloat, i.e. redundant code, in generated heuristics produced by ant-based generation hyper-heuristics under different generation size limits, the operator limit. This study considers three domains, the travelling salesman problem, movie scene scheduling problem and capacitated vehicle routing problem. The results of the study showed that type of pheromone map and operator limits were most important for generality, with the number of ants and number of iterations being most important for optimality and computational effort. Additionally, the study also demonstrated that ant-based generation hyper-heuristics produce highly compact, readable heuristics even with large operator limits that demonstrate resistance to bloat.