Генетичний алгоритм для структурної адаптації алгоритмів сортування
| dc.contributor.author | Шинкаренко, Віктор Іванович | uk_UA |
| dc.contributor.author | Макаров, Олексій Вікторович | uk_UA |
| dc.date.accessioned | 2025-03-18T18:55:57Z | |
| dc.date.available | 2025-03-18T18:55:57Z | |
| dc.date.issued | 2024 | |
| dc.description | В. Шинкаренко: ORCID 0000-0001-8738-72254; О. Макаров: ORCID 0009-0003-0921-155X | uk_UA |
| dc.description.abstract | UKR: Застосовано конструктивізм для формування коду алгоритму сортування. Представлено метаалгоритм генерації програмного коду. Для генерації використовуються частини існуючих алгоритмів сортування і допоміжні утиліти. Використано генетичний алгоритм для вибору алгоритму з максимальною часовою ефективністю у заданих умовах використання. Використання стандартного генетичного алгоритму стикається з проблемою, пов’язаною з різною кількістю елементарних дій по сортуванню, що призводить до використання хромосом різної довжини. Для рішення проблеми запропоновано представлення хромосоми у формі бінарного дерева. Кожен вузол має гени початку, кінця і двох вузлів-нащадків. Для формування алгоритму, який гарантовано буде сортувати масив, усі кінцеві вузли (листя) включають ген фінального сортування у кінець початкової послідовності генів. Даний ген декодується викликом існуючого алгоритму сортування, який гарантовано виконає сортування. Операції кросоверу та мутацій виконуються на хромосомах у формі бінарного дерева. Схрещення виконується за допомогою обміну вузлами дерева. Реалізовані механізми кодування і декодування алгоритму сортування із хромосоми. Для декодування і формування відповідного алгоритму сортування виконується лінеріалізація: формування текстового представлення за алгоритмом обходу дерева у глибину. Фітнес функція визначається як середній час сортування випадково сформованих масивів для сортування (для всіх хромосом однакові масиви) у деякому стабільному середовищі з урахуванням певних особливостей цих масивів. Передбачено застосування інших фітнес функцій пов’язаних з кількістю обчислень, порівнянь або перестановок. Розроблене програмне забезпечення має застосовуватись у процесі адаптації алгоритмів сортування до стабільних потоків вхідних даних та середовищ використання. | uk_UA |
| dc.description.abstract | ENG: 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 bi nary 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. | en |
| dc.identifier.citation | Шинкаренко В. І., Макаров О. В. Генетичний алгоритм для структурної адаптації алгоритмів сортування. Проблеми програмування. 2024. № 2/3. С. 11–18. DOI: 10.15407/pp2024.02-03.011. | uk_UA |
| dc.identifier.doi | 10.15407/pp2024.02-03.011 | |
| dc.identifier.issn | 1727-4907 (print) | |
| dc.identifier.uri | https://crust.ust.edu.ua/handle/123456789/19838 | |
| dc.identifier.uri | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/614 | |
| dc.language.iso | uk | |
| dc.publisher | Інститут програмних систем НАН України, Київ | 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 | sorting algorithm | en |
| dc.subject | sorting | en |
| dc.subject | constructivism | en |
| dc.subject | genetic algorithm | en |
| dc.subject | chromosome | en |
| dc.subject | binary tree | en |
| dc.subject | КІТ | uk_UA |
| dc.subject.classification | TECHNOLOGY | en |
| dc.subject.classification | TECHNOLOGY::Information technology | en |
| dc.title | Генетичний алгоритм для структурної адаптації алгоритмів сортування | uk_UA |
| dc.title.alternative | Genetic Algorithm for Structural Adaptation of Sorting Algorithms | en |
| dc.type | Article | en |