Аналіз методів відбору в генетичних алгоритмах
Loading...
Date
2021-12-10
Authors
Гулаєва, Наталія
Устілов, Артем
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Розглянуто методи відбору, що використовуються в генетичних алгоритмах із генераційним типом репродукції. Наведено основні теоретичні відомості про такі властивості методів відбору: шум, тиск, швидкість росту, швидкість репродукції, обчислювальна складність. Проведено порівняльний аналіз методів відбору за зазначеними властивостями. Охарактеризовано та проілюстровано зміни в розподілі коефіцієнта пристосованості особин популяції після застосування різних методів відбору.
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.
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.
Description
Keywords
генетичні алгоритми, методи відбору, пропорційний відбір, відбір за методом рулетки, масштабування функції пристосованості, відбір за рангом, турнірний відбір, відбір відтинанням, шум відбору, тиск відбору, час поглинання, інтенсивність відбору, швидкість росту, втрата різноманітності, швидкість репродукції, обчислювальна складність, стаття, genetic algorithms, selection methods, fitness proportionate selection, roulette-wheel selection, fitness function scaling, ranking selection, tournament selection, truncation selection, selection noise, selection pressure, takeover time, selection intensity, growth rate, loss of diversity, reproduction rate, computational complexity, article
Citation
Гулаєва Н.М. Аналіз методів відбору в генетичних алгоритмах / Гулаєва Н. М., Устілов А. О. // Наукові записки НаУКМА. Комп'ютерні науки. - 2021. - Т. 4. - С. 29-43. - https://doi.org/10.18523/2617-3808.2021.4.29-43