A novel memetic genetic algorithm for solving traveling salesman problem based on multi-parent crossover technique

  • Arindam Roy Deptartment of Computer Science, Prabhat Kumar College, Purba Medinipur, West Bengal, India
  • Apurba Manna Deptartment of Computer Science, Prabhat Kumar College, Purba Medinipur, West Bengal, India
  • Samir Maity Operations Management Group, Indian Institute of Management, Kolkata, India
Keywords: TSP, Memetic GA, multi-parent crossover.


In the present study, a Novel Memetic Genetic Algorithm (NMGA) is developed to solve the Traveling Salesman Problem (TSP). The proposed NMGA is the combination of Boltzmann probability selection and a multi-parent crossover technique with known random mutation. In the proposed multi-parent crossover parents and common crossing point are selected randomly. After comparing the cost/distance with the adjacent nodes (genes) of participated parents, two offspring’s are produced. To establish the efficiency of the developed algorithm standard benchmarks are solved from TSPLIB against classical genetic algorithm (GA) and the fruitfulness of the proposed algorithm is recognized. Some statistical test has been done and the parameters are studied.


Download data is not yet available.


Aguilar, J. & Colmenares, A. (1998). Resolution of pattern recognition problems using a hybrid genetic/random neural network learning algorithm. Pattern Analysis and Applications, 1(1), 52–61. DOI: https://doi.org/10.1007/BF01238026

Baldwin, J.M. (1896). A new factor in evolution. The american naturalist, 30(3), 441–451. DOI: https://doi.org/10.1086/276408

Chyu, C.C., & Chang, W.S. (2010). A competitive evolution strategy memetic algorithm for unrelated parallel machine scheduling to minimize total weighted tardiness and flow time. The 40th International Conference on Computers & Indutrial Engineering, 1–6. DOI: https://doi.org/10.1109/ICCIE.2010.5668388

Das, D., Roy, A., Kar, S. (2010). Improving production policy for a deteriorating item under permissible delay in payments with stock-dependent demand rate. Computers & Mathematics with Applications, 60(7), 1973–1985. DOI: https://doi.org/10.1016/j.camwa.2010.07.031

Das, D., Roy, A., Kar, S. (2011). A volume flexible economic production lot-sizing problem with imperfect quality and random machine failure in fuzzy-stochastic environment. Computers & Mathematics with Applications, 61(9), 2388–2400. DOI: https://doi.org/10.1016/j.camwa.2011.02.015

Goldberg, D.E. & Holland, J.H. (1998). Genetic algorithms and machine learning. Machine learning, 3(2), 95–99. DOI: https://doi.org/10.1023/A:1022602019183

Haas, O.C.L., Burnham, K.J. & Mills, J.A. (1998). Optimization of beam orientation in radiotherapy using planar geometry. Physics in Medicine & Biology, 43(8), 217-229. DOI: https://doi.org/10.1088/0031-9155/43/8/013

Harris, S.P. & Ifeachor, E.C. (1998). Automatic design of frequency sampling filters by hybrid genetic algorithm techniques. IEEE Transactions on Signal Processing, 46(12), 3304–3314. DOI: https://doi.org/10.1109/78.735305

Hiremath, C.S. & Hill, R.R. (2013). First-level tabu search approach for solving the multiple-choice multidimensional knapsack problem. International Journal of Metaheuristics, 2(2), 174–199. DOI: https://doi.org/10.1504/IJMHEUR.2013.054150

Holland, J.H. (1992). Genetic algorithms. Scientific American, 267(1), 66–73. DOI: https://doi.org/10.1038/scientificamerican0792-66

Ichimura, T. & Kuriyama, Y. (1998). Learning of neural networks with parallel hybrid GA using a royal road function. IEEE World Congress on Computational Intelligence in Neural Networks Proceedings, 2, 1131–1136.

Jampani, J. (2010). Integrated heuristics for scheduling multiple order jobs in a complex job shop. International Journal of Metaheuristics, 1(2), 156-180. DOI: https://doi.org/10.1504/IJMHEUR.2010.034204

