Niching for ant colony optimization.pdf

Niching for Ant Colony Optimization Technical Report: TR006 Daniel Angus dangus@.au Complex Intelligent Systems Laboratory Centre for Information Technology Research Faculty of Information Communication Technologies Swinburne University of Technology Melbourne, Australia Niching for Ant Colony Optimization Daniel Angus Complex Intelligent Systems Laboratory Centre for Information Technology Research Faculty of Information Communication Technologies Swinburne University of Technology Melbourne, Australia dangus@.au Abstract. 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 opti- mization 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 simul- taneously locate and maintain multiple areas of interest in the search space, with minimal impact on the quality of solutions found. 1 Introduction In natural ecologies, a population of organisms is rarely spread uniformly (within an environment), but rather is typically distributed ac