APPLICATION OF GENETIC ALGORITHMS TO THE TRAVELING SALESMAN PROBLEM

Tomasz Sikora; Wanda Gryglewicz-Kacerka

doi:10.35784/acs-2023-14

Open full text

PDF

Published: Jun 30, 2023

DOI: https://doi.org/10.35784/acs-2023-14

Issue Vol. 19 No. 2 (2023)

Articles

CNN AND LSTM FOR THE CLASSIFICATION OF PARKINSON'S DISEASE BASED ON THE GTCC AND MFCC
Nouhaila BOUALOULOU, Taoufiq BELHOUSSINE DRISSI, Benayad NSIRI

1-24
MASK FACE INPAINTING BASED ON IMPROVED GENERATIVE ADVERSARIAL NETWORK
Qingyu Liu, Roben A. Juanatas

25-42
APPLICATION OF THE REAL-TIME FAN SCHEDULING IN THE EXPLORATION-EXPLOITATION TO OPTIMIZE MINIMUM FUNCTIONS OBJECTIVES
Mariano LARIOS, Perfecto M. QUINTERO-FLORES , Mario ANZURES-GARCÍA , Miguel CAMACHO-HERNANDEZ

43-54
APPLICATION OF GENETIC ALGORITHMS TO THE TRAVELING SALESMAN PROBLEM
Tomasz Sikora, Wanda Gryglewicz-Kacerka

55-62
THE POTENTIAL FOR REAL-TIME TESTING OF HIGH FREQUENCY TRADING STRATEGIES THROUGH A DEVELOPED TOOL DURING VOLATILE MARKET CONDITIONS
Mantas Vaitonis, Konstantinas Korovkinas

63-81
NAVIGATION STRATEGY FOR MOBILE ROBOT BASED ON COMPUTER VISION AND YOLOV5 NETWORK IN THE UNKNOWN ENVIRONMENT
Thanh-Lam BUI, Ngoc-Tien TRAN

82-95
A NEW METHOD FOR GENERATING VIRTUAL MODELS OF NONLINEAR HELICAL SPRINGS BASED ON A RIGOROUS MATHEMATICAL MODEL
Krzysztof Michalczyk, Mariusz Warzecha, Robert Baran

96-111
HYBRID FEATURE SELECTION AND SUPPORT VECTOR MACHINE FRAMEWORK FOR PREDICTING MAINTENANCE FAILURES
Mouna TARIK, Ayoub MNIAI, Khalid JEBARI

112-124
CLASSIFICATION OF PARKINSON'S DISEASE IN BRAIN MRI IMAGES USING DEEP RESIDUAL CONVOLUTIONAL NEURAL NETWORK
Puppala Praneeth, Majety Sathvika, Vivek Kommareddy, Madala Sarath, Saran Mallela, Koneru Suvarna Vani, Prasun Chkrabarti

125-146
EXPLOITING BERT FOR MALFORMED SEGMENTATION DETECTION TO IMPROVE SCIENTIFIC WRITINGS
Abdelrahman Halawa, Shehab Gamalel-Din; Abdurrahman Nasr

126-141

DOI

https://doi.org/10.35784/acs-2023-14

Authors

Tomasz Sikora

tomek.sikora@pm.me

Akademia Humanistyczno-Ekonomiczna, Łódź, Poland

https://orcid.org/0009-0009-2721-6796

Wanda Gryglewicz-Kacerka

wgryglewicz@ahe.lodz.pl

Akademia 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, TSP

References

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

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

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

Davis, L. (1985). Applying Adaptive Algorithms to Epistatic Domains. Proceedings of the 9th International Joint Conference on Artificial Intelligence, (vol 1, pp. 162-164).

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

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).

Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Boston: AddisonWesley Longman Publishing Co.

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

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

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

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

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

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

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).

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

Zieliński, D., & Dereniowski, D. (2015). Evolutionary Algorithm for Solving the Traveling Salesman Problem. International Journal of Computer Science, 12(2), 1-7.

Sikora, T., & Gryglewicz-Kacerka, W. (2023). APPLICATION OF GENETIC ALGORITHMS TO THE TRAVELING SALESMAN PROBLEM. Applied Computer Science, 19(2), 55–62. https://doi.org/10.35784/acs-2023-14

APPLICATION OF GENETIC ALGORITHMS TO THE TRAVELING SALESMAN PROBLEM

Issue Vol. 19 No. 2 (2023)

Archives

DOI

Authors

Abstract

Keywords:

References

License

Article Sidebar

Issue Vol. 19 No. 2 (2023)

Archives

Main Article Content

DOI

Authors

Abstract

Keywords:

References

Article Details

License