[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

Genetic Algorithm Incorporating Group Theory for Solving the General Travelling Salesman Problem

  • Original Research
  • Published:
SN Computer Science Aims and scope Submit manuscript

Abstract

This paper presents a novel Genetic Algorithm (GA) designed to tackle the Travelling Salesman Problem (TSP) with remarkable efficacy. It integrates group theory into population initialization, employs Partially Matched Crossover (PMX), and adopts a 2-optimal mutation strategy. The pioneering approach harnesses algebraic structures in constructing group tours, utilizing integer addition modulo n within \({\mathbb {Z}}_{n}\) to generate varied initial solutions. The initial population enhances diversity by ensuring that each individual/tour shares an identical node order but begins from a distinct starting node. This distinctiveness in starting nodes facilitates thorough exploration of the entire search space. The Partially mapped Crossover operator, grounded in order principles, is a crucial mechanism for transferring sequence and value characteristics from parental to offspring tour. This operation effectively guides a strong local search. Subsequently, applying a 2-opt optimal mutation seeks to refine the solution further, targeting a more globally optimal outcome. The effectiveness of this methodology is evaluated through experiments with TSP instances sourced from the widely recognized TSPLIB. Furthermore, the superiority of our proposed approach is demonstrated through comparisons with state-of-the-art methods developed within hybrid frameworks. Statistical analyses underscore the significance and effectiveness of the proposed methodology.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.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

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Algorithm 1
Fig. 1
Fig. 2
Algorithm 2
Fig. 3

Similar content being viewed by others

Data Availibility

http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/index.html.

Notes

  1. http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/index.html.

  2. https://www.socscistatistics.com/tests/signedranks/default2.aspx.

References

  1. Akhand M, Akter S, Rashid M, Yaakob S. Velocity tentative pso: an optimal velocity implementation based particle swarm optimization to solve traveling salesman problem. IAENG Int J Comput Sci. 2015;42:1–12.

    Google Scholar 

  2. Akhand M, Ayon SI, Shahriyar S, Siddique N, Adeli H. Discrete spider monkey optimization for travelling salesman problem. Appl Soft Comput. 2020;86: 105887.

    Article  Google Scholar 

  3. Albayrak M, Allahverdi N. Development a new mutation operator to solve the traveling salesman problem by aid of genetic algorithms. Expert Syst Appl. 2011;38:1313–20.

    Article  Google Scholar 

  4. Ali MKM, Kamoun F. Neural networks for shortest path computation and routing in computer networks. IEEE Trans Neural Netw. 1993;4:941–54.

    Article  Google Scholar 

  5. Baraglia R, Hidalgo JI, Perego R. A hybrid heuristic for the traveling salesman problem. IEEE Trans Evol Comput. 2001;5:613–22.

    Article  Google Scholar 

  6. Bektas T. The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega. 2006;34:209–19.

    Article  Google Scholar 

  7. Bullnheimer B, Hartl RF, Strauss C. An improved ant system algorithm for the vehicle routing problem. Ann Oper Res. 1999;89:319–28.

    Article  MathSciNet  Google Scholar 

  8. Chang P-C, Hsieh J-C, Wang C-Y. Adaptive multi-objective genetic algorithms for scheduling of drilling operation in printed circuit board industry. Appl Soft Comput. 2007;7:800–6.

    Article  Google Scholar 

  9. Chen S-M, Chien C-Y. Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques. Expert Syst Appl. 2011;38:14439–50.

    Article  Google Scholar 

  10. Chen X, Zhou Y, Tang Z, Luo Q. A hybrid algorithm combining glowworm swarm optimization and complete 2-opt algorithm for spherical travelling salesman problems. Appl Soft Comput. 2017;58:104–14.

    Article  Google Scholar 

  11. Črepinšek M, Liu S-H, Mernik M. Exploration and exploitation in evolutionary algorithms: a survey. ACM Comput Surv (CSUR). 2013;45:1–33.

    Article  Google Scholar 

  12. Créput J-C, Koukam A. A memetic neural network for the Euclidean traveling salesman problem. Neurocomputing. 2009;72:1250–64.

    Article  Google Scholar 

  13. Croes GA. A method for solving traveling-salesman problems. Oper Res. 1958;6:791–812.

    Article  MathSciNet  Google Scholar 

  14. Davis L. Handbook of genetic algorithms. New York: Van Nostrand Reinhold; 1991.

    Google Scholar 

  15. Deng W, Chen R, He B, Liu Y, Yin L, Guo J. A novel two-stage hybrid swarm intelligence optimization algorithm and application. Soft Comput. 2012;16:1707–22.

    Article  Google Scholar 

  16. Deo N. Graph theory with applications to engineering and computer science. Courier Dover Publications; 2017.

    Google Scholar 

  17. Derrac J, García S, Molina D, Herrera F. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm Evol Comput. 2011;1:3–18.

    Article  Google Scholar 

  18. Dong X, Cai Y. A novel genetic algorithm for large scale colored balanced traveling salesman problem. Future Gener Comput Syst. 2019;95:727–42.

    Article  Google Scholar 

  19. Dorigo M, Gambardella LM. Ant colonies for the travelling salesman problem. Biosystems. 1997;43:73–81.

    Article  Google Scholar 

  20. Durbin R, Szeliski R, Yuille A. An analysis of the elastic net approach to the traveling salesman problem. Neural Comput. 1989;1:348–58.

    Article  Google Scholar 

  21. Ezugwu AE-S, Adewumi AO. Discrete symbiotic organisms search algorithm for travelling salesman problem. Expert Syst Appl. 2017;87:70–8.

    Article  Google Scholar 

  22. Ezugwu AE-S, Adewumi AO, Frîncu ME. Simulated annealing based symbiotic organisms search optimization algorithm for traveling salesman problem. Expert Syst Appl. 2017;77:189–210.

    Article  Google Scholar 

  23. Fogel DB. Applying evolutionary programming to selected traveling salesman problems. Cybern Syst. 1993;24:27–36.

    Article  MathSciNet  Google Scholar 

  24. Gen M, Cheng R. Genetic algorithms and engineering optimization, vol. 7. Wiley; 1999.

    Book  Google Scholar 

  25. Geng X, Chen Z, Yang W, Shi D, Zhao K. Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search. Appl Soft Comput. 2011;11:3680–9.

    Article  Google Scholar 

  26. Gil-Gala FJ, Durasević M, Sierra MR, Varela R. Evolving ensembles of heuristics for the travelling salesman problem. Nat Comput. 2023;22:671–84.

    Article  MathSciNet  Google Scholar 

  27. Goldberg D.E, Lingle Jr R. Alleleslociand the traveling salesman problem. In: Proceedings of the 1st International Conference on Genetic Algorithms; 1985. pp. 154–159.

  28. Gong X, Rong Z, Wang J, Zhang K, Yang S. A hybrid algorithm based on state-adaptive slime mold model and fractional-order ant system for the travelling salesman problem. Complex Intell Syst. 2023;9:3951–70.

    Article  Google Scholar 

  29. Grötschel M, Padberg M, Lawler E, Lenstra J, Rinnooy Kan A, Schmoys D. The traveling salesman problem; 1985

  30. Gutiérrez-Aguirre P, Contreras-Bolton C. A multioperator genetic algorithm for the traveling salesman problem with job-times. Expert Syst Appl. 2024;240: 122472.

    Article  Google Scholar 

  31. Halim AH, Ismail I, Das S. Performance assessment of the metaheuristic optimization algorithms: an exhaustive review. Artif Intell Rev. 2020;54(3):2323–409.

    Article  Google Scholar 

  32. Held M, Karp RM. The traveling-salesman problem and minimum spanning trees. Oper Res. 1970;18:1138–62.

    Article  MathSciNet  Google Scholar 

  33. Helsgaun K. An effective implementation of the Lin–Kernighan traveling salesman heuristic. Eur J Oper Res. 2000;126:106–30.

    Article  MathSciNet  Google Scholar 

  34. Holland JH. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT press; 1992.

    Book  Google Scholar 

  35. Jun-man K, Yi Z. Application of an improved ant colony optimization on generalized traveling salesman problem. Energy Procedia. 2012;17:319–25.

    Article  Google Scholar 

  36. Karp RM. A patching algorithm for the nonsymmetric traveling-salesman problem. SIAM J Comput. 1979;8:561–73.

    Article  MathSciNet  Google Scholar 

  37. Khan I, Maiti MK. A swap sequence based artificial bee colony algorithm for traveling salesman problem. Swarm Evol Comput. 2019;44:428–38.

    Article  Google Scholar 

  38. Liu S-H, Mernik M, Hrnčič D, Črepinšek M. A parameter control method of evolutionary algorithms using exploration and exploitation measures with a practical application for fitting sovova’s mass transfer model. Appl Soft Comput. 2013;13:3792–805.

    Article  Google Scholar 

  39. Mahi M, Baykan ÖK, Kodaz H. A new hybrid method based on particle swarm optimization, ant colony optimization and 3-opt algorithms for traveling salesman problem. Appl Soft Comput. 2015;30:484–90.

    Article  Google Scholar 

  40. Marinakis Y, Marinaki M. A hybrid multi-swarm particle swarm optimization algorithm for the probabilistic traveling salesman problem. Comput Oper Res. 2010;37:432–42.

    Article  MathSciNet  Google Scholar 

  41. Masutti TA, de Castro LN. A self-organizing neural network using ideas from the immune system to solve the traveling salesman problem. Inf Sci. 2009;179:1454–68.

    Article  MathSciNet  Google Scholar 

  42. Osaba E, Yang X-S, Diaz F, Lopez-Garcia P, Carballedo R. An improved discrete bat algorithm for symmetric and asymmetric traveling salesman problems. Eng Appl Artif Intell. 2016;48:59–71.

    Article  Google Scholar 

  43. Ouaarab A, Ahiod B, Yang X-S. Discrete cuckoo search algorithm for the travelling salesman problem. Neural Comput Appl. 2014;24:1659–69.

    Article  Google Scholar 

  44. Panwar K, Deep K. Discrete grey wolf optimizer for symmetric travelling salesman problem. Appl Soft Comput J. 2021;105: 107298.

    Article  Google Scholar 

  45. Pop PC, Cosma O, Sabo C, Sitar CP. A comprehensive survey on the generalized traveling salesman problem. Eur J Oper Res. 2023;314(3):819–35.

    Article  MathSciNet  Google Scholar 

  46. Reinelt G. The traveling salesman: computational solutions for TSP applications, vol. 840. Springer; 2003.

    Google Scholar 

  47. Rosen KH, Krithivasan K. Discrete mathematics and its applications: with combinatorics and graph theory. Tata McGraw-Hill Education; 2012.

    Google Scholar 

  48. Saleh HA, Chelouah R. The design of the global navigation satellite system surveying networks using genetic algorithms. Eng Appl Artif Intell. 2004;17:111–22.

    Article  Google Scholar 

  49. Shi XH, Liang YC, Lee HP, Lu C, Wang Q. Particle swarm optimization-based algorithms for TSP and generalized TSP. Inf Process Lett. 2007;103:169–76.

    Article  MathSciNet  Google Scholar 

  50. Singh DR, Singh MK, Singh T. A hybrid heuristic algorithm for the Euclidean traveling salesman problem. In: International Conference on Computing, Communication & Automation. IEEE; 2015. pp. 773–778.

  51. Singh DR, Singh MK, Singh T. Multiple traveling salesman problem using novel crossover and group theory. In: 2017 International Conference on Computing, Communication and Automation (ICCCA). IEEE; 2017. pp. 368–372.

  52. Sivanandam SN, Deepa SN. Genetic algorithms. In: Introduction to genetic algorithms. Springer; 2008. p. 15–37.

    Chapter  Google Scholar 

  53. Somhom S, Modares A, Enkawa T. A self-organising model for the travelling salesman problem. J Oper Res Soc. 1997;48:919–28.

    Article  Google Scholar 

  54. Stodola P, Michenka K, Nohel J, Rybanskỳ M. Hybrid algorithm based on ant colony optimization and simulated annealing applied to the dynamic traveling salesman problem. Entropy. 2020;22:884.

    Article  MathSciNet  Google Scholar 

  55. Storer RH, Wu SD, Vaccari R. New search spaces for sequencing problems with application to job shop scheduling. Manag Sci. 1992;38:1495–509.

    Article  Google Scholar 

  56. Tawanda T, Nyamugure P, Kumar S, Munapo E. A labelling method for the travelling salesman problem. Appl Sci. 2023;13:6417.

    Article  Google Scholar 

  57. Tsai C-F, Tsai C-W, Tseng C-C. A new hybrid heuristic approach for solving large traveling salesman problem. Inf Sci. 2004;166:67–81.

    Article  MathSciNet  Google Scholar 

  58. Tuba M, Jovanovic R. Improved ACO algorithm with pheromone correction strategy for the traveling salesman problem. Int J Comput Commun Control. 2013;8:477–85.

    Article  Google Scholar 

  59. Uğur A, Aydin D. An interactive simulation and analysis software for solving TSP using ant colony optimization algorithms. Adv Eng Softw. 2009;40:341–9.

    Article  Google Scholar 

  60. Volgenant T, Jonker R. A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation. Eur J Oper Res. 1982;9:83–9.

    Article  MathSciNet  Google Scholar 

  61. Wang H, Zhang N, Créput J-C. A massively parallel neural network approach to large-scale Euclidean traveling salesman problems. Neurocomputing. 2017;240:137–51.

    Article  Google Scholar 

  62. Wang Y-T, Li J-Q, Gao K-Z, Pan Q-K. Memetic algorithm based on improved Inver-over operator and Lin-Kernighan local search for the Euclidean traveling salesman problem. Comput Math Appl. 2011;62:2743–54.

    Article  MathSciNet  Google Scholar 

  63. Yun H-Y, Jeong S-J, Kim K-S. Advanced harmony search with ant colony optimization for solving the traveling salesman problem. J Appl Math. 2013;2013(1): 123738.

    MathSciNet  Google Scholar 

  64. Zhang W. Truncated branch-and-bound: a case study on the asymmetric TSP. In: Proc. Of AAAI 1993 Spring Symposium on AI and NP-hard problems, vol. 160166. 1993. pp. 160–166.

  65. Zhao W, Ammar M, Zegura E. A message ferrying approach for data delivery in sparse mobile ad hoc networks. In: Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing. 2004. pp. 187–198.

Download references

Funding

The third author extends their appreciation to the Institute of Excellence, Banaras Hindu University (IoE BHU), for their support and collaborative efforts in carrying out this research.

Author information

Authors and Affiliations

  1. Department of Computer Application, Jagatpur P. G. College, Varanasi, Uttar Pradesh, 221302, India

    Dharm Raj Singh

  2. Department of Computer Science, Banaras Hindu University, Varanasi, Uttar Pradesh, 221005, India

    Manoj Kumar Singh, Sachchida Nand Chaurasia & Anshul Verma

Authors
  1. Dharm Raj Singh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Manoj Kumar Singh
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Sachchida Nand Chaurasia
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Anshul Verma
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

Dharm Raj Singh: Implementation, Validation, Writing- original draft. Manoj Kumar Singh: Conceptualization, Supervision, Writing-review & editing. Sachchida Nand Chaurasia: Writing- draft review & editing, Statistical analysis of results. Anshul Verma: Investigation, Visualization, Writing - Review and Editing.

Corresponding author

Correspondence to Sachchida Nand Chaurasia.

Ethics declarations

Conflict of interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Ethical Approval

This article does not contain any studies with human participants or animals performed by any of the authors.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Singh, D.R., Singh, M.K., Chaurasia, S.N. et al. Genetic Algorithm Incorporating Group Theory for Solving the General Travelling Salesman Problem. SN COMPUT. SCI. 5, 1075 (2024). https://doi.org/10.1007/s42979-024-03420-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s42979-024-03420-0

Keywords

Search

Navigation