Оцінка обчислювальної складності генетичного алгоритму

Abstract

Статтю присвячено оцінці обчислювальної складності генетичного алгоритму як одного із ключових засобів для розв’язання оптимізаційних задач. Розглянуто теоретичні аспекти обчислювальної складності алгоритмів та взаємозв'язок елементів генетичного алгоритму. Описано основні види обчислювальної складності алгоритмів: часову, просторову та асимптотичну. Наведено п’ять основних правил для розрахунку асимптотичної складності. Представлено математичний апарат для оцінки асимптотичної складності генетичного алгоритму, який враховує витрати на формування початкової популяції та на виконання еволюції. Еволюція відбувається через ітерації, під час яких покоління індивідів піддаються певним операціям з метою знаходження оптимального рішення (схрещування, мутації, декодування хромосоми тощо). ГА, в якості алгоритму глобального пошуку, розглядається для знаходження оптимального шляху без застрягання в локальних мінімумах. Для оцінки обчислювальної складності ГА розглянуто розв’язання задачі комівояжера (TSP) для 28 міст України з використанням модифікованої бібліотеки TSPLIB та платформи DEAP, створеної на мові програмування Python. Представлено блок-схему ГА, основними елементами якого є турнірний оператор відбору, оператор впорядкованого схрещування та інверсійний оператор мутації. Здійснено дослідження впливу розміру популяції та кількості поколінь на асимптотичну складність генетичного алгоритму при розв’язанні задачі TSP. Під час проведення дослідження розглядалась зміна розміру популяції ГА від 50 до 500 з кроком 50, при цьому для кожного такого значення моделювалось чотири набори кількості поколінь: від 50 до 200 із кроком 50. На основі отриманих результатів представлено лінійну залежність часу виконання ГА від розміру розглянутих вхідних даних. Показано, що найменша часова складність представленого ГА для наведеної задачі TSP становить 0.33848 секунди при розмірі популяції 50 та аналогічній кількості поколінь, тоді як найбільше значення – 3.752734 секунди при розмірі популяції 500 та кількості поколінь 200. Отримані результати можуть бути використані для оптимізації роботи ГА, зокрема в задачі TSP.

The article is devoted to the estimation of computational complexity of a genetic algorithm as one of the key tools for solving optimisation problems. The theoretical aspects of computational complexity of algorithms and the interrelation of elements of a genetic algorithm are considered. The main types of computational complexity of algorithms are described: time, simple and asymptotic. Five basic rules for calculating the asymptotic complexity are given. A mathematical apparatus for estimating the asymptotic complexity of a genetic algorithm is presented, which takes into account the costs of forming the initial population and performing evolution. Evolution occurs through iterations, during which generations of individuals are subjected to certain operations in order to find an optimal solution (crossing, mutation, chromosome decoding, etc.). GA, as a global search algorithm, is considered to find the optimal path without getting stuck in local minima. To assess the computational complexity of GA, we consider solving the traveling salesman problem (TSP) for 28 cities of Ukraine using a modified TSPLIB library and the DEAP platform created in the Python programming language. A block diagram of the GA is presented, the main elements of which are the tournament selection operator, the ordered crossover operator, and the inversion mutation operator. The influence of the population size and the number of generations on the asymptotic complexity of the genetic algorithm in solving the TSP problem is studied. The study considered changing the size of the GA population from 50 to 500 with a step of 50, while for each such value four sets of the number of generations were modelled: from 50 to 200 with a step of 50. Based on the obtained results, we show a linear dependence of the GA execution time on the size of the considered input data. It is shown that the smallest time complexity of the presented GA for the given TSP problem is 0.33848 seconds with a population size of 50 and a similar number of generations, while the largest value is 3.752734 seconds with a population size of 500 and a number of generations of 200. The obtained results can be used to optimise the performance of a GA in the TSP problem.