2

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.

Glorfindel
  • 21,988
  • 13
  • 81
  • 109
James
  • 65,548
  • 14
  • 155
  • 193

2 Answers2

2

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:

  • The local pheromone update process is triggered after an Ant has finished building a solution. This process has an specific pheromone evaporation ratio and it is not dependant on the solution quality.
  • The global pheromone update process is located at the end of the iteration, when all the ants of the colony have built a solution. This phase works with a different evaporation ratio and it is dependant on the quality of the solutions.

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.

Carlos Gavidia-Calderon
  • 7,145
  • 9
  • 34
  • 59
0

Do all edges suffer from evaporation under the global updating rule?

Yes.

The Idea is that the path that is taken by more ants (short path) will have more pheromone and thus will be taken by even more ants, and ultimately every ant will take that path only. So, after sometime, pheromone will get evaporated (just like it does in natural process), so you have to simulate the evaporation by decreasing the pheromone content.

Haris
  • 12,120
  • 6
  • 43
  • 70
  • Thanks, that makes sense, but the appendix left this bit out and confused me. I've since found some code, in the edit to the question, that looks like it was written by Dorigo. It seems the implementation is different further still in that global best tour edges get double evaporation. – James Mar 28 '16 at 12:54