A novel memetic genetic algorithm for solving traveling salesman problem based on multi-parent crossover technique
Abstract
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.
Downloads
References
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.
