Ant Colony Optimization

The Simplest Explanation

Real ants find food with two tiny rules: deposit pheromone where you walk and prefer stronger trails. Shorter paths get round-tripped faster → more pheromone per minute → attract more ants → even more pheromone. The colony as a whole converges on the short route though no individual ant knows anything about it.

Ant Colony Optimization (Dorigo, 1992) ports this to graph problems like TSP.

Emergence Context

ACO is a swarm intelligence method — complex collective behavior from simple local rules. Sibling phenomena: Conway's Game of Life (gliders from four trivial rules), flocks, termite mounds, brains. No central controller; the pattern emerges.

The ACO Algorithm for TSP

Place m ants on n cities at random. Each ant constructs a full tour in n steps. Ant k at city i picks next city j with probability:

$P_{ij}^k(t) = \frac{[\tau_{ij}(t)]^\alpha \cdot [\eta_{ij}]^\beta}{\sum_{l \in \text{allowed}} [\tau_{il}(t)]^\alpha \cdot [\eta_{il}]^\beta}$

• $\tau_{ij}$ = pheromone on edge (i,j) — collective memory
• $\eta_{ij} = 1/d_{ij}$ = visibility — greedy pull toward near cities
• α, β weight trail vs visibility
• "allowed" excludes already-visited cities (no premature cycles)

Greedy stochastic construction: prefers near AND well-traveled, but never deterministic.

Pheromone Update

After all m ants complete tours, in two steps:

Evaporation (trails fade):

$\tau_{ij}(t+n) = (1-\rho)\,\tau_{ij}(t)$

Deposition (each ant k reinforces every edge of its own tour):

$\Delta\tau_{ij}^k = \frac{Q}{L_k}, \qquad \tau_{ij}(t+n) = (1-\rho)\tau_{ij}(t) + \sum_{k=1}^{m}\Delta\tau_{ij}^k$

where $L_k$ = length of ant k's tour. Shorter tours deposit MORE per edge — reward inversely proportional to cost.

Why Shorter Paths Win

If an obstacle splits an ant column into a short and long detour, both sides get traffic initially. But ants on the short side complete round trips faster, depositing pheromone at a higher rate. Positive feedback amplifies the advantage until nearly all traffic takes the short path.

Properties