Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Hybridising Self-Organising Maps with Genetic Algorithms

  • Conference paper
  • First Online:
Learning and Intelligent Optimization (LION 2021)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 12931))

Included in the following conference series:

  • 726 Accesses

Abstract

The aim of this work is to develop a hybridised approach consisting of the Self-Organising Map (SOM), which is an artificial neural network, and a Genetic Algorithm (GA) to tackle large and complex optimisation problems by decomposition. The approach is tested on the travelling salesman problem (TSP), which is a very important problem in combinatorial optimisation. The SOM clusters the nodes into a specified number of groups. Then, the resulting smaller TSPs within each cluster are solved, and finally, the solutions of the clusters are connected to build a high quality solution for the whole TSP. In the two latter steps, a GA is used. Our approach is examined on some random examples including 100 to 10000 nodes as well as 12 benchmark instances. The results with various numbers of clusters are compared to each other and also to the case of solving the TSP with all nodes and without any clustering. Furthermore, the effect of each component algorithm in the hybridised approach is evaluated by some complementary experiments in which the clustering and the optimisation algorithm are replaced by other methods.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 69.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 89.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Der Handlungsreisende - wie er sein soll und was er zu tun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein - von einem alten Commis-Voyageur. Springer (1832)

    Google Scholar 

  2. Aggarwal, C.C.: Neural Networks and Deep Learning. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-94463-0

    Book  MATH  Google Scholar 

  3. Alsheddy, A.: Solving the free clustered TSP using a memetic algorithm. Int. J. Adv. Comput. Sci. Appl. 8(8), 404–408 (2017). https://doi.org/10.14569/ijacsa.2017.080852

    Article  Google Scholar 

  4. Applegate, D.L., et al.: Certification of an optimal TSP tour through 85,900 cities. Oper. Res. Lett. 37(1), 11–15 (2009). https://doi.org/10.1016/j.orl.2008.09.006

    Article  MathSciNet  MATH  Google Scholar 

  5. Bai, Y., Zhang, W., Jin, Z.: An new self-organizing maps strategy for solving the traveling salesman problem. Chaos, Solitons & Fractals 28(4), 1082–1089 (2006). https://doi.org/10.1016/j.chaos.2005.08.114

  6. Bergmann, B., Hommel, G.: Improvements of general multiple test procedures for redundant systems of hypotheses. In: Bauer, P., Hommel, G., Sonnemann, E. (eds.) Multiple Hypothesenprüfung/Multiple Hypotheses Testing. MEDINFO, vol. 70, pp. 100–115. Springer, Heidelberg (1988). https://doi.org/10.1007/978-3-642-52307-6_8

    Chapter  Google Scholar 

  7. Blickle, T., Thiele, L.: A comparison of selection schemes used in evolutionary algorithms. Evol. Comput. 4(4), 361–394 (1996). https://doi.org/10.1162/evco.1996.4.4.361

    Article  Google Scholar 

  8. Brocki, Ł, Koržinek, D.: Kohonen self-organizing map for the traveling salesperson problem. In: Jabłoński, R., Turkowski, M., Szewczyk, R. (eds.) Recent Advances in Mechatronics, pp. 116–119. Springer, Heidelberg (1999). https://doi.org/10.1007/978-3-540-73956-2_24

    Chapter  Google Scholar 

  9. Dantzig, G., Fulkerson, R., Johnson, S.: Solution of a large-scale traveling-salesman problem. J. Oper. Res. Soc. Am. 2(4), 393–410 (1954). https://doi.org/10.1287/opre.2.4.393

    Article  MathSciNet  MATH  Google Scholar 

  10. D’Urso, P., Giovanni, L.D., Massari, R.: Smoothed self-organizing map for robust clustering. Inf. Sci. 512, 381–401 (2020). https://doi.org/10.1016/j.ins.2019.06.038

    Article  MathSciNet  MATH  Google Scholar 

  11. Faigl, J., Hollinger, G.A.: Self-organizing map for the prize-collecting traveling salesman problem. In: Villmann, T., Schleif, F.-M., Kaden, M., Lange, M. (eds.) Advances in Self-Organizing Maps and Learning Vector Quantization. AISC, vol. 295, pp. 281–291. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-07695-9_27

    Chapter  Google Scholar 

  12. Fuentes, G.E.A., Gress, E.S.H., Mora, J.C.S.T., Marín, J.M.: Solution to travelling salesman problem by clusters and a modified multi-restart iterated local search metaheuristic. PLoS ONE 13(8), e0201868 (2018). https://doi.org/10.1371/journal.pone.0201868

    Article  Google Scholar 

  13. Gendreau, M., Potvin, J.Y. (eds.): Handbook of Metaheuristics. Springer, Boston (2010). https://doi.org/10.1007/978-1-4419-1665-5

    Book  MATH  Google Scholar 

  14. Grabusts, P., Musatovs, J.: The application of simulated annealing method for solving travelling salesman problem. In: Proceedings of the 4th Global Virtual Conference. Publishing Society, pp. 225–229 (2016). https://doi.org/10.18638/gv.2016.4.1.732

  15. Grice, J.V., Montgomery, D.C.: Design and analysis of experiments. Technometrics 42(2), 208 (2000). https://doi.org/10.2307/1271458

    Article  Google Scholar 

  16. Guttmann-Beck, N., Knaan, E., Stern, M.: Approximation algorithms for not necessarily disjoint clustered TSP. J. Graph Algorithms Appl. 22(4), 555–575 (2018). https://doi.org/10.7155/jgaa.00478

    Article  MathSciNet  MATH  Google Scholar 

  17. Haupt, R.L., Haupt, S.E.: Practical Genetic Algorithms. Wiley, Hoboken (2003). https://doi.org/10.1002/0471671746

    Book  MATH  Google Scholar 

  18. Jaradat, A., Matalkeh, B., Diabat, W.: Solving traveling salesman problem using firefly algorithm and k-means clustering. In: 2019 IEEE Jordan International Joint Conference on Electrical Engineering and Information Technology (JEEIT). IEEE, pp. 586–589 (2019). https://doi.org/10.1109/jeeit.2019.8717463

  19. Jovanovic, R., Tuba, M., Voß, S.: Fixed set search applied to the traveling salesman problem. In: Blesa Aguilera, M.J., Blum, C., Gambini Santos, H., Pinacho-Davidson, P., Godoy del Campo, J. (eds.) HM 2019. LNCS, vol. 11299, pp. 63–77. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-05983-5_5

    Chapter  Google Scholar 

  20. King, B., Barve, S., Ford, A., Jha, R.: Unsupervised clustering of COVID-19 chest X-ray images with a self-organizing feature map. In: 2020 IEEE 63rd International Midwest Symposium on Circuits and Systems (MWSCAS). IEEE (2020). https://doi.org/10.1109/mwscas48704.2020.9184493

  21. Kohonen, T.: Self-organized formation of topologically correct feature maps. Biol. Cybern. 43(1), 59–69 (1982). https://doi.org/10.1007/bf00337288

    Article  MathSciNet  MATH  Google Scholar 

  22. Laporte, G., Palekar, U.: Some applications of the clustered travelling salesman problem. J. Oper. Res. Soc. 53(9), 972–976 (2002). https://doi.org/10.1057/palgrave.jors.2601420

    Article  MATH  Google Scholar 

  23. Liu, D., Wang, X., Du, J.: A clustering-based evolutionary algorithm for traveling salesman problem. In: 2009 International Conference on Computational Intelligence and Security. IEEE, pp. 118–122 (2009). https://doi.org/10.1109/cis.2009.80

  24. Matai, R., Singh, S., Lal, M.: Traveling salesman problem: an overview of applications, formulations, and solution approaches. In: Davendra, D. (ed.) Traveling Salesman Problem, Theory and Applications. InTech (2010). https://doi.org/10.5772/12909

  25. Potvin, J.Y., Guertin, F.: The clustered traveling salesman problem: a genetic approach. In: Osman, I.H., Kelly, J.P. (eds.) Meta-Heuristics, pp. 619–631. Springer, Boston (1996). https://doi.org/10.1007/978-1-4613-1361-8_37

    Chapter  Google Scholar 

  26. Rego, C., Gamboa, D., Glover, F., Osterman, C.: Traveling salesman problem heuristics: leading methods, implementations and latest advances. Eur. J. Oper. Res. 211(3), 427–441 (2011). https://doi.org/10.1016/j.ejor.2010.09.010

    Article  MathSciNet  MATH  Google Scholar 

  27. Reinelt, G.: TSPLIB—a traveling salesman problem library. ORSA J. Comput. 3(4), 376–384 (1991). https://doi.org/10.1287/ijoc.3.4.376

    Article  MATH  Google Scholar 

  28. Schneider, J.J., Bukur, T., Krause, A.: Traveling salesman problem with clustering. J. Stat. Phys. 141(5), 767–784 (2010). https://doi.org/10.1007/s10955-010-0080-z

    Article  MathSciNet  MATH  Google Scholar 

  29. Suhriani, I.F., Mutawalli, L., Widiami, B.R.A., Chumairoh: Implementation self organizing map for cluster flood disaster risk. In: Proceedings of the International Conference on Mathematics and Islam. SCITEPRESS - Science and Technology Publications, pp. 405–409 (2018). https://doi.org/10.5220/0008522604050409

  30. Taillard, É.D., Helsgaun, K.: POPMUSIC for the travelling salesman problem. Eur. J. Oper. Res. 272(2), 420–429 (2019). https://doi.org/10.1016/j.ejor.2018.06.039

    Article  MathSciNet  MATH  Google Scholar 

  31. Yu, S., Yang, M., Wei, L., Hu, J.S., Tseng, H.W., Meen, T.H.: Combination of self-organizing map and k-means methods of clustering for online games marketing. Sens. Mater. 32(8), 2801 (2020). https://doi.org/10.18494/sam.2020.2800

    Article  Google Scholar 

  32. Yuanyuan, L., Jing, Z.: An application of ant colony optimization algorithm in TSP. In: 2012 Fifth International Conference on Intelligent Networks and Intelligent Systems. IEEE, pp. 61–64 (2012). https://doi.org/10.1109/icinis.2012.20

Download references

Author information

Authors and Affiliations

  1. Institute of Information Systems (IWI), University of Hamburg, Hamburg, Germany

    Abtin Nourmohammadzadeh & Stefan Voß

Authors
  1. Abtin Nourmohammadzadeh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Stefan Voß
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Abtin Nourmohammadzadeh .

Editor information

Editors and Affiliations

  1. SBA Research, Vienna, Austria

    Dimitris E. Simos

  2. University of Florida, Gainesville, FL, USA

    Panos M. Pardalos

  3. Wilfrid Laurier University, Waterloo, ON, Canada

    Ilias S. Kotsireas

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Nourmohammadzadeh, A., Voß, S. (2021). Hybridising Self-Organising Maps with Genetic Algorithms. In: Simos, D.E., Pardalos, P.M., Kotsireas, I.S. (eds) Learning and Intelligent Optimization. LION 2021. Lecture Notes in Computer Science(), vol 12931. Springer, Cham. https://doi.org/10.1007/978-3-030-92121-7_22

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-92121-7_22

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-92120-0

  • Online ISBN: 978-3-030-92121-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics