SORTING ALGORITHMS FORMATION BY MEANS OF CONSTRUCTIVE- SYNTHESIZING MODELING AND GENETIC ALGORITHM

Abstract

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.