Аналіз методів відбору в генетичних алгоритмах

Simple item page
dc.contributor.authorГулаєва, Наталія
dc.contributor.authorУстілов, Артем
dc.date.accessioned2021-12-14T15:49:56Z
dc.date.available2021-12-14T15:49:56Z
dc.date.issued2021-12-10
dc.description.abstractРозглянуто методи відбору, що використовуються в генетичних алгоритмах із генераційним типом репродукції. Наведено основні теоретичні відомості про такі властивості методів відбору: шум, тиск, швидкість росту, швидкість репродукції, обчислювальна складність. Проведено порівняльний аналіз методів відбору за зазначеними властивостями. Охарактеризовано та проілюстровано зміни в розподілі коефіцієнта пристосованості особин популяції після застосування різних методів відбору.uk_UA
dc.description.abstractThis 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.
dc.identifier.citationГулаєва Н.М. Аналіз методів відбору в генетичних алгоритмах / Гулаєва Н. М., Устілов А. О. // Наукові записки НаУКМА. Комп'ютерні науки. - 2021. - Т. 4. - С. 29-43. - https://doi.org/10.18523/2617-3808.2021.4.29-43uk_UA
dc.identifier.issn2617-3808
dc.identifier.issn2617-7323
dc.identifier.urihttps://doi.org/10.18523/2617-3808.2021.4.29-43
dc.identifier.urihttps://ekmair.ukma.edu.ua/handle/123456789/21885
dc.language.isoukuk_UA
dc.relation.sourceНаукові записки НаУКМА. Комп'ютерні науки.uk_UA
dc.statusfirst publisheduk_UA
dc.subjectгенетичні алгоритмиuk_UA
dc.subjectметоди відборуuk_UA
dc.subjectпропорційний відбірuk_UA
dc.subjectвідбір за методом рулеткиuk_UA
dc.subjectмасштабування функції пристосованостіuk_UA
dc.subjectвідбір за рангомuk_UA
dc.subjectтурнірний відбірuk_UA
dc.subjectвідбір відтинаннямuk_UA
dc.subjectшум відборуuk_UA
dc.subjectтиск відборуuk_UA
dc.subjectчас поглинанняuk_UA
dc.subjectінтенсивність відборуuk_UA
dc.subjectшвидкість ростуuk_UA
dc.subjectвтрата різноманітностіuk_UA
dc.subjectшвидкість репродукціїuk_UA
dc.subjectобчислювальна складністьuk_UA
dc.subjectстаттяuk_UA
dc.subjectgenetic algorithmsuk_UA
dc.subjectselection methodsuk_UA
dc.subjectfitness proportionate selectionuk_UA
dc.subjectroulette-wheel selectionuk_UA
dc.subjectfitness function scalinguk_UA
dc.subjectranking selectionuk_UA
dc.subjecttournament selectionuk_UA
dc.subjecttruncation selectionuk_UA
dc.subjectselection noiseuk_UA
dc.subjectselection pressureuk_UA
dc.subjecttakeover timeuk_UA
dc.subjectselection intensityuk_UA
dc.subjectgrowth rateuk_UA
dc.subjectloss of diversityuk_UA
dc.subjectreproduction rateuk_UA
dc.subjectcomputational complexityuk_UA
dc.subjectarticleuk_UA
dc.titleАналіз методів відбору в генетичних алгоритмахuk_UA
dc.title.alternativeAnalysis of Selection Methods Used in Genetic Algorithmsuk_UA
dc.typeArticleuk_UA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Analiz_metodiv_vidboru_v_henetychnykh_alhorytmakh.pdf
Size:
786.37 KB
Format:
Adobe Portable Document Format
Description:
стаття
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
7.54 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Том 4