algorithmant-colony

How are the pheromone rules applied in the ant colony system?


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:

  1. Update as an ant builds a tour, i.e. after moving to a new city. (As suggested in the text on p.56)
  2. Update after an ant has built a tour, before the next ant begins. (As suggested in Fig. 3 on p.55)
  3. Update after all ants have built a tour. (As specified in Appendix A and would make the algorithm the most parallelisable as it claims to be).

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:

  1. Local updating (evaporation + depositing) as each ant transitions to a new city (i.e. option 1 above).
  2. Global evaporation of all edges (or only close cities if certain flags are set).
  3. Global updating (evaporation + depositing) along only the global best tour.

Which is even more confusing as it suggests that double (or even triple) evaporation is taking place.


Solution

  • 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.