The Ant System: TSP
Choose next town to go to with probability that is a function of distance of town and amount of pheromone on edge.
Legal tours are “forced” by use of a tabu list; an ant can only visit a town once. Each ant has its own “tour memory”.
When the tour is complete, a pheromone is laid down on the trail.
Iteration is defined to be m moves -- one by each ant. Tour complete in n moves I.e. n iterations.
Tij = pheromone intensity on edge
bi(t) = # ants at ith town at t
(1 - e) = evaporation rate
Tij(t+n) = e Tij(t) + d Tij
d Tijk= Q/Lk (on route, else 0)
[Dorigo ‘92] and later...