MMAS ant algorithm

Greetings to all readers. Today I will try to continue a series of fairly rare articles on natural algorithms. In particular, this article will be devoted to the modification of the ant algorithm, known as the Max-Min Ant System (MMAS). I will tell you about the differences from the classical ant algorithm and the reasons for making such modifications. Details under the cut.

Instead of the preface

A few years ago, an article entitled “Ant Algorithms” was published on Habré, in which the original Dorigo ant algorithm was described in some detail. Those who are not familiar with the algorithm, I recommend reading this article, in it, by the way, a number of modifications of the algorithm are listed. Now a little about the promised MMAS algorithm for the traveling salesman problem.

Idea

The MMAS algorithm is a kind of superstructure over the ACO algorithm (Ant Colony Optimization, Dorigo and Stutzle, 2004). According to the ACO algorithm, ants are independent agents and interact with each other only through a pheromone located on the paths of ants (on the edges of the graph). At the first launch, an initial amount of pheromone is applied to each edge, which then varies depending on how often the ants walk along the edges.


')
p is the evaporation coefficient of pheromone, F is the reciprocal of the cost of the best solution. And, in fact, a modification of the algorithm: the amount of pheromone lies in the interval .
Further, in order to provide ants with the opportunity to visit even the most unattractive edges, the following formula from the classical ant algorithm is applied:



For readers who are familiar with the ant algorithm, there should be nothing new in this formula, but I’ll send the rest to read the article about the classical algorithm.

Now add another modification proposed by Dorigo and Gambardello (Dorigo and Gambardella, 1997).



Here I will explain a little more detail. To save the best path in the graph are used "greedy" ants. Their share in the total number of ants is equal to q , that is, the path that an ant will take is determined by formula (3). The peak to which the ant goes further is selected from all adjacent unvisited vertices so that its appeal is greatest. Accordingly, 0 < q <1 is the probability that the current ant is greedy, and with probability 1 - q the ant behaves in a standard way. The coefficient q , like all the others, is determined experimentally.

Explanation

The modification associated with pheromone restriction, like the algorithm itself, fits very well with the natural laws of nature. It is intuitively clear that the amount of pheromone in real conditions cannot grow all the time. At some point, the evaporation rate of the pheromone becomes equal to the rate of pheromone renewal, and the rate of change of the amount of pheromone is not constant, but using such a function will greatly increase the execution time, so it is optimal to simply set the maximum value of the amount of pheromone. The situation is similar with the lower bar of the amount of pheromone. The values ​​of the constraints affect the efficiency of the algorithm and, as you already guessed, are selected experimentally.

Thanks for attention.

Literature

Dorigo M., Stutzle T. (2004) Ant Colony Optimization. MIT Press, Cambridge, MA
Pellegrini P., Stutzle T, and Birattari M. (2011) A Critical Analysis of the Parameter Adaptation in Ant Colony Optimization. IRIDIA - Technical Report Series