Ants find short routes

Ant colony optimization Real ants mark their way with pheromone. Short routes get more pheromone because ants walk them more often. Here every ant builds a round trip through all cities. At each step it prefers a near city and an edge with a strong trail. After each iteration the trails fade a little, and every ant adds pheromone to its own tour. Short tours add more. Wikipedia

Travelling salesman problem Find the shortest round trip that visits every city once. The problem is hard: the number of tours grows faster than any power of the city count. Ant colonies give good tours, not always the best one. The baseline is the nearest-neighbor tour: always go to the closest unvisited city. Lengths are in world units (the canvas is 1000 x 1000), not pixels. Wikipedia

Original work

• Marco Dorigo, Vittorio Maniezzo, Alberto Colorni (1996): Ant System: Optimization by a Colony of Cooperating Agents

How it works

Each iteration every ant builds a tour with a roulette wheel. From city i it goes to the unvisited city j with a probability proportional to tau(i,j)^alpha * (1/d(i,j))^beta. Then all trails evaporate and every ant deposits pheromone on its edges.

• The weights tau^alpha * (1/d)^beta are computed once per iteration, so each ant only adds numbers.
• Evaporation multiplies every trail by (1 - rate). A tiny floor keeps all probabilities above zero.
• An ant with a tour of length L adds 1/L to each of its edges, in both directions.
• A new city gets the mean trail of the old matrix. The best tour is repaired by cheapest insertion, so the colony does not start from zero.
• Drawing uses Canvas 2D with requestAnimationFrame outside the Angular zone. Line opacity shows the trail strength, the red line is the best tour.

Source code:ant-colony-simulation.tsant-colony.model.ts

Note Simplifications in this demo:

• This is the plain Ant System. There is no elite ant, no local search and no pheromone limits except a tiny floor.
• The ants you see move along their last tour. The tour itself is built in one step per iteration.
• Under a time limit per frame the demo drops iterations, so with many cities and ants the real speed can be lower than the slider.