Application of genetic algorithms to the traveling salesman problem

• Autorzy: Sikora Tomasz , Gryglewicz-Kacerka Wanda

Identyfikatory

DOI

10.35784/acs-2023-14

• Języki publikacji: EN

Abstrakty

EN

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 to set selected parameters of the evolutionary algorithm and solve 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 was found.

Słowa kluczowe

EN

evolutionary algorithms; genetic algorithms; traveling salesman problem; TSP

• Wydawca: Polskie Towarzystwo Promocji Wiedzy ; Lublin University of Technology
• Czasopismo: Applied Computer Science
• Rocznik: 2023
• Tom: Vol. 19, no 2
• Strony: 55--62
• Opis fizyczny: Bibliogr. 15 poz., fig.

Twórcy

autor

Sikora Tomasz

• Akademia Humanistyczno-Ekonomiczna, Łódź, Poland,

autor

Gryglewicz-Kacerka Wanda

• Akademia Humanistyczno-Ekonomiczna, Łódź, Poland,

• https://orcid.org/0000-0003-4656-0540

Bibliografia

• [1] 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
• [2] Davis, L. (1985). Applying Adaptive Algorithms to Epistatic Domains. Proceedings of the 9th International Joint Conference on Artificial Intelligence, 1, 162-164. https://dl.acm.org/doi/10.5555/1625135.1625164
• [3] Eiben, A.E., & Smith, J.E. (2015). Fitness, Selection, and Population Management. Introduction to Evolutionary Computing (pp. 79–98). Springer. https://doi.org/10.1007/978-3-662-44874-8_5
• [4] Goldberg, D. & Lingle, R. (1985). Alleles, Loci and the Traveling Salesman Problem. Proceedings of the 1st International Conference on Genetic Algorithms and Their Applications, 154-159. https://dl.acm.org/doi/10.5555/645511.657095
• [5] Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Boston. Addison-Wesley Publishing Company. https://dl.acm.org/doi/book/10.5555/534133
• [6] 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.289288
• [7] 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
• [8] 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
• [9] 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). https://doi.org/10.7771/1932-6246.1004
• [10] 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
• [11] 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. 224-230. https://dl.acm.org/doi/abs/10.5555/42512.42542
• [12] 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
• [13] Silberholz J., Golden B. (2007), The Generalized Traveling Salesman Problem: A New Genetic Algorithm Approach, In Baker, E.K., Joseph, A., Mehrotra, A., Trick, M.A. (Eds), Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies, 37. Springer 165–181. https://doi.org/10.1007/978-0-387-48793-9_11
• [14] Yu, F., Fu, X., Li, H., & Dong, G. (2016). Improved Roulette Wheel Selection-Based Genetic Algorithm for TSP. 2016 Insternational Conference on Network and Information Systems for Computers (ICNISC) (151-154). https://doi.org/10.1109/icnisc.2016.041
• [15] Yu, X., & Gen, M. (2010). Introduction to Evolutionary Algorithms. Decision Engineering. (pp. 286–288) Springer. https://doi.org/10.1007/978-1-84996-129-5