Эволюции эвристик для синтеза селекции в генетическом алгоритме
Автор: Кораблева А.А., Становов В.В.
Журнал: Сибирский аэрокосмический журнал @vestnik-sibsau
Рубрика: Информатика, вычислительная техника и управление
Статья в выпуске: 1 т.27, 2026 года.
Бесплатный доступ
Предлагается метод автоматического проектирования операторов селекции для генетического алгоритма, основанный на подходе Evolution of Heuristics (EoH), который объединяет возможности больших языковых моделей (LLM) и эволюционного поиска. Проектирование селекции проводилось на трех задачах псевдобулевой оптимизации, а тестирование на 17 функциях из набора IOHprofiler. Проводились два эксперимента с явным знанием о типе решаемой задачи и без него. В качестве языковой модели использовалась DeepSeek-Coder-V2, которая была локально развернута с помощью фреймворка Ollama. Качество спроектированных эвристик определялось на основании сравнения с результатами стандартной ранговой селекции. Проведено сравнение качества полученных решений с классическими схемами селекции (турнирной, пропорциональной, ранговой), а также с методом FunSearch, ранее применявшимся для генерации новых реализаций ранговой селекции. Сравнение различных эвристик проводилось по множеству запусков на каждой из 17 задач с помощью непараметрического статистического теста Манна – Уитни. Было показано, что автоматически спроектированные эвристики обладают уникальными свойствами, причем отсутствие информации о типе и структуре решаемой задачи привело к большему разнообразию сгенерированных решений. А именно в одном из запусков спроектированный код без информации о типе задачи выбирает особей, чья приспособленность отличается от максимальной менее чем на половину расстояния от максимальной приспособленности до медианной. Иными словами, это вариант турнирной селекции с адаптивным размером турнира, основанным на распределении качества. Наличие информации о типе решаемой задачи приводило к тому, что языковая модель генерировала типовые известные решения, в частности варианты простой турнирной селекции. Предложенный подход может быть применен и для других задач автоматического проектирования алгоритмов целиком или в виде компонентов алгоритмов.
EoH, генетический алгоритм, селекция, FunSearch, LLM, IOHprofiler, гиперэвристики, автоматическое проектирование алгоритмов
Короткий адрес: https://sciup.org/148333105
IDR: 148333105 | УДК: 519.87 | DOI: 10.31772/2712-8970-2026-27-1-21-32
Evolution of heuristics for selection synthesis in a genetic algorithm
A method for the automatic design of selection operators for a genetic algorithm is proposed, based on the Evolution of Heuristics (EoH) approach, which integrates the capabilities of Large Language Models (LLMs) and evolutionary search. The design of selection operators was carried out on three pseudo-Boolean optimization problems, and testing was performed on 17 functions from the IOHprofiler benchmark set. Two experimental setups were considered with and without explicit knowledge of the type of problem being solved. The language model used was DeepSeek-Coder-V2, which was deployed locally using the Ollama framework. The quality of the designed heuristics was determined based on the comparison with the results of standard rank selection. The quality of the obtained solutions is compared with classical selection schemes (tournament, proportional, and rank-based), as well as with the FunSearch method, previously used to generate new implementations of rank-based selection. A comparison of various heuristics was carried out for multiple runs on each of the 17 tasks using the nonparametric Mann-Whitney statistical test. It has been shown that automatically designed heuristics have unique properties, and the lack of information about the type and structure of the problem being solved has led to a greater variety of generated solutions. Namely, in one of the launches, without information about the type of task, the designed code selects individuals whose fitness differs from the maximum by less than half the distance from the maximum fitness to the median. In other words, it is a variant of tournament selection with an adaptive tournament size based on the distribution of quality. The availability of information about the type of problem being solved led to the fact that the language model generated typical known solutions, in particular, variants of simple tournament selection. The proposed approach can be applied to other tasks of automatic design of algorithms as a whole or components of algorithms.
