I'm reviewing the paper of Dorigo & Gambardella (1997) on the ant colony system (ACS). There are two pheromone updating rules: local updating and global updating. However, I'm not finding it clear how each should be applied.
Local updating
As far as I can tell there are 3 options:
Which option is the intended one?
Global updating
It is also not clear from the text (equation 4, p.56) and the appendix if the pheromone evaporation part of the updating rule applies to all edges or only those on the global best tour.
Do all edges suffer from evaporation under the global updating rule?
Edit
I have since found this GitHub repository which seems to contain Dorigo's original code where the following rules appear to take place:
Which is even more confusing as it suggests that double (or even triple) evaporation is taking place.
The implementation of Ant Colony System for the Travelling Salesman Problem present in the Clever Algorithms book (by Jason Brownlee) claims to be based on the Dorigo(1997) paper. According to the code included the pheromone update process goes as follows:
In this implementation the pheromone update process happen for all the ants and all its solution components (and the corresponding pheromone matrix cells). I ported the algorithm to Java and I got solutions close to the optimal, so the proposed procedure seems to work.