liveBook · Manning

Pheromone

As explained in Algorithms Every Programmer Should Know

A chemical signal deposited by ants that influences other ants’ route choices; in ant colony optimization, a digital analogue encodes route preference.

Imagine ants searching for food. They leave a chemical trail as they travel, and later ants are more likely to follow a stronger trail. In ant colony optimization (ACO), pheromone is the digital version: a weight on a path that records how successful earlier routes were. It helps artificial ants make local choices without knowing the best complete route in advance. section 8.0 section 8.1

Pheromone is only part of the decision. An ant also considers a path’s heuristic desirability, calculated here as 1 ÷ distance. For each unvisited destination, it multiplies pheromone by desirability, then divides that score by the sum of all available scores. The result is a set of selection probabilities—not an instruction to always take the strongest trail. section 8.1 section 8.4

A first choice from the nest

Suppose three paths have distances of 10, 15, and 20, and each starts with pheromone 1. Their scores are 0.10, about 0.067, and 0.05. Dividing each by their total, about 0.217, gives selection chances of roughly 46%, 31%, and 23%. The shortest path is favored, but the others can still be explored. section 8.1

Table 8.1 Calculating the initial path probabilities for an artificial ant leaving the Nest (Node A)
Available path
Distance
Heuristic
Pheromone
Raw Score
Nest to Crumb B
10
0.10
1
0.10
Nest to Crumb C
15
0.067
1
0.067
Nest to Crumb D
20
0.05
1
0.05
Total Sum
 
 
 
0.217

Compare the three starting paths’ distances, equal pheromone weights, and resulting scores before converting them to probabilities. section 8.1

After ants complete their tours, the weights change. Evaporation reduces pheromone across the graph; deposit adds it back to edges an ant actually used. A shorter completed tour receives a larger deposit than a longer one. Together, these steps reinforce useful routes while allowing older trails to fade, helping the swarm balance following promising paths with exploring alternatives. section 8.1 section 8.4

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

Follow one update: evaporation lowers every starting weight from 1 to 0.5; traversed edges then receive a 1.67 deposit, while ignored edges remain at 0.5. section 8.1

The same idea supports tours through multiple cities and adaptive network routing. In both cases, pheromone carries experience from earlier trips into the next local choice. That experience improves the search without promising a mathematically perfect route. section 8.2 section 8.4

How Algorithms Every Programmer Should Know covers it

How deep it goes
Works through probability scores and an evaporation-and-deposit update, then connects the mechanism to pseudocode and Python.
Examples
Uses a nest-and-food graph, a three-path probability calculation, a 60-mile tour update, city tours, and telecommunications routing.
What it assumes
Starts with a foraging analogy and small graph; introduces pheromone and the distance heuristic before calculating probabilities.
What you can do after
Build it from scratch in Python by weighting path choices and updating pheromone after completed tours.
How it connects
Links pheromone to distance heuristics, probabilistic selection, evaporation, positive feedback, and exploration versus exploitation.

Also explained in

Compare how 3 books explain pheromone →

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.