A new pheromone update strategy for ant colony optimization

Abstract

Ant system (AS), the first Ant Colony Optimization algorithm (ACO), was proposed by mimicking the foraging behavior of real ants. The inspiring source of ACO is the pheromone laying and following behavior of real ants. The pheromone serves as numerical information to reflect ants’ experience accumulated. However, tests on AS indicate that its pheromone update method can’t always retain the ants’ useful search experiences which mainly refer to the better solutions found. In this study we propose a new pheromone update strategy that uses the Traveling Salesman Problem (TSP) as the instance problem. The idea is to update the pheromone on each edge in TSP by a variable termed component best solution (CBS) matrix, which stores the length of the best tour found for each edge. Simultaneously, the importance of pheromone is strengthened gradually by augmenting the value of its exponent. To investigate its effectiveness, comparisons of experiments are conducted among AS, Elitist ACO and the new algorithm (CBSACO) on five TSP instances. Results show that the performance of CBSACO outperforms that of AS and Elitist ACO. Because this modification to AS is based on the pheromone update method, it can be easily transferred to other combinatorial optimization problems.