A Study of Ant-Based Pheromone Spaces for Generation Perturbative Hyper-Heuristics

Recent work has shown the potential of ant algorithms for generation constructive hyper-heuristics. This paper extends the previous research by presenting a novel ant algorithm that is used to drive the heuristic search for a generation perturbative hyper-heuristic, the other type of generation hyper-heuristic. The ant-based generation perturbative hyper-heuristic is presented and compared against existing heuristics in two combinatorial domains, the movie scene scheduling and capacitated vehicle routing problems, to assess the heuristic generation efficacy. The comparison is further extended by assessing the effect of different pheromone maps (1D, 2D and 3D) on the ant-based hyper-heuristic, an important factor in the previous study. The results showed that, in both domains, the hyper-heuristic was able to generate perturbative heuristics that were competitive or better than the existing heuristics. Furthermore, the type of pheromone map was relevant to the hyper-heuristic performance as the 3D map performed best for the first domain and the 1D map for the second, confirming the trend shown in previous research, as well as the validity of ant algorithms for generation perturbative hyper-heuristics.