Гулаєва, НаталіяУстілов, Артем2021-12-142021-12-142021-12-10Гулаєва Н.М. Аналіз методів відбору в генетичних алгоритмах / Гулаєва Н. М., Устілов А. О. // Наукові записки НаУКМА. Комп'ютерні науки. - 2021. - Т. 4. - С. 29-43. - https://doi.org/10.18523/2617-3808.2021.4.29-432617-38082617-7323https://doi.org/10.18523/2617-3808.2021.4.29-43https://ekmair.ukma.edu.ua/handle/123456789/21885Розглянуто методи відбору, що використовуються в генетичних алгоритмах із генераційним типом репродукції. Наведено основні теоретичні відомості про такі властивості методів відбору: шум, тиск, швидкість росту, швидкість репродукції, обчислювальна складність. Проведено порівняльний аналіз методів відбору за зазначеними властивостями. Охарактеризовано та проілюстровано зміни в розподілі коефіцієнта пристосованості особин популяції після застосування різних методів відбору.This paper offers a comprehensive review of selection methods used in the generational genetic algorithms. Firstly, a brief description of the following selection methods is presented: fitness proportionate selection methods including roulette-wheel selection (RWS) and its modifications, stochastic remainder selection with replacement (SRSWR), remainder stochastic independent selection (RSIS), and stochastic universal selection (SUS); ranking selection methods including linear and nonlinear rankings; tournament selection methods including deterministic and stochastic tournaments as well as tournaments with and without replacement; elitist and truncation selection methods; fitness uniform selection scheme (FUSS). Second, basic theoretical statements on selection method properties are given. Particularly, the selection noise, selection pressure, growth rate, reproduction rate, and computational complexity are considered. To illustrate selection method properties, numerous runs of genetic algorithms using the only selection method and no other genetic operator are conducted, and numerical characteristics of analyzed properties are computed. Specifically, to estimate the selection pressure, the takeover time and selection intensity are computed; to estimate the growth rate, the ratio of best individual copies in two consecutive populations is computed; to estimate the selection noise, the algorithm convergence speed is analyzed based on experiments carried out on a specific fitness function assigning the same fitness value to all individuals. Third, the effect of selection methods on the population fitness distribution is investigated. To do this, there are conducted genetic algorithm runs starting with a binomially distributed initial population. It is shown that most selection methods keep the distribution close to the original one providing an increased mean value of the distribution, while others (such as disruptive RWS, exponential ranking, truncation, and FUSS) change the distribution significantly. The obtained results are illustrated with the help of tables and histograms.ukгенетичні алгоритмиметоди відборупропорційний відбірвідбір за методом рулеткимасштабування функції пристосованостівідбір за рангомтурнірний відбірвідбір відтинаннямшум відборутиск відборучас поглинанняінтенсивність відборушвидкість ростувтрата різноманітностішвидкість репродукціїобчислювальна складністьстаттяgenetic algorithmsselection methodsfitness proportionate selectionroulette-wheel selectionfitness function scalingranking selectiontournament selectiontruncation selectionselection noiseselection pressuretakeover timeselection intensitygrowth rateloss of diversityreproduction ratecomputational complexityarticleArticle