liveBook · Manning

Pheromone deposit

As explained in Algorithms Every Programmer Should Know

An ant colony optimization operation that adds pheromone to traversed edges in proportion to a reward and inversely to tour distance.

In ant colony optimization (ACO), a pheromone deposit is positive feedback: after an ant completes a tour, it adds pheromone to the edges it traversed. The deposit decreases as tour distance increases, so shorter tours strengthen their edges more. 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

For a 60-mile tour, the example adds 1.67 pheromone to traversed edges after evaporation, bringing their weights to 2.17; untouched edges fall to 0.5. section 8.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Calculates deposits inversely to tour length and restricts them to edges traversed by that ant.
Examples
Uses a 60-mile tour to illustrate a 1.67 deposit and resulting edge weights of 2.17 or 0.5.
What you can do after
Apply a reward divided by tour distance to the edges traversed by a completed ant tour.
How it connects
Connects ant colony optimization with pheromone evaporation as complementary feedback.

Also explained in

Compare how 2 books explain pheromone deposit →

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.