Constructive-synthesizing modeling of the genetic algorithm chromosomes with encoded sorting algorithms
In the structural adaptation of algorithms using a genetic algorithm, one of the challenges is encoding the struc ture of algorithms into a chromosome. This article explores an approach to structural adaptation and the devel opment of efficient sorting algorithms based on the paradigm of constructiv...
Gespeichert in:
| Datum: | 2025 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
PROBLEMS IN PROGRAMMING
2025
|
| Schlagworte: | |
| Online Zugang: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/857 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Institution
Problems in programming| id |
pp_isofts_kiev_ua-article-857 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/26/dc4bccbfbd63fdf10ef038a71cabfb26.pdf |
| spelling |
pp_isofts_kiev_ua-article-8572025-11-20T15:26:28Z Constructive-synthesizing modeling of the genetic algorithm chromosomes with encoded sorting algorithms Конструктивно-продукційне моделювання хромосом генетичного алгоритму з закодованими алгоритмами сортування Shinkarenko, V.I. Makarov, O.V. constructive-synthesizing modeling; sorting algorithm; time efficiency; software; information tech nology; genetic algorithm UDC 004.4 конструктивно-продукційне моделювання; алгоритми сортування; часова ефективність; програмне забезпечення; інформаційні технології; генетичний алгоритм УДК 004.4 In the structural adaptation of algorithms using a genetic algorithm, one of the challenges is encoding the struc ture of algorithms into a chromosome. This article explores an approach to structural adaptation and the devel opment of efficient sorting algorithms based on the paradigm of constructive-synthesizing modeling. A method is proposed for representing chromosomes as encoded structures corresponding to various variants of sorting algorithms. This approach allows the solution search space to be formed not only as a set of numerical parameters but also as complete software. Operations of substitution, partial inference, and composition are described, which enable the synthesis of new sorting algorithms. A genetic algorithm is applied to generate and select functionally equivalent algorithms. Examples are provided of constructing chromosome trees that encode sorting procedures of varying complexity. A program has been implemented for generating and evolutionarily improving chromo somes with encoded sorting algorithms. The application of constructive-synthesizing modeling to the problem of encoding structurally different but functionally equivalent algorithms into chromosomes is demonstrated. Ex perimental results confirmed that usage of constructive-synthesizing modeling increases population diversity and accelerates the discovery of efficient solutions compared to classical genetic algorithms. The proposed method ology can be used for automated algorithm construction, optimization of their structure, and adaptation to spe cific usage conditions.Prombles in programming 2025; 3: 39-52 У разі структурної адаптації алгоритмів із використанням генетичного алгоритму однією із проблем є кодування структури алгоритмів у хромосому. У статті розглядається підхід до структурної адаптації та формування ефективних алгоритмів сортування на основі парадигми конструктивно-продукційного мо делювання. Запропоновано метод представлення хромосом у вигляді закодованих структур, що відобра жають різні варіанти алгоритмів сортування. Такий підхід дозволяє формувати простір пошуку рішень не лише у вигляді набору числових параметрів, а й у вигляді цілісних програмних конструкцій. Описано операції підстановки, часткового виведення та композиції, які забезпечують синтез нових алгоритмів со ртування. Для формування і відбору функціонально еквівалентних алгоритмів застосовано генетичний алгоритм. Наведено приклади побудови хромосом-дерев, що кодують сортувальні процедури різної скла дності. Реалізовано програму для генерації та еволюційного вдосконалення хромосом із закодованими алгоритмами сортування. продемонстровано застосування конструктивно-продукційного моделювання для вирішення задачі кодування структурно різних, але функціонально еквівалентних алгоритмів у хро мосомах. Результати експериментів підтвердили, що застосування конструктивно-продукційного моде лювання забезпечує підвищення різноманітності популяцій та прискорює знаходження ефективних рішень у порівнянні з класичними генетичними алгоритмами. Запропонована методика може бути вико ристана для автоматизованого конструювання алгоритмів, оптимізації їхньої структури та адаптації до специфічних умов використання.Prombles in programming 2025; 3: 39-52 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2025-11-14 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/857 10.15407/pp2025.03.039 PROBLEMS IN PROGRAMMING; No 3 (2025); 39-52 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 3 (2025); 39-52 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 3 (2025); 39-52 1727-4907 10.15407/pp2025.03 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/857/908 Copyright (c) 2025 PROBLEMS IN PROGRAMMING |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2025-11-20T15:26:28Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
constructive-synthesizing modeling sorting algorithm time efficiency software information tech nology genetic algorithm UDC 004.4 |
| spellingShingle |
constructive-synthesizing modeling sorting algorithm time efficiency software information tech nology genetic algorithm UDC 004.4 Shinkarenko, V.I. Makarov, O.V. Constructive-synthesizing modeling of the genetic algorithm chromosomes with encoded sorting algorithms |
| topic_facet |
constructive-synthesizing modeling sorting algorithm time efficiency software information tech nology genetic algorithm 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 |
Constructive-synthesizing modeling of the genetic algorithm chromosomes with encoded sorting algorithms |
| title_short |
Constructive-synthesizing modeling of the genetic algorithm chromosomes with encoded sorting algorithms |
| title_full |
Constructive-synthesizing modeling of the genetic algorithm chromosomes with encoded sorting algorithms |
| title_fullStr |
Constructive-synthesizing modeling of the genetic algorithm chromosomes with encoded sorting algorithms |
| title_full_unstemmed |
Constructive-synthesizing modeling of the genetic algorithm chromosomes with encoded sorting algorithms |
| title_sort |
constructive-synthesizing modeling of the genetic algorithm chromosomes with encoded sorting algorithms |
| title_alt |
Конструктивно-продукційне моделювання хромосом генетичного алгоритму з закодованими алгоритмами сортування |
| description |
In the structural adaptation of algorithms using a genetic algorithm, one of the challenges is encoding the struc ture of algorithms into a chromosome. This article explores an approach to structural adaptation and the devel opment of efficient sorting algorithms based on the paradigm of constructive-synthesizing modeling. A method is proposed for representing chromosomes as encoded structures corresponding to various variants of sorting algorithms. This approach allows the solution search space to be formed not only as a set of numerical parameters but also as complete software. Operations of substitution, partial inference, and composition are described, which enable the synthesis of new sorting algorithms. A genetic algorithm is applied to generate and select functionally equivalent algorithms. Examples are provided of constructing chromosome trees that encode sorting procedures of varying complexity. A program has been implemented for generating and evolutionarily improving chromo somes with encoded sorting algorithms. The application of constructive-synthesizing modeling to the problem of encoding structurally different but functionally equivalent algorithms into chromosomes is demonstrated. Ex perimental results confirmed that usage of constructive-synthesizing modeling increases population diversity and accelerates the discovery of efficient solutions compared to classical genetic algorithms. The proposed method ology can be used for automated algorithm construction, optimization of their structure, and adaptation to spe cific usage conditions.Prombles in programming 2025; 3: 39-52 |
| publisher |
PROBLEMS IN PROGRAMMING |
| publishDate |
2025 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/857 |
| work_keys_str_mv |
AT shinkarenkovi constructivesynthesizingmodelingofthegeneticalgorithmchromosomeswithencodedsortingalgorithms AT makarovov constructivesynthesizingmodelingofthegeneticalgorithmchromosomeswithencodedsortingalgorithms AT shinkarenkovi konstruktivnoprodukcíjnemodelûvannâhromosomgenetičnogoalgoritmuzzakodovanimialgoritmamisortuvannâ AT makarovov konstruktivnoprodukcíjnemodelûvannâhromosomgenetičnogoalgoritmuzzakodovanimialgoritmamisortuvannâ |
| first_indexed |
2025-11-15T02:08:55Z |
| last_indexed |
2025-11-21T02:19:53Z |
| _version_ |
1850423544672944128 |
| fulltext |
Штучний інтелект
39
© В.І. Шинкаренко, О.В. Макаров, 2025
ISSN 1727-4907. Проблеми програмування. 2025. №3
УДК 004.4 https://doi.org/10.15407/pp2025.03.039
В.І. Шинкаренко, О.В. Макаров
КОНСТРУКТИВНО-ПРОДУКЦІЙНЕ
МОДЕЛЮВАННЯ ХРОМОСОМ ГЕНЕТИЧНОГО
АЛГОРИТМУ ІЗ ЗАКОДОВАНИМИ АЛГОРИТМАМИ
СОРТУВАННЯ
У разі структурної адаптації алгоритмів із використанням генетичного алгоритму однією із проблем є
кодування структури алгоритмів у хромосому. У статті розглядається підхід до структурної адаптації та
формування ефективних алгоритмів сортування на основі парадигми конструктивно-продукційного мо-
делювання. Запропоновано метод представлення хромосом у вигляді закодованих структур, що відобра-
жають різні варіанти алгоритмів сортування. Такий підхід дозволяє формувати простір пошуку рішень
не лише у вигляді набору числових параметрів, а й у вигляді цілісних програмних конструкцій. Описано
операції підстановки, часткового виведення та композиції, які забезпечують синтез нових алгоритмів со-
ртування. Для формування і відбору функціонально еквівалентних алгоритмів застосовано генетичний
алгоритм. Наведено приклади побудови хромосом-дерев, що кодують сортувальні процедури різної скла-
дності. Реалізовано програму для генерації та еволюційного вдосконалення хромосом із закодованими
алгоритмами сортування. продемонстровано застосування конструктивно-продукційного моделювання
для вирішення задачі кодування структурно різних, але функціонально еквівалентних алгоритмів у хро-
мосомах. Результати експериментів підтвердили, що застосування конструктивно-продукційного моде-
лювання забезпечує підвищення різноманітності популяцій та прискорює знаходження ефективних
рішень у порівнянні з класичними генетичними алгоритмами. Запропонована методика може бути вико-
ристана для автоматизованого конструювання алгоритмів, оптимізації їхньої структури та адаптації до
специфічних умов використання.
Ключові слова: конструктивно-продукційне моделювання, алгоритми сортування, часова ефективність,
програмне забезпечення, інформаційні технології, генетичний алгоритм.
V.I. Shinkarenko, O.V. Makarov
CONSTRUCTIVE-SYNTHESIZING MODELING OF THE
GENETIC ALGORITHM CHROMOSOMES WITH ENCODED
SORTING ALGORITHMS
In the structural adaptation of algorithms using a genetic algorithm, one of the challenges is encoding the struc-
ture of algorithms into a chromosome. This article explores an approach to structural adaptation and the devel-
opment of efficient sorting algorithms based on the paradigm of constructive-synthesizing modeling. A method
is proposed for representing chromosomes as encoded structures corresponding to various variants of sorting
algorithms. This approach allows the solution search space to be formed not only as a set of numerical parameters
but also as complete software. Operations of substitution, partial inference, and composition are described, which
enable the synthesis of new sorting algorithms. A genetic algorithm is applied to generate and select functionally
equivalent algorithms. Examples are provided of constructing chromosome trees that encode sorting procedures
of varying complexity. A program has been implemented for generating and evolutionarily improving chromo-
somes with encoded sorting algorithms. The application of constructive-synthesizing modeling to the problem
of encoding structurally different but functionally equivalent algorithms into chromosomes is demonstrated. Ex-
perimental results confirmed that usage of constructive-synthesizing modeling increases population diversity and
accelerates the discovery of efficient solutions compared to classical genetic algorithms. The proposed method-
ology can be used for automated algorithm construction, optimization of their structure, and adaptation to spe-
cific usage conditions.
Key words: constructive-synthesizing modeling, sorting algorithm, time efficiency, software, information tech-
nology, genetic algorithm.
Штучний інтелект
40
Вступ
Структурна адаптація алгоритмів за
показниками часової ефективності перед-
бачає зміну складових цих алгоритмів. Для
формування і відбору функціонально екві-
валентних алгоритмів застосовується гене-
тичний алгоритм. Тут постає проблема
кодування алгоритмів, що підлягають адап-
тації, у вигляді хромосоми. Це ускладню-
ється ще й можливістю розподілу
обчислень у різних частинах даних. Ета-
лонними алгоритмами у програмуванні є
алгоритми сортування. Тому на прикладі
алгоритмів сортування у цій роботі проде-
монстровано застосування конструктивно-
продукційного моделювання для вирі-
шення задачі кодування структурно різних,
але функціонально еквівалентних алгорит-
мів у хромосомах.
Незважаючи на наявність великої кі-
лькості фундаментальних алгоритмів сор-
тування, таких як Insertion Sort, Quick Sort
[1] або Merge Sort [2], які широко викорис-
товуються завдяки своїй простоті реалізації
та зрозумілій логіці, проблема підвищення
їхньої ефективності залишається актуаль-
ною. Зростання обсягів даних, розвиток ба-
гатоядерних і паралельних архітектур, а
також потреба в оптимізації під кеш-
пам’ять і специфічні структури даних зумо-
влюють появу нових підходів. Саме тому
активно ведуться наукові дослідження,
спрямовані як на удосконалення класичних
методів (Insertion Sort, Merge Sort,
Quicksort), так і на створення нових алгори-
тмів, здатних поєднувати простоту, стабі-
льність і високу продуктивність у сучасних
умовах.
До найбільш відомих прикладів по-
будови алгоритмів на основі кількох класи-
чних належить Timsort [3] – гібридний
алгоритм, що поєднує переваги Merge Sort
та Insertion Sort і використовується в стан-
дартних бібліотеках Python та Java, а також
Introsort [4], який адаптивно перемикається
між Quick Sort, Heap Sort і Insertion Sort за-
лежно від глибини рекурсії, забезпечуючи
гарантовану ефективність у найгіршому ви-
падку.
Попри наявність ефективних рі-
шень, розробка нових алгоритмів сорту-
вання продовжується. Одним із сучасних
підходів до вдосконалення алгоритмів сор-
тування є розробка паралельних методів,
що враховують особливості розподілу да-
них та ефективність операцій ранжування.
Наприклад, у роботі [5] запропоновано мо-
дель паралельного алгоритму сортування з
формуванням рангу, яка демонструє пере-
ваги у швидкодії та масштабованості для
великих обсягів даних.
Сучасні дослідження пропонують
вдосконалення класичних алгоритмів сор-
тування. Наприклад, Multi-Pivot Quicksort
[6] – використання декількох опорних еле-
ментів (k-pivot), що покращує ефективність
роботи із кешем та знижує кількість порів-
нянь. Однією із можливих реалізацій є варі-
ант із трьома опорними елементами, який
продемонстрував приріст продуктивності у
7-8% порівняно із класичним алгоритмом з
1 опорним елементом.
На відміну від класичного сорту-
вання вставками, у [7] масив має дві відсо-
ртовані послідовності на початку і в кінці
масиву, а невідсортована частина знахо-
диться між ними. Також важливою перева-
гою є можливість вставляти більше одного
елемента на правильні позиції за одну іте-
рацію. Експериментально алгоритм пока-
зав менший середній час виконання, ніж
Quick Sort для відносно невеликих масивів
обсягом до 1500 елементів.
Adaptive ShiversSort [8] – алгоритм
сортування, заснований на TimSort. Особ-
ливо ефективний для сортування частково
впорядкованих даних. Основна ідея поля-
гає в тому, що масив спочатку розбивається
на вже відсортовані підпослідовності, які
виявляються під час одного проходу.
Adaptive ShiversSort є 3-aware алгоритмом –
тобто, вибираючи операції злиття, він ана-
лізує лише три верхні елементи стека пос-
лідовностей, що знижує складність
керування процесом. Алгоритм додатково
приймає цілочислений параметр, який змі-
нює логіку злиття послідовностей.
Magnetic Bubble Sort [9]: Іновацій-
ний метод, який замість поодиноких перес-
тановок сусідніх елементів, оперує
«блоком» елементів. Такі блоки поводяться
Штучний інтелект
41
як "магнітики", притягуючись або відштов-
хуючись залежно від значень. Такий підхід
дозволяє «переносити» відразу кілька еле-
ментів, що економить кількість проходів
масивом у випадках, коли в масиві багато
повторів. У деяких тестах час сортування
зменшився на 20 % порівняно з bubble sort.
One-By-One (OBO): A Fast Sorting
Algorithm [10]: Новий in-place алгоритм со-
ртування. Ідея полягає у поступовому "ви-
вільненні" кожного елемента на правильне
місце по черзі (one-by-one), комбінуючи
стратегічне локальне впорядкування і гло-
бальну оптимізацію. Такий підхід особливо
ефективний у разі невеликих масивів і ма-
сивів, що частково або майже впорядко-
вані, оскільки він зменшує непотрібні
переміщення шляхом прямого позиціону-
вання. OBO демонструє кращий середній
час виконання в порівнянні з класичними
квадратичними алгоритмами, наприклад
Selection Sort і Bubble Sort.
Для відбору кращого за часовими
показниками алгоритму сортування доці-
льне використання генетичного алгоритму
[11] (ГА), що є поширеним інструментом
для розв'язання складних оптимізаційних
задач, які виникають у різних галузях науки
і техніки. Він базується на принципах при-
родного відбору та генетики і використовує
популяцію можливих розв'язків, які еволю-
ціонують з покоління в покоління [12]. Од-
ним із ключових аспектів генетичного
алгоритму є формування хромосом, які
представляють можливі розв'язки задачі, у
даному випадку конкретні алгоритми сор-
тування.
Для формування хромосом у цій ро-
боті використано конструктивно-продук-
ційне моделювання (КПМ) – підхід, який
дозволяє створювати складні структури
шляхом застосування продукційних пра-
вил [13]. Цей метод широко використову-
ється в різних галузях, таких як
комп'ютерна графіка, моделювання біоло-
гічних систем та автоматизоване проєкту-
вання. Однією з основних переваг
використання КПМ у генетичних алгорит-
мах є можливість створення структур, які
відповідають певним обмеженням та ви-
могам задачі. Це дозволяє зменшити роз-
мір пошукового простору та підвищити
ефективність алгоритму. Крім того, КПМ
дозволяє легко інтегрувати доменні знання
у процес генерації хромосом, що може зна-
чно покращити якість розв'язків.
У цій статті буде детально розгля-
нуто процес формування хромосом за допо-
могою КПМ, включаючи опис правил
продукції.
Конструктивно-продукційна
модель формування хромосоми
Узагальненим конструктором [13]
називається трійка
𝐶𝐶 = 〈𝑀𝑀, Σ, Λ〉, (1)
де 𝑀𝑀 – неоднорідний розширюваний носій;
Σ – сигнатура операцій та відношень; Λ – ін-
формаційне забезпечення конструювання
(ІЗК): онтологія, мета, правила та обме-
ження, початкова форма та умови закін-
чення.
Визначимо спеціалізацію конструк-
тору 𝐶𝐶𝑆𝑆𝑆𝑆 – моделі формування хромосоми,
що кодує алгоритм сортування. Виконаємо
операцію уточнюючого перетворення уза-
гальненого конструктора 𝐶𝐶.
𝐶𝐶 = 〈𝑀𝑀, Σ, Λ〉 ⟼𝑠𝑠 𝐶𝐶𝑆𝑆𝑆𝑆
= 〈𝑀𝑀𝑆𝑆𝑆𝑆, Σ𝑆𝑆𝑆𝑆, Λ𝑆𝑆𝑆𝑆〉, (2)
де 𝑀𝑀𝑆𝑆𝑆𝑆 – носій, що включає, зокрема, термі-
нальний (T1) і нетермінальний(N1) алфавіт,
а також множину правил продукції Ψ з пра-
вилами 𝜓𝜓𝑖𝑖 = 〈𝑠𝑠𝑖𝑖, 𝑔𝑔𝑖𝑖〉 ∈ Ψ, де i – номер пра-
вила, 𝑠𝑠𝑖𝑖 – послідовність відношень
підстановки, 𝑔𝑔𝑖𝑖 – послідовність операцій
над атрибутами. Σ𝑆𝑆𝑆𝑆 – операції та відносини
на елементах 𝑀𝑀𝑆𝑆𝑆𝑆. ІЗК Λ𝑆𝑆𝑆𝑆 ⊃ Λ.
Для формування конструкцій у ви-
гляді хромосоми у Σ𝑆𝑆𝑆𝑆 передбачені операції
підстановки, часткового та повного виводу.
Вивід виконується від початкового нетер-
міналу, який є початковою формою ітера-
ційним виконанням операцій часткового
виводу. Операція часткового виводу обирає
одне з правил із множини Ψ та виконує за-
міну лівої частини правила на праву у пото-
чній формі та виконує операції над
атрибутами. Вона використовує операцію
підстановки: саме зміна поточної форми і є
частиною операції повного виводу, почина-
ючи з початкового нетерміналу і закінчу-
ючи готовою конструкцією.
Штучний інтелект
42
У цій роботі 𝑔𝑔𝑖𝑖 = 〈𝑔𝑔𝑖𝑖,1, 𝑔𝑔𝑖𝑖,2〉 ∈ Ψ.
Операції виконуються у наступній послідо-
вності: спочатку виконуються операції над
атрибутами 𝑔𝑔𝑖𝑖,1 потім операції підстановки
𝑠𝑠𝑖𝑖 і в кінці – 𝑔𝑔𝑖𝑖,2.
ІЗК ΛS𝐴𝐴 містить визначення, допов-
нення та обмеження, які уточнюють алфа-
віт, атрибути носія, відносини підстановки
задають особливості виконання операцій
підстановки та виведення.
Нетермінальний алфавіт 𝑁𝑁1 = { 𝛼𝛼𝑖𝑖𝜙𝜙 }
складається з допоміжних символів з атри-
бутами, що позначаються грецькими літе-
рами.
Термінальним алфавітом T1 є мно-
жина генів, які утворюють хромосому, від-
повідну алгоритму сортування. Гени
відповідають частинам відомих алгоритмів
сортування, алгоритмам передобробки
[14,15] даних і допоміжним функціям. На-
ведемо список усіх терміналів – генів, від-
повідно до:
BSF (Bubble sort forward) – одного
проходу алгоритму сортування бу-
льбашкою;
BSB (Bubble sort backward) – одного
проходу алгоритму сортування бу-
льбашкою у зворотному порядку;
FSB (Find swap biggest element) – по-
шуку найбільшого елементу у невід-
сортованій частині масиву із
перестановкою на поточне місце;
FSS (Find swap smallest element) –
пошуку найменшого елементу у не-
відсортованій частині масиву із пе-
рестановкою на поточне місце;
SEEI (Single element end insertion) –
операції вставки поточного елеме-
нта у відсортовану частину в кінці
масиву;
SEI (Single element insertion) – опе-
рації вставки поточного елемента у
відсортовану частину на початку ма-
сиву;
SIS (Split in subarrays) – операції ро-
зділення невідсортованої частини
масиву на дві рівні частини для по-
дальшого сортування кожної з них
окремо. Також зберігання покажчи-
ків та розмірів масивів для подаль-
шого виконання операції злиття;
P (Partition) – встановлення елеме-
нта під індексом i на правильне мі-
сце у відсортованому масиві і
перекидання менших елементів лі-
воруч, а більших – праворуч;
FS (Final sort) – одного із загальнові-
домих алгоритмів сортування
(quicksort, mergesort, heapsort);
PUA (Pop unsorted array) – діста-
вання покажчика і розміру наступ-
ної невідсортованої частини для
сортування;
ESS (End subarray sort) – допоміжної
операції, яка закриває фігурні дужки
відкриті попередніми операціями
для перевірки індикатора відсорто-
ваності;
ML (Merge left) – збереження пока-
жчиків на відсортовану частину на
початку та решту масиву для пода-
льшого злиття в один відсортований
масив;
MR (Merge right) – збереження пока-
жчиків на відсортовану частину в кі-
нці та решту масиву для подальшого
злиття в один відсортований масив;
QP (Quick Preprocess) – передба-
чення позиції елемента у відсортова-
ному масиві й перестановка;
PM (Preprocess with Memory) – те
саме, що і QP, але передбачені інде-
кси запам’ятовуються і перестано-
вка виконується на наступне раніше
не передбачувану позицію;
SR (Sort Ranges) – розвертання усіх
послідовностей елементів, що йдуть
у зворотному порядку;
BLQP (Block Local Quick
Preprocessing) – розбивка сортова-
них даних на блоки певного обсягу і
виконання швидкої перестановки у
межах блоку;
BLPM (Block Local Preprocessing
with Memory) – розбивка сортованих
даних на блоки певного обсягу і ви-
конання перестановки із пам’яттю у
межах блока;
BGQP (Block Global Quick
Preprocessing) – визначення позиції
елемента (як у швидкій передоброб-
ці) і виконання перестановки тільки
Штучний інтелект
43
якщо передбачена позиція перебу-
ває у межах блоку;
BGPM (Block Global Preprocessing
with Memory) – визначення позиції
елемента (як у передобробці з
пам’яттю) і виконання перестано-
вки, тільки якщо передбачена пози-
ція є у межах блоку.
У процесі формування хромосоми
[16] операції підстановки (на основі відпо-
відних відношень підстановки) реалізують
додавання терміналів (генів) до вузлів де-
рева і нових вузлів до дерева. Розглянемо
відношення підстановки.
Відношення 𝛽𝛽 → 𝛾𝛾𝜏𝜏 дає можливість
виконати заміну 𝛽𝛽 на 𝛾𝛾 у збудованій частині
хромосоми, якщо в ній є 𝛽𝛽 і атрибут досту-
пності 𝜏𝜏 дорівнює true.
𝛽𝛽 → 𝛾𝛾𝜏𝜏
↗ 𝜌𝜌
↘ 𝛿𝛿, де 𝛽𝛽, 𝛾𝛾, 𝛿𝛿 і 𝜌𝜌 –деякі пос-
лідовності терміналів і нетерміналів. Від-
ношення дає можливість виконати заміну 𝛽𝛽
на 𝛾𝛾 у збудованій частині хромосоми, а кон-
кретно у поточному вузлі хромосоми-де-
рева, якщо в ній є 𝛽𝛽 і атрибут доступності 𝜏𝜏
дорівнює true. Відношення «↗» і «↘» дають
можливість додати лівий і правий вузли на-
щадки до поточного вузла дерева і додати 𝜌𝜌
і 𝛿𝛿 до відповідних вузлів.
Розглянемо наступний приклад пра-
вила підстановки.
𝛼𝛼 → 𝐶𝐶𝜏𝜏
↗ 𝐷𝐷 ∙ 𝛼𝛼 ∙ 𝐸𝐸
↘ 𝐹𝐹 ∙ 𝛼𝛼 ∙ 𝐺𝐺 , (3)
Поточна послідовність 𝐴𝐴 ∙ 𝛼𝛼 ∙ 𝐵𝐵, де 𝛼𝛼
– нетермінал і 𝐴𝐴, 𝐵𝐵 – термінали. У ході ви-
конання операції підстановки на основі від-
ношення підстановки (3) буде додано ген C
до початкової послідовності генів поточ-
ного вузла (Node level 1), два вузли-наща-
дки до поточного вузла. Також додано ген
D і нетермінал 𝛼𝛼 до початкової послідовно-
сті та ген E до кінцевої послідовності лівого
вузла нащадка. Ген F і нетермінал 𝛼𝛼 буде
додано до початкової послідовності пра-
вого вузла нащадка, а ген G – відповідно до
кінцевої. Результат підстановки представ-
лено на рис. 1. Далі підстановки будуть
продовжені відповідно для нетерміналів лі-
вого та правого вузлів.
Визначені такі операції над атрибу-
тами: :=(a, b) – присвоєння значення b змін-
ній a; +(a, b, c) – додавання аргументів b і c,
результат зберігається у a; ==(a, b, c) – якщо
b дорівнює c, зберігає true у a, інакше –
false; ∧(a, b, c) – виконання операції логічне
«і» над агрументами b і с, результат збері-
гається у a; >(a, b, c) – порівнює аргументи
b і c. Якщо b більше за c, присвоює a зна-
чення true, інакше – false; <(a, b, c) – порів-
нює аргументи b і c. Якщо b менше за c,
присвоює a значення true, інакше – false;
>=(a, b, c) – порівнює аргументи b і c. Якщо
b більше або рівне c, присвоює a значення
true, інакше – false; <=(a, b, c) – порівнює
аргументи b і c. Якщо b менше або рівне c,
присвоює a значення true, інакше – false.
Атрибути терміналів і нетерміналів поточ-
ної форми:
b1/b2 – ознаки того, що елементи у
відсортованій частині на початку/кі-
нці масиву менші/більші за усі інші;
cD – поточна глибина дерева-хромо-
соми;
nG – кількість генів у поточному ву-
злі дерева-хромосоми;
pGU – ознака того, що попередній
використаний ген є будь-яким геном
передобробки;
MD – значення максимальної гли-
бини дерева-хромосоми;
MGBS – значення мінімальної кіль-
кості генів у вузлі, після досягнення
якого стають доступними гени роз-
биття.
Початкові умови конструювання:
𝛼𝛼 – нетермінал, з якого починається виве-
дення.
Умови завершення конструювання:
Хромосома повністю сконструйована (по-
точна форма не містить нетерміналів).
Рис 1. Початкова форма (зліва) і форма
після виконання операції підстановки
(справа)
Штучний інтелект
44
Правила підстановки
конструктора формування
хромосом
У підході, що розглядається, після
додавання кожного нового вузла до де-
рева-хромосоми, одразу додаються ген
PUA до початкової послідовності генів і
ген ESS – до кінцевої.
Перша група правил містить відно-
шення підстановки генів, що відповіда-
ють частинам існуючих алгоритмів
сортування. Від значення атрибута зале-
жить кількість доданих терміналів і зна-
чення атрибутів, які змінюються після
виконання підстановки.
Детально розглянемо правило 𝜓𝜓1 =
〈𝑠𝑠1,, 〈𝑔𝑔1,1 , 𝑔𝑔1,2 〉〉.
До операцій підстановки викону-
ються операції над атрибутами g1,1. Вста-
новлюються флаги τ1 і τ2, що роблять
доступними відношення s1.
Виконання операції підстановки за
вибраним відношенням підстановки
𝛼𝛼 →𝜏𝜏1 𝐹𝐹𝐹𝐹𝐹𝐹 ∙ 𝛼𝛼 забезпечить додавання тер-
міналу FSS до початкової послідовності
генів поточного вузла і нетермінала 𝛼𝛼.
Якщо значення атрибута 𝜏𝜏2 буде дорівню-
вати true, то доступним стає відношення
𝛼𝛼 →𝜏𝜏2 𝑀𝑀𝑀𝑀 ∙ 𝐹𝐹𝐹𝐹𝐹𝐹 ∙ 𝛼𝛼 і замість одного буде
додано два термінали: ML і FSS.
Після операцій підстановки вико-
нуються операції над атрибутами g1,2. По-
точні значення деяких атрибутів можуть
змінювати цю поведінку. Якщо значення
атрибута b1 дорівнює true, то значення ат-
рибута nG збільшиться на 1, і на 2 якщо b1
дорівнює false. Далі втановлюються зна-
чення атрибутів pGU = false і b1 = true.
𝑠𝑠1 = 〈 𝛼𝛼 →𝜏𝜏1 𝐹𝐹𝑆𝑆𝑆𝑆∙𝛼𝛼,
𝛼𝛼 →𝜏𝜏2 𝑀𝑀𝑀𝑀∙𝐹𝐹𝑆𝑆𝑆𝑆∙𝛼𝛼.
〉;
𝑔𝑔1,1 = 〈==(τ1,𝑏𝑏1,true),
==(τ2,𝑏𝑏1,false).〉;
𝑔𝑔1,2 = 〈
if (b1, +(nG, nG, 1), +(nG, nG, 2)),
≔ (pGU, false),
: = (𝑏𝑏1, true).
〉
(4)
Аналогічно до правила 𝜓𝜓1 у пра-
вилі 𝜓𝜓2 = 〈𝑠𝑠2,, 〈𝑔𝑔2,1 , 𝑔𝑔2,2 〉〉 до початкової
послідовності генів додається один (FSB)
або два (𝑀𝑀𝑀𝑀 ∙ 𝐹𝐹𝐹𝐹𝐹𝐹) термінали залежно від
значення атрибутів τ1 і τ2.
𝑠𝑠2 = 〈 𝛼𝛼 →𝜏𝜏1 𝐹𝐹𝑆𝑆𝑆𝑆∙𝛼𝛼,
𝛼𝛼 →𝜏𝜏2 𝑀𝑀𝑀𝑀∙𝐹𝐹𝑆𝑆𝑆𝑆∙𝛼𝛼.
〉;
𝑔𝑔2,1 = 〈==(τ1,𝑏𝑏2,true),
==(τ2,𝑏𝑏2,false).〉;
𝑔𝑔2,2 = 〈if (b2,+(nG,nG,1),+(nG,nG,2)),
≔(pGU,false),
:=(𝑏𝑏1,true).
〉
(5)
Наступні правила містять відно-
шення підстановки генів SEI і SEEI:
𝑠𝑠3 = 〈𝛼𝛼 → 𝐹𝐹𝑆𝑆𝑆𝑆 ∙ 𝛼𝛼〉; 𝑔𝑔3,1 = 〈ε〉;
𝑔𝑔3,2 = 〈 +(nG,nG,1),
≔(pGU,false),
:=(𝑏𝑏1,false).
〉 (6)
𝑠𝑠4 = 〈𝛼𝛼 → 𝐹𝐹𝑆𝑆𝑆𝑆𝑆𝑆 ∙ 𝛼𝛼〉; 𝑔𝑔4,1 = 〈ε〉;
𝑔𝑔4,2 = 〈 +(nG,nG,1),
≔(pGU,false),
:=(𝑏𝑏2,false).
〉 (7)
Символ ε – порожньо, означає від-
сутність операцій над атрибутами до опе-
рацій підстановки.
Після виконання підстановки зна-
чення атрибута nG збільшується на 1,
pGU стає рівним false. Відповідно для
першого і другого правила виконується b1
= false або b2 = false.
Правило 𝜓𝜓5 = 〈𝑠𝑠5,, 〈𝑔𝑔5,1 , 𝑔𝑔5,2 〉〉 міс-
тить відношення підстановки гена BSF:
Якщо значення атрибута 𝜏𝜏1 іс-
тинне, доступне відношення →𝜏𝜏1 , і до по-
точного вузла буде додано ген BSF і
нетермінал 𝛼𝛼, для якого будуть продов-
жені підстановки. Якщо істинне значення
𝜏𝜏2, то →𝜏𝜏2 доступне. Буде додано два гени
MR і BSF та нетермінал 𝛼𝛼. Правило підс-
тановки буде виконуватись, якщо хоча б
одне відношення доступне.
𝑠𝑠5 = 〈 𝛼𝛼 →𝜏𝜏1 𝑆𝑆𝑆𝑆𝐹𝐹∙𝛼𝛼,
𝛼𝛼 →𝜏𝜏2 𝑀𝑀𝑀𝑀∙𝑆𝑆𝑆𝑆𝐹𝐹∙𝛼𝛼.
〉; 𝑔𝑔5,1 = 𝑔𝑔2,1;
𝑔𝑔5,2 = 𝑔𝑔2,2
(8)
Правило 𝜓𝜓6 = 〈𝑠𝑠6,, 〈𝑔𝑔6,1 , 𝑔𝑔6,2 〉〉 міс-
тить відношення підстановки для дода-
вання (під час реалізації конструктора)
гена BSB у частково сформовану хромо-
сому:
𝑠𝑠6 = 〈 𝛼𝛼 →𝜏𝜏1 𝑆𝑆𝑆𝑆𝑆𝑆∙𝛼𝛼,
𝛼𝛼 →𝜏𝜏2 𝑀𝑀𝑀𝑀∙𝑆𝑆𝑆𝑆𝑆𝑆∙𝛼𝛼.
〉; 𝑔𝑔6,1 = 𝑔𝑔1,1;
𝑔𝑔6,2 = 𝑔𝑔1,2
(9)
Наступні два правила містять від-
ношення підстановки генів розбиття P і
SIS – у процесі виконання підстановки, за
Штучний інтелект
45
якими до поточного вузла додаються два
вузли-нащадки. Виконання підстановок
завершується для поточного вузла і буде
продовжено для вузлів-нащадків.
У результаті підстановки 𝑠𝑠7 до по-
точного вузла додається ген P і два вузли-
нащадки (лівий і правий). Далі парале-
льно виконуються 2 підстановки. Для до-
даних нетерміналів будуть продовжені
підстановки відповідно у лівий і правий
вузли. Гени, що стоять зліва від нетермі-
нала 𝛼𝛼, будуть додані у початкову послі-
довність генів вузла, справа – у кінцеву
послідовність.
𝑠𝑠7 = ⟨𝛼𝛼 →𝜏𝜏1 𝑃𝑃↘𝑃𝑃𝑃𝑃𝑃𝑃∙𝛼𝛼∙𝐸𝐸𝐸𝐸𝐸𝐸
↗𝑃𝑃𝑃𝑃𝑃𝑃∙𝛼𝛼∙𝐸𝐸𝐸𝐸𝐸𝐸⟩;
𝑔𝑔7,1 = 〈 <(𝑓𝑓1,cD,MD),
>=(𝑓𝑓2,nG,MGBS),
⋀(τ1,𝑓𝑓1,𝑓𝑓2).
〉;
𝑔𝑔7,2 = 〈
+(cD, cD, 1),
: = (pGU, false),
: = (nG, 0).
〉
(10)
Правило 𝜓𝜓8 = 〈𝑠𝑠8,, 〈𝑔𝑔8,1 , 𝑔𝑔8,2 〉〉 міс-
тить відношення підстановки гена SIS:
𝑠𝑠8 = ⟨𝛼𝛼 → 𝑆𝑆𝑆𝑆𝑆𝑆↘𝑃𝑃𝑃𝑃𝑃𝑃∙𝛼𝛼∙𝐸𝐸𝐸𝐸𝐸𝐸
↗𝑃𝑃𝑃𝑃𝑃𝑃∙𝛼𝛼∙𝐸𝐸𝐸𝐸𝐸𝐸
𝜏𝜏1 ⟩,
𝑔𝑔8,1 = 𝑔𝑔7,1; 𝑔𝑔8,2 = 𝑔𝑔7,2
(11)
Правило 𝜓𝜓9 = 〈𝑠𝑠9,, 〈𝑔𝑔9,1 , 𝑔𝑔9,2 〉〉 міс-
тить відношення підстановки гена фіналь-
ного сортування FS. Даний ген
використовується для гарантованого від-
сортування поточної частини масиву сор-
тованих даних, тому в результаті
підстановки до послідовності не дода-
ються нетермінали і після не виконуються
операції над атрибутами.
Наступне правило 𝜓𝜓10 =
〈𝑠𝑠10,, 〈𝑔𝑔10,1 , 𝑔𝑔10,2 〉〉 містить відношення пі-
дстановки генів передобробки. До опера-
ції підстановки виконується операція над
атрибутом і встановлюється значення τ1.
У процесі виконання операції підстано-
вки до послідовності терміналів дода-
ється ген передобробки і нетермінал 𝛼𝛼.
Символ “|” позначає відношення «або»:
можливість виконання лише однієї із за-
значених підстановок. Потім значення
атрибута nG збільшується на 1, pGU стає
рівним false.
𝑠𝑠10 = 〈𝛼𝛼 →𝜏𝜏1 𝑄𝑄𝑃𝑃 ∙ 𝛼𝛼 | 𝑃𝑃𝑃𝑃 ∙
𝛼𝛼 | 𝑆𝑆𝑆𝑆 ∙ 𝛼𝛼 | 𝐵𝐵𝐿𝐿𝑄𝑄𝑃𝑃 ∙ 𝛼𝛼 | 𝐵𝐵𝐿𝐿𝑃𝑃𝑃𝑃 ∙
𝛼𝛼 | 𝐵𝐵𝐺𝐺𝑄𝑄𝑃𝑃 ∙ 𝛼𝛼 | 𝐵𝐵𝐺𝐺𝑃𝑃𝑃𝑃 ∙ 𝛼𝛼〉;
𝑔𝑔10,1 = 〈== (τ1, pGU, false)〉;
𝑔𝑔10,2 = 〈 +(nG,nG,1),
≔(pGU,true).〉
(12)
Розширений приклад
формування хромосоми
Розглянемо приклад покрокового
процесу формування хромосоми-дерева.
На початку встановлюються наступні по-
чаткові значення параметрів конструю-
вання і атрибутів: MD = 3, MGBS = 1, b1
= true, b2 = true, cD = 1, nG = 0, pGU = false.
Розглянемо послідовність підста-
новок для кореневого вузла хромосоми рі-
вня 1 під номером 1. Першим обирається
правило підстановки 𝜓𝜓10, додається ген
швидкої передобробки QP, встановлю-
ються значення атрибутів 𝑛𝑛𝐺𝐺 = 1; 𝑝𝑝𝐺𝐺𝑝𝑝 =
𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡;. Наступними обираються два одна-
кових правила 𝜓𝜓5. Додаються гени BSF,
встановлюються атрибути 𝑛𝑛𝐺𝐺 = 3; 𝑝𝑝𝐺𝐺𝑝𝑝 =
𝑓𝑓𝑓𝑓𝑓𝑓𝑠𝑠𝑡𝑡;. Останнім обирається правило 𝜓𝜓8,
що завершує вибір правил для поточного
вузла, додає ген SIS і встановлює зна-
чення атрибутів cD=1; pGU=false; nG=0;.
Також додає два вузли - нащадки і відпо-
відні термінали і нетермінали у їхній пос-
Рис. 2. Змінена форма після застосування правил 𝝍𝝍𝟏𝟏𝟏𝟏, 𝝍𝝍𝟓𝟓, 𝝍𝝍𝟓𝟓, 𝝍𝝍𝟖𝟖
Штучний інтелект
46
лідовності генів (рис. 2). Нерозкриті нете-
рмінали лишились у блоках 2 та 5.
Наступними виконуються підстано-
вки для вузла 2 (рис. 3). Обирається пра-
вило підстановки 𝜓𝜓14. Додається ген BLPM
та встановлюються значення атрибутів
𝑛𝑛𝑛𝑛 = 1; 𝑝𝑝𝑛𝑛𝑝𝑝 = 𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡;. Далі обираються два
правила 𝜓𝜓1. Додаються гени FSS і встанов-
люються значення атрибутів 𝑛𝑛𝑛𝑛 =
3; 𝑝𝑝𝑛𝑛𝑝𝑝 = 𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑡𝑡;.
Обирається останнє правило 𝜓𝜓7. До-
дається ген і встановлюються значення ат-
рибутів cD=2; pGU=false; nG=0;.
Додаються два вузли-нащадки під номе-
рами 3 і 4 до поточного вузла, також гени і
нетермінали.
Рис. 3. Змінена форма після застосування правил 𝝍𝝍𝟏𝟏𝟏𝟏, 𝝍𝝍𝟏𝟏, 𝝍𝝍𝟏𝟏, 𝝍𝝍𝟕𝟕 щодо форми на рис. 2
Рис. 5. Змінена форма після застосування правил 𝝍𝝍𝟏𝟏𝟏𝟏, 𝝍𝝍𝟏𝟏, 𝝍𝝍𝟐𝟐, 𝝍𝝍𝟗𝟗 щодо форми на рис. 4
Рис. 4. Змінена форма після застосування правил 𝝍𝝍𝟓𝟓, 𝝍𝝍𝟏𝟏𝟐𝟐, 𝝍𝝍𝟏𝟏, 𝝍𝝍𝟗𝟗 щодо форми на рис 3
Штучний інтелект
47
Наступним виконуються підстано-
вки для вузла 3 (рис. 4). Обирається пра-
вило підстановки 𝜓𝜓5. Додається ген BSF,
встановлюються атрибути 𝑛𝑛𝑛𝑛 = 1; 𝑝𝑝𝑛𝑛𝑝𝑝 =
𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓;. Під час виконання підстановки за
правилом 𝜓𝜓12, до послідоності генів дода-
ється ген SR, встановлюються значення ат-
рибутів 𝑛𝑛𝑛𝑛 = 2; 𝑝𝑝𝑛𝑛𝑝𝑝 = 𝑡𝑡𝑡𝑡𝑡𝑡𝑓𝑓;. Далі
обирається правило 𝜓𝜓1, додається ген FSS,
встановлюються значення атрибутів 𝑛𝑛𝑛𝑛 =
3; 𝑝𝑝𝑛𝑛𝑝𝑝 = 𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓;. Оскільки досягнута мак-
симальна глибина хромосоми-дерева, гени
розбиття стають недоступними і обира-
ється правило фінального сортування 𝜓𝜓9.
Нові вузли не створюються і формування
поточного вузла завершується.
Наступними виконуються підстано-
вки для вузла 4 (рис. 5). Обираються пра-
вила підстановки 𝜓𝜓14, 𝜓𝜓1, 𝜓𝜓2. Оскільки
досягнута максимальна глибина хромо-
соми-дерева, гени розбиття стають недо-
ступні і обирається правило фінального
сортування 𝜓𝜓9. Нові вузли не створюються
і формування поточного вузла завершу-
ється.
Виконуються підстановки для вузла
5 (рис. 6). Обираються правила підстановки
𝜓𝜓12, 𝜓𝜓6, 𝜓𝜓15, 𝜓𝜓8. Додаються два вузли-на-
щадки під номерами 6 і 7 до поточного ву-
зла, додаються гени і нетермінали.
Виконуються підстановки для вузла
6 (рис. 7). Обираються правила підстановки
𝜓𝜓5, 𝜓𝜓12, 𝜓𝜓1. Оскільки досягнута максима-
льна глибина хромосоми-дерева, гени роз-
биття стають недоступними і обирається
правило фінального сортування 𝜓𝜓9. Нові
вузли не створюються і формування поточ-
ного вузла завершується.
Виконуються підстановки для вузла
7 (рис. 8). Обираються правила підстановки
𝜓𝜓15, 𝜓𝜓2, 𝜓𝜓6. Оскільки досягнута максима-
льна глибина хромосоми-дерева, гени роз-
биття стають недоступні і обирається
правило фінального сортування 𝜓𝜓9. Нові
Рис. 6. Змінена форма після застосування правил 𝝍𝝍𝟏𝟏𝟏𝟏, 𝝍𝝍𝟔𝟔, 𝝍𝝍𝟏𝟏𝟏𝟏, 𝝍𝝍𝟖𝟖 щодо форми на рис. 5
Рис. 7. Змінена форма після застосування правил 𝝍𝝍𝟏𝟏, 𝝍𝝍𝟏𝟏𝟏𝟏, 𝝍𝝍𝟏𝟏, 𝝍𝝍𝟏𝟏 щодо форми на рис. 6
Штучний інтелект
48
вузли не створюються і формування поточ-
ного вузла завершується.
Використання хромосом
генетичним алгоритмом
Для застосування генетичного алго-
ритму необхідно сформувати початкову по-
пуляцію хромосом. Потрібне перетворення
хромосоми у текст програми і виконання со-
ртування експериментальних даних кожним
алгоритмом-індивідом популяції. Здійсню-
ється пошук певної кількості кращих алго-
ритмів. Кращим вважається алгоритм, що
виконує сортування за менший проміжок
часу. Потрібен відбір певної кількості кра-
щих хромосом і додавання їх до наступної
популяції. Далі - формування нових хромо-
сом із застосуванням механізмів схрещення
і мутацій, а також додавання нових.
Далі представлений скелет програми.
[Крок 1. Налаштування параметрів
експерименту]
[Крок 2. Генерація популяції]
[Крок 3. Генерація вхідних даних]
[Крок 4. Оцінка хромосоми]
[Крок 4.1. Декодування хромосоми в код
алгоритму сортування]
[Крок 4.1.1. Для кожного гена]
[Крок 4.1.1.1. Отримати код, що
відповідає переданому гену]
[Крок 4.1.1.2. Додати код гена до коду
алгоритму сортування]
[Крок 4.2. Побудова програми для за-
пуску згенерованого алгоритму сорту-
вання]
[Крок 4.3. Запуск програми, яка сортує
вхідні дані та вимірює час виконання]
[Крок 5. Отримання результатів оцінки]
[Крок 6. Генерація нової популяції або за-
вершення експерименту]
Приклад коду формування тексту
програми за геном QP у кроці 4.1.1.1.
std::tie(min, max) = Utilities::Find-
MinMax(arr + s, e - s + 1);
if (min == max)
{
isSorted = true;
}
if (!isSorted)
{
auto range = max - min;
auto maxIndex = e - s;
auto maxStepsQP = std::min(std::max((e -
s + 1) / 1000, 10), 100);
for (int i = s; i <= e; ++i)
{
int j = 0;
while (j++ < maxStepsQP)
{
int predictedPlace = double(arr[i] - min)
/ range * maxIndex + s;
if (i == predictedPlace || arr[i] ==
arr[predictedPlace])
{
break;
}
std::swap(arr[i], arr[predictedPlace]);
}
}
Рис. 8. Змінена форма після застосування правил 𝝍𝝍𝟏𝟏𝟏𝟏, 𝝍𝝍𝟐𝟐, 𝝍𝝍𝟔𝟔, 𝝍𝝍𝟏𝟏𝟏𝟏 щодо форми на рис. 7
Штучний інтелект
49
У тексті програми: s – індекс пер-
шого елемента сортованого підмасива; e –
індекс останнього елемента сортованого
підмасива; maxStepsQP – максимальна кі-
лькість передбачень для кожного елеме-
нта; min, max – значення найменшого і
найбільшого елементів сортованого під-
масиву; arr – сортований масив.
Експериментальні дослідження
У ході роботи було проведено багато
експериментів із різними типами і обсягами
даних за різних початкових умов і парамет-
рів завершення. Далі представлено один із
експериментів еволюційного вибору кра-
щого алгоритму сортування спецефічних
даних.
Специфікація полягає у наступному.
Експеримент проводився на даних обсягом
один мільйон елементів. Масив заповнюва-
вся випадковими числами у діапазоні від
нуля до одного мільйона, потім виконува-
лось повне сортування даних. Далі у повні-
стю відсортованому масиві вибирались N
ділянок з сумарною довжиною L. У межах
кожної ділянки випадковим чином вибира-
лись 2 індекси, і елементи за обраними ін-
дексами мінялись місцями, процес
повторювався кількість разів відповідну
довжині ділянки. Наведені експерименти
виконувались на ноутбуці із технічними ха-
рактеристиками, представленими у табл.1.
Таблиця 1.
Технічні засоби експерименту
Характеристики центрального проце-
сору
Поле Значення
Тип Intel Core i7-12650H (12th
Gen)
Кількість
ядер
10 cores (6 Performance + 4
Efficiency)
Кеш L1 864 KB
Кеш L2 9.5 MB
Кеш L3 24 MB
Характеристики оперативної пам’яті
Поле Значення
Тип DDR5-4800
Розмір мо-
дулю
8 ГБ
Кількість
модулів
2 х 8 ГБ
На рис. 9 представлені результати
експерименту. До останньої популяції до-
дано 4 загальновідомі алгоритми для порів-
няння: швидке, злиттям, вставками і
сортування вибором. Кращий алгоритм
знаходиться праворуч вгорі, нижче йдуть
усі інші алгоритми у порядку погіршення
часової ефективності.
Далі представлені п’ять кращих хро-
мосом і усі загальновідомі алгоритми, поз-
начені на графіку числами відповідно:
Рис. 9. Зміна часу сортування у різних поколіннях хромосом
0
100000
200000
300000
400000
500000
600000
0 5 10 15 20 25
Ex
ec
ut
io
n
Ti
m
e
(m
s)
Population Index
Execution Times per Population
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Штучний інтелект
50
1. SR_SIS_PUA_P_PUA_BSB_BSF_FS
_ESS_PUA_FSS_BSB_BSB_FS_ESS
_ESS_PUA_P_PUA_FSB_FS_ESS_P
UA_FS_ESS_ESS_ESS
2. SR_SIS_PUA_P_PUA_BSB_FSS_FS
_ESS_PUA_FSB_BSB_BSB_FS_ES
S_ESS_PUA_P_PUA_FSB_FS_ESS_
PUA_FS_ESS_ESS_ESS
3. SR_SIS_PUA_P_PUA_BSB_FSS_FS
_ESS_PUA_FSS_BSB_BSB_FS_ESS
_ESS_PUA_P_PUA_FSB_FS_ESS_P
UA_FS_ESS_ESS_ESS
4. SR_SIS_PUA_P_PUA_BSB_FSS_FS
_ESS_PUA_FSS_BSB_BSB_FS_ESS
_ESS_PUA_P_PUA_FSB_FS_ESS_P
UA_FS_ESS_ESS_ESS
5. QuickSort
…
14. HeapSort
…
18. MergeSort
…
20. InsertionSort
На графіку надано час сортування
різних алгоритмів. Перші чотири алгори-
тми (позиції 1–4) сформовані генетичним
алгоритмом на основі підходу, представле-
ного в даній роботі. Час сортування порів-
нюється з класичними алгоритмами
сортування, які розмістились на позиціях 5,
14, 18 та 20.
Результати демонструють, що конс-
труйовані алгоритми, представлені хромо-
сомами, здатні перевершити традиційні за
швидкістю виконання на тестових наборах
даних. Підтверджують доцільність викори-
стання нових алгоритмів у задачах, де кри-
тичним є час обробки великих масивів
інформації.
Висновки
У разі структурної адаптації алгори-
тмів досягається можливість гнучко пере-
будовувати їхню внутрішню структуру
залежно від властивостей вхідних даних,
цільових вимог чи обмежень обчислюваль-
ного середовища. Такий підхід дозволяє по-
єднувати фундаментальні алгоритмічні
фрагменти у нові структури, що зберігають
коректність і водночас покращують часові
та ресурсні характеристики.
Розроблено підхід до формування
хромосом, які відповідають алгоритмам
сортування, сформованим із частин класи-
чних алгоритмів сортування (таких як
Bubble Sort, Quick Sort, Merge Sort) і де-
яких передобробок у вигляді структур,
придатних для генетичних та еволюційних
обчислень.
Конструктивно-продукційне моде-
лювання продемонструвало ефективність у
формуванні хромосом, що забезпечує мож-
ливість структурної адаптації алгоритмів
для специфічних вхідних даних.
Запропонована модель забезпечує
гнучкість у генерації хромосом з урахуван-
ням різних критеріїв оптимізації, таких як
час виконання. Структура кодованого де-
рева забезпечує уніфікований підхід до
процесу генерації послідовності генів для
кожного вузла за допомогою рекурсії. Та-
ким чином уможливлюється генерування
хромосом будь-якої довжини.
Проведені експерименти підтвер-
дили, що структуровані хромосоми, сфор-
мовані за допомогою продукційних правил,
демонструють вищу ефективність у задачах
еволюційного пошуку порівняно з випадко-
вою ініціалізацією.
Отримані результати можуть бути
використані для автоматизованого синтезу
алгоритмів, оптимізації програмного коду
та побудови інтелектуальних систем, що
навчаються.
Література
1. C. A. R. Hoare. Quicksort. The Computer
Journal. – Vol. 5, No. 1. – pp. 10–16. – 1962.
2. D. E. Knuth. Sorting by Exchanging. The Art
of Computer Programming. – Vol. 3: Sorting
and Searching. – 1st ed. – Addison-Wesley. –
pp. 110–111. – 1973.
3. N. Auger, V. Jugé, C. Nicaud, C. Pivoteau. On
the worst-case complexity of Timsort. 26th
Annual European Symposium on Algorithms
(ESA 2018). – LIPIcs, Vol. 112. – pp. 4:1–13.
– 2018. – Available:
https://arxiv.org/abs/1805.08612
4. D. R. Musser. Introspective Sorting and
Selection Algorithms. Software: Practice and
Experience. – Vol. 27, No. 8. – pp. 983–993. –
1997.
5. T. B. Martyniuk, B. I. Krukivskyi. Peculiarities
of the parallel sorting algorithm with rank
Штучний інтелект
51
formation. Cybernetics and Systems Analysis.
– Vol. 58, No. 1. – pp. 24–28. – 2022. – DOI:
https://doi.org/10.1007/s10559-022-00431-8.
6. M. Dietzfelbinger. How Good Is Multi-Pivot
Quicksort?. ArXiv, Cornell University. – 2015.
7. A. S. Mohammed, Ş. E. Amrahov, F. V.
Çelebi. Bidirectional Conditional Insertion
Sort algorithm: An efficient progress on the
classical insertion sort. Future Generation
Computer Systems. – Vol. 71. – pp. 102–112.
– June 2017.
8. V. Jugé. Adaptive shivers sort: an alternative
sorting algorithm. ACM Transactions on
Algorithms. – Vol. 20, No. 4. – pp. 1–55. –
August 2024.
9. O. Appiah, E. M. Martey. Magnetic Bubble
Sort Algorithm. International Journal of
Computer Applications. – Vol. 122, No. 21. –
pp. 24–28. – 2015. – DOI: 10.5120/21850-
5168
10. A. Alotaibi, A. Almutairi, H. Kurdi. Onebyone
(obo): A fast sorting algorithm. Procedia
Computer Science. – Vol. 175. – pp. 270–277.
– 2020.
11. F. M. Isa, W. N. M. Ariffin, M. S. Jusoh, E. P.
Putri. A Review of Genetic Algorithm:
Operations and Applications. Journal of
Advanced Research in Applied Sciences and
Engineering Technology. – 2020. – DOI:
10.37934/araset.40.1.134
12. Z. Michalewicz. Genetic Algorithms + Data
Structures = Evolution Programs. – 3rd ed. –
Springer. – 1996.
13. В.І. Шинкаренко, В.М. Ільман. Конструкти-
вно-продукційні структури та їх граматичні
інтерпретації. I. Узагальнена формальна
конструктивно-продукційна структура . Кі-
бернетика і системний аналіз. – 2014. – Т.
50, № 5. – С. 8–16.
14. В.І. Шинкаренко, А.Ю. Дорошенко, О.А.
Яценко, В.В. Разносілін, К.К. Галанін, Дво-
компонентні алгоритми сортування, Про-
блеми програмування, 2022, № 3-4. С. 32-
41. doi: 10.15407/pp2022.03-04.032.
15. В.І. Шинкаренко, О.В. Макаров, До-
слідження ефективності деяких детерміно-
ваних методів передобробки сортування
даних, Проблеми програмування, 2023, №
4, С. 3-14. doi: 10.15407/pp2023.04.003.
16. V. I. Shynkarenko, O. V. Makarov. Structural
Adaptation of Sorting Algorithms Based on
Constructive Fragments. CEUR Workshop
Proceedings. – Vol. 3806. – pp. 16–29. – 2024.
References
1. C. A. R. Hoare. Quicksort. The Computer
Journal. – Vol. 5, No. 1. – pp. 10–16. – 1962.
2. D. E. Knuth. Sorting by Exchanging. The Art
of Computer Programming. – Vol. 3: Sorting
and Searching. – 1st ed. – Addison-Wesley. –
pp. 110–111. – 1973.
3. N. Auger, V. Jugé, C. Nicaud, C. Pivoteau. On
the worst-case complexity of Timsort. 26th
Annual European Symposium on Algorithms
(ESA 2018). – LIPIcs, Vol. 112. – pp. 4:1–13.
– 2018. – Available:
https://arxiv.org/abs/1805.08612
4. D. R. Musser. Introspective Sorting and
Selection Algorithms. Software: Practice and
Experience. – Vol. 27, No. 8. – pp. 983–993. –
1997.
5. T. B. Martyniuk, B. I. Krukivskyi. Peculiarities
of the parallel sorting algorithm with rank
formation. Cybernetics and Systems Analysis.
– Vol. 58, No. 1. – pp. 24–28. – 2022. – DOI:
https://doi.org/10.1007/s10559-022-00431-8
6. M. Dietzfelbinger. How Good Is Multi-Pivot
Quicksort?. ArXiv, Cornell University. – 2015.
7. A. S. Mohammed, Ş. E. Amrahov, F. V.
Çelebi. Bidirectional Conditional Insertion
Sort algorithm: An efficient progress on the
classical insertion sort. Future Generation
Computer Systems. – Vol. 71. – pp. 102–112.
– June 2017.
8. V. Jugé. Adaptive shivers sort: an alternative
sorting algorithm. ACM Transactions on
Algorithms. – Vol. 20, No. 4. – pp. 1–55. –
August 2024.
9. O. Appiah, E. M. Martey. Magnetic Bubble
Sort Algorithm. International Journal of
Computer Applications. – Vol. 122, No. 21. –
pp. 24–28. – 2015. – DOI: 10.5120/21850-
5168
10. A. Alotaibi, A. Almutairi, H. Kurdi. Onebyone
(obo): A fast sorting algorithm. Procedia
Computer Science. – Vol. 175. – pp. 270–277.
– 2020.
11. F. M. Isa, W. N. M. Ariffin, M. S. Jusoh, E. P.
Putri. A Review of Genetic Algorithm:
Operations and Applications. Journal of
Advanced Research in Applied Sciences and
Engineering Technology. – 2020. – DOI:
10.37934/araset.40.1.134
12. Z. Michalewicz. Genetic Algorithms + Data
Structures = Evolution Programs. – 3rd ed. –
Springer. – 1996.
13. V. I. Shynkarenko, V. M. Ilman. Constructive-
Synthesizing Structures and Their
Grammatical Interpretations. I. Generalized
Formal Constructive-Synthesizing Structure.
Штучний інтелект
52
Cybernetics and Systems Analysis. – Vol. 50,
No. 5. – pp. 8–16.
14. V. I. Shinkarenko, A. Yu. Doroshenko, O. A.
Yatsenko, V. V. Raznosilin, K. K. Galanin.
Bicomponent sorting algorithms. Problems of
Programming. – 2022. – No. 3–4. – pp. 32–41.
– DOI: 10.15407/pp2022.03-04.032
15. V. I. Shinkarenko, O. V. Makarov. Study of the
effectiveness of some deterministic prepro-
cessing methods of data sorting. Problems of
Programming. – 2023. – No. 4. – pp. 3–14. –
DOI: 10.15407/pp2023.04.003
16. V. I. Shynkarenko, O. V. Makarov. Structural
Adaptation of Sorting Algorithms Based on
Constructive Fragments. CEUR Workshop
Proceedings. – Vol. 3806. – pp. 16–29. – 2024.
Одержано: 12.10.2025
Внутрішня рецензія отримана: 18.10.2025
Зовнішня рецензія отримана: 19.10.2025
Про авторів:
Шинкаренко Віктор Іванович,
доктор технічних наук, професор,
https://orcid.org/0000-0001-8738-7225
E-mail: shinkarenko_vi@ua.fm
Макаров Олексій Вікторович,
аспірант,
https://orcid.org/0009-0003-0921-155X
E-mail: makarovov@hotmail.com
Місце роботи авторів:
Український державний університет
науки і технологій,
49010, Україна, Дніпро,
вул. Академіка Лазаряна, 2.
E-mail: office@ust.edu.ua
|