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 ant colony is simple. Ants are able to select the shortest way to get from the nest to a food source by depositing and following pheromone trails. These are deposited by ants on their way. An ant tends 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 all choose the shortest path between the nest and the food.
Ant colony optimization
The algorithm was introduced by Mr. Dorigo in 1991, initially intended for the TSP (travelling salesman). We represent the problem to be solved in the form of the search for 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 ant, a taboo list assigned to him, it contains his start list. Pheromone trails 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 nearest cities are more likely to be selected, this is a algorithm gluttonous. Whether 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.