Abstract
This paper presents a method to assess the state of convergence of Ant Colony Optimization algorithms (ACO) using network science metrics. ACO are inspired by the behavior of ants in nature, and it is commonly used to solve combinatorial optimization problems. Network Science allows studying the structure and the dynamics of networks. This area of study provides metrics used to extract global information from networks in a particular moment. This paper aims to show that two network science metrics, the Clustering coefficient and the Assortativity, can be adapted and used to assess the pheromone graph and extract information to identify the convergence state of the ACO. We analyze the convergence of the four variations of the ACO in the Traveling Salesman Problem (TSP). Based on the obtained results, we demonstrate that it is possible to evaluate the convergence of the ACO for the TSP based on the proposed metrics, especially the adapted clustering coefficient.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Albert, R., Barabasi, A.L.: Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47–97 (2002)
Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999)
Dorigo, M.: Optimization, learning and natural algorithms. Ph.D. thesis. Dipartimento di Elettronica, Politecnico di Milano, Milão, Italy (1992). (in Italian)
Dorigo, M., Gambardella, L.M.: Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans. Evol. Comput. 1(1), 53–66 (1997)
Dorigo, M., Maniezzo, V., Colorni, A.: Ant system: optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern. Part B: Cybern. 26(1), 29–41 (1996)
Lewis, T.G., Pickl, S., Peek, B., Xu, G.: Network science [guest editorial]. IEEE Netw. 24(6), 4–5 (2010). https://doi.org/10.1109/MNET.2010.5634435
Newman, M.: Networks: An Introduction. OUP, Oxford (2010)
Newman, M.E.: Assortative mixing in networks. Phys. Rev. Lett. 89(20), 208701 (2002)
Newman, M.E.: Random graphs as models of networks. arXiv preprint cond-mat/0202208 (2002)
Newman, M.E.: The structure and function of complex networks. SIAM Rev. 45(2), 167–256 (2003)
Noldus, R., Van Mieghem, P.: Assortativity in complex networks. J. Complex Netw. 3(4), 507–542 (2015)
Oliveira, M., Bastos-Filho, C.J., Menezes, R.: Assessing particle swarm optimizers using network science metrics. In: Complex Networks IV, pp. 173–184. Springer, Heidelberg (2013)
Oliveira, M., Bastos-Filho, C.J., Menezes, R.: Towards a network-based approach to analyze particle swarm optimizers. In: 2014 IEEE Symposium on Swarm Intelligence, SIS, pp. 1–8. IEEE (2014)
Oliveira, M., Bastos-Filho, C.J., Menezes, R.: Using network science to assess particle swarm optimizers. Soc. Netw. Anal. Min. 5(1), 1–13 (2015)
Oliveira, M., Pinheiro, D., Andrade, B., Bastos-Filho, C., Menezes, R.: Communication diversity in particle swarm optimizers. In: International Conference on Swarm Intelligence, pp. 77–88. Springer (2016)
Piraveenan, M.: Topological analysis of complex networks using assortativity. School of Information technologies, The University of Sydney, Doutorado (2010)
Sekunda, A., Komareji, M., Bouffanais, R.: Interplay between signaling network design and swarm dynamics. Netw. Sci. 4(2), 244–265 (2016)
Thedchanamoorthy, G., Piraveenan, M., Kasthuriratna, D., Senanayake, U.: Node assortativity in complex networks: an alternative approach. Proc. Comput. Sci. 29, 2449–2461 (2014). https://doi.org/10.1016/j.procs.2014.05.229. 2014 International Conference on Computational Science
Weise, T., Chiong, R., Lassig, J., Tang, K., Tsutsui, S., Chen, W., Michalewicz, Z., Yao, X.: Benchmarking optimization algorithms: an open source framework for the traveling salesman problem. IEEE Comput. Intell. Mag. 9(3), 40–52 (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Ribeiro, S.F., Bastos-Filho, C.J.A. (2020). Assessing Ant Colony Optimization Using Adapted Networks Science Metrics. In: Madureira, A., Abraham, A., Gandhi, N., Varela, M. (eds) Hybrid Intelligent Systems. HIS 2018. Advances in Intelligent Systems and Computing, vol 923. Springer, Cham. https://doi.org/10.1007/978-3-030-14347-3_13
Download citation
DOI: https://doi.org/10.1007/978-3-030-14347-3_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-14346-6
Online ISBN: 978-3-030-14347-3
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)