liveBook · Manning

Ant colony optimization

As explained in Algorithms Every Programmer Should Know

A metaheuristic inspired by ant foraging in which artificial agents explore solutions and use simulated pheromone trails to reinforce promising choices.

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

How Algorithms Every Programmer Should Know covers it

How deep it goes
Works through weighted path choices and pheromone updates, then provides pseudocode and Python implementation without guaranteeing an optimum.
Examples
Uses a small distance graph, weighted-choice tables, a 60-mile pheromone update, and traveling salesperson and telecommunications routing scenarios.
What it assumes
Introduces pheromone and inverse-distance heuristics through a small graph before moving to pseudocode and Python.
What you can do after
Build it from scratch using the Python examples to construct tours, update pheromones, and tune the search for strong routes.
How it connects
Connects swarm intelligence and probabilistic search to the traveling salesperson problem, dynamic programming, and the exploration–exploitation tradeoff.

Also explained in

Compare how 3 books explain ant colony optimization →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.