An online step-by-step pheromone update deposits pheromone on each edge while an ant incrementally constructs a candidate solution. Strengthened trails increase the probability that later ants choose those edges, linking construction with collective search. section 10.2 section 10.6
The update operates within the broader ACO cycle:
- Evaporate existing pheromone before depositing new trail; evaporation prevents permanent commitment to one route. section 10.2 section 10.6
- Deposit pheromone immediately on every traversed edge during solution construction. section 10.2
- Choose the deposit rule: ant density adds a constant Q, while ant quantity makes deposition proportional to local edge quality, such as Q/dij. section 10.2
- Balance reinforcement against exploration: no evaporation can trap ants in a local optimum, whereas maximal evaporation forces largely random exploration. section 10.2
Routing interpretation
When an ant traverses an edge from node i to node j, the ant quantity model deposits Q/dij. Shorter edges therefore receive stronger reinforcement, while the ant density model rewards edges selected by more ants without considering edge length. section 10.2
Figure 10.5 Pheromone update methods
Compare online step-by-step deposition with delayed pheromone updating after a complete solution has been constructed. section 10.2 section 10.6
