Ants in action

What have ants to do with finding best solutions? Well, ants can find the shortest way to the food being almost blind. How? Because of their cooperation and smell. They leave pheromone when they move. When deciding where to go, they choose the direction where the pheromone smell is the strongest.

In a computer algorithm, each simulated ant also has to choose its direction of movement. It takes into account two factors: intensities of pheromones (maximized) and distances to next locations (minimized). While moving, each ant leaves the pheromone.

Although each ant is independent, it unconsciously affects the behavior of other ants. This is how the pheromone gradually marks the globally optimal (shortest) path.

The program below (click and choose your language) demonstrates the ant algorithm. Green lines correspond to the intensity of pheromone, and the black line is the shortest path found so far.

The ant algorithm can be used to solve various optimization problems, not just the problem of finding the shortest path (called the Traveling Salesman Problem).