Paper ID: 2410.09059

The Impact of Network Structure on Ant Colony Optimization

Taiyo Shimizu, Shintaro Mori

Ant Colony Optimization (ACO) is a swarm intelligence methodology utilized for solving optimization problems through information transmission mediated by pheromones. As ants sequentially secrete pheromones that subsequently evaporate, the information conveyed predominantly comprises pheromones secreted by recent ants. This paper introduces a network structure into the information transmission process and examines its impact on optimization performance. The network structure is characterized by an asymmetric BA model with parameters for in-degree $r$ and asymmetry $\omega$. At $\omega=1$, the model describes a scale-free network; at $\omega=0$, a random network; and at $\omega=-1$, an extended lattice. We aim to solve the ground state search of the mean-field Ising model, employing a linear decision function for the ants with their response to pheromones quantified by the parameter $\alpha$. For $\omega>-1$, the pheromone rates for options converge to stable fixed points of the stochastic system. Below the critical threshold $\alpha_c$, there is one stable fixed point, while above $\alpha_c$, there are two. Notably, as $\omega \to -1$, both the driving force toward stable fixed points and the strength of the noise reach their maximum, significantly enhancing the probability of finding the ground state of the Ising model.

Submitted: Sep 27, 2024