Генетичний алгоритм як засіб розв’язання оптимізаційних задач

Simple item page
dc.citation.epage107
dc.citation.issue2
dc.citation.journalTitleІнфокомунікаційні технології та електронна інженерія
dc.citation.spage95
dc.citation.volume3
dc.contributor.affiliationНаціональний університет “Львівська політехніка”
dc.contributor.affiliationLviv Polytechnic National University
dc.contributor.authorПиріг, Я.
dc.contributor.authorКлимаш, М.
dc.contributor.authorПиріг, Ю.
dc.contributor.authorЛаврів, О.
dc.contributor.authorPyrih, Ya.
dc.contributor.authorKlymash, M.
dc.contributor.authorPyrih, Yu.
dc.contributor.authorLavriv, O.
dc.coverage.placenameЛьвів
dc.coverage.placenameLviv
dc.date.accessioned2025-07-22T11:15:20Z
dc.date.created2023-02-28
dc.date.issued2023-02-28
dc.description.abstractРозглянуто особливості використання генетичного алгоритму (ГА) для розв’язання оптимізаційних задач. Наведено класифікацію оптимізаційних задач. Детально описано структурні елементи ГА та їх роль для розв’язання задачі комівояжера. Для оцінювання впливу параметрів ГА на ефективність його застосування здійснено дослідження впливу розміру популяції на довжину маршруту комівояжера. На основі отриманих результатів показано, що розмір популяції впливає на довжину маршруту, а оптимальне значення розміру популяції для цієї задачі становить 150. Використання турнірного оператора відбору, оператора впорядкованого схрещування, інверсійного оператора мутації дало змогу сформувати маршрут комівояжера завдовжки 9271,735 км, який, на основі викладених у роботі результатів, є оптимальним для відвідування 29 міст.
dc.description.abstractThe 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.
dc.format.extent95-107
dc.format.pages13
dc.identifier.citationГенетичний алгоритм як засіб розв’язання оптимізаційних задач / Я. Пиріг, М. Климаш, Ю. Пиріг, О. Лаврів // Інфокомунікаційні технології та електронна інженерія. — Львів : Видавництво Львівської політехніки, 2023. — Том 3. — № 2. — С. 95–107.
dc.identifier.citationenGenetic algorithm as a tool for solving optimisation problems / Ya. Pyrih, M. Klymash, Yu. Pyrih, O. Lavriv // Infocommunication Technologies and Electronic Engineering. — Lviv : Lviv Politechnic Publishing House, 2023. — Vol 3. — No 2. — P. 95–107.
dc.identifier.doidoi.org/10.23939/ictee2023.02.095
dc.identifier.urihttps://ena.lpnu.ua/handle/ntb/111443
dc.language.isouk
dc.publisherВидавництво Львівської політехніки
dc.publisherLviv Politechnic Publishing House
dc.relation.ispartofІнфокомунікаційні технології та електронна інженерія, 2 (3), 2023
dc.relation.ispartofInfocommunication Technologies and Electronic Engineering, 2 (3), 2023
dc.relation.references[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
dc.relation.references[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
dc.relation.references[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
dc.relation.references[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
dc.relation.references[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
dc.relation.references[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
dc.relation.references[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
dc.relation.references[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.
dc.relation.references[9] Grant, R. (2022), TSPLIB 95 Documentation, Release 0.7.1, 52 p.
dc.relation.references[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.
dc.relation.referencesen[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
dc.relation.referencesen[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
dc.relation.referencesen[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
dc.relation.referencesen[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
dc.relation.referencesen[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
dc.relation.referencesen[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
dc.relation.referencesen[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
dc.relation.referencesen[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.
dc.relation.referencesen[9] Grant, R. (2022), TSPLIB 95 Documentation, Release 0.7.1, 52 p.
dc.relation.referencesen[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.
dc.relation.urihttps://doi.org/10.1007/978-3-031-24963-1_16
dc.relation.urihttps://doi.org/10.48550/arXiv.2202.13735
dc.rights.holder© Національний університет “Львівська політехніка”, 2023
dc.subjectгенетичний алгоритм
dc.subjectзадача комівояжера
dc.subjectмаршрут
dc.subjectпопуляція
dc.subjectgenetic algorithm
dc.subjecttraveling salesman problem
dc.subjectroute
dc.subjectpopulation
dc.subject.udc519.876
dc.titleГенетичний алгоритм як засіб розв’язання оптимізаційних задач
dc.title.alternativeGenetic algorithm as a tool for solving optimisation problems
dc.typeArticle

Files

Original bundle

Now showing 1 - 2 of 2
Thumbnail Image
Name:
2023v3n2_Pyrih_Ya-Genetic_algorithm_as_a_tool_95-107.pdf
Size:
1.35 MB
Format:
Adobe Portable Document Format
Download
Thumbnail Image
Name:
2023v3n2_Pyrih_Ya-Genetic_algorithm_as_a_tool_95-107__COVER.png
Size:
1.01 MB
Format:
Portable Network Graphics
Download

License bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.84 KB
Format:
Plain Text
Description:
Download

Collections

Infocommunication Technologies and Electronic Engineering. – 2023. – Vol. 3, No. 2