APPLICATION OF GENETIC ALGORITHMS TO THE TRAVELING SALESMAN PROBLEM
Tomasz Sikora
Akademia Humanistyczno-Ekonomiczna, Łódź (Poland)
https://orcid.org/0009-0009-2721-6796
Wanda Gryglewicz-Kacerka
wgryglewicz@ahe.lodz.plAkademia Humanistyczno-Ekonomiczna, Łódź (Poland)
https://orcid.org/0000-0003-4656-0540
Abstract
The purpose of this paper was to investigate in practice the possibility of using evolutionary algorithms to solve the traveling salesman problem on a real example. The goal was achieved by developing an original implementation of the evolutionary algorithm in Python, and by preparing an example of the traveling salesman problem in the form of a directed graph representing polish voivodship cities. As part of the work an application in Python was written. It provides a user interface which allows setting selected parameters of the evolutionary algorithm and solving the prepared problem. The results are presented in both text and graphical form. The correctness of the evolutionary algorithm's operation and the implementation was confirmed by performed tests. A large number of tested solutions (2500) and the analysis of the obtained results allowed for a conclusion that an optimal (relatively suboptimal) solution had been found.
Keywords:
evolutionary algorithms, genetic algorithms, traveling salesman problem, TSPReferences
Abdoun, O. & Abouchabaka, J. (2011). A Comparative Study of Adaptive Crossover Operators for Genetic Algorithms to Resolve the Traveling Salesman Problem. arXiv. https://doi.org/10.48550/arXiv.1203.3097
Google Scholar
Abellanas, M. R., & López-Ibáñez, M. (2008). An Introduction to the Traveling Salesman Problem. International Journal of Combinatorial Optimization Problems and Informatics, 1(1), 1-11. https://doi.org/10.4018/jcopi.2008010101
Google Scholar
Crainic, T. G., Fodor, J., & Grigoras, C. (2007). A Hybrid Evolutionary Algorithm for the Traveling Salesman Problem. IEEE Intelligent Systems, 22(2), 41-48. https://doi.org/10.1109/MIS.2007.37
DOI: https://doi.org/10.1109/MIS.2007.37
Google Scholar
Davis, L. (1985). Applying Adaptive Algorithms to Epistatic Domains. Proceedings of the 9th International Joint Conference on Artificial Intelligence, (vol 1, pp. 162-164).
Google Scholar
Gao, Y., & Li, X. (2018). A Novel Hybrid Evolutionary Algorithm for the Traveling Salesman Problem. IEEE Access, 6, 7072-7081. https://doi.org/10.1109/ACCESS.2018.2848862
Google Scholar
Goldberg, D. & Lingle, R. (1985). Alleles, Loci and the Traveling Salesman Problem. Proceedings of the 1st International Conference on Genetic Algorithms and Their Applications, (pp. 154-159).
Google Scholar
Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Boston: AddisonWesley Longman Publishing Co.
Google Scholar
Grefenstette, J. J. (1986). Optimization of Control Parameters for Genetic Algorithms. IEEE Transactions on Systems, Man, and Cybernetics, 16(1), 122-128. https://doi.org/10.1109/TSMC.1986.289287
DOI: https://doi.org/10.1109/TSMC.1986.289288
Google Scholar
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. Ann Arbor: University of Michigan Press. https://doi.org/10.7551/mitpress/1090.001.0001
DOI: https://doi.org/10.7551/mitpress/1090.001.0001
Google Scholar
Kumar, S., & Sharma, S. (2017). A Novel Hybrid Genetic Algorithm for Solving Traveling Salesman Problem. International Journal of Computer Applications, 159(2), 1-7. https://doi.org/10.5120/ijca2017914072
Google Scholar
Liao, Y. F., Yau, D. H., & Chen, C. L. (2012). Evolutionary algorithm to traveling salesman problems. Computers & Mathematics with Applications, 64(5), 788-797. https://doi.org/10.1016/j.camwa.2011.12.018
DOI: https://doi.org/10.1016/j.camwa.2011.12.018
Google Scholar
Dry, M., Lee, M. D., Vickers, D., & Hughes, P. (2006). Human Performance on Visually Presented Traveling Salesperson Problems with Varying Numbers of Nodes. The Journal of Problem Solving, 1(1).
DOI: https://doi.org/10.7771/1932-6246.1004
Google Scholar
Mousa, A. A., El-Shorbagy, M. A. & Farag, M. A. (2017). K-means-Clustering Based Evolutionary Algorithm for Multi-objective Resource Allocation Problems. Applied Mathematics & Information Sciences. 11(6), 1681-1692. https://doi.org/10.18576/amis/110615
DOI: https://doi.org/10.18576/amis/110615
Google Scholar
Oliver, I. M., Smith, D. j., & Holland, J. R. C. (1987). A Study of Permutation Crossover Operators on the Traveling Salesman Problem. International Conference on Genetic Algorithms. (pp. 224-230).
Google Scholar
Macgregor, J. N., & Ormerod, T. (1996). Human performance on the traveling salesman problem. Perception & Psychophysics, 58(4), 527–539. https://doi.org/10.3758/BF03213088
DOI: https://doi.org/10.3758/BF03213088
Google Scholar
Zieliński, D., & Dereniowski, D. (2015). Evolutionary Algorithm for Solving the Traveling Salesman Problem. International Journal of Computer Science, 12(2), 1-7.
Google Scholar
Authors
Tomasz SikoraAkademia Humanistyczno-Ekonomiczna, Łódź Poland
https://orcid.org/0009-0009-2721-6796
Authors
Wanda Gryglewicz-Kacerkawgryglewicz@ahe.lodz.pl
Akademia Humanistyczno-Ekonomiczna, Łódź Poland
https://orcid.org/0000-0003-4656-0540
Statistics
Abstract views: 323PDF downloads: 159
License
This work is licensed under a Creative Commons Attribution 4.0 International License.
All articles published in Applied Computer Science are open-access and distributed under the terms of the Creative Commons Attribution 4.0 International License.
Similar Articles
- Anitha Rani PALAKAYALA, Kuppusamy P, A QUALITATIVE AND QUANTITATIVE APPROACH USING MACHINE LEARNING AND NON-MOTOR SYMPTOMS FOR PARKINSON’S DISEASE CLASSIFICATION. A HIERARCHICAL STUDY , Applied Computer Science: Vol. 20 No. 3 (2024)
- Mariano LARIOS, Perfecto M. QUINTERO-FLORES , Mario ANZURES-GARCÍA , Miguel CAMACHO-HERNANDEZ , APPLICATION OF THE REAL-TIME FAN SCHEDULING IN THE EXPLORATION-EXPLOITATION TO OPTIMIZE MINIMUM FUNCTIONS OBJECTIVES , Applied Computer Science: Vol. 19 No. 2 (2023)
- Andrij MILENIN, PARALLEL SOLUTION OF THERMOMECHANICAL INVERSE PROBLEMS FOR LASER DIELESS DRAWING OF ULTRA-THIN WIRE , Applied Computer Science: Vol. 18 No. 3 (2022)
- Miguel Angel BELLO RIVERA, Carlos Alberto REYES GARCÍA, Tania Cristal TALAVERA ROJAS, Perfecto Malaquías QUINTERO FLORES, Rodolfo Eleazar PÉREZ LOAIZA, AUTOMATIC IDENTIFICATION OF DYSPHONIAS USING MACHINE LEARNING ALGORITHMS , Applied Computer Science: Vol. 19 No. 4 (2023)
- Wojciech DANILCZUK, THE USE OF SIMULATION ENVIRONMENT FOR SOLVING THE ASSEMBLY LINE BALANCING PROBLEM , Applied Computer Science: Vol. 14 No. 1 (2018)
- Andrzej ŁUKASZEWICZ, Jerzy JÓZWIK, Kamil CYBUL, IMPACT OF FRICTION COEFFICIENT VARIATION ON TEMPERATURE FIELD IN ROTARY FRICTION WELDING OF METALS – FEM STUDY , Applied Computer Science: Vol. 19 No. 3 (2023)
- Nataliya SHABLIY, Serhii LUPENKO, Nadiia LUTSYK, Oleh YASNIY, Olha MALYSHEVSKA, KEYSTROKE DYNAMICS ANALYSIS USING MACHINE LEARNING METHODS , Applied Computer Science: Vol. 17 No. 4 (2021)
- Marcin MACIEJEWSKI, Barbara MACIEJEWSKA, Robert KARPIŃSKI, Przemysław KRAKOWSKI, ELECTROCARDIOGRAM GENERATION SOFTWARE FOR TESTING OF PARAMETER EXTRACTION ALGORITHMS , Applied Computer Science: Vol. 16 No. 4 (2020)
- Sheikh Amir FAYAZ, Majid ZAMAN, Muheet Ahmed BUTT, Sameer KAUL, HOW MACHINE LEARNING ALGORITHMS ARE USED IN METEOROLOGICAL DATA CLASSIFICATION: A COMPARATIVE APPROACH BETWEEN DT, LMT, M5-MT, GRADIENT BOOSTING AND GWLM-NARX MODELS , Applied Computer Science: Vol. 18 No. 4 (2022)
- Jarelh Galdos, Nikolai Lopez, Angie Medina, Jorge Huarca, Jorge Rendulich, Erasmo Sulla, COMPARISON AND EVALUATION OF LMS-DERIVED ALGORITHMS APPLIED ON ECG SIGNALS CONTAMINATED WITH MOTION ARTIFACT DURING PHYSICAL ACTIVITIES , Applied Computer Science: Vol. 20 No. 1 (2024)
You may also start an advanced similarity search for this article.
