🐜 Ant Colony Optimization

Ant colony optimization (ACO) is a probabilistic metaheuristic inspired by the foraging behaviour of real ants, who lay down pheromone trails as they travel and preferentially follow trails left by others, so that shorter paths accumulate pheromone faster and are reinforced over successive trips. Introduced by Marco Dorigo in the early 1990s, ACO algorithms simulate a population of virtual ants that build candidate solutions step by step, biased by a combination of pheromone strength and heuristic desirability, then deposit virtual pheromone proportional to solution quality while old pheromone evaporates over time. This simple feedback loop lets a colony collectively discover near-optimal solutions to hard combinatorial problems such as the travelling salesman problem and network routing, without any central coordinator directing the search. Evaporation is essential to the algorithm's success: without it, pheromone on early, possibly suboptimal paths would keep growing and trap the whole colony in a local optimum, whereas a steady decay rate lets weaker trails fade so better routes discovered later can still win out. Because each ant's decision depends only on local pheromone concentrations and simple probabilistic rules, ACO scales gracefully to large problem instances and is easy to parallelize, which is why it remains a standard tool for vehicle routing, job-shop scheduling and other NP-hard optimization problems.