Дослідження часової ефективності генетичних алгоритмів

UKR: Пояснювальна записка до кваліфікаційної роботи магістра виконана на 97 сторінках, містить 39 рисунків, 4 додатки, 39 джерел Магістерська робота присвячена дослідженню часової ефективності генетичних алгоритмів та аналізу впливу їх основних параметрів на тривалість виконання алгоритму. Генетичні алгоритми належать до стохастичних методів оптимізації та широко застосовуються для розв’язання складних задач у різних галузях інформаційних технологій, проте їх часові характеристики значною мірою залежать від конфігурації параметрів та властивостей оптимізаційної задачі. У роботі проаналізовано теоретичні засади генетичних алгоритмів, їх структуру, оператори селекції, кросинговеру та мутації, а також критерії зупинки. Окрему увагу приділено питанням оцінювання часової ефективності стохастичних алгоритмів і чинникам, що впливають на обчислювальні витрати. Розроблено програмний інструмент мовою Python для експериментального дослідження часової ефективності генетичних алгоритмів. Програма реалізує класичний генетичний алгоритм із можливістю налаштування основних параметрів, автоматично вимірює час виконання та кількість поколінь до зупинки, зберігає результати у CSV-файл і будує графіки для подальшого аналізу. Для експериментів використано стандартні тестові функції оптимізації Sphere, Rastrigin та Rosenbrock. У межах роботи проведено серію експериментів для шести конфігурацій алгоритму, що дозволило проаналізувати вплив кількості поколінь, розміру популяції, розмірності задачі, ймовірності кросинговеру та параметрів мутації на час виконання генетичного алгоритму. Отримані результати підтверджують, що найбільший вплив на часову ефективність мають розмір популяції, кількість поколінь та параметри мутації, причому ступінь їх впливу залежить від складності оптимізаційної задачі. Результати дослідження можуть бути використані для обґрунтованого налаштування параметрів генетичних алгоритмів з метою підвищення їх швидкодії та ефективності.

ENG: The master’s thesis is devoted to the study of the time efficiency of genetic algorithms and the analysis of the influence of their main parameters on the algorithm execution time. Genetic algorithms are stochastic optimization methods widely used to solve complex problems in various fields of information technology; however, their time performance strongly depends on parameter settings and problem characteristics. The thesis analyzes the theoretical foundations of genetic algorithms, their structure, selection, crossover and mutation operators, as well as stopping criteria. Special attention is paid to the evaluation of time efficiency of stochastic algorithms and the factors that affect computational costs. A software tool implemented in Python was developed for experimental research of genetic algorithm time efficiency. The program implements a classical genetic algorithm with configurable parameters, automatically measures execution time and the number of generations until termination, stores experimental results in CSV format, and builds graphical visualizations for further analysis. Standard benchmark optimization functions Sphere, Rastrigin, and Rosenbrock were used in the experiments. A series of experiments was conducted for six different algorithm configurations, which made it possible to analyze the impact of the number of generations, population size, problem dimensionality, crossover probability, and mutation parameters on the execution time of the genetic algorithm. The results show that population size, number of generations, and mutation parameters have the most significant influence on time efficiency, while the degree of influence depends on the complexity of the optimization problem.