Niching for ant colony optimization

Ant Colony Optimization (ACO) is a relatively new class of algorithm inspired by the foraging behaviour of biological ants that has shown promise for application to optimization problems. The ability of ACO algorithms to solve more difficult artificial problem instances is an important result for researchers, as these are often more akin to industrial (real-world) applications. While most ACO algorithms are able to find a single (or few) optimal, or near-optimal, solution to difficult (NP-hard) problems, these solutions are often located in the same neighbourhood of solution space. A small change to the problem can have a large impact on a specific solution by decreasing its quality, or worse still, by rendering it infeasible. Over the past 20 years, niching methods, such as fitness sharing and crowding, have been implemented with success in the field of Evolutionary Computation (EC). Such niching methods try to simultaneously locate and maintain multiple optima to increase search robustness - typically in multi-modal function optimization. In this paper it is shown that a niching technique applied to an ACO algorithm permits the niching ACO algorithm to simultaneously locate and maintain multiple areas of interest in the search space, with minimal impact on the quality of solutions found.