Browsing by Author "Makarov, Oleksii"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Structural Adaptation of Sorting Algorithms Based on Constructive Fragments
    (CEUR-WS Team, Aachen, Germany, 2024) Shynkarenko, Viktor I.; Makarov, Oleksii
    ENG: Modern information technologies are based on processing large volumes of data. At the same time, the task of developing and applying effective algorithms for data processing, in particular sorting, remains relevant. Constructive-synthesizing modeling 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 caused by a different number of elementary sorting operations, which leads to the use of chromosomes of different lengths. To solve the problem, a representation of the chromosome in the form of a binary tree is proposed. To form an algorithm that is guaranteed to sort the array, all leaf nodes include the final sorting gene at the end of the initial sequence of genes. This gene is decoded by calling the existing sorting algorithm, which is guaranteed to perform the sorting. Mechanisms of coding and decoding of the sorting algorithm from chromosome have been implemented. Linearization is performed for decoding and formation of the appropriate sorting algorithm: formation of a textual representation using a depth-first tree traversal algorithm. The fitness function is defined as the median sorting time of randomly generated sorting arrays (the same arrays for all chromosomes) in some stable environment, taking into account certain features of these arrays. The use of other fitness functions related to the number of calculations, comparisons or permutations is foreseen. The developed software should be applied in adapting sorting algorithms to stable input data streams and usage environments. An experiment was performed to verify the ability of the developed method and the corresponding software to form time-efficient sorting algorithms in different hardware and software environments. In the performed experiments, one component of the hardware and software environment was varied, namely the features of the data to be sorted.