Ant Colony Optimization
Studies have shown that over time ants will be able to find the shortest path in between the location of their colony and their food source. The mathematics behind this phenomenon is known as the ant colony optimization algorithm. This algoritm is also a solution of the traveling salesman problem, which are both optimization problems.

Imagine a space which includes both an ant colony and food. The area is divided into a number of vertices. In the model, an ant is only able to walk from vertex to vertex in order to reach the food. At each vertex, the ant has to choose via which route he continues.

In the journey to the source of food, each ant will leave behind a pheromone trail. An ant which leaves from a vertex is more likely to choose the path with the highest concentration of pheromone to continue his journey. Although, some ants won't choose the path with the highest pheromone concentration. This encourages exploration of the area. If there exist a shorter path, eventually some ant will find it. The probability for an ant to move from some node i to another node j is obtained:

Ant Colony Optimization algorithm

In this equation, τ is the pheromone variable and η a heuristic variable. The heuristic variable represents a short term quality measure, in this case the distance between two vertices. The relative importance between the pheromone and heuristic variables are set by α and β.

The pheromone trail will evaporate over time. This causes the previous, less optimal, path to fade when a shorter path is found. To model the decreasing amount of pheromones a forgetting factor ρ is introduced, which decreases the pheromone level in each iteration:

Ant Colony Optimization algorithm pheromone level

In the above equation, the first term is the residual pheromone level after evaporation. The last term is the pheromone level added by the ants who have just walked over route ij.