A Critical Analysis of Heterogeneous Ant Colony Optimization for Combinatorial Optimization Problems

Abstract

Ant Colony Optimization (ACO) is an optimization algorithm that is inspired by the foraging behavior of real ants in locating and transporting food source to their nest. It is designed as a population-based metaheuristic and have been successfully implemented on various NP-hard problems. However, majority of the studies in ACO focused on homogeneous artificial ants although biologists suggest that real ants exhibit heterogeneous behavior thus improving the overall efficiency of the ant colonies. Equally important is that most, if not all, optimization algorithms require proper parameter tuning to achieve optimal performance. However, it is well-known that parameters are problem-dependant as different problems or even different instances have different optimal parameter settings. One method to mitigate this is to introduce heterogeneity by initializing the artificial agents with indi vidual parameters rather than colony level parameters. This allows the algorithm to either actively or passively discover good parameter settings during the search. Unfortunately, very little research has been conducted that adopts the heterogeneous approach. This paper conducts a critical review of ACO algorithms that integrates heterogeneity in their solution as well as providing a basis for our implementation.