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.

AS for the TSP

The AS algorithm can be described as follows:

  • A tour of a single ant includes every city of the TSP only once
  • During tour construction the ant chooses the next city based on a probability which is anti-proportional to the distance to the next city, and proportional to the amounts of pheromones already deployed on this path.
  • At the end of each tour, pheromones are deployed anti-proportional to the length of this tour

After every iteration (a number of ants each perform a whole tour), local search might be applied to optimize the solution.
Posted by Nicolaus Correll on Monday 7 February 2005 at 16:21