A study of pheromone maps for ant colony optimization hyper-heuristics

Abstract

In recent years, there has been an increasing development of hyper-heuristics in the field of combinatorial optimisation. Broadly speaking, the term hyper-heuristic refers to a technique or algorithm that aims to provide a more generalised solution to, usually, a combinatorial problem. Hyper-heuristics differ from other combinatorial solution methods by working primarily in the heuristic space, as opposed to the solution space, to create more generalisable solutions for problems. There are four types of hyper-heuristics: generation constructive (GC), generation perturbative (GP), selection constructive (SC) and selection perturbative (SP). Each type functions by either generating new heuristics or by selecting which existing heuristics to apply to a problem. They are further delineated by whether the hyper-heuristic is constructive or perturbative with the former making solutions from scratch and the latter modifying and refining existing solutions.

Despite increasing research into hyper-heuristics, one area where research has been lacking is in the use of ant algorithms by hyper-heuristics to drive the search through the heuristic space. While there have been some investigations into the employment of ant algorithms by hyper-heuristics, a comprehensive study into the use of ant algorithms and in particular their central search mechanism, the pheromone map, has largely not been done. This research endeavours to investigate and study the use of ant algorithms by the four different types of hyper-heuristic to search the heuristic space. The goal is to improve the employment of ant algorithms by hyper-heuristics through the study of how the pheromone map can be used to explore the heuristic space.

A general ant algorithm for searching the heuristic space (HACO) was presented and extended for each of the four types of hyper-heuristics. This investigation specifically focused on examining the impact that using different pheromone maps (1D, 2D and 3D) would have on the ant algorithms used by the hyper-heuristics. Furthermore, a hybrid algorithm (HACOH), one that combines multiple HACO algorithms with their pheromone maps, was presented to improve upon the use of the different pheromone maps.

The proposed algorithms (HACO and HACOH) were evaluated in multiple problem domains based on their use as one of the four hyper-heuristics. The SC and SP experiments were performed in the quadratic assignment problem (QAP) and movie scene scheduling problem (MSSP) domains. The GC experiments were conducted in the one-dimensional bin packing problem (1BPP) and MSSP domains and finally, the GP experiments were conducted in the capacitated vehicle routing problem (CVRP) and MSSP domains. These algorithms were assessed primarily in terms of optimality and generality although consideration of runtimes and comparisons with existing heuristics was included as well.

The results showed that there were statistically significant differences between the different pheromone maps when used in ant-based hyper-heuristics across a wide number of the problem domains. The only exception was the SC-MSSP experiments where differences were observed but not significant. In these experiments, at least one type of pheromone map emerged as suboptimal for use in the hyper-heuristic in the problem domain. It was not always the case that a single type of pheromone map would predominate over the others, but the results indicated clear delineations between better or worse pheromone maps to use in hyper-heuristics across the domain experiments. The HACOH algorithm showed some promise in use in the generation hyper-heuristics, in the 1BPP and MSSP domains, but was generally inferior to a non-hybrid HACO algorithm in the majority of the experiments, indicating that the hybrid algorithm is not universally superior to its non-hybrid counterparts.

These results have met the research objectives of this thesis by showing that, firstly, ant algorithms can be employed successfully, by all four types of hyper-heuristics. More importantly, however, the results showed that there are meaningful differences between the use of the different pheromone maps in ant-based hyper-heuristics and that choosing the optimal map for an ant-based hyper-heuristic depends on the problem domain among other factors.