An Early Exploratory Method to Avoid Local Minima in Ant Colony System

Abstract

Ant Colony Optimization (ACO) is a famous technique for solving the Travelling Salesman Problem (TSP.) The first implementation of ACO is Ant System. Itcan be used to solve different combinatorial optimization problems, e.g., TSP, job-shop scheduling, quadratic assignment. However, one of its disadvantages is that it can be easily trapped into local optima. Although there is an attempt by Ant Colony System (ACS) to improve the local optima by introducing local pheromone updating rule, the chance of being trapped into local optima still persists. This paper presents an extension of ACS algorithm by modifying the construction solution phase of the algorithm, the phase that ants move and build their tours, to reduce the duplication of tours produced by ants. This modification forces ants to select unique path which has never been visited by other ants in the current iteration. As a result, the modified ACS can explore more search space than the conventional ACS. The experimental results on five standard benchmarks from TSPLIB show improvements on both the quality and the number of optimal solutions founded.