In TSP, a solution is a permutation (tour). Each ant builds a tour by visiting each city exactly once. From the current city , the feasible next cities are the unvisited ones:
The effects on probabilities is that the denominator sums only over . As the tour grows, the candidate set shrinks.
Ideally, we would have something like this happen:
- Early iterations: Pheromone levels are nearly uniform. Ant decisions are dominated by heuristic information. Many different tours are sampled, resulting is diversity.
- Mid iterations: Some edges appear frequently in good tours. Pheromones begin to differentiate edges. Ants start to share partial subpaths: Exploration and exploitation co-exist.
- Late iterations: A small set of tours dominate, with most ants re-using the same edges. Improvements become incremental, exploiting high-quality solutions.
Example
Framework
