An Efficient Solution to Travelling Salesman Problem using Genetic Algorithm with Modified Crossover Operator
Abstract
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.
Downloads
References
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.
Retained Rights/Terms and Conditions
- Authors retain all proprietary rights in any process, procedure, or article of manufacture described in the Work.
- Authors may reproduce or authorize others to reproduce the work or derivative works for the author’s personal use or company use, provided that the source and the copyright notice of Politeknik Elektronika Negeri Surabaya (PENS) publisher are indicated.
- Authors are allowed to use and reuse their articles under the same CC-BY-NC-SA license as third parties.
- Third-parties are allowed to share and adapt the publication work for all non-commercial purposes and if they remix, transform, or build upon the material, they must distribute under the same license as the original.
Plagiarism Check
To avoid plagiarism activities, the manuscript will be checked twice by the Editorial Board of the EMITTER International Journal of Engineering Technology (EMITTER Journal) using iThenticate Plagiarism Checker and the CrossCheck plagiarism screening service. The similarity score of a manuscript has should be less than 25%. The manuscript that plagiarizes another author’s work or author's own will be rejected by EMITTER Journal.
Authors are expected to comply with EMITTER Journal's plagiarism rules by downloading and signing the plagiarism declaration form here and resubmitting the form, along with the copyright transfer form via online submission.
