Cette page appartient aux archives web de l'EPFL et n'est plus tenue à jour.
This page belongs to EPFL's web archive and is no longer updated.

ACS for the TSP

Ant Colony System (ACS) for the Traveling Salesman Problem (TSP)

Local pheromone update: While in AS the pheromone level on the graph is only increasing (except for evaporation), ACS explicitly diminuishes the pheromone level on every edge that is part of a tour. By this, exploration of unvisited edges is favored, and the side-effect of positive feedback that all ants stagnate on a poor initial solution reduces.

Transition rule:Different to Ant System (AS), ACS allows for tuning the rate between exploration and exploitation not only via the exponent of the heuristic (distance) and pheromone metric, but by introducing an explicit random choice between favoring the best known choice, and a probabilistic decision as in AS.

Pheromone trail update and candidate list: In contrast to AS where all ants are allowed to deploy pheromones, in ACS only the best ant of an iteration is allowed to deploy a pheromone. Also, ants are bound to choose from a limited set of neighboring cities that has been initially determined on heuristic information, for instance by choosing only n nearest cities as candiates.

In AS, the latter two improvements are picked up by Elitist AS, and maintained in Rank-Based AS and Max-Min AS.
Posted by Nicolaus Correll on Monday 7 February 2005 at 16:49