Imagine planning a round trip through many cities. Checking every possible tour soon becomes impractical, but always choosing the nearest city may miss a better route. Ant colony optimization (ACO) looks for a good tour without promising the perfect one. It borrows an idea from foraging ants: useful trails attract followers, while unused trails fade. section 8.0 section 8.2
Each artificial ant builds a tour through a graph. At every stop, it considers only unvisited nodes and weighs two clues: the next edge’s pheromone level, representing earlier success, and its heuristic desirability, typically 1 ÷ distance. It then makes a weighted random choice. A promising edge is more likely to be chosen, not guaranteed to be chosen. section 8.1 section 8.2
The first choice
Suppose three available edges have distances of 10, 15, and 20, and each starts with pheromone 1. Their raw scores are 0.10, about 0.067, and 0.05. Divide each by their total, about 0.217, to get selection chances of roughly 46%, 31%, and 23%. The shortest edge leads, but another edge can still be explored. section 8.1
A run repeats this feedback loop:
- Initialize distances and equal pheromone levels; set the number of ants, iterations, evaporation rate, and reward. section 8.1
- Let each ant choose among unvisited nodes, complete its tour, and measure the total distance. section 8.1 section 8.2
- Evaporate pheromone across the graph, then reinforce traveled edges. Shorter tours receive stronger reinforcement, making their edges more attractive to later ants. section 8.1 section 8.2
Table 8.3 Applying the feedback loop of mandatory pheromone evaporation and reward deposit after the ant completes a 60-mile tour
|
Path status
|
Base Pheromone
|
After Evaporation
|
Deposit Added
|
Final Weight Pheromone
|
|
Traversed (A-B, B-C, C-D, A-D)
|
1
|
0.5
|
+1.67
|
2.17
|
|
Ignored (A-C, B-D)
|
1
|
0.5
|
+0
|
0.5
|
The 60-mile tour makes the feedback concrete: after evaporation, traveled edges receive a deposit and reach 2.17 pheromone, while ignored edges fall to 0.5. section 8.1
The balance matters. Too much trust in pheromone can lock the swarm onto an early, mediocre route; too much trust in distance reduces the search to nearest-choice behavior. Evaporation that is too fast forgets useful routes, while evaporation that is too slow preserves stale ones. ACO suits large or changing routing problems where a timely, strong solution matters more than a guaranteed global optimum. Its choices are probabilistic, though a fixed random seed makes identical test runs reproducible. section 8.3 section 8.1


