Ant Colony Optimisation

Imagine you're a tiny ant, part of a colony that's constantly on the lookout for food. You have no map, no GPS, and no fancy gadgets. Yet, somehow, your colony always seems to find the shortest path to food and back to the nest. How do you do it? The secret lies in a simple, yet remarkably effective strategy: cooperation through pheromones. This strategy forms the basis of the Ant Colony Algorithm, a clever way of solving complex problems by mimicking the behavior of real ants.

The problem this algorithm tackles is finding the best path in a maze of possibilities—whether that maze is a network of roads, a series of job tasks, or even the layout of a circuit. In technical terms, it’s about optimizing paths in a graph, which is a fancy way of saying that it helps find the shortest, most efficient route between points. Traditionally, this kind of problem could take a long time to solve, especially as the maze gets bigger and more complicated. But by thinking like ants, we can arrive at a good solution more quickly.

The Ant Colony Optimization (ACO) algorithm is a probabilistic technique inspired by the foraging behavior of ants. It is used to solve combinatorial optimization problems, where the objective is to find the best possible solution from a finite set of possible solutions.

Key Concepts:

• Pheromone Trails: In ACO, artificial ants traverse a graph (which represents the problem space) and deposit pheromones on the edges they travel. The amount of pheromone deposited is typically proportional to the quality of the solution (e.g., shorter paths result in more pheromones).
• Probability of Path Selection: The probability that an ant will choose a specific path is influenced by the amount of pheromone on that path and the heuristic information (e.g., the length of the path). Over time, paths with higher pheromone levels are more likely to be chosen by other ants, reinforcing successful solutions.
• Pheromone Update: As ants traverse the graph, the pheromone levels on all paths are updated. Paths with more pheromone become more attractive, while pheromones on less successful paths evaporate, reducing their influence over time. This balance between exploration and exploitation allows the algorithm to converge to an optimal or near-optimal solution.

• Initialization: initially, an arbitrary decided amount of pheromone is given to each edge in the graph: \(\tau_{xy} = I\), with \(I\) this arbitrary value and \(x,y\) two distinct vertices.
• Construct Solutions: then, at each timestep, each ant moves from \(x\) to \(y\) with probability \(p_{xy} = \frac {(\tau _{xy}^{\alpha })(\eta _{xy}^{\beta })}{\sum _{z\in \mathrm {allowed} _{x}}(\tau _{xz}^{\alpha })(\eta _{xz}^{\beta })}\), with \( \eta _{xy}\) the desirability of moving from \(x\) to \(y\) based on some a priori knowledge (in our implementation, \( \eta _{xy}\) is always 1), \(\alpha \geq 0\) and \(\beta \geq 0\) two constants defining the influence of resp. the pheromone and the desirability. In our implementation, \(2\geq \alpha \geq 0\) and \(2\geq \beta \geq 0\), and \(\alpha + \beta = 2\). Moving the cursor to full exploitation will set \(\alpha = 2, \beta = 0\).
• Update Pheromones: Once each ant has reached the objective, the pheromone is updated for each edge \(x,y\) as follows: \(\tau _{xy}\leftarrow (1-\rho )\tau _{xy}+\sum _{k \in \mathrm{Ants}_{xy}}Q/L_{k}\), with \(Q\) a constant, \(L_k\) the length of the path used by ant \(k\) to reach the goal, \(\mathrm{Ants}_{xy}\) the set of ants who moved from \(x\) to \(y\) while reaching the goal, and \(\rho\) the evaporation factor.

I had the great pleasure of having Marco Dorigo as my professor during my final year of Master’s studies at ULB. Beyond being a brilliant scientist and researcher, I can confidently say that he is an exceptional teacher who managed to instill in me—and undoubtedly in many of my peers—a deep fascination for the field of Swarm Intelligence. And he did so in a remarkably short span of time: due to the COVID-19 pandemic, our classes, which began in February 2020, were prematurely interrupted less than two months later. Yet, the seed of passion for this field had already been planted. Enthralling, captivating, and deeply human, Marco Dorigo has, unknowingly, become a model for me in my quest to become a university professor.