Slide 10 of 41
Notes:
Distances are 1 or 0.5 in graph.
Consider discretized intervals t=0, 1, 2.
Suppose that 30 new ants come from A to B every time unit and 30 from E to D. Each ant walks at a speed of 1 per time unit, and that an ant lays down at time t a pheromone of intensity 1 while walking and that this evaporates completely and instantaneously in the middle of time intervals (t+1, t+2).
At t=0, there is no trail yet but 30 ants are in B and 30 in D. Their choice of direction is random. Therefore, on average 15 will go to H and 15 to C.
At t=1, the 30 new ants come to B from A and find a trail of intensity 15 on the path that leads to H, laid by the 15 ants that went that way from B, and a trail of intensity 30 on the path to C obtained as the sum of the trail laid by the 15 ants that went that way from B and by the 15 ants that reached B coming from D via C. The probability of choosing a path is therefore biased, so that the expected number of ants going towards C will be double that of those going towards H. The same is true for the new 30 ants in D which came from E.
Process continues until all ants choose the shortest path. The idea is that if at a given point an ant has to choose among different paths, those which were heavily chosen by preceding ants are chosen with higher probability.
This is an example of an autocatalytic process.
