GENETIC ALGORITHM AS A TOOL FOR SOLVING OPTIMISATION PROBLEMS

2023;
: 95-107
1
Lviv Polytechnic National University
2
Lviv Polytechnic National University
3
Lviv Polytechnic National University
4
Lviv Polytechnic National University

The article focuses on the peculiarities of using the genetic algorithm (GA) for solving optimization problems. It provides a classification of optimization problems and offers a detailed description of the structural elements of the GA and their role in solving the traveling salesman problem. To assess the impact of GA parameters on its effectiveness, a study on the influence of population size on the length of the traveling salesman's route is conducted. Based on the obtained results, it is shown that population size affects the route length, and the optimal population size for this problem is found to be 150. Using the tournament selection operator, the ordered crossover operator, and the inverse mutation operator, we obtained a salesman's route of 9271.735 km, which, based on the results presented in this paper, is optimal for visiting 29 cities.

[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