3
$\begingroup$

I'm studying ant colony optimization. I'm trying to understand the difference between the ant system (AS) and the max-min ant system (MMAS) approaches. As far as I found out, the main difference between these 2 is that in AS the pheromone trail is updated after all ants have finished the tour (it means all ants participate in this update), but in MMAS, only the best ant updates this value. Am I right? Is there any other significant difference?

$\endgroup$
2
$\begingroup$

Well, it's been some time since you posted the question, however, the answer might still be useful for you and others.

Let's start by making clear that both AS and MMAS use only global pheromone update. Now, the MMAS has two main differences regarding AS:

  1. In AS, all ants that completed a solution are used for the update, while in MMAS only the best ant with complete solution is used for update (as you had point out).
  2. In AS, the pheromone values are not explicitly bounded. In MMAS, the pheromones are enforced to lie within a pre-set interval $\tau_{min} \leq \tau_{ij} \leq \tau_{max}$ (which gives its name to the algorithm). To ensure this condition, the pheromone update is done by means of the formula

$$ \tau_{ij} \leftarrow \left[ (1-\rho) \cdot \tau_{ij} + \Delta \tau_{ij}^{best} \right]_{\tau_{min}}^{\tau_{max}}, $$

with the operator $[x]_a^b$ defined as

$$ [x]_a^b= \begin{cases} a \qquad \mathrm{if} \quad x > a\\ b \qquad \mathrm{if} \quad x < b\\ x \qquad \mathrm{otherwise} \end{cases} $$

Reference: Ant Colony Optimization. Artificial Ants as a Computational Intelligence Technique.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.