Стаття присвячена особливостям використання генетичного алгоритму (ГА) для розв’язання оптимізаційних задач. Наведено класифікацію оптимізаційних задач. Детально описано структурні елементи ГА та їх роль для розв’язання задачі комівояжера. Для оцінки впливу параметрів ГА на ефективність його застосування здійснено дослідження впливу розміру популяції на довжину маршруту комівояжера. На основі отриманих результатів показано, що розмір популяції впливає на довжину маршруту, а оптимальне значення розміру популяції для даної задачі становить 150. Використання турнірного оператора відбору, оператора впорядкованого схрещування, інверсійного оператора мутації дозволило сформувати маршрут комівояжера довжиною 9271.735 км, який, на основі представлених у роботі результатів, є оптимальним для відвідування 29 міст.
[1] Liu, R. and Wang, Y. (2019), “Research on TSP Solution Based on Genetic Algorithm,” IEEE ACIS 18th International Conference on Computer and Information Science (ICIS), Beijing, China, pp. 230-23. doi: 10.1109/ICIS46139.2019.8940186
[2] Pavlenko, O., Tymoshenko, A., Tymoshenko, O., Luntovskyy, A., Pyrih, Y. and Melnyk, I. (2023), Searching Extreme Paths Based on Travelling Salesman’s Problem for Wireless Emerging Networking. In: Klymash, M., Luntovskyy, A., Beshley, M., Melnyk, I., Schill, A. (eds) Emerging Networking in the Digital Transformation Age. TCSET 2022. Lecture Notes in Electrical Engineering, vol 965. Springer, Cham. doi: https://doi.org/10.1007/978-3-031-24963-1_16
[3] Pyrih, Y., Kaidan, M., Tchaikovskyi, I. and Pleskanka, M. (2019), “Research of Genetic Algorithms for Increasing the Efficiency of Data Routing,” 3rd International Conference on Advanced Information and Communications Technologies (AICT), Lviv, Ukraine, pp. 157-160. doi: 10.1109/AIACT.2019.8847814
[4] Swarnakar, S., Kumar, N., Kumar, A. and Banerjee, C. (2020), “Modified Genetic Based Algorithm for Load Balancing in Cloud Computing,” IEEE 1st International Conference for Convergence in Engineering (ICCE), Kolkata, India, pp. 255-259. doi: 10.1109/ICCE50343.2020.9290563
[5] Zitar, R. (2022), “A Review of the Genetic Algorithm and JAYA Algorithm Applications, ” 15th International Congress on Image and Signal Processing, (CISP-BMEI), Beijing, China, pp. 1-7. doi: 10.1109/CISP-BMEI56279.2022.9980332
[6] Abdallah, W. and Val, T. (2020), “Genetic-Voronoi algorithm for coverage of IoT data collection networks,” 30th International Conference on Computer Theory and Applications (ICCTA), Alexandria, Egypt, pp. 16-22. doi: https://doi.org/10.48550/arXiv.2202.13735
[7] Sharaf, A. and Pillai, M. (2019), “Genetic Algorithm Based Clustering Techniques in Wireless Sensor Networks: A Comprehensive Study, ” 1st International Conference on Innovations in Information and Communication Technology (ICIICT), Chennai, India, pp. 1-5. doi: 10.1109/ICIICT1.2019.8741485
[8] Klymash, M., Kaidan, M., Strykhalyuk, B., Pyrih, Y. and Pyrih, Y. (2023), “Method for Estimating the Topological Structure of Self-Organized Networks,” 17th Int. Conf.on the Experience of Designing and Application of CAD Systems (CADSM), Jaroslaw, Poland, 2023, pp. 14-17. doi: 10.1109/CADSM58174.2023.10076498.
[9] Grant, R. (2022), TSPLIB 95 Documentation, Release 0.7.1, 52 p.
[10] Rainville, F., Fortin, F., Gardner, M., Parizeau, M., Gagné, C. (2012), “DEAP: a python framework for evolutionary algorithms,” 14th annual conference companion on Genetic and Evolutionary Computation (GECCO '12). Association for Computing Machinery, New York, NY, USA, pp 85–92. doi: 10.1145/2330784.2330799