Генетическое программирование: от теории к практике

В статье собран небольшой теоретический материал и несколько практических кейсов применения генетического программирования для символьной регрессии (и не только) на простых, наглядных задачах. Надеюсь, это поможет начинающим исследователям и практикам быстрее разобраться в теме или просто будет познавательно. Все эксперименты из статьи доступны по ссылке на Google Colab.

Содержание

• Введение

• Немного теории

  • Кодирование решений

  • Функция пригодности

  • Цикл работы

• Переходим к практике

  • Задача 1. Выражение косинуса через синус

  • Задача 2. Аппроксимация синуса

  • Задача 3. Символьная регрессия расхода топлива автомобиля

  • Не только символьная регрессия: оптимизация нейросетей

• Заключение

Введение

Машинное обучение за последние 70 лет проделало большой путь: от элементарного перцептрона Розенблатта и линейных моделей вроде логистической регрессии до трансформеров и архитектур наподобие YOLO.

Примерно с 2010-х стало популярным условное разделение обучения на «классическое» и «глубокое». В первом случае чаще выполняют ручной инжиниринг признаков и обучают сравнительно компактные модели (например, в sklearn или CatBoost пакетах), а во втором случае признаки автоматически извлекаются глубокими нейронными сетями, а обучение обычно выполняется во фреймворках вроде PyTorch.

Но сегодня предлагаю отложить хайп в сторону и поговорить об эффективных классических подходах. Есть целый класс методов, которые, в отличие от больших нейросетей, дают интерпретируемые, то есть понятные человеку, решения. В частности, сюда относятся нечеткая логика, деревья решений и символьная регрессия.

Нечеткая логика формирует понятные человеку правила, но для их корректной интерпретации нужно разбираться в функциях принадлежности и других деталях. Дерево решений легко читать, пока оно одно. Но как только нужна точность, одного дерева обычно мало, и в ход идут случайный лес или градиентный бустинг. С ростом числа деревьев растет и сложность, и структура превращается в черный ящик.

Хорошим вариантом в данном случае является символьная регрессия — класс методов, который, в отличие от традиционных регрессионных подходов, не оптимизирует параметры заранее заданной структуры модели, а выполняет поиск в пространстве математических выражений (формул), наилучшим образом описывающих данные. При этом формулы часто оказываются выразительнее деревьев.

Немного теории

Если символьная регрессия ищет решение в пространстве математических выражений, то генетическое программирование (ГП) — один из подходов, позволяющих организовать этот поиск. Более формально ГП — это алгоритм оптимизации, в котором программы оптимизируются через имитацию отбора, скрещивания и мутаций.

Кодирование решений

На практике решение чаще всего представляют в виде дерева. Узлы внутри дерева — функции или операторы, листья — входные значения. В частном случае, если операции математические, а листья — переменные и константы, то такое дерево кодирует математическое выражение (формулу). Вычисляется такое дерево снизу вверх: сначала подставляются значения в листья, затем результаты поднимаются к родительским узлам, где применяются соответствующие операции. Так шаг за шагом доходят до корня — там и получается итоговый результат.

В этом контексте дерево — это генотип (genotype): внутреннее представление решения, с которым работает алгоритм и к которому применяются генетические операторы, а фенотип (phenotype) — внешнее представление решения, которое этот генотип кодирует и которое оценивает функция пригодности.

Здесь удобно провести аналогию с биологией: генотип — это ДНК человека, а фенотип — то, как он выглядит и ведет себя (цвет глаз, рост и т.д.).

Функция пригодности

Как уже понятно из контекста, функция пригодности — это по сути целевая функция оптимизации: численно измеримый критерий качества кандидатного решения.

Цикл работы

Вся механика ГП — это повторяющийся цикл, где популяция постепенно «эволюционирует» путем применения генетических операторов отбора, скрещивания и мутации индивидов.

Сначала формируется начальная популяция (population) деревьев. Затем на этапе оценки (evaluation) для каждой особи вычисляется значение функции пригодности (fitness).

