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}}$$

Note that pheromones are very important: ACS without heuristics performs better than ACS without pheromone. This is because ACS with pheromone (but no heuristics) is still guided by the global update rule, reflecting the importance of high-quality solutions. ACS without pheromone reduces to a stochastic multi-greedy algorithm.