Стаття присвячена оцінці обчислювальної складності генетичного алгоритму як одного із ключових засобів для розв’язання оптимізаційних задач. Розглянуто теоретичні аспекти обчислювальної складності алгоритмів та взаємозв'язок елементів генетичного алгоритму. Описано основні види обчислювальної складності алгоритмів: часову, просторову та асимптотичну. Наведено п’ять основних правил для розрахунку асимптотичної складності. Представлено математичний апарат для оцінки асимптотичної складності генетичного алгоритму, який враховує витрати на формування початкової популяції та на виконання еволюції. Еволюція відбувається через ітерації, під час яких покоління індивідів піддаються певним операціям з метою знаходження оптимального рішення (схрещування, мутації, декодування хромосоми тощо). ГА, в якості алгоритму глобального пошуку, розглядається для знаходження оптимального шляху без застрягання в локальних мінімумах. Для оцінки обчислювальної складності ГА розглянуто розв’язання задачі комівояжера (TSP) для 28 міст України з використанням модифікованої бібліотеки TSPLIB та платформи DEAP, створеної на мові програмування Python. Представлено блок-схему ГА, основними елементами якого є турнірний оператор відбору, оператор впорядкованого схрещування та інверсійний оператор мутації. Здійснено дослідження впливу розміру популяції та кількості поколінь на асимптотичну складність генетичного алгоритму при розв’язанні задачі TSP. Під час проведення дослідження розглядалась зміна розміру популяції ГА від 50 до 500 з кроком 50, при цьому для кожного такого значення моделювалось чотири набори кількості поколінь: від 50 до 200 із кроком 50. На основі отриманих результатів представлено лінійну залежність часу виконання ГА від розміру розглянутих вхідних даних. Показано, що найменша часова складність представленого ГА для наведеної задачі TSP становить 0.33848 секунди при розмірі популяції 50 та аналогічній кількості поколінь, тоді як найбільше значення – 3.752734 секунди при розмірі популяції 500 та кількості поколінь 200. Отримані результати можуть бути використані для оптимізації роботи ГА, зокрема в задачі TSP.
[1] Čoriс, R., Dumiс, M., & Jakoboviс, D. (2017). "Complexity comparison of integer programming and genetic algorithms for resource constrained scheduling problems," 2017 40th Int. Convention on Information and Communication Technology, Electronics and Microelectronics, Croatia, pp. 1182-1188.
[2] Marappan, R., & Sethumadhavan, G. (2020). Complexity Analysis and Stochastic Convergence of Some Well-known Evolutionary Operators for Solving Graph Coloring Problem. Mathematics, 8(3):303. https://doi.org/10.3390/math8030303.
[3] Hafiiak A. (2018). Application of genetic programming tools as a means of solving optimization. Системи управління, навігації та зв’язку. Збірник наукових праць. – Полтава, Т. 6 (52). – С. 58-60.
[4] Коваль, В.С., & Струбицький, П.Р. (2017). Алгоритми і структури даних. – Навчальний посібник –Тернопіль: ФОП Шпак В. Б., 74 с.
[5] Bektas, T. (2006). The multiple traveling salesman problem: an overview of formulations and solution procedures. // Omega. Volume 34, Issue 3, p. 209-219.
[6] Sabbah, T. (2020). "Enhanced Genetic Algorithm for Optimized Classification," 2020 International Conference on Promising Electronic Technologies (ICPET), Jerusalem, Palestine, pp. 161-166, doi: 10.1109/ICPET51420.2020.00039.
[7] Muh-Cherng, W., Chi-Shiuan, L., Chia-Hui, L., & Chen-Fu, C. (2017). Effects of different chromosome representations in developing genetic algorithms to solve DFJS scheduling problems, Computers & Operations Research, Volume 80, рр. 101-112, https://doi.org/10.1016/j.cor.2016.11.021.
[8] Ashraf, M., Gola, A., AlArjani, A., Hasan, F. (2022). Optimization of a Can Size Problem Using Real Encoded Chromosome in Genetic Algorithm. Journal of Physics: Conference Series, vol. 2198, https://dx.doi.org/10.1088/1742-6596/2198/1/012004.
[9] Lissovoi, A. & Oliveto, P.S. (2019) On the time and space complexity of genetic programming for evolving Boolean conjunctions. Journal of Artificial Intelligence Research, 66. pp. 655-689.
[10] Durrett, G., Neumann, F., & O’Reilly, U. M. (2011). "Computational complexity analysis of simple genetic programming on two problems modeling isolated program semantics". In Proceedings of the Foundations of Genetic Algorithms workshop (FOGA 2011), pp.69–80.
[11] Volovyk, A., Pyrih, Y., Urikova ,O., Masiuk, A., Shubyn, B., & Maksymyuk, T. (2024). Dynamic System State Estimation with a Resilience to Observation Data Anomalies. Contemporary Mathematics (Singapore), 5 (1).
[12] Oliveto, P. S., He, J., & Yao, X. (2017). Time complexity of evolutionary algorithms for combinatorial optimization: A decade of results. International Journal of Automation and Computing, 4 (3), 281–293.
[13] Pyrih, Y., Klymash, M., Kaidan, M., & Strykhalyuk, B. (2023). "Investigating the Efficiency of Tournament Selection Operator in Genetic Algorithm for Solving TSP", IEEE 5th International Conference on Advanced Information and Communication Technologies (AICT-2023), 21-25 November, Lviv, Ukraine.
[14] Пиріг, Я., Климаш, М., Пиріг, Ю., & Лаврів, О.(2023). Генетичний алгоритм як засіб розв'язання оптимізаційних задач. Інфокомунікаційні технології та електронна інженерія, №3(2), С. 95-107. https://doi.org/10.23939/ictee2023.02.
[15] Maha Ata Al-Omeer & Zakir Hussain Ahmed (2019). "Comparative study of crossover operators for the mtsp", 2019 International Conference on Computer and Information Sciences (ICCIS), pр. 1–6, doi: 10.1109/ICCISci.2019.8716483.
[16] Bernardino, R., & Paias, A .(2018). Metaheuristics based on decision hierarchies for the traveling purchaser problem. International Transactions in Operational Research, 25(4):1269–1295, doi: 10.1111/itor.12330.
[17] Pavlenko, O., Tymoshenko, A., Tymoshenko, O., Luntovskyy, A., Pyrih, Y., & 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. Lecture Notes in Electrical Engineering, vol 965. Springer, Cham. https://doi.org/10.1007/978-3-031-24963-1_16
[18] Pyrih, Y., Masiuk, A., Pyrih, Y., & Urikova, O. (2024). Investigation of a Genetic Algorithm for Solving the Travelling Salesman Problem. In: Luntovskyy, A., Klymash, M., Melnyk, I., Beshley, M., Schill, A. (eds) Digital Ecosystems: Interconnecting Advanced Networks with AI Applications. Springer.
[19] Lakshmi, R., & Vivekanandan, K. (2013). "An analysis of recombination operator in genetic algorithms," 2013 Fifth International Conference on Advanced Computing (ICoAC), Chennai, India, pp. 223-226, doi: 10.1109/ICoAC.2013.6921954.
[20] Pravesjit, S., & Kantawong, K. (2017). "An improvement of genetic algorithm for optimization problem," 2017 International Conference on Digital Arts, Media and Technology (ICDAMT), Chiang Mai, Thailand, pp. 226-229, doi: 10.1109/ICDAMT.2017.7904966.
[21] Roeva, O., Shannon, A., & Pencheva, T.(2012) "Description of simple genetic algorithm modifications using Generalized Nets," 2012 6th IEEE International Conference Intelligent Systems, Sofia, Bulgaria, 2012, pp. 178-183, doi: 10.1109/IS.2012.6335212.
[22] Hildayanti, I.K., Soesanti, I. & Permanasari, A.E.(2018). "Performance Comparison of Genetic Algorithm Operator Combinations for optimization Problems," 2018 International Seminar on Research of Information Technology and Intelligent Systems (ISRITI), Yogyakarta, Indonesia, pp. 43-48, doi: 10.1109/ISRITI.2018.8864469.