Note: This post was originally published on AH’s Blog (WordPress) on May 18, 2014, and has been migrated here.

Ants are fascinating creatures. Their cooperation and coordination are genuinely impressive, and these behaviors pushed scientists to study how they communicate and self-organize to accomplish complex tasks.

Stigmergy and Pheromone Trails

Stigmergy is the indirect communication mechanism ants use to influence each other’s behavior. Rather than communicating directly, an ant modifies the environment — leaving a signal that other ants detect and act on, enabling emergent self-organization.

Biologists discovered that certain ant species use pheromone trails: chemical markers deposited along paths as ants walk. Other ants sense and follow these trails, allowing the colony to collectively navigate toward food sources and back to the nest. Critically, the amount of pheromone on a path is proportional to the number of ants using it — the more popular the path, the stronger the signal.

The Experiment

Scientists placed ants in a dynamic environment where new paths were introduced at runtime to observe the colony’s response:

Initially, there was only one path from the nest to the food source, so all ants walked it and reinforced it with pheromones. When a shorter path was added, it was expected that ants would switch immediately — but they didn’t. They continued on the longer path for many trips before eventually migrating to the shorter one.

The explanation: ants follow pheromone concentration. The longer path had accumulated far more pheromone than the newly introduced shorter path. Over time, some ants explored the new route and found it shorter, depositing fresh pheromone there. As more ants took the shorter path, its pheromone concentration grew. Meanwhile, pheromone on the longer path evaporated over several minutes, weakening its attraction until the colony fully converged on the optimal route.

Probabilistic Model

To formalize this in mathematical terms, we construct a stochastic model. Let:

• i ∈ {p1, p2} be the decision position of an ant
• a ∈ {s, l} denote the short or long path
• p_ia(t) be the probability that an ant at position i chooses path a at time t
• φ_ia(t) be the pheromone amount on path a from position i at time t

Since an ant must choose one of the two paths:

p_is(t) + p_il(t) = 1

The probability of choosing the shorter path is:

where α = 2, empirically derived from the experiment.

The evolution of pheromone concentration over time is described by differential equations:

dφis/dt = Ψ · Pjs(t − ts)  + Ψ · Pis(t)     [i=a, j=b; i=b, j=a]
dφil/dt = Ψ · Pjl(t − r·ts) + Ψ · Pil(t)    [i=a, j=b; i=b, j=a]

Where:

• Ψ is a constant
• r is the ratio between the long and short path lengths
• Ants deposit pheromone in both directions (nest → food, food → nest)

These equations inspired the use of ant colony behavior to solve minimum cost path problems on graphs.

Challenges: Building a Simple Ant Colony

Directly applying the biological behavior to graph search introduces two problems:

1. Loop generation Ants spread pheromone in both the forward and backward directions. This can create loops where pheromone accumulates, trapping ants in circular paths.

2. Ignoring short paths If a short path exists but ants are trapped in a loop, the short path’s pheromone evaporates before it can be reinforced — causing it to be permanently ignored.

The Solution: Three Behaviors

To address these issues and build a viable S-ACO (Simple Ant Colony Optimization) algorithm, three behaviors are introduced:

1. Probabilistic forward path construction via pheromone trails In the forward trip (nest → food), each ant probabilistically selects paths based on current pheromone levels deposited by previous ants. Ants do not deposit pheromone on the forward trip.

2. Deterministic backward path with loop elimination and pheromone update Upon reaching the destination, the ant memorizes the full path taken and eliminates any loops before beginning its return trip. Pheromone is deposited only on the backward (food → nest) trip, on the cleaned loop-free path.

3. Solution quality evaluation per iteration Ants record the total cost of their path. Higher-quality (lower-cost) paths receive proportionally more pheromone. Controlling the evaporation rate prevents the algorithm from converging prematurely on poor solutions.

Combining these three behaviors produces the S-ACO algorithm for finding minimum cost paths on simple graphs — the subject of the next post.

References

• Marco Dorigo and Thomas Stützle, Ant Colony Optimization (MIT Press)