Abstract
The optimization provides resolutions to complex combinatorial problems that generally deal within large data size and expensive operating processes. Metaheuristics target the promoting of new applied algorithms to resolve NP-Hard problems in order to improve resolutions requiring enhanced search strategies. Travelling Salesman Problem (TSP) is a common combinatorial problem, applied on several benchmark networks, namely the transportation networks and the routing vehicle problem in order to establish new intelligent computing methods as well as, to prove studies on their performances and efficiencies. Collective intelligence has proven satisfactory resolutions wherewith metaheuristics, although their algorithms complexity. The aim of this work is to solve the Euclidean TSP, classified as a NP-hard problem by means of Self-Organizing Maps (SOM) which is a Kohonen-type network. The resolution is also computed corresponding to a new bio-inspired evolutionary strategy so-called coronavirus optimization algorithm combined with SOM algorithm. The present approach is combining an unsupervised learning strategy within the new coronavirus optimization algorithm to replicate iteratively new infected individuals and to generate diversification on the search space. This new hybrid method presents a good approximative resolutions, proved by applying tests for TSPLIB instances wherein the exact optimum is defined corresponding to each TSP data. However, the present resolutions are complex specifically for large scale by means of increasing the size of input data or size parameters.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bovet DP, Clementi A, Crescenzi P, Silvestri R (1996) Parallel approximation of optimization problems. In: Ferreira A, Pardalos PM (eds) Solving combinatorial optimization problems in parallel. LNCS, vol 1054, pp 248–274. Springer, Berlin
Lüling R, Monien B, Reinefeld A, Tschöke S (1996) Mapping tree-structured combinatorial optimization problems onto parallel computers. In: Ferreira A, Pardalos PM (eds) Solving combinatorial optimization problems in parallel. LNCS, vol. 1054. Springer, Berlin, Heidelberg
Laursen PS (1996) Parallel heuristic search – introductions and a new approach. In: Ferreira A, Pardalos PM (eds) Solving combinatorial optimization problems in parallel, LNCS, vol 1054. Springer, Berlin, Heidelberg, pp 248–274
Akhand MAH, Ayon SI, Shahriyar SA, Siddique N, Adeli H (2020) Discrete spider monkey optimization for TSP. Appl Soft Comput vol 86, p 105887
Clementi A, Rolim JDP, Urland E (1996) Randomized parallel algorithms. In: Ferreira A, Pardalos PM (eds) Solving combinatorial optimization problems in parallel. LNCS, vol 1054. Springer, Heidelberg
Bouzidi A, Riffi ME (2019) Improved CSO to solve the TSP. In: Ezziyyani M (eds) AI2SD Conference 2018. Advances in Intelligent Systems and Computing, vol 714. Springer, Singapore
Othman A, Haimoudi E, Mouhssine R, Ezziyyani M (2019) An effective parallel approach to solve multiple TSP. In: Ezziyyani M (eds) AI2SD Conference 2018. Advances in Intelligent Systems and Computing, vol 714. Springer
Ferreira A, Pardalos PM (1996) SCOOP: Solving combinatorial optimization problems in parallel. In: Ferreira A, Pardalos PM (eds) Solving combinatorial optimization problems in parallel. LNCS, vol 1054. Springer, Berlin
Durbin R, Willshaw D (1987) An analogue approach to the travelling salesman problem using an elastic net method. Nature 326:689–691
Wang J, Ersoy OK, He M, Wang F (2016) Multi-offspring genetic algorithm and its application to TSP. Appl Soft Comput 30:484–490
Ezugwu AES, Adewumi A, Frîncu M (2017) Simulated annealing based symbiotic organisms search optimization algorithm for traveling salesman problem. Expert Syst Appl 77:189–210
Choong SS, Wong LP, Lim CP (2019) An artificial bee colony algorithm with a modified choice function for the traveling salesman problem. Swarm Evol Comput 44:22–635
Chen WL, Dai SG (2006) Survey of algorithms for traveling salesman problem. J Chuzhou Univ 8(3):1–6
Guo JY (2006) An overview of traveling salesman problem. Pop Sci Technol 8:229–230
Lahjouji A, Tajani C, Krkri I, Fakhouri H (2019) Immune based genetic algorithm to solve a combinatorial optimization problem: Application to traveling salesman problem. In: Ezziyyani M (eds) AI2SD Conference 2018, Advances in intelligent systems and computing, vol 915. Springer
Ismail MA, Daryl E, Kathryn K (2020) A novel design of differential evolution for solving discrete TSP. Swarm Evol Comput 52:100607
Hoffman KL, Padberg M, Rinaldi G (2013) Traveling salesman problem. In: Gass S I, Fu MC (eds) Encyclopedia of operations research and management science. Springer, Boston
Gilmore PC, Gomory RE (1964) A solvable case of the traveling salesman problem. Proc Natl Acad Sci 51:178–181
Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows. Prentice-Hall
Bazaraa MS, Jarvis JJ, Sherali HD (1990) Linear programming and network flows. Wiley, New York
Koprinkova HP, Mladenov V, Kasabov NK (2015) Artificial neural networks. Springer Series in Bio-/Neuroinformatics
Trick M (2008) Oper Res Lett 36(2):276–277
Khourdifi Y, Bahaj M (2020) Analyzing social media opinions using hybrid machine learning model based on artificial neural network optimized by particle swarm optimization. In: Ezziyyani M (eds) AI2SD Conference 2019. Advances in Intelligent Systems and Computing, vol 714. Springer, Singapore
Kohonen T (1990) The self-organizing map. Proc IEEE 78(9):1464–1480
Kohonen T (2001) Self-organizing maps. Springer , Heidelberg
Somhom S, Modares A, Enkawa T (1997) A self-organising model for TSP problem. J Oper Res Soc 48(9):919–928
Kohonen T, Kaski S, Lagus K, Salojarvi J, Honkela J, Paatero V, Saarela A (2000) Self organization of a massive document collection. IEEE Trans Neural Netw 11(3):574–585
Moukhafi M, Yassini KE, Bri S, Oufaska K (2019) Artificial neural network optimized by genetic algorithm for intrusion detection system. In: Ezziyyani M (eds) AI2SD Conference 2018. Advances in Intelligent Systems and Computing, vol 714. Springer, Singapore
Yanping B, Wendong Z, Zhen J (2006) A new self-organizing maps strategy for solving TSP. Chaos Solitons Fractals 28(4):1082–1089
Jan F, Miroslav K, Vojtěch V, Libor P (2011) An application of the self-organizing map in the non-euclidean TSP. Neurocomputing 74(5):671–679
Créput JC, Koukam A (2009) A memetic neural network for the euclidean TSP. Neurocomputing 72(4–6):1250–1264
Tinós R (2020) Artificial neural network based crossover for evolutionary algorithms. Appl Soft Comput 95:106512
Martínez-Álvarez F, Asencio-Cortés G, Torres JF, Gutiérrez-Avilés D, Melgar-García L, Pérez-Chacón R, Rubio-Escudero C, Riquelme JC, Troncoso A (2020) Coronavirus optimization algorithm: a bioinspired metaheuristic based on the COVID-19 propagation model. Big data 8(4):308–322
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
EL Majdoubi, O., Abdoun, F., Abdoun, O. (2021). A New Optimized Approach to Resolve a Combinatorial Problem: CoronaVirus Optimization Algorithm and Self-organizing Maps. In: Motahhir, S., Bossoufi, B. (eds) Digital Technologies and Applications. ICDTA 2021. Lecture Notes in Networks and Systems, vol 211. Springer, Cham. https://doi.org/10.1007/978-3-030-73882-2_86
Download citation
DOI: https://doi.org/10.1007/978-3-030-73882-2_86
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-73881-5
Online ISBN: 978-3-030-73882-2
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)