Genetic algorithm and discrete marine predators hybrid optimization technique for traveling salesman problem
*Mukhtar RajiCorresponding authorraji123.mukhtar@gmail.comDepartment of MathematicsPunjabi University PatialaPatiala, Punjab, 147002, IndiaView full profile → , Arjan SinghArjan.pup@gmail.comDepartment of MathematicsPunjabi University PatialaPatiala, Punjab, 147002, IndiaView full profile → , Satya Bir Singhsbsingh69@pbi.ac.inDepartment of MathematicsPunjabi University PatialaPatiala, Punjab, 147002, IndiaView full profile →
* Corresponding author · click or hover a name for details
- Received:
- 01 Dec 2025
- Published Online:
- 30 Sep 2026
- Article type:
- Research Article
- Language:
- EN
- Article no.:
- JIOS-2356
- Pages:
- 3167–3178
Abstract
The Traveling Salesman Problem (TSP) is a well-known combinatorial optimization problem, that has gained popularity over the past few years because of its broad applicability in service, logistics, and industrial optimization processes. The search for the optimal path, whose result is minimizing the total cost or distance, has always been a computationally intensive and difficult task.
This paper proposed a new hybrid meta-heuristic algorithm, Genetic Algorithm and Discrete Marine Predators Algorithm (GA-DMPA), for solving the TSP. In the first phase (exploration), the genetic algorithm is used to generate candidate tours per iteration. The second phase (exploitation) is the stage in which the Discrete Marine Predators Algorithm further narrows down on these candidate solutions to improve local search and increase convergence to the global optimum. This hybridization can be used to avoid premature convergence and to improve the quality and strength of the solutions. The practicality of the proposed GA-DMPA is proved by applying it to 20 real Indian cities and a benchmark function. The outcomes of the experiment compared with GA and DMPA algorithms, and the introduced hybrid GA-DMPA algorithm give better results. The results are summarized and present in form of figures and table.
Keywords
Subject Classifications
References
[1] A. E.-S. Ezugwu and A. O. Adewumi, “Discrete symbiotic organisms search algorithm for travelling salesman problem,” Expert Syst Appl, vol. 87, pp. 70–78 (Nov. 2017), doi: 10.1016/j.eswa.2017.06.007.
[2] J. Zhang, L. Hong, and Q. Liu, “An Improved Whale Optimization Algorithm for the Traveling Salesman Problem,” Symmetry (Basel), vol. 13, no. 1, p. 48 (Dec. 2020), doi: 10.3390/sym13010048.
[3] E. Osaba, J. Del Ser, A. Sadollah, M. N. Bilbao, and D. Camacho, “A discrete water cycle algorithm for solving the symmetric and asymmetric traveling salesman problem,” Appl Soft Comput, vol. 71, pp. 277–290 (Oct. 2018), doi: 10.1016/j.asoc.2018.06.047.
[4] Y. Zhong, J. Lin, L. Wang, and H. Zhang, “Discrete comprehensive learning particle swarm optimization algorithm with Metropolis acceptance criterion for traveling salesman problem,” Swarm Evol Comput, vol. 42, pp. 77–88 (Oct. 2018), doi: 10.1016/j.swevo.2018.02.017.
[5] A. Ouaarab, B. Ahiod, and X.-S. Yang, “Discrete cuckoo search algorithm for the travelling salesman problem,” Neural Comput Appl, vol. 24, no. 7–8, pp. 1659–1669 (Jun. 2014), doi: 10.1007/s00521-013-1402-2.
[6] H. B. Ban, “An efficient two-phase metaheuristic algorithm for the time dependent traveling Salesman problem,” RAIRO - Operations Research, vol. 53, no. 3, pp. 917–935 (Jul. 2019), doi: 10.1051/ro/2019006.
[7] J. Bi, G. Zhou, Y. Zhou, Q. Luo, and W. Deng, “Artificial Electric Field Algorithm with Greedy State Transition Strategy for Spherical Multiple Traveling Salesmen Problem,” International Journal of Computational Intelligence Systems, vol. 15, no. 1, p. 5 (Dec. 2022), doi: 10.1007/s44196-021-00059-0.
[8] P. Pirozmand, A. Hosseinabadi, M. J. Chari, F. Pahlavan, S. Mirkamali, G.-W. Weber, S. Nosheen, and A. Abraham, “D-PFA: A Discrete Metaheuristic Method for Solving Traveling Salesman Problem Using Pathfinder Algorithm,” IEEE Access, vol. 11, pp. 106544–106566 (2023), doi: 10.1109/ACCESS.2023.3320562.
[9] A. A. Chaves, B. L. Vianna, T. T. da Silva, and C. M. Schenekemberg, “A parallel branch-and-cut and an adaptive metaheuristic to solve the Family Traveling Salesman Problem,” Expert Syst Appl, vol. 238, p. 121735 (Mar. 2024), doi: 10.1016/j.eswa.2023.121735.
[10] K. Panwar and K. Deep, “Discrete Grey Wolf Optimizer for symmetric travelling salesman problem,” Appl Soft Comput, vol. 105, p. 107298 (Jul. 2021), doi: 10.1016/j.asoc.2021.107298.
[11] M. A. H. Akhand, S. I. Ayon, S. A. Shahriyar, N. Siddique, and H. Adeli, “Discrete Spider Monkey Optimization for Travelling Salesman Problem,” Appl Soft Comput, vol. 86, p. 105887 (Jan. 2020), doi: 10.1016/j.asoc.2019.105887.
[12] Y. Wang, Y. W. Wu, and N. Xu, “Discrete symbiotic organism search with excellence coefficients and self-escape for traveling salesman problem,” Comput Ind Eng, vol. 131, pp. 269–281 (May 2019), doi: 10.1016/j.cie.2019.04.008.
[13] G. H. Al-Gaphari, R. Al-Amry, and A. S. Al-Nuzaili, “Discrete crow-inspired algorithms for traveling salesman problem,” Eng. Appl Artif Intell, vol. 97, p. 104006 (Jan. 2021), doi: 10.1016/j.engappai.2020.104006.
[14] Y. Wang, “The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem,” Comput Ind Eng, vol. 70, pp. 124–133 (Apr. 2014), doi: 10.1016/j.cie.2014.01.015.
[15] M. Kumar, K. Panwar, and K. Deep, “Discrete Marine Predators Algorithm for Symmetric Travelling Salesman Problem,” Evol Intell, vol. 17, no. 5–6, pp. 3833–3848 (Oct. 2024), doi: 10.1007/s12065-024-00960-5.
[16] W. J. Cook, D. L. Applegate, R. E. Bixby, and V. Chvátal, The Traveling Salesman Problem. Princeton University Press (Sep. 2011), doi: 10.1515/9781400841103.
[17] T. Tawanda, P. Nyamugure, S. Kumar, and E. Munapo, “A Labelling Method for the Travelling Salesman Problem,” Applied Sciences, vol. 13, no. 11, p. 6417 (May 2023), doi: 10.3390/app13116417.
[18] R. Jain, M. L. Meena, and K. P. Singh, “Travelling salesman problem optimization using hybrid genetic algorithm,” in Conference Proceedings of ICDLAIR2019, M. Tripathi and S. Upadhyaya, Eds., Lecture Notes in Networks and Systems, vol. 175. Cham, Switzerland: Springer, 2021, pp. 350–356, doi: 10.1007/978-3-030-67187-7_36.
[19] M. Abdel-Basset, L. Abdel-Fatah, and A. K. Sangaiah, “Metaheuristic Algorithms: A Comprehensive Review,” in Computational Intelligence for Multimedia Big Data on the Cloud with Engineering Applications, Elsevier, pp. 185–231 (2018), doi: 10.1016/B978-0-12-813314-9.00010-4.
[20] A. J. Jones, “Genetic algorithms and their applications to the design of neural networks,” Neural Comput Appl, vol. 1, no. 1, pp. 32–45 (Mar. 1993), doi: 10.1007/BF01411373.
[21] S. M. Stefanov, “Multi-objective optimization revisited,” Journal of Information & Optimization Sciences, vol. 47, no. 3, pp. 833–848 (2026), doi: 10.47974/JIOS-1395.
[22] C.-C. Chou, “Touring a Sequence of Spheres in R3,” Journal of Interdisciplinary Mathematics, vol. 27, no. 7, pp. 1615–1636 (2024), doi: 10.47974/JIM-2002.
[23] A. Faramarzi, M. Heidarinejad, B. Stephens, and S. Mirjalili, “Equilibrium optimizer: A novel optimization algorithm”, Knowledge-based systems, vol. 191, Art. no. 105190 (2020).
