Ant Based Hyper Heuristics with Space Reduction: A Case Study of the p-Median Problem

Recent years have witnessed great success of ant based hyper heuristics applying to real world applications. Ant based hyper heuristics intend to explore the heuristic space by traversing the fully connected graph induced by low level heuristics (LLHs). However, existing ant based models treat LLH in an equivalent way, which may lead to imbalance between the intensification and the diversification of the search procedure. Following the definition of meta heuristics, we propose an Ant based Hyper heuristic with SpAce Reduction (AHSAR) to adapt the search over the heuristic space. AHSAR reduces the heuristic space by replacing the fully connected graph with a bipartite graph, which is induced by the Cartesian product of two LLH subsets. With the space reduction, AHSAR enforces consecutive execution of intensification and diversification LLHs. We apply AHSAR to the p-median problem, and experimental results demonstrate that our algorithm outperforms meta heuristics from which LLHs are extracted.