Conclusions
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.
This is a preview of subscription content, log in via an institution to check access.
References
Neumann F, Witt C. Bioinspired Computation in Combinatorial Optimization — Algorithms and Their Computational Complexity. Springer Science & Business Media, 2010
Zhou Z H, Yu Y, Qian C. Evolutionary Learning: Advances in Theories and Algorithms. Singapore: Springer, 2019
Garey M R, Johnson D S. Computers and Intractability: A Guide to The Theory of NP-completeness. New York, NY: Freeman, 1979
Pat A. Ant colony optimization and hypergraph covering problems. In: Proceedings of the IEEE Congress on Evolutionary Computation. 2014, 1714–1720
Xia X, Zhou Y. Performance analysis of ACO on the quadratic assignment problem. Chinese Journal of Electronics, 2018, 27(1): 26–34
Kötzing T, Neumann F, Roglin H. Theoretical analysis of two ACO approaches for the traveling salesman problem. Swarm Intelligence, 2012, 6: 1–21
Khanna S, Motwani R, Sudan M, Vazirani U. On syntactic versus computational views of approximability. In: Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science. 1994, 819–836
Acknowledgements
This work was supported by the National Natural Science Foundation of China (Grant Nos. 61703183, 61773410 and 61876207), the Public Welfare Technology Application Research Plan of Zhejiang Province (LGG19F030010), and the Science and Technology Program of Guangzhou (202002030260).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Xia, X., Peng, X. & Liao, W. On the analysis of ant colony optimization for the maximum independent set problem. Front. Comput. Sci. 15, 154329 (2021). https://doi.org/10.1007/s11704-020-9464-7
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s11704-020-9464-7