Ant colony-based algorithms solve static problems and provide a high degree of flexibility and robustness in dynamic environments. The colony adapts to sudden changes in the environment and continues to function when certain individuals fail to complete their task.
The principle of an ant colony is simple. Ants are able to select the shortest route from the nest to a food source through pheromone deposition and tracking. These are deposited by the ants on their way. An ants tend to follow the trail with the highest pheromone impact. Pheromones dissipate over time (not in all versions of the algorithm). We therefore conclude that after a time, the ants will choose all the shortest tracks between the nest and the food.
Ant colony optimization
The algorithm was introduced by M. Dorigo in 1991, initially intended for the TSP (traveling salesman). We represent the problem to be solved in the form of finding a shortest path in a graph.
ACO type algorithms have proofs of convergence that will not be shown in this course.
Initialization (case of TSP)
The m ants are distributed randomly on the not cities. For each ants, a taboo list is assigned to it, it contains its starting list. Pheromone tracks are initialized to a value vs positive not zero. Each edge of the graph ij has its pheromone track noted Tij= c.
Construction of the solution and local search
The choice is random according to a probability where two parameters To and b control the relative importance of visibility and the amount of pheromones. Yes b = 0, the closest cities are more likely to be selected, it is a greedy algorithm. Yes a = 0, only the amplification of the pheromones acts, there is premature convergence and non-optimal results. The new city is added to the taboo list of the ants.
Each ants proceeds in this way until they go through all the towns.
End of a cycle
For each ants k, we calculate the length of his turn THEk(t) then we empty its taboo-list (except initialization).
Evaporation from the track is calculated directly in the previous formula. Indeed p represents the persistence of the track, that is to say the memory of the quantity of pheromones which one keeps for the following cycle. Yes p = 1, there is no evaporation therefore no limitation of the autocatalytic phenomenon. Yes p = 0, the system has no memory, only the last cycle performed is taken into account.
For each ants k passing through the ridge ij, it increases the quantity of pheromone deposited according to the following calculation:
The smallest lap is kept in memory if it is better than the last one to memorize. The ants start a cycle again from their initial city (kept in their taboo list).
Algorithm variants: MMAS
The Max-min ant system (MMAS) is an efficient variant of the algorithm. Only the best ants trace trails where the deposition of pheromones is limited by an upper bound and a lower bound. Thus we prevent a track from being too reinforced and we leave the possibility of exploring any track. In particular, this prevents premature convergence.