Constructive-synthesizing modeling of the genetic algorithm chromosomes with encoded sorting algorithms

V.I. Shinkarenko, O.V. Makarov

Abstract


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

 


Keywords


constructive-synthesizing modeling; sorting algorithm; time efficiency; software; information tech nology; genetic algorithm

References


C. A. R. Hoare. Quicksort. The Computer Journal. – Vol. 5, No. 1. –pp. 10–16.– 962.

D. E. Knuth. Sorting by Exchanging. The Art of Computer Programming. – Vol. 3: Sorting and Searching. – 1st ed. – Addison Wesley. pp. 110–111. – 1973.

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.

D. R. Musser. Introspective Sorting and Selection Algorithms. Software: Practice and Experience. – Vol. 27, No. 8. – pp. 983–993. 1997.

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.

M. Dietzfelbinger. How Good Is Multi-Pivot Quicksort?. ArXiv, Cornell University. – 2015.

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.

V. Jugé. Adaptive shivers sort: an alternative sorting algorithm. ACM Transactions on Algorithms. – Vol. 20, No. 4. – pp. 1–55. August 2024.

O. Appiah, E. M. Martey. Magnetic Bubble Sort Algorithm. International Journal of Computer Applications. – Vol. 122, No. 21. pp. 24–28.– 2015.

A. Alotaibi, A. Almutairi, H. Kurdi. Onebyone (obo): A fast sorting algorithm. Procedia Computer Science. – Vol. 175. – pp. 270–277. – 2020.

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.

Z. Michalewicz. Genetic Algorithms + Data Structures = Evolution Programs. – 3rd ed. Springer. – 1996.

V. I. Shynkarenko, V. M. Ilman. Constructive Synthesizing Structures and Their Grammatical Interpretations. I. Generalized Formal Constructive-Synthesizing Structure. Cybernetics and Systems Analysis. – Vol. 50, No. 5. – pp. 8–16.

V. I. Shinkarenko, A. Yu. Doroshenko, O. A. Yatsenko, V. V. Raznosilin, K. K. Galanin. Bicomponent sorting algorithms. Problems in Programming. – 2022. – No. 3–4.– pp. 32–41.

V. I. Shinkarenko, O. V. Makarov. Study of the effectiveness of some deterministic preprocessing methods of data sorting. Problems in Programming. – 2023. – No. 4.– pp. 3–14.

V. I. Shynkarenko, O. V. Makarov. Structural Adaptation of Sorting Algorithms Based on Constructive Fragments. CEUR Workshop Proceedings. – Vol. 3806. – pp. 16–29.– 2024.


Refbacks

  • There are currently no refbacks.