Kar, K. (2018). A multi-objective multi-item solid transportation problem with vehicle cost, volume and weight capacity under fuzzy environment. Journal of Intelligent & Fuzzy Systems, 35, 1–10.

Kumar, Y., Das, B., & Sharma, J. (2006). Genetic algorithm for supply restoration in distribution system with priority customers. International Conference on Probabilistic Methods Applied to Power Systems, 1–7. DOI: https://doi.org/10.1109/PMAPS.2006.360295

Kundu, P. (2017). A solid transportation model with product blending and parameters as rough variables. Soft Computing, 21, 2297–2306. DOI: https://doi.org/10.1007/s00500-015-1941-9

Lawler, E.L., & Lenstra, J.K. (1985). The traveling salesman problem: a guided tour of combinatorial optimization. Wiley, 3, 1–463.

Li, W., & Feng, M. (2013). Solution attractor of local search in travelling salesman problem: concept, construction and application. International Journal of Metaheuristics, 2(3), 201–233. DOI: https://doi.org/10.1504/IJMHEUR.2013.056388

Martinez-Estudillo, A.C. (2005). Hybridization of evolutionary algorithms and local search by means of a clustering method. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 36, 534–545. DOI: https://doi.org/10.1109/TSMCB.2005.860138

Moscato, P. (1989). On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. Caltech concurrent computation program, 3, 826-839.

Nesmachnow, S. (2014). An overview of metaheuristics: accurate and efficient methods for optimisation. International Journal of Metaheuristics, 3(4), 320–347. DOI: https://doi.org/10.1504/IJMHEUR.2014.068914

Omran, M.G. (2016). A novel cultural algorithm for real-parameter optimization. International Journal of Computer Mathematics, 93(9), 1541–1563. DOI: https://doi.org/10.1080/00207160.2015.1067309

Reinelt, G. (1991). TSPLIB-A Traveling Salesman Problem Library. ORSA Journal on Computing, 3(4), 376-384. DOI: https://doi.org/10.1287/ijoc.3.4.376

Reynolds, R.G., & Peng, B. (2004). Cultural algorithms: modeling of how cultures learn to solve problems. In Tools with Artificial Intelligence. IEEE International Conference, 166–172.

Roy, A., Chakraborty, G., Khan, I., Maity, S., & Maiti, M. (2018). A Hybrid Heuristic for Restricted 4-Dimensional TSP (r-4DTSP). Proceedings in Mathematics & Statistics, 285–302. DOI: https://doi.org/10.1007/978-981-10-7814-9_20

Silberholz, J. (2013). Comparison of heuristics for the colorful traveling salesman problem. International Journal of Metaheuristics, 2, 141–173. DOI: https://doi.org/10.1504/IJMHEUR.2013.054143

Skinner, M.K. (2015). Environmental epigenetics and a unified theory of the molecular aspects of evolution: A neo-Lamarckian concept that facilitates neo-Darwinian evolution. Genome biology and evolution, 7(5), 1296–1302. DOI: https://doi.org/10.1093/gbe/evv073

Wang, Y., Lu, Z., & Hao, J.K. (2010). A study of multi-parent crossover operators in a memetic algorithm. International Conference on Parallel Problem Solving from Nature, 556–565. DOI: https://doi.org/10.1007/978-3-642-15844-5_56

Wehrens, R. (1993). HIPS, a hybrid self-adapting expert system for nuclear magnetic resonance spectrum interpretation using genetic algorithms. Analytica Chimica Acta, 277(2), 313–324. DOI: https://doi.org/10.1016/0003-2670(93)80444-P

Ye, T., Lu, Z., & Hao, J.K. (2014). A Multi-parent memetic algorithm for the linear ordering problem. arXiv preprint arXiv:1405.4507.

How to Cite
Roy, A., Manna, A., & Maity, S. (2019). A novel memetic genetic algorithm for solving traveling salesman problem based on multi-parent crossover technique. Decision Making: Applications in Management and Engineering, 2(2), 100-111. https://doi.org/10.31181/dmame1902076r