В статье представлена процедура динамической модификации схемы бинарного кодирования в генетическом алгоритме (ГА), обеспечивающая адаптивную коррекцию области поиска в процессе работы алгоритма. В предложенной процедуре шаг дискретизации каждой координаты изменяется от поколения к поколению в зависимости от текущих границ областей с качественными решениями и плотности распределения индивидов в них. Для каждого такого диапазона рассчитывается число бит бинарной строки, представляющей решения в алгоритме, на основе количества кодируемых точек, после чего пересчитывается шаг дискретизации области поиска. При этом схема кодирования перестраивается таким образом, чтобы обеспечить корректность выполнения генетических операторов при наличии разрывов в области поиска, сохранить постоянную мощность множества перебираемых решений на каждом поколении, а также повысить точность найденных решений за счет динамически изменяющегося шага дискретизации. Экспериментальные результаты на многомодальных тестовых функциях, таких как Растригина и Стыблински-Танга, показали, что предложенная модификация ГА последовательно корректирует область поиска в ходе эволюции, концентрируя найденные решения вокруг глобальных экстремумов. В случае функции Растригина изначально разрозненные диапазоны постепенно фокусируются на области с максимальными значениями. Для функции Стыблински-Танга из заведомо неверного начальной области алгоритм смещает поиск к одному из глобальных оптимумов.
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. Мясников А.С. Островной генетический алгоритм с динамическим распределением вероятностей выбора генетических операторов. Наука и образование: научное издание МГТУ им. Н.Э. Баумана. 2010;(1). URL: https://www.elibrary.ru/download/elibrary_13062781_75581185.pdf
4. Звонков В.Б., Попов А.М. Сравнительное исследование классических методов оптимизации и генетических алгоритмов. Вестник Сибирского государственного аэрокосмического университета им. академика М.Ф. Решетнева. 2013;(4):23–27.
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. Нейский И.М. Классификация и сравнение методов кластеризации. В сборнике: Интеллектуальные технологии и системы: сборник учебно‑методических работ и статей аспирантов и студентов: Выпуск 8. Москва: НОК «CLAIM»; 2006. С. 130–142.
10. Дугушкина Н.В. Обзор популярных методов кластеризации в машинном обучении. Наукосфера. 2020;(7):112–118.
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
Малашин Иван Павлович
Scopus | ORCID |
Московский государственный технический университет имени Н.Э. Баумана
Москва, Российская Федерация
