H-ACO: A Heterogeneous Ant Colony Optimisation approach with Application to the Travelling Salesman Problem

Abstract

Ant Colony Optimization (ACO) is a field of study that mimics the behaviour of ants to solve computationally hard problems. The majority of research in ACO focuses on homogeneous artificial ants although animal behaviour research suggests that heterogeneity of behaviour improves the overall efficiency of ant colonies. Therefore, this paper introduces and analyses the effects of heterogeneity of behavioural traits in ACO to solve hard optimisation problems. The developed approach implements different behaviour by introducing unique biases towards the pheromone trail and local heuristic (the next hop distance) for each ant. The well-known Ant System (AS) and Max-Min Ant System (MMAS) are used as the base algorithms to implement heterogeneity and experiments show that this method improves the performance when tested using several Travelling Salesman Problem (TSP) instances particularly for larger instances. The diversity preservation introduced by this algorithm helps balance exploration-exploitation, increases robustness with respect to parameter settings and reduces the number of algorithm parameters that need to be set.