A procedure for dynamic modification of binary encoding scheme in genetic algorithms

This paper presents a procedure for dynamically modifying the binary encoding scheme in a genetic algorithm (GA), enabling adaptive adjustment of the search space during the algorithm’s execution. In the proposed approach, the discretization step for each coordinate is updated from generation to generation based on the current boundaries of regions containing high-quality solutions and the density of individuals within them. For each such region, the number of bits in the binary string representing solutions is determined according to the number of encoded points, after which the discretization step is recalculated. The encoding scheme is restructured in a way that ensures the correctness of genetic operators in the presence of discontinuities in the search space, preserves the fixed cardinality of the solution set at each generation, and increases the precision of the solutions due to the dynamic adjustment of the discretization step. Experimental results on multimodal test functions such as Rastrigin and Styblinski–Tang demonstrate that the proposed GA modification progressively refines the search area during evolution, concentrating solutions around the global extrema. For the Rastrigin function, initially fragmented regions gradually focus around the global maximum. In the Styblinski–Tang case, the algorithm shifts the search from an intentionally incorrect initial area toward one of the global optima.

1. Mirjalili S. Genetic Algorithm. In: Evolutionary Algorithms and Neural Networks: Theory and Applications. Cham: Springer; 2018. P. 43–55. https://doi.org/10.1007/978-3-319-93025-1_4

2. Katoch S., Chauhan S.S., Kumar V. A Review on Genetic Algorithm: Past, Present, and Future. Multimedia Tools and Applications. 2021;80:8091–8126. https://doi.org/10.1007/s11042-020-10139-6

3. Myasnikov A.S. Ostrovnoi geneticheskii algoritm s dinamicheskim raspredeleniem veroyatnostei vybora geneticheskikh operatorov. Nauka i obrazovanie: nauchnoe izdanie MGTU im. N.E. Baumana. 2010;(1). (In Russ.). URL: https://www.elibrary.ru/download/elibrary_13062781_75581185.pdf

4. Zvonkov V.B., Popov A.M. Comparative Investigation of Classical Optimization Methods and Genetic Algorithms. Vestnik of SibGAU. 2013;(4):23–27. (In Russ.).

5. Maaranen H., Miettinen K., Penttinen A. On Initial Populations of a Genetic Algorithm for Continuous Optimization Problems. Journal of Global Optimization. 2007;37(3):405–436. https://doi.org/10.1007/s10898-006-9056-6

6. Yang J., Soh Ch.K. Structural Optimization by Genetic Algorithms with Tournament Selection. Journal of Computing in Civil Engineering. 1997;11(3):195–200. https://doi.org/10.1061/(ASCE)0887-3801(1997)11:3(195)

7. Shukla A., Pandey H.M., Mehrotra D. Comparative Review of Selection Techniques in Genetic Algorithm. In: 2015 International Conference on Futuristic Trends on Computational Analysis and Knowledge Management (ABLAZE 2015), 25–27 February 2015, Greater Noida, India. IEEE; 2015. P. 515–519. https://doi.org/10.1109/ABLAZE.2015.7154916

8. Kumar A. Encoding Schemes in Genetic Algorithm. International Journal of Advanced Research in IT and Engineering. 2013;2(3):1–7.

9. Neiskii I.M. Klassifikatsiya i sravnenie metodov klasterizatsii. In: Intellektual'nye tekhnologii i sistemy: sbornik uchebno‑metodicheskikh rabot i statei aspirantov i studentov: Vypusk 8. Moscow: NOK "CLAIM"; 2006. P. 130–142. (In Russ.).

10. Dugushkina N.V. Overview of Popular Clustering Methods in Machine Learning. Naukosfera. 2020;(7):112–118. (In Russ.).

11. Bacha S.Z.A., Benatchba K., Tayeb F.B.-S. Adaptive Search Space to Generate a Per-Instance Genetic Algorithm for the Permutation Flow Shop Problem. Applied Soft Computing. 2022;124. https://doi.org/10.1016/j.asoc.2022.109079

12. Omeradzic A., Beyer H.-G. Self-Adaptation of Multi-Recombinant Evolution Strategies on the Highly Multimodal Rastrigin Function. IEEE Transactions on Evolutionary Computation. 2024. https://doi.org/10.1109/TEVC.2024.3400857

13. Ustun D., Erkan U., Toktas A., Lai Q., Yang L. 2D Hyperchaotic Styblinski-Tang Map for Image Encryption and Its Hardware Implementation. Multimedia Tools and Applications. 2024;83:34759–34772. https://doi.org/10.1007/s11042-023-17054-6