graduate student, Research Engineer; Artificial Intelligence Center
аспирант кафедры программной инженерии, инженер-исследователь Центра искусственного интеллекта
Dr. Sc., Professor, Department of Systems Analysis and Operations Research
доктор технических наук, профессор; кафедра системного анализа и исследования операций
In this work, a novel method for self-tuning genetic programming (GP) algorithms is presented, based on the ideas of the Success History based Parameter Adaptation (SHA) method, originally developed for the Differential Evolution (DE) algorithm. The main idea of the method is to perform a dynamic analysis of the history of successful solutions to adapt the algorithm's parameters during the search process. To implement this concept, the operation scheme of classical GP was modified to mimic the DE scheme, allowing the integration of the success history mechanism into GP. The resulting algorithm, denoted as SHAGP (Success-History based Adaptive Genetic Programming), demonstrates new capabilities for parameter adaptation, such as the adjustment of crossover and mutation probabilities. The work also includes a detailed review of existing self-tuning methods for GP algorithms, which allowed for the identification of their key advantages and limitations and the application of this knowledge in the development of SHAGP. Additionally, new crossover operators are proposed that enable dynamic adjustment of the crossover probability, account for the selective pressure at the current stage, and implement a multi-parent approach. This modification allows for more flexible control over the process of genotype recombination, thereby enhancing the algorithm's adaptability to the problem at hand. To adjust the probabilities of applying various operators (selection, crossover, mutation), self-configuring evolutionary algorithm methods are employed, in particular, the Self-Configuring Evolutionary Algorithm and the Population-Level Dynamic Probabilities Evolutionary Algorithm. Within the framework of this work, two variants of the algorithm were implemented – SelfCSHAGP and PDPSHAGP. The efficiency of the proposed algorithms was tested on problem sets from the Feynman Symbolic Regression Database. Each algorithm was run multiple times on each problem to obtain a reliable statistical sample, and the results were compared using the Mann–Whitney statistical test. The experimental data showed that the proposed algorithms achieve a higher reliability metric compared to existing GP self-tuning methods, with the PDPSHAGP method demonstrating the best efficiency in more than 90 % of the cases. Such a universal self-tuning mechanism can find applications in a wide range of fields, such as automated machine learning, big data processing, engineering design, and medicine, as well as in space applications – for example, in the design of navigation systems for spacecraft and the development of control systems for aerial vehicles. In these areas, the high reliability of algorithms and their ability to find optimal solutions in complex multidimensional spaces are critically important.
В данной работе представлен новый метод самонастройки алгоритмов генетического программирования (ГП), который базируется на идеях метода Success History based Parameter Adaptation (SHA), изначально разработанного для алгоритма дифференциальной эволюции (ДЭ). Основная идея метода заключается в динамическом анализе истории успешных решений для адаптации параметров алгоритма в процессе поиска решения. Для реализации этой концепции схема работы классического ГП была модифицирована таким образом, чтобы имитировать схему ДЭ, что позволило интегрировать механизм SHA в ГП. Полученный алгоритм, обозначенный как SHAGP (Success-History based Adaptive Genetic Programming), демонстрирует новые возможности для адаптации параметров, таких как вероятность скрещивания и мутации. В работе также проведён обзор существующих методов самонастройки алгоритмов ГП, что позволило выявить их ключевые преимущества и ограничения и использовать эти знания при разработке SHAGP. Дополнительно предложены новые операторы скрещивания, позволяющие динамически настраивать вероятность скрещивания, учитывать селективное давление на данном этапе, а также реализующие многородительское скрещивание. Такая модификация позволяет более гибко управлять процессом рекомбинации генотипов, улучшая адаптивность алгоритма к решаемой задаче. Для настройки вероятностей применения различных операторов (селекции, скрещивания, мутации) используются методы самоконфигурирования эволюционных алгоритмов, в частности, Self-Configuring Evolutionary Algorithm и Population-Level Dynamic Probabilities Evolutionary Algorithm. В рамках работы было реализовано два варианта алгоритма – SelfCSHAGP и PDPSHAGP. Эффективность предложенных алгоритмов была проверена на наборах задач из Feynman Symbolic Regression Database. Каждый алгоритм запускался многократно на каждой задаче для получения достоверной статистической выборки, а результаты сравнивались с использованием статистического критерия Манна – Уитни. Экспериментальные данные показали, что предложенные алгоритмы достигают более высокого показателя надёжности по сравнению с существующими методами самонастройки ГП, причём метод PDPSHAGP демонстрирует наилучшую эффективность более чем в 90 % случаев. Такой универсальный механизм самонастройки может найти применение в широком наборе областей, таких как автоматизация машинного обучения, обработка больших данных, инженерный дизайн, медицина, а также в космических приложениях, например, при проектировании навигационных систем для космических аппаратов и разработке систем управления летательными аппаратами. В этих сферах критически важны высокая надёжность алгоритмов и их способность находить оптимальные решения в сложных многомерных пространствах.