Genetic algorithm for structural adaptation of sorting algorithms
Constructivism was applied to form the sorting algorithm code. The meta-algorithm of program code generation is presented. Parts of existing sorting algorithms and auxiliary utilities are used for generation. A genetic algorithm was used to select the algorithm with the maximum time efficiency under...
Збережено в:
| Дата: | 2024 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
PROBLEMS IN PROGRAMMING
2024
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/614 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Репозитарії
Problems in programming| id |
pp_isofts_kiev_ua-article-614 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/16/1e33d634a8bfab73e6a1bbb97cb48a16.pdf |
| spelling |
pp_isofts_kiev_ua-article-6142025-02-14T10:14:51Z Genetic algorithm for structural adaptation of sorting algorithms Генетичний алгоритм для структурної адаптації алгоритмів сортування Shinkarenko, V.I. Makarov, O.V. Key wosorting algorithm; sorting; constructivism; genetic algorithm; chromosome; binary tree UDC 004.4 алгоритм сортування, сортування; конструктивізм; генетичний алгоритм; хромосома; бінарне дерево УДК 004.4 Constructivism was applied to form the sorting algorithm code. The meta-algorithm of program code generation is presented. Parts of existing sorting algorithms and auxiliary utilities are used for generation. A genetic algorithm was used to select the algorithm with the maximum time efficiency under the given conditions of use. The use of a standard genetic algorithm faces a problem associated with a different number of elementary sorting operations, which leads to the use of chromosomes of diff erent lengths. To solve the problem, a representation of the chromosome in the form of a binary tree is proposed. Each node has start genes, end genes, and two child nodes. To form an algorithm that is guaranteed to sort the array, all end nodes (leaves) include the final sorting gene at the end of the start genes sequence. This gene is decoded by calling the existing sorting algorithm, which is guaranteed to perform sorting. Crossover and mutation operations are performed on chromosomes in the form of a binary tree. Crossover is performed using the exchange of tree branches. Mechanisms of coding and decoding of the sorting algorithm from chromosome have been implemented. Decoding and formation of a suitable sorting algorithm is performed using linearization: formation of a textual representation using a depth-first tree traversal algorithm. The fitness function is defined as the average time of sorting randomly generated arrays for sorting (identical arrays for all chromosomes) in some stable environment, considering certain features of these arrays. It is possible to use other fitness functions related to the number of calculations, comparisons, or permutations. The developed software should be used for adaptation of sorting algorithms to stable input data streams and environments. Prombles in programming 2024; 2-3: 11-18 Застосовано конструктивізм для формування коду алгоритму сортування. Представлено метаалгоритм генерації програмного коду. Для генерації використовуються частини існуючих алгоритмів сортування і допоміжні утиліти. Використано генетичний алгоритм для вибору алгоритму з максимальною часовою ефективністю у заданих умовах використання. Використання стандартного генетичного алгоритму стикається з проблемою, пов’язаною з різною кількістю елементарних дій по сортуванню, що призводить до використання хромосом різної довжини. Для рішення проблеми запропоновано представлення хромосоми у формі бінарного дерева. Кожен вузол має гени початку, кінця і двох вузлів-нащадків. Для формування алгоритму, який гарантовано буде сортувати масив, усі кінцеві вузли (листя) включають ген фінального сортування у кінець початкової послідовності генів. Даний ген декодується викликом існуючого алгоритму сортування, який гарантовано виконає сортування. Операції кросоверу та мутацій виконуються на хромосомах у формі бінарного дерева. Схрещення виконується за допомогою обміну вузлами дерева. Реалізовані механізми кодування і декодування алгоритму сортування із хромосоми. Для декодування і формування відповідного алгоритму сортування виконується лінеріалізація: формування текстового представлення за алгоритмом обходу дерева у глибину. Фітнес функція визначається як середній час сортування випадково сформованих масивів для сортування (для всіх хромосом однакові масиви) у деякому стабільному середовищі з урахуванням певних особливостей цих масивів. Передбачено застосування інших фітнес функцій пов’язаних з кількістю обчислень, порівнянь або перестановок. Розроблене програмне забезпечення має застосовуватись у процесі адаптації алгоритмів сортування до стабільних потоків вхідних даних та середовищ використання.Prombles in programming 2024; 2-3: 11-18 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2024-12-17 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/614 10.15407/pp2024.02-03.011 PROBLEMS IN PROGRAMMING; No 2-3 (2024); 11-18 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2024); 11-18 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2024); 11-18 1727-4907 10.15407/pp2024.02-03 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/614/666 Copyright (c) 2024 PROBLEMS IN PROGRAMMING |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2025-02-14T10:14:51Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
Key wosorting algorithm sorting constructivism genetic algorithm chromosome binary tree UDC 004.4 |
| spellingShingle |
Key wosorting algorithm sorting constructivism genetic algorithm chromosome binary tree UDC 004.4 Shinkarenko, V.I. Makarov, O.V. Genetic algorithm for structural adaptation of sorting algorithms |
| topic_facet |
Key wosorting algorithm sorting constructivism genetic algorithm chromosome binary tree UDC 004.4 алгоритм сортування сортування; конструктивізм; генетичний алгоритм; хромосома; бінарне дерево УДК 004.4 |
| format |
Article |
| author |
Shinkarenko, V.I. Makarov, O.V. |
| author_facet |
Shinkarenko, V.I. Makarov, O.V. |
| author_sort |
Shinkarenko, V.I. |
| title |
Genetic algorithm for structural adaptation of sorting algorithms |
| title_short |
Genetic algorithm for structural adaptation of sorting algorithms |
| title_full |
Genetic algorithm for structural adaptation of sorting algorithms |
| title_fullStr |
Genetic algorithm for structural adaptation of sorting algorithms |
| title_full_unstemmed |
Genetic algorithm for structural adaptation of sorting algorithms |
| title_sort |
genetic algorithm for structural adaptation of sorting algorithms |
| title_alt |
Генетичний алгоритм для структурної адаптації алгоритмів сортування |
| description |
Constructivism was applied to form the sorting algorithm code. The meta-algorithm of program code generation is presented. Parts of existing sorting algorithms and auxiliary utilities are used for generation. A genetic algorithm was used to select the algorithm with the maximum time efficiency under the given conditions of use. The use of a standard genetic algorithm faces a problem associated with a different number of elementary sorting operations, which leads to the use of chromosomes of diff erent lengths. To solve the problem, a representation of the chromosome in the form of a binary tree is proposed. Each node has start genes, end genes, and two child nodes. To form an algorithm that is guaranteed to sort the array, all end nodes (leaves) include the final sorting gene at the end of the start genes sequence. This gene is decoded by calling the existing sorting algorithm, which is guaranteed to perform sorting. Crossover and mutation operations are performed on chromosomes in the form of a binary tree. Crossover is performed using the exchange of tree branches. Mechanisms of coding and decoding of the sorting algorithm from chromosome have been implemented. Decoding and formation of a suitable sorting algorithm is performed using linearization: formation of a textual representation using a depth-first tree traversal algorithm. The fitness function is defined as the average time of sorting randomly generated arrays for sorting (identical arrays for all chromosomes) in some stable environment, considering certain features of these arrays. It is possible to use other fitness functions related to the number of calculations, comparisons, or permutations. The developed software should be used for adaptation of sorting algorithms to stable input data streams and environments. Prombles in programming 2024; 2-3: 11-18 |
| publisher |
PROBLEMS IN PROGRAMMING |
| publishDate |
2024 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/614 |
| work_keys_str_mv |
AT shinkarenkovi geneticalgorithmforstructuraladaptationofsortingalgorithms AT makarovov geneticalgorithmforstructuraladaptationofsortingalgorithms AT shinkarenkovi genetičnijalgoritmdlâstrukturnoíadaptacííalgoritmívsortuvannâ AT makarovov genetičnijalgoritmdlâstrukturnoíadaptacííalgoritmívsortuvannâ |
| first_indexed |
2025-07-17T10:07:48Z |
| last_indexed |
2025-07-17T10:07:48Z |
| _version_ |
1850411868719415296 |
| fulltext |
Теоретичні і методологічні основи програмування
11
УДК 004.4 http://doi.org/10.15407/pp2024.02-03.011
В.І. Шинкаренко, О.В. Макаров
ГЕНЕТИЧНИЙ АЛГОРИТМ ДЛЯ СТРУКТУРНОЇ АДАПТАЦІЇ
АЛГОРИТМІВ СОРТУВАННЯ
Застосовано конструктивізм для формування коду алгоритму сортування. Представлено метаалго-
ритм генерації програмного коду. Для генерації використовуються частини існуючих алгоритмів со-
ртування і допоміжні утиліти. Використано генетичний алгоритм для вибору алгоритму з максима-
льною часовою ефективністю у заданих умовах використання. Використання стандартного генетич-
ного алгоритму стикається з проблемою, пов’язаною з різною кількістю елементарних дій по сорту-
ванню, що призводить до використання хромосом різної довжини. Для рішення проблеми запропо-
новано представлення хромосоми у формі бінарного дерева. Кожен вузол має гени початку, кінця і
двох вузлів-нащадків. Для формування алгоритму, який гарантовано буде сортувати масив, усі кін-
цеві вузли (листя) включають ген фінального сортування у кінець початкової послідовності генів.
Даний ген декодується викликом існуючого алгоритму сортування , який гарантовано виконає сор-
тування. Операції кросоверу та мутацій виконуються на хромосомах у формі бінарного дерева. Схре-
щення виконується за допомогою обміну вузлами дерева. Реалізовані механізми кодування і деко-
дування алгоритму сортування із хромосоми. Для декодування і формування відповідного алгоритму
сортування виконується лінеріалізація: формування текстового представлення за алгоритмом об-
ходу дерева у глибину. Фітнес функція визначається як середній час сортування випадково сформо-
ваних масивів для сортування (для всіх хромосом однакові масиви) у деякому стабільному середо-
вищі з урахуванням певних особливостей цих масивів. Передбачено застосування інших фітнес фу-
нкцій пов’язаних з кількістю обчислень, порівнянь або перестановок. Розроблене програмне забез-
печення має застосовуватись у процесі адаптації алгоритмів сортування до стабільних потоків вхід-
них даних та середовищ використання.
Ключові слова: алгоритм сортування, сортування, конструктивізм, генетичний алгоритм, хромосома,
бінарне дерево.
V.I. Shinkarenko, O.V. Makarov
GENETIC ALGORITHM FOR STRUCTURAL ADAPTATION
OF SORTING ALGORITHMS
Constructivism was applied to form the sorting algorithm code. The meta-algorithm of program code
generation is presented. Parts of existing sorting algorithms and auxiliary utilities are used for generation.
A genetic algorithm was used to select the algorithm with the maximum time efficiency under the given
conditions of use. The use of a standard genetic algorithm faces a problem associated with a different
number of elementary sorting operations, which leads to the use of chromosomes of diff erent lengths. To
solve the problem, a representation of the chromosome in the form of a binary tree is proposed. Each
node has start genes, end genes, and two child nodes. To form an algorithm that is guaranteed to sort the
array, all end nodes (leaves) include the final sorting gene at the end of the start genes sequence. This
gene is decoded by calling the existing sorting algorithm, which is guaranteed to perform sorting. Cross-
over and mutation operations are performed on chromosomes in the form of a binary tree. Crossover is
performed using the exchange of tree branches. Mechanisms of coding and decoding of the sorting algo-
rithm from chromosome have been implemented. Decoding and formation of a suitable sorting algorithm
is performed using linearization: formation of a textual representation using a depth-first tree traversal
algorithm. The fitness function is defined as the average time of sorting randomly generated arrays for
sorting (identical arrays for all chromosomes) in some stable environment, considering certain features
of these arrays. It is possible to use other fitness functions related to the number of calculations, com-
parisons, or permutations. The developed software should be used for adaptation of sorting algorithms
to stable input data streams and environments.
Key words: sorting algorithm, sorting, constructivism, genetic algorithm, chromosome, binary tree.
© В.І. Шинкаренко, О.В. Макаров, 2024
ISSN 1727-4907. Проблеми програмування. 2024. №2-3
Теоретичні і методологічні основи програмування
12
Вступ
Із появою Інтернету і цифрової тех-
нології взагалі, стрімко зростають обсяги
даних, що генеруються та зберігаються. З
цифровізацією більшості сфер життя – від
бізнесу та науки до особистих комунікацій
– виникає потреба в ефективному управ-
лінні цими даними. Зростання обсягів да-
них ставить перед нами виклики, пов'язані
зі збереженням, обробкою, аналізом та ін-
терпретацією.
У такому контексті актуальність
ефективних алгоритмів сортування стає
критичною. Для ефективної роботи з вели-
кими обсягами даних необхідно швидко та
ефективно впоратися з їх обробкою. Навіть
найпростіші операції, такі як сортування,
можуть стати часо- та ресурсо- затратними,
якщо використовуються неефективні ме-
тоди.
Ефективні алгоритми сортування
дозволяють швидко опрацьовувати великі
обсяги даних, що є критичним для бага-
тьох застосувань. У деяких мережевих
пристроях сортування даних може викори-
стовуватися для оптимізації обробки паке-
тів даних та керування мережевим трафі-
ком. Системи керування базами даних
(СКБД) використовують алгоритми сорту-
вання для виконання запитів, об'єднання
даних та інших операцій [1]. У розподіле-
них системах зберігання даних, таких як
Hadoop або Apache Spark [2], алгоритми
сортування використовуються для обро-
бки великих обсягів інформації та забезпе-
чення швидкодії.
Еволюція алгоритмів сортування є
захоплюючим шляхом в історії обчислю-
вальної науки, який почався з простих,
але ефективних методів. Наприклад, сор-
тування бульбашкою (Bubble sort) або
вставками (Insertion sort) із обчислюваль-
ною складністю 𝑂𝑂(𝑛𝑛2) [3]. У подальшому
з’явились більш складні та оптимізовані
алгоритми, більш придатні для сорту-
вання великих обсягів даних. Такі як
швидке сортування (Quick sort) чи сорту-
вання злиттям (Merge sort), із обчислюва-
льною складністю у середньому 𝑂𝑂(𝑛𝑛 ∗
𝑙𝑙𝑙𝑙𝑙𝑙(𝑛𝑛)). У подальшому зростання вимог
до стабільності і швидкості сортування
привели до появи комбінованих алгорит-
мів. Найвідомішими представниками
яких є Timsort [4] – симбіоз сортувань
вставками та злиттям. Інтроспективне со-
ртування (Introsort) [5] починає із швид-
кого сортування, потім за певних умов пе-
реходить на пірамідальне сортування
(Heapsort) і викликає сортування встав-
ками для невеликих послідовностей.
Комбіновані алгоритми поєднують у
собі переваги складових для підвищення
ефективності. У [6] розглядається новітній
підхід до формування, перетворення та ана-
лізу конструкцій за допомогою операцій
зв’язування, підстановки, виводу тощо.
Для формування структур (складо-
вих та їх взаємного розташування) алгорит-
мів сортування застосований підхід конс-
труктивно-продукційного моделювання.
Це забезпечує вирішення наступних задач:
створення нових алгоритмів сор-
тування із частин існуючих;
адаптація алгоритмів сортування
до сортованих даних;
адаптація структур даних в опе-
ративній пам’яті.
В даній роботі не розглядається тео-
ретична модель, а лише за цією моделлю її
практичне застосування.
Мета
Метою даної роботи є розробка ге-
нетичного алгоритму [7] для структурної
адаптації алгоритмів сортування. Структу-
рна адаптація алгоритмів сортування поля-
гає у формуванні адаптованого алгоритму з
частин відомих алгоритмів таким чином,
щоб він був не гіршим за часовими показ-
никами від інших алгоритмів сортування в
деякому стабільному середовищі викорис-
тання.
Особливістю генетичного алгори-
тму для даної задачі є формування хромо-
сом невизначеної довжини і складу з мож-
ливістю як кодування, так і декодування у
алгоритм сортування.
Теоретичні і методологічні основи програмування
13
Конструювання алгоритмів
сортування
Для конструювання алгоритмів сор-
тування будемо використовувати частини
існуючих загальновідомих алгоритмів сор-
тування. Використовувались у поточній ве-
рсії програми такі базові (атомарні) опера-
ції з даних алгоритмів:
швидке сортування (Quick sort).
Розділення масиву даних на дві частини ві-
дносно обраного елемента, який назива-
ється опорним (pivot). Усі елементи, менші
за опорний, переставляються ліворуч від
нього, а всі більші елементи – праворуч;
сортування вставками (Insertion
sort). Вставка одного елемента із невідсор-
тованої частини масиву у відсортований пі-
дмасив;
сортування вибором (Selection
sort). Пошук мінімального або максималь-
ного елемента у невідсортованому підма-
сиві і перестановка;
шейкерне сортування (Cocktail
shaker sort). Прохід масивом у прямому або
зворотному напрямку і перестановка усіх
пар елементів, що стоять у зворотному по-
рядку;
сортування злиттям (Merge sort).
Злиття двох відсортованих масивів у один.
Також можливою операцією є умо-
вне розбиття масиву на дві частини і сорту-
вання кожної окремо. Після того, як кожна
частина буде відсортована необхідно вико-
нати злиття у єдиний відсортований масив.
Модель передбачає додавання ін-
ших базових операцій. Це можуть бути ча-
стини існуючих алгоритмів сортування. На-
приклад, вставка елемента із певним кро-
ком, використана у сортуванні Шелла. Та-
кож доцільне використання детермінова-
них і стохастичних передобробок [6, 8], або
Рис. 1. Блок-схема метаалгоритму генерації програмного коду
Теоретичні і методологічні основи програмування
14
їхніх складових операцій. Це може підви-
щити ефективність кінцевого алгоритму.
Правила формування алгоритму.
Для формування алгоритму (рис. 1) скла-
дові базові операції вибираються випад-
ково. Таким чином можливі будь-які комбі-
нації атомарних алгоритмів і, як результат,
безліч унікальних конструйованих алгори-
тмів сортування.
Деякі базові алгоритми мають спеці-
альні вимоги до їхнього використання. У
разі, якщо вимоги не виконуються, генера-
ція буде неможливою або конструйований
алгоритм не виконуватиме повне сорту-
вання масиву. Наприклад, під час викорис-
тання розбиття масиву на дві частині і сор-
тування кожної частини окремо, має викли-
катись операція злиття в один відсортова-
ний масив.
Розглянемо проблеми з комбінацією
алгоритмів сортування. Атомарні частини
алгоритмів сортування вибором і бульбаш-
кою розділяють масив на невідсортовану
(або ще не проаналізовану) частину та від-
сортовану. Якщо виконуються проходи у
прямому та зворотному напрямку, то масив
ділиться на дві відсортовані частини на по-
чатку і в кінці масиву та невідсортовану.
Через особливості логіки алгоритмів відсо-
ртовані частини мають у собі елементи
строго менші (на початку) або більші (у кі-
нці масиву), ніж ті, що лишаються у невід-
сортованій серединній частині. Якщо вико-
ристовувати проходи тільки в один бік, то
отримаємо класичне сортування вибором
або бульбашкою. У цьому випадку масив
буде повністю відсортований. Якщо вико-
ристовувати проходи у різних напрямках,
то відсортовані частини на початку і в кінці
будуть збільшуватись доки не зустрінуться
і утворять єдиний відсортований масив.
Для класичного сортування встав-
ками – коли усі вставки виконуються тільки
у ліву (або тільки у праву) частину – також
результатом роботи буде повністю відсор-
тований масив. Але, якщо виконувати вста-
вки у початок і кінець масиву, то будемо
отримувати відповідно два відсортованих
масиви. Але немає жодних гарантій, що
елементи правого масиву строго більші або
рівні елементам з лівого. Для об’єднання
двох відсортованих підмасивів у один необ-
хідно викликати операцію злиття (Merge).
Додаткова складність виникає у про-
цесі комбінування алгоритмів, описаних
вище. Припустимо, що сортується масив
довжиною N. Після виконання M операцій
вибору в початок або проходів сортуванням
бульбашкою у зворотному напрямку гаран-
товано матимемо відсортований підмасив
[0, M-1] зліва, усі елементи якого строго ме-
нші або рівні решті елементів у невідсорто-
ваній частині. Якщо тепер виконати вста-
вку елемента під індексом M у ліву час-
тину, то матимемо відсортований масив [0,
M], але тепер його елементи не будуть ме-
нші, ніж ті, що лишились у невідсортованій
частині.
Подальші виклики операцій вибору
можуть бути не ефективні через те, що най-
менший елемент із невідсортованої час-
тини масиву може виявитись меншим, ніж
той, що додався сортуванням вставкою. І
ліва відсортована частина після додавання
цього елемента стає невідсортованою, що
означає неефективність створеного алгори-
тму.
Для сортування бульбашкою одна
операція вставки не є критичною. Якщо
елемент доданий вставкою під індексом M
більший, ніж наступний (M+1), що буде до-
даний сортуванням бульбашкою, то на пер-
шому кроці вони поміняються місцями і пі-
дмасив буде відсортований. Однак, якщо
була виконана вставка і хоча б одна опера-
ція вибору, то сортування бульбашкою
втрачає ефективність, і масив може лиши-
тись у невідсортованому стані (рис. 2).
2 7 4 3 1 0
Бульбашкою
0 2 7 4 3 1 Вибором
0 1 7 4 3 2 Вставкою
0 1 7 4 3 2 Вибором
0 1 7 2 3 4 Ліва частина невідсор-
тована
Рис. 2. Приклад невірної послідовності
базових алгоритмів
Теоретичні і методологічні основи програмування
15
Для вирішення вищезгаданої про-
блеми введемо нові атомарні операції –
злиття зліва (ML) і злиття справа (MR). Для
відстежування викликів операцій вставки
будуть використовуватись додаткові інди-
катори. Якщо було використано операцію
вставки у початок, відповідний індикатор
буде встановлено. Перед наступним викли-
ком операцій сортування бульбашкою або
вибором для поточного масиву, потрібно
буде спочатку викликати операцію злиття
зліва. Тобто зберегти покажчики відсорто-
ваної частини зліва і решти масиву для по-
дальшого злиття. Для аналогічної ситуації
у кінці масиву буде викликатись операція
злиття справа.
Застосування генетичного
алгоритму для вибору найбільш
ефективного алгоритму
сортування
Хромосому представимо послідов-
ністю генів – базових алгоритмів сорту-
вання та допоміжних утиліт. Для представ-
лення хромосоми у текстовому вигляді за-
даємо текстове представлення кожному
гену. Таким чином хромосома буде мати
послідовність генів, розділених символом -
«,». Через те, що кожен ген являє собою
якусь функцію, то використаємо для текс-
тового представлення її абревіатуру. Розг-
лянемо існуючі гени:
BSB (Bubble sort backward) –
один прохід масивом із кінця у початок із
перестановкою пар елементів, що йдуть у
зворотному порядку;
BSF (Bubble sort forward) – те
саме, що і BSF, тільки прохід від початку у
кінець масиву;
FSB (Find swap biggest element) –
пошук найбільшого елемента у невідсорто-
ваній частині масиву і перестановка на по-
точне місце;
FSS (Find swap smallest element)
– те саме що і FSB, тільки виконується по-
шук найменшого елемента;
SEEI (Single element end
insertion) – вставка поточного елемента у
відсортовану частину в кінці масиву;
SEI (Single element insertion) –
вставка поточного елемента у відсортовану
частину на початку масиву;
SIS (Split in subarrays) – розді-
лення невідсортованої частини масиву на
дві рівні частини для подальшого сорту-
вання кожної з них окремо. Також збері-
гання покажчиків та розмірів масивів для
подальшого виконання операції злиття;
FS (Final sort) – один із загально-
відомих алгоритмів сортування, який гара-
нтовано виконає сортування;
PUA (Pop unsorted array) – діс-
тати покажчик і розмір наступної невідсор-
тованої частини для сортування. Викону-
ється для кожної частини збереженої опера-
цією SIS;
ESS (End subarray sort) – допо-
міжна операція, яка закриває фігурні ду-
жки, відкриті попередніми операціями для
перевірки індикатора відсортованості. Ви-
конується для кожної операції PUA після
послідовності генів сортування;
ML (Merge left) – збереження по-
кажчиків на відсортовану частину на поча-
тку та решту масиву для подальшого злиття
в один відсортований масив;
MR (Merge right) – те ж саме, що
і ML тільки для відсортованої частини в кі-
нці масиву;
Приклад сформованої хромосоми у тексто-
вому вигляді:
SEEI, MR, FSB, SIS, PUA, BSF, FSS, FS,
ESS, PUA, SEI, ML, FSS, FS, ESS, ESS.
Для обмеження довжини хромо-
соми, введемо певні обмеження.
На початку сортування вхідного ма-
сиву глибина дорівнює одному. У процесі
розбиття масиву і переходу до сортування
будь-якої із його частин, глибина збільшу-
ється на одиницю. Таким способом обме-
жується кількість розбивань масиву на час-
тини.
Окремим параметром обмежується
кількість базових операцій сортування для
кожного підмасиву. При досягненні макси-
мального значення, викликається розбиття
або фінальне сортування.
Генетичний алгоритм для генера-
ції алгоритмів сортування. Кожен індиві-
дуум представляє собою алгоритм сорту-
Теоретичні і методологічні основи програмування
16
вання. Генами представлені атомарні опе-
рації-складові існуючих алгоритмів сорту-
вання та допоміжні утиліти.
Функцією придатності, яка оцінює
якість кожного індивідуума, буде часова
ефективність. Але можуть бути і такі: кіль-
кість порівнянь, кількість перестановок
тощо. Або зважена комбінація таких чин-
ників.
Генерація наступної популяції здій-
снюється за допомогою схрещування і му-
тацій. Схрещування здійснює обмін части-
нами між двома батьками для створення но-
вого індивідуума.
Мутація випадковим чином змінює
деякі елементи генетичної послідовності.
Заново генеруються деякі ділянки хромо-
соми і випадково вибираються атомарні
операції.
Для наступного покоління обира-
ються індивідууми на основі їхньої придат-
ності. Індивіди з більшою придатністю ма-
ють більше шансів вижити і брати участь у
створенні нових індивідів.
Певна кількість індивідів з найкра-
щими показниками переноситься в насту-
пне покоління без змін. Інші формуються
схрещуванням індивідів існуючої популя-
ції. Індивіди для схрещення можуть виби-
ратись випадково, або за певними прави-
лами. Також можливий варіант із схре-
щенням кращих індивідів за правилами, а
решти – випадково. Для урізноманітнення
популяції додається певна кількість інди-
відів, згенерованих випадковим чином,
так само, як була створена найперша по-
пуляція.
Встановлюються параметри генети-
чного алгоритму, такі як розмір популяції,
ймовірність мутації, кількість поколінь
тощо. Визначається умова зупинки, напри-
клад, максимальна кількість поколінь або
досягнення певного рівня придатності.
Проводиться декілька ітерацій гене-
тичного пошуку, оптимізуються параметри
і функція придатності для покращення ре-
зультатів.
Застосування генетичного алгори-
тму до генерації алгоритмів сортування до-
зволяє автоматично еволюціонувати рі-
шення, призначені для різних сценаріїв, та
адаптувати їх до умов, що постійно зміню-
ються.
Представлення хромосоми
у вигляді дерева
Вхідний масив може мати будь-який
відсоток відсортованості. Як тільки дані у
масиві будуть відсортовані, доцільно завер-
шити виконання для уникнення погіршення
часової ефективності. Відстежування такої
ситуації реалізуємо використанням ознаки
відсортованості масиву, яка буде перевіря-
тись після кожної базової операції сорту-
вання.
Постійне оновлення і перевірки
ознаки відсортованості масиву вводить до-
даткові правила та обмеження у процес ге-
нерації хромосоми. У коді кожна наступна
перевірка додає новий рівень вкладеності і
область видимості, обмежену фігурними
дужками “{“ та “}”. Перевірка ознаки відсо-
ртованості і відкриття області видимості
має у собі кожний ген, що представляє ба-
зову операцію сортування. Відповідно кін-
цева ділянка хромосоми повинна мати фігу-
рні дужки, що закриваються у кількості рі-
вній відкритим дужкам. При розбитті ма-
сиву на підмасиви і сортуванні кожного ок-
ремо, матимемо послідовність базових опе-
рацій сортування і відповідну кількість за-
критих дужок. Оптимальною структурою
даних для представлення вище описаного
підходу є бінарне дерево (рис. 3).
Кожен вузол представляє собою ча-
стину хромосоми (послідовність генів) що
відповідає сортуванню певної частини ма-
сиву. Окремо зберігаються гени початку і
кінця. Вузли нащадків створюються під час
розбиття масиву і сортування частин ма-
сиву окремо. Наприклад, під час розбиття
масиву на дві рівні частини створюються
два вузла нащадків. Кожний створений
вузол матиме частину хромосоми, що реа-
лізує сортування відповідної частини ма-
сиву. Масив генів кінця включатиме у собі
злиття відсортованих масивів і ген завер-
шення сортування поточного масиву, що
включає закриття фігурних дужок і обну-
ління змінних.
Генерація алгоритму із хромосоми
повинна відбуватись за принципом обходу
Теоретичні і методологічні основи програмування
17
дерева вглиб [9]. Тобто для кожного вузла
гени ідуть у наступній послідовності:
гени початку;
гени першого дитячого вузла;
гени другого дитячого вузла;
гени кінця.
Операція схрещення деревовидних
хромосом виконується як обмін вузлами.
Для збереження глибини дерева-хромо-
соми обмін може бути проведений тільки
між вузлами відповідного рівня. Однак че-
рез те, що вершини на останньому рівні ма-
ють ген фінального сортування, а це гаран-
товано відсортує масив, обмін можливо
проводити між вузлами різних рівнів.
Висновки
Розроблений генетичний алгоритм
для структурної адаптації алгоритмів сор-
тування. Його застосування дозволяє здійс-
нити структурну адаптацію і вибрати най-
більш ефективні та пристосовані до стабі-
льних середовищ використання.
Представлений підхід до форму-
вання хромосоми у вигляді дерева дозволяє
вирішити наявні проблеми. Він дозволяє
ефективно формувати хромосоми, резуль-
татом декодування яких буде алгоритм,
який гарантовано виконує сортування.
Формалізована модель формування
алгоритмів сортування засобами конструк-
тивно-продукційного моделювання є до-
Рис. 3. Схема хромосоми у формі дерева
Теоретичні і методологічні основи програмування
18
сить об’ємною та буде представлена окре-
мою статтею.
Розроблене програмне забезпечення
має застосовуватись у процесі адаптації ал-
горитмів сортування до стабільних потоків
вхідних даних та середовищ використання.
Література
1. А.Ю. Берко, О.М. Верес, В.В. Пасічник, Си-
стеми баз даних та знань. Книга 2, Магно-
лія-2006, 2013.
2. O. Mendelevitch, C. Stella, D. Eadline, Practi-
cal Data Science with Hadoop and Spark, Ad-
dison-Wesley, 2016.
3. D. Knuth, The Art Of Computer Programming,
vol. 3: Sorting And Searching, Addison-
Wesley, 1973.
4. Timsort. Accessed: 08.07.2023.
https://svn.python.org/projects/python/trunk/
Objects/listsort.txt.
5. D.R. Musser, Introspective Sorting and
Selection Algorithms, Software: Practice and
Experience, 1997, № 27 (8), pp.983–993. doi:
10.5555/261387.261395.
6. В.І. Шинкаренко, А.Ю. Дорошенко, О.А.
Яценко, В.В. Разносілін, К.К. Галанін, Дво-
компонентні алгоритми сортування, Про-
блеми програмування, 2022, № 3-4. С. 32-
41. doi: 10.15407/pp2022.03-04.032.
7. J.H. Holland, Adaptation in Natural and Artifi-
cial Systems, The MIT Press, 1992.
8. В.І. Шинкаренко, О.В. Макаров, Дослі-
дження ефективності деяких детермінова-
них методів передобробки сортування да-
них, Проблеми програмування, 2023, № 4,
С. 3-14. doi: 10.15407/pp2023.04.003.
9. R. Tarjan, Depth-First Search and Linear
Graph Algorithms, SIAM Journal on Compu-
ting, 1972, № 1(2). doi: 10.1137/0201010.
References
1. A.Yu. Berko, O.M. Veres, V.V. Pasichnik, Da-
tabase and knowledge systems. Book 2, Mag-
nolia-2006, 2013.
2. O. Mendelevitch, C. Stella, D. Eadline, Practi-
cal Data Science with Hadoop and Spark, Ad-
dison-Wesley, 2016.
3. D. Knuth, The Art Of Computer
Programming, vol. 3: Sorting And Searching,
Addison-Wesley, 1973.
4. Timsort. Accessed: 08.07.2023.
https://svn.python.org/projects/python/trunk/
Objects/listsort.txt.
5. D.R. Musser, Introspective Sorting and
Selection Algorithms, in: Software: Practice
and Experience, 1997, 27 (8), pp.983–993. doi:
10.5555/261387.261395.
6. V.I. Shinkarenko, A.Yu. Doroshenko,
O.A. Yatsenko, V.V. Raznosilin,
K.K. Galanin, Bicomponent sorting algo-
rithms, in: Problems of programming, 2022, №
3-4, pp.32-41. doi: 10.15407/pp2022.03-
04.032. [in Ukrainian]
7. J.H. Holland, Adaptation in Natural and Artifi-
cial Systems, The MIT Press, 1992.
8. V.I. Shinkarenko, O.V. Makarov, Study of the
effectiveness of some deterministic prepro-
cessing methods of data sorting, in: Problems
of programming, 2023, № 4, pp.3-14. doi:
10.15407/pp2023.04.003. [in Ukrainian]
9. R. Tarjan, Depth-First Search and Linear
Graph Algorithms, in: SIAM Journal on Com-
puting, 1972, № 1(2). doi: 10.1137/0201010.
Одержано: 14.04.2024
Внутрішня рецензія отримана: 26.04.2024
Зовнішня рецензія отримана: 29.04.2024
Про авторів:
Шинкаренко Віктор Іванович,
доктор технічних наук, професор,
https://orcid.org/0000-0001-8738-7225
Макаров Олексій Вікторович,
аспірант,
https://orcid.org/0009-0003-0921-155X
Місце роботи авторів:
Український державний університет
науки і технологій,
49010, Україна, Дніпро,
вул. академіка Лазаряна, 2.
E-mail: office@ust.edu.ua
https://ust.edu.ua/
|