Phase Transition in Ant Colony Optimization.

Ant colony optimization (ACO) is a stochastic optimization algorithm inspired by the foraging behavior of ants. We investigate a simplified computational model of ACO, wherein ants sequentially engage in binary decision-making tasks, leaving pheromone trails contingent upon their choices. The quantity of pheromone left is the number of correct answers. We scrutinize the impact of a salient parameter in the ACO algorithm, specifically, the exponent α , which governs the pheromone levels in the stochastic choice function. In the absence of pheromone evaporation, the system is accurately modeled as a multivariate nonlinear Pólya urn, undergoing phase transition as α varies. The probability of selecting the correct answer for each question asymptotically approaches the stable fixed point of the nonlinear Pólya urn. The system exhibits dual stable fixed points for α ≥ α c and a singular stable fixed point for α < α c where α c is the critical value. When pheromone evaporates over a time scale τ , the phase transition does not occur and leads to a bimodal stationary distribution of probabilities for α ≥ α c and a monomodal distribution for α < α c . [ABSTRACT FROM AUTHOR]