An Efficient Solution to Travelling Salesman Problem using Genetic Algorithm with Modified Crossover Operator
The traveling salesman problem (TSP) is a famous NP-hard problem in the area of combinatorial optimization. It is utilized to locate the shortest possible route that visits every city precisely once and comes back to the beginning point from a given set of cities and distance. This paper proposes an efficient and effective solution for solving such a query. A modified crossover method using Minimal Weight Variable, Order Selection Crossover operator, a modified mutation using local optimization and a modified selection method using KMST is proposed. The crossover operator (MWVOSX) chooses a particular order from multiple orders which have the minimum cost and takes the remaining from the other parent in backward and forward order. Then it creates two new offspring. Further, it selects the least weight new offspring from those two offspring. The efficiency of the proposed algorithm is compared to the classical genetic algorithm. Comparisons show that our proposed algorithm provides much efficient results than the existing classical genetic algorithm.
Ezugwu, A. E. S., & Adewumi, A. O. Discrete symbiotic organisms search algorithm for travelling salesman problem. Expert Systems With Applications, 87, 70-78. 2017 DOI: https://doi.org/10.1016/j.eswa.2017.06.007
Chudasama, C., Shah, S. M., & Panchal, M. Comparison of parents selection methods of genetic algorithm for TSP. In International Conference on Computer Communication and Networks CSI-COMNET, Proceedings (pp. 85-87). 2011.
Xu, S., Wang, Y., & Huang, A. Application of imperialist competitive algorithm on solving the traveling salesman problem. Algorithms, 7(2), 229-242. 2014 DOI: https://doi.org/10.3390/a7020229
Srinivasan, K., Satyajit, S., Behera, B. K., & Panigrahi, P. K. Efficient quantum algorithm for solving travelling salesman problem: An IBM quantum experience. arXiv preprint arXiv:1805.10928. 2018
Hatamlou, A. Solving travelling salesman problem using black hole algorithm. Soft Computing, 22(24), 8167-8175. 2018. DOI: https://doi.org/10.1007/s00500-017-2760-y
Abdoun, O., & Abouchabaka, J. A comparative study of adaptive crossover operators for genetic algorithms to resolve the traveling salesman problem. arXiv preprint arXiv:1203.3097. 2012
Hussain, A., Muhammad, Y. S., Nauman Sajid, M., Hussain, I., Mohamd Shoukry, A., & Gani, S. Genetic Algorithm for Traveling Salesman Problem with Modified Cycle Crossover Operator. Computational intelligence and neuroscience, 2017. DOI: https://doi.org/10.1155/2017/7430125
Dwivedi, V., Chauhan, T., Saxena, S., & Agrawal, P. Travelling salesman problem using genetic algorithm. IJCA Proceedings on Development of Reliable Information Systems, Techniques and Related Issues (DRISTI 2012), 1, 25. 2012.
Islam, M. L., Pandhare, D., Makhthedar, A., & Shaikh, N. A Heuristic Approach for Optimizing Travel Planning Using Genetics Algorithm. International Journal of Research in Engineering and Technology eISSN, 2319-1163. 2014.
Karaboga, D., & Gorkemli, B. Solving Traveling Salesman Problem by Using Combinatorial Artificial Bee Colony Algorithms. International Journal on Artificial Intelligence Tools, 28(01), 1950004. 2019 DOI: https://doi.org/10.1142/S0218213019500040
Dorigo, M., & Gambardella, L. M. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on evolutionary computation, 1(1), 53-66. 1997 DOI: https://doi.org/10.1109/4235.585892
Copyright (c) 2020 EMITTER International Journal of Engineering Technology
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
The copyright to this article is transferred to Politeknik Elektronika Negeri Surabaya(PENS) if and when the article is accepted for publication. The undersigned hereby transfers any and all rights in and to the paper including without limitation all copyrights to PENS. The undersigned hereby represents and warrants that the paper is original and that he/she is the author of the paper, except for material that is clearly identified as to its original source, with permission notices from the copyright owners where required. The undersigned represents that he/she has the power and authority to make and execute this assignment. The copyright transfer form can be downloaded here .
The corresponding author signs for and accepts responsibility for releasing this material on behalf of any and all co-authors. This agreement is to be signed by at least one of the authors who have obtained the assent of the co-author(s) where applicable. After submission of this agreement signed by the corresponding author, changes of authorship or in the order of the authors listed will not be accepted.
Plagiarism screening will be conducted by EMITTER Journal Editorial Board using iThenticate Plagiarism Checker and CrossCheck plagiarism screening service. Author should download and signing declaration of plagiarism form here and resubmit it with copyright transfer form via online submission.