A study of ant-based pheromone spaces for generation constructive hyper-heuristics

Abstract

Research into the applicability of ant-based optimisation techniques for hyper-heuristics is largely limited. This paper expands upon the existing body of research by presenting a novel ant-based generation constructive hyper-heuristic and then investigates how different pheromone maps affect its performance. Previous work has focused on applying ant-based optimisation techniques that work in the solution space directly to the heuristic space and we hypothesise that this may be problematic for the hyper-heuristic’s efficacy. The focus of this analysis is primarily on how the pheromone map, 2D and 3D, of ant-based methods, can be used for this hyper-heuristic task. 2D pheromone maps are the predominant pheromone map type used by ant-based algorithms. Thus the comparison here is between the existing 2D pheromone map and the newly introduced 3D pheromone map. The analysis consists of multiple experiments with algorithms in the TSP and 1DBPP domain which are assessed in terms of optimality and generality. The results of the experiment demonstrate key differences in performance between the two different pheromone spaces. The 3D pheromone map showed better generality and optimality in the 1DBPP domain whereas the 2D pheromone map showed better generality and only marginally better optimality for the TSP domain. The analysis indicated that the different pheromone maps work most optimally for different types of optimisation problems. The hybrid method showed some improvements in generality but showed little improvements in optimality overall.