Далее выполняется отбор (selection), в ходе которого выбираются родители (обычно два). Затем к выбранным родителям применяется оператор скрещивания (crossover), в результате которого получается новый потомок.

К полученному потомку с небольшой вероятностью применяется мутация (mutation) — дерево случайно модифицируется.

Описанная цепочка повторяется многократно, чтобы получить набор потомков. А уже на этапе замещения (replacement) из текущей популяции и полученных потомков формируется новое поколение. Затем цикл запускается снова.

Дальше разберем ключевые этапы подробнее и посмотрим, как устроены популяции и основные генетические операторы.

Популяция

Популяция (population) — это множество индивидов (кандидатных решений), с которыми алгоритм работает в рамках одного поколения. Каждый индивид задается генотипом, соответствует фенотипу и имеет численную оценку пригодности.

Этого достаточно, чтобы на следующих шагах выполнять отбор, применять генетические операторы и формировать новое поколение.

Отбор

На этапе отбора из текущей популяции выбираются индивиды, которые будут участвовать в скрещивании. Как правило, вероятность выбора каждого индивида зависит от значения ее пригодности: более качественные решения имеют больший шанс быть отобранными, однако менее удачные все еще могут попасть в выборку, что позволяет сохранять разнообразие популяции и увеличивать устойчивость поиска.

На рисунке показан пример оператора селекции, который называется пропорциональной селекцией (fitness-proportionate selection). Ее удобно представить как колесо фортуны, в котором сектор каждого индивида имеет размер, пропорциональный его пригодности. Чем выше пригодность, тем больше сектор и тем выше вероятность, что колесо остановится на этом индивиде и он будет отобран.

При этом выбирать индивидов строго пропорционально пригодности не всегда лучший вариант: поиск может стать слишком «жадным» и преждевременно сойтись к локальному оптимуму. Алгоритм пропустит кандидатов, которые сейчас выглядят слабее, но могут иметь перспективные гены.

Скрещивание

После этапа отбора из популяции выбираются два родителя, из которых формируется новый потомок.

Отобранные на предыдущем этапе родители передаются в оператор скрещивания. Цель оператора в том, чтобы перемешать генетическую информацию двух индивидов и создать нового.

На рисунке показан пример стандартного скрещивания (standard crossover). В каждом из родительских деревьев случайным образом выбирается поддеревья, после чего эти поддеревья меняются местами. В результате получается новое дерево, комбинирующее части обоих родителей.

Мутация

После скрещивания полученный потомок с небольшой вероятностью подвергается мутации. В ГП мутация — это случайное изменение структуры дерева. Ее основная роль — поддерживать разнообразие популяции и позволять алгоритму исследовать новые области пространства.

На практике существует несколько вариантов мутации (точечная, выращиванием и др.), но общая идея одна: внести небольшое случайное изменение в генотип.

На рисунке показан пример мутации, при которой один из фрагментов дерева заменяется новым поддеревом. В результате изменяется соответствующая часть формулы.

И так поколение за поколением

Полученный в итоге потомок попадает в новую популяцию, после чего процесс повторяется: снова выполняются оценка, отбор и генерация новых особей, пока не будет сформировано следующее поколение. Как уже отмечалось ранее, этот цикл итеративно повторяется, постепенно улучшая качество решений. Поиск останавливается если: достигнуто качество решения с заданной точностью; достигнут лимит вычислений функции пригодности; лучшее решение не улучшается далее в течение некоторого числа поколений.

Переходим к практике

Как мы уже убедились, ГП довольно простой и интуитивный метод, поскольку не требует вычисления градиентов и в целом знаний о том, что оптимизируется. Нужен только способ кодирования решения и функция пригодности.

Тем не менее, несмотря на эту кажущуюся простоту, такой подход способен находить нетривиальные и интересные решения. Посмотрим на практических примерах, какие результаты можно получить, эволюционируя деревья.

Все вычисления я буду проводить на Python с помощью библиотеки Thefittest, о которой рассказывал в статье «Thefittest: зачем я пишу свою open-source библиотеку эволюционных алгоритмов». В ней реализовано множество эволюционных алгоритмов оптимизации, включая генетическое программирование. Все эксперименты из статьи доступны по ссылке на Google Colab.

Задача 1. Выражение косинуса через синус

Тригонометрия содержит множество разнообразных тождеств и выражений. Среди них — связи между синусом и косинусом, знакомые еще со школьного курса математики. Например, косинус можно выразить как синус со сдвигом аргумента:

Попробуем проверить, сможет ли символьная регрессия восстановить такую зависимость по данным, если целевая функция задана как , но среди доступных функций, которыми можно оперировать, присутствует только .

Для этого сгенерируем выборку из 50 точек на интервале для функции:

В качестве функций и операций оставим только и арифметические операции . В качестве терминальных элементов будем использовать переменную , а также случайные константы из диапазона . И запустим алгоритм несколько раз.

Рассмотрим некоторые из полученных выражений. Например, ГП возвращает такие формулы:

и

На первый взгляд они выглядят громоздко. Однако после алгебраического упрощения они приводятся соответственно к:

и

В первом случае мы фактически получаем синус с фазовым сдвигом. Интересно отметить, что ГП сумел собрать из того что было под рукой очень точную константу. Это видно по фрагменту . После упрощения он дает

Во втором варианте появляется дополнительный линейный член . Формально он искажает точное тождество, однако из-за малого коэффициента его вклад остается незначительным на рассматриваемом интервале. Кроме того, знак «минус» перед синусом также соответствует фазовому сдвигу на и эквивалентен еще одному смещению аргумента.

Также во втором выражении присутствует слагаемое которое фактически равно нулю и не вносит вклад в результат. Оно не улучшают решение, но и не ухудшают его, являясь примером своеобразного «генетического дрейфа» в пространстве выражений.

На гифке ниже можно посмотреть процесс смены лучшего индивида каждого поколения:

Хорошо видно, что эволюция идет немонотонно: алгоритм может откатиться от текущего лучшего решения к более слабому, а затем снова найти улучшение. Иногда за счет полной смены дерева, а иногда через небольшие модификации.

В целом алгоритм уверенно справляется с этой задачей. Однако стоит признать, что она очень простая, поскольку тригонометрическая структура уже присутствует в пространстве поиска, и по сути ГП остается только подобрать подходящую константу.

Но как алгоритм справится, если усложнить постановку и полностью убрать тригонометрические функции из набора доступных операций?

Задача 2. Аппроксимация синуса

С математической точки зрения это не новая задача — синус можно приближать разными способами, например через ряд Тейлора или рациональные аппроксимации. Теперь попробуем поставить тот же вопрос в терминах символьной регрессии: сможет ли ГП, имея в распоряжении только базовые арифметические операции, самостоятельно найти ( «переоткрыть») подобное приближение?

В этом эксперименте в качестве целевой функции возьмем:

,

а в качестве примитивов оставим только операции , переменную и случайные константы. Также добавим небольшой шум.

Сырые результаты алгоритма выглядят примерно так (не поместится в latex формате):

((((((1.627 / (x0 (7.4745 + x0))) / ((3.9516 / 5.4943) ((9 + 6.2809) / (3.9516 + (x0 7.4745))))) / ((((x0 / (x0 + (6.2809 - 5))) (2.7809 / 5.4597)) x0) / ((x0 x0) 1))) + (9 - (3.9516 + x0))) - x0) / (x0 + (((((3.9516 + x0) / ((x0 x0) + 0.1448)) - x0) + ((7.4745 + x0) / ((6.2809 ((x0 + x0) 1.781)) + (1.627 / 3.9516)))) + ((((x0 x0) (1 (x0 + x0))) / ((0 + (2.7809 / (1 + (x0 + x0)))) (0.1448 (((5.4943 5.255) (6.2809 - x0)) (x0 (x0 + x0)))))) (5 / x0)))))

Но рассмотрим лучше сразу варианты выражений, полученные после упрощения:

и

Видно несколько закономерностей:

Во-первых, во всех случаях ГП приходит к рациональным функциям. При отсутствии тригонометрических примитивов отношения многочленов это один из самых естественных способов аппроксимировать синус на ограниченном интервале (по форме очень близко к аппроксимациям Паде, хотя сам алгоритм о них, разумеется, ничего не «знает»).

Во-вторых, почти во всех решениях появляется множитель x в числителе или знаменателе. Таким образом ГП фактически воспроизводит нечетность синуса: умножение на автоматически придает выражению правильную симметрию относительно нуля.

В-третьих, коэффициенты получаются очень большими, потому что в процессе эволюции они позволяют точнее аппроксимировать функцию на заданном интервале. Однако за пределами этого интервала такие коэффициенты могут приводить к «взрывам»

Давайте попробуем наглядно проверить третий тезис. Для этого построим график найденной аппроксимации на расширенном интервале и сравним ее с истинным . Пунктирными вертикальными линиями отметим обучающий интервал:

Как и в первой задаче, можем рассмотреть процесс поиска решения:

Таким образом, ГП успешно аппроксимирует , используя только арифметику, и при этом выходит на рациональные формы, очень похожие на классические приближения из численных методов.

А она вообще нужна, эта эволюция?

Все эти скрещивания, мутации, отбор… Может, они лишние? Почему бы нам, как у Пелевина в IPhuck 10, не устроить упрощенный RCP (random code programming): просто нагенерировать очень много случайных деревьев и выбрать то, у которого ошибка минимальна?

Проверим на этой же задаче. Для честности с бюджетом вычислений сгенерируем 300 000 деревьев — ровно столько, сколько было «посмотрено» эволюцией ранее (300 поколений по 1000 индивидов), и возьмем лучший результат.

Лучшая формула имеет вид (не поместится в latex формате):

(((((((8 / (3.6978 - ((x0 6.2428) / x0))) x0) + (((((4.5375 - 0) (4 - 1.549)) + (2.7827 (2 / 6.1586))) (((6 - x0) / (1.5043 - x0)) / x0)) / ((2 / x0) x0))) + (x0 + 4.2865)) / 5) / (((0 x0) 0.7145) * (x0 - x0))) - (x0 / 3.2684))

На первый взгляд выглядит серьезно: сложное, с дробями, с множеством констант. Но если посмотреть внимательнее, внутри есть деление на выражение вида , а это деление на ноль.

В реальной реализации ГП такие ситуации почти всегда обрабатываются защищенными операциями: например, protected division возвращает 1, если в знаменателе ноль (это делают, чтобы сохранялась замкнутость: любая функция должна быть определена для любых значений аргументов, которые может породить дерево). Если следовать этой логике, то большая дробь обнуляется, и все выражение упрощается до:

То есть случайный поиск, потратив тот же бюджет, в итоге нашел просто прямую. И это как раз хорошо объясняет, зачем нужна эволюция. Мутация случайна, а естественный отбор — полная противоположность случайности.

Задача 3. Символьная регрессия расхода топлива автомобиля

Конечно, предыдущий пример с синусом всего лишь одномерная функция, пусть и нелинейная. Хороший демонстрационный пример, но все же довольно искусственный. Поэтому логично перейти к более практической задаче и посмотреть, как символьная регрессия ведет себя на реальных данных.

В качестве следующего эксперимента возьмем классический набор данных Auto MPG из репозитория UCI. Целевая переменная — расход топлива (mpg), а в качестве признаков используем только физические характеристики автомобиля: — рабочий объем двигателя (куб. дюймы), ​ — мощность (л. с.), ​ — масса (фунты), ​ — число цилиндров (шт.), ​ — разгон 0–60 миль/ч (сек).

После завершения работы ГП получаем следующие метрики на тестовой выборке: MAE = 2.982 и R² = 0.70. При этом ГП возвращает явную аналитическую формулу:

и продолжение:

Видно несколько закономерностей.

Во-первых, выражение устроено как «базовый уровень + поправки»: большая константа задает типичный расход, а остальные слагаемые его корректируют. Нелинейные части вроде синусов здесь скорее играют роль гибких корректоров, которые подстраивают модель под локальные нелинейности в данных, чем несут прямой физический смысл. На это же намекают сдвиги вида и добавления констант в знаменатели — так обычно появляются точки перегиба или стабилизация поведения в крайних областях.

