On the analysis of ant colony optimization for the maximum independent set problem

In the present work, we contribute to the theoretical understanding of a kind of ACO algorithm by investigating the classic maximum independent set problem. Our theoretical results show that with a new construction graph, the ACO algorithm can obtain an approximation ability on maximum independent set problem, and also show the impact of the parameter settings. We first obtain two general upper bounds on arbitrary maximum independent set instance, then we obtain an approximation ratio by ACO algorithm in polynomial time. Finally, we give an instance on which ACO algorithm can escape from local optimum in polynomial time while the local search algorithm is easy to get stuck in local optimum. In the future, we will extend the running time analysis to pheromone evaporation factor, and make in-depth analysis of the impact of pheromone value on the running time.