Intelligent Ant Colony System for Traveling Salesman Problem and Clustering

Abstract

Processes that simulate natural phenomena have successfully been applied to a number of problems for which no simple mathematical solution is known or is practicable. Such meta-heuristic algorithms include genetic algorithms, particle swarm optimization and ant colony systems and have received increasing attention in recent years. This work parallelizes the ant colony systems and introduces the communication strategies so as to reduce the computation time and reach the better solution for traveling salesman problem. We also extend ant colony systems and discuss a novel data clustering process using Constrained Ant Colony Optimization (CACO). The CACO algorithm extends the ant colony optimization algorithm by accommodating a quadratic distance metric, the Sum of K Nearest Neighbor Distances (SKNND) metric, constrained addition of pheromone and a shrinking range strategy to improve data clustering. We show that the CACO algorithm can resolve the problems of clusters with arbitrary shapes, clusters with outliers and bridges between clusters