Ant Colony System

ACS is a stronger variant of ant colony optimization, introducing two key modifications over AS.

First, a pseudo-random proportional rule. When picking the next move, we pick the next best edge with probability $q_0$, encouraging exploration. Otherwise, we sample by probabilities (exploration).

Second, a local pheromone update during construction:

$${\tau }_{ij}\leftarrow (1-\xi ){\tau }_{ij}+\xi {\tau }_0$$

which temporarily reduces the attractiveness of recently used edges. Note that this is during construction, as the ants walk! In AS, the pheromones do not change while the ants walk, only updating after tours finish.

ACS also uses a global update, but it is used on the best-so-far tour only:

$${\tau }_{ij}\leftarrow (1-\rho ){\tau }_{ij}+\Delta {\tau }_{ij}^{\text{best}}$$