Pheromone update reinforces solution components chosen by ants. Each update evaporates existing pheromone and deposits new pheromone, so better paths gradually attract more ants while evaporation preserves exploration. section 10.2 section 10.6
A practical update proceeds in these stages:
- Initialize pheromone values, often equally across paths or edges. section 10.2
- Construct ant solutions using pheromone concentration and, where applicable, transition probabilities or heuristic information. section 10.2 section 10.3.3
- Evaporate pheromone by decreasing its concentration at rate ρ; low evaporation can trap the search, while maximum evaporation forces random exploration. section 10.2
- Deposit pheromone on selected components, either during construction or after evaluating a completed solution. section 10.6
- Choose the depositing ants according to the ACO variant: ACS uses the global-best solution, while MMAS uses the iteration-best path and bounds pheromone values. section 10.3.3 section 10.6
Shortest-path update
Suppose an ant constructs the path 1 → 3 → 4 → 5 with length 11. With Q = 1, delayed deposition reinforces edges {1,3}, {3,4}, and {4,5} by Q/L = 1/11 after evaporation. Repeating this process over three iterations identifies the shortest path in the toy graph. section 10.3.1
Figure 10.5 Pheromone update methods
Compare online step-by-step and delayed pheromone update methods in a single visual overview. section 10.2