Во-вторых, по структуре видно, что мощность ​ действует как более активный фактор (она входит и напрямую, и внутри сложных комбинаций), а масса ​ чаще работает через взаимодействия — то есть не просто добавляет вклад, а меняет эффект других параметров.

И, наконец, важно, что ГП снова тяготеет к рациональным формам (отношениям выражений): такие зависимости естественно дают эффект насыщения, когда рост одной характеристики дает все меньший эффект при фиксированных остальных.

Таким образом, формула описывает систему с режимами работы, взаимодействиями между признаками и эффектами насыщения, в которых рост одной характеристики приводит к все меньшему изменению целевой переменной. Именно такие свойства сложно выявить в черных ящиках, но они хорошо просматриваются в явном аналитическом выражении.

Для сравнения, градиентный бустинг достигает MAE = 2.658 и R² = 0.714 — то есть действительно немного лучше. Однако за этим стоят 600 деревьев глубиной до 10, и в таком виде модель уже практически невозможно интерпретировать.

Не только символьная регрессия: оптимизация нейросетей

ГП — это в первую очередь общий метод оптимизации, а символьная регрессия лишь один из частных случаев его применения. По сути, ГП можно применять к любой задаче, где решение можно закодировать в виде дерева (и то необязательно, потому что кроме Tree-Based GP есть и другие вариации) и оценить численной функцией пригодности.

Например, с помощью ГП можно успешно оптимизировать структуру (количество и типы нейронов и связи) нейронных сетей.

В функциональном множестве используются две операции: объединяет нейроны в слой, а задает последовательное соединение блоков. Терминальное множество содержит блоки входных и скрытых нейронов. Например, — это два скрытых нейрона с гауссовой активацией, а — входные блоки: включает нейроны — нейрон .

Слева — бинарное дерево (генотип), справа — соответствующая ему архитектура нейросети (фенотип). С этим представлением ГП может оптимизировать именно структуру сети, а функция пригодности задается качеством модели (ошибкой на задаче). Перед ее вычислением для каждой найденной архитектуры нужно настроить веса — например, обучить сеть методом обратного распространения ошибки.

К примеру, так выглядит процесс оптимизации структуры сети для той же задачи регрессии расхода топлива автомобиля:

Полученная нейронная сеть имеет сравнимую ошибку (MAE = 2.890 и R² = 0.711) однако и структуру имеет сравнительно минималистичную.

Заключение

ГП — это мощный и гибкий метод оптимизации со своими сильными сторонами и ограничениями. Как мы увидели на примерах, оно позволяет работать с очень разными типами задач — от поиска аналитических формул и оптимизации архитектур нейронных сетей до приближенного решения дифференциальных уравнений, задач управления и даже автоматического синтеза новых эвристик и эволюционных алгоритмов. При этом ГП требует сравнительно немного предположений о виде решения: достаточно задать способ кодирования и функцию пригодности.

К его плюсам можно отнести универсальность, устойчивость поиска и способность находить нетривиальные структуры без градиентов и ручного проектирования. Эволюционные алгоритмы хорошо подходят для задач со сложным или дискретным пространством решений, где классические методы оптимизации работают плохо.

При этом у подхода есть и очевидные минусы: высокая вычислительная стоимость, чувствительность к выбору генетических операторов и параметров, а также сложности с корректным кодированием решений (например, необходимость обеспечивать замкнутость через защищенные операции). Поэтому, как и любой инструмент, ГП имеет смысл применять там, где его сильные стороны действительно востребованы.

Тем, кто хочет глубже разобраться в теме, можно посмотреть в сторону библиотек gplearn, DEAP, thefittest, а также фреймворка FEDOT. Из классики по теме стоит отметить книгу Genetic Programming: On the Programming of Computers by Means of Natural Selection — именно она во многом заложила основы современного генетического программирования. Как уже упоминалось, весь код из статьи доступен в Google Colab. Спасибо, что дочитали — надеюсь, материал оказался полезным или хотя бы дал пищу для экспериментов.