Формування алгоритмів сортування засобами конструктивно-продукційного моделювання та генетичного алгоритму

UKR: Розглянуто підхід до автоматизованого синтезу алгоритмів сортування на основі конструктивно‑продукційного моделювання. Описано конструктивну модель хромосоми деревовидної структури, яка кодує алгоритм сортування у вигляді ієрархічної композиції алгоритмічних фрагментів і допоміжних операцій. Представлено систему з трьох взаємопов’язаних конструкторів: конструктора формування хромосоми‑дерева, конструктора‑трансформера для перетворення деревоподібної хромосоми у лінійну послідовність генів та конструктора‑ трансформера, що забезпечує генерацію програмного коду алгоритму сортування мовою програмування. Показано, що використання чотирьох етапів конструктивно‑продукційного моделювання – спеціалізації, інтерпретації, конкретизації та реалізації – дозволяє формалізувати процес переходу від абстрактного опису алгоритму до його виконуваної програмної реалізації. Застосування генетичного алгоритму забезпечує еволюційний відбір та оптимізацію алгоритмів сортування за заданими критеріями якості з урахуванням властивостей вхідних даних і обмежень обчислювального середовища. Запропонований підхід створює умови для структурної адаптації алгоритмів, поєднання базових алгоритмічних примітивів у нові коректні композиції та розширення простору пошуку ефективних алгоритмічних рішень. Отримані результати підтверджують доцільність використання конструктивно‑продукційного моделювання як основи для автоматизованого синтезу та оптимізації алгоритмів сортування.

ENG: An approach to automated synthesis of sorting algorithms based on constructive-synthesizing modeling is considered. A constructive model of a chromosome with a tree-like structure is described, which encodes the sorting algorithm in the form of a hierarchical composition of algorithmic fragments and auxiliary operations. A system of three interconnected constructors is presented: a constructor for forming a chromosome-tree, a constructor-transformer for transforming a tree-like chromosome into a linear sequence of genes, and a constructor-transformer that provides the generation of the sorting algorithm program code written in a programming language. It is shown that the use of four stages of constructive-synthesizing modeling – specialization, interpretation, concretization, and implementation – allows formalization of transition from an abstract description of the algorithm to its executable program implementation process. The use of a genetic algorithm provides evolutionary selection and optimization of sorting algorithms according to specified quality criteria, considering the properties of the input data and the limitations of the computing environment. The proposed approach creates conditions for structural adaptation of algorithms, combination of basic algorithmic primitives into new correct compositions and expansion of the search space for effective algorithmic solutions. The obtained results confirm the feasibility of using constructive-synthesizing modeling as a basis for automated synthesis and optimization of sorting algorithms.