Генетическое программирование выражения

Эволюционные алгоритмы работают с популяциями особей, выполняют их отбор по критерию приспособленности (fitness) и вносят генетическое разнообразие с помощью одного или нескольких генетических операторов. Применение эволюционных подходов в вычислительных системах началось в 1950-х годах для решения задач оптимизации^[1][2]. Популярность эволюционных алгоритмов выросла с появлением эволюционных стратегий, введённых Инго Рехенбергом в 1965 году^[3]. Обобщающий труд — книга М. Митчелл «An Introduction to Genetic Algorithms» (1996)^[4].

Генетическое программирование выражения^[5] относится к семейству эволюционных алгоритмов и тесно связано с генетическими алгоритмами и генетическим программированием. От генетических алгоритмов GEP унаследовало линейную структуру хромосом фиксированной длины, а от генетического программирования — выразительные дерева разбора (выражений) переменных размеров.

В GEP линейные хромосомы выступают в роли генотипа, а деревья выражений — в роли фенотипа, формируя генотипно/фенотипную систему. Эта система мультигенная (мультигенная хромосома), то есть кодирует несколько деревьев разбора в одной хромосоме (несколько программ). Такие деревья здесь называются деревьями выражения. Применение данного стиля программирования в алгоритмах ABC описано в работе Masood Nekoei и др., где метод ABCEP показал лучшие результаты, чем прочие эволюционные алгоритмы.

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

012345678012345678

L+a-baccd**cLabacd

Здесь «L» обозначает функцию натурального логарифма, а «a», «b», «c», «d» — переменные и константы.

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

Пример математического выражения:

${\displaystyle {\sqrt {(a-b)(c+d)}}}$

может быть представлен как дерево выражения:

Здесь «Q» обозначает функцию квадратного корня.

Линейная строка (k-выражение, или карава-нотация) для такого дерева:

01234567

Q*-+abcd

Преобразование из k-выражения в дерево выражения также тривиально. Например, следующее k-выражение:

01234567890

Q*b**+baQba

содержит два терминала («a» и «b»), две бинарные функции («*» и «+») и одну унарную функцию («Q»). Оно выражается как:

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

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

Длина хвоста вычисляется по формуле:

${\displaystyle t=h(n_{\max }-1)+1}$

где h — длина головы, n_\max — максимальная арность функций. Например, для головы длиной 15 и максимальной арности 2: t = 15·1 + 1 = 16, а общая длина гена — 31 символ. Пример:

0123456789012345678901234567890

*b+a-aQab+//+b+babbabbbababbaaa

Он кодирует дерево выражения:

В данном случае используются только первые 8 элементов из 31, составляющих ген.

Таким образом, каждый ген может кодировать деревья от одного узла (если первый элемент — терминал) до максимальной структуры (если все элементы головы — функции максимальной арности).

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

Хромосомы в GEP обычно содержат несколько генов одинаковой длины. Каждый ген кодирует отдельное поддерево выражения (sub-ET). После экспрессии все поддеревья могут соединяться различными способами (например, сложением, усреднением, медианой, использованием пороговых функций, сигмоиды и др.). Способ соединения («linker function») определяется заранее или эволюционирует автоматически с помощью клеточной системы GEP^[6][7].

В GEP гомеотические гены управляют взаимодействием различных под-деревьев основной программы. Экспрессия таких генов формирует разные главные программы или клетки: определяет, какие гены будут экспрессированы и как модули взаимодействуют.

Гомеотические гены имеют такую же структуру, как и обычные, и состоят из головы (linking-функции и специальных терминалов — ссылок на обычные гены) и хвоста (только генические терминалы). Обычные гены, экспрессированные из них, формируют автоматически определяемые функции (ADF). Хвост содержит только генические терминалы — новые признаки.

Такая система позволяет не только свободную эволюцию linking-функций, но и повторное использование кода, а также, потенциально, реализацию рекурсии.

Многоклеточные системы состоят из нескольких гомеотических генов, каждый из которых объединяет разные комбинации под-деревьев или ADF в разные главные программы (клетки). Такие системы подходят и для задач с одним выходом, и для задач с несколькими выходами.

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

Основные этапы базового алгоритма:

1. Выбор множества функций.
2. Выбор множества терминалов.
3. Загрузка набора данных для оценки приспособленности.
4. Случайное создание хромосом начальной популяции.
5. Для каждой программы в популяции:
   • Экспрессия хромосомы.
   • Выполнение программы.
   • Оценка приспособленности.
6. Проверка условия остановки.
7. Отбор программ.
8. Репликация отобранных программ для формирования следующей популяции.
9. Модификация хромосом генетическими операторами.
10. Переход к шагу 5.

Как и все эволюционные алгоритмы, GEP работает с популяциями программ. Начальная популяция формируется случайно, последующие — путём отбора и генетической модификации. Структурная корректность программ обеспечивается автоматически.

Функции приспособленности (fitness function) и обучающая выборка (training dataset) — две стороны оценки решений. Качество решения определяется не только функцией ошибки, но и качеством обучающих данных.

Обучающая выборка (selection environment) представляет собой набор тренировочных записей или fitness case. Она должна быть достаточно представительна и сбалансирована.

Различают три типа задач по типу предсказываемого значения:

1. Численные (непрерывные) предсказания (регрессия).
2. Категориальные/номинальные (классификация, логистическая регрессия).
3. Двоичные/булевы задачи (булева алгебра).

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

Часто используется просто подсчёт правильных классификаций («hits»), однако для сложных и несбалансированных выборок это неэффективно. Более точные функции приспособленности используют матрицу ошибок (confusion matrix):

Веса для TP, TN, FP, FN позволяют создавать более плавные и эффективные функции. Популярные метрики: чувствительность и специфичность, точность и полнота, F-мера, коэффициент Жаккара, коэффициент корреляции Мэтьюса и др. Более сложные функции потенциально комбинируют информацию о структуре модели (домен, диапазон, маржа классификатора и др.) с традиционными метриками.

В булевой алгебре, поскольку на выходе только 0 и 1, используются простые метрики: подсчёт «hits» и матрица ошибок.

Отбор по принципу рулетки — популярная схема, при которой вероятность отбора пропорциональна приспособленности решения. В сочетании с простым элитизмом (клонирование лучшей программы в новое поколение) гарантируется сохранение наилучших черт.

Репродукция программ включает отбор и копирование геномов, причём разнообразие достигается с помощью генетических операторов: мутации, кроссовера, транспозиции, инверсии и др.

Мутация — основной оператор в GEP^[8]. Каждый элемент гена может быть заменён на любой другой, что обеспечивает высокий потенциал изменения и адаптации.

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

Транспозиция — вставка произвольной последовательности в голову гена. Это допускается только в голове и никогда не портит синтаксическую корректность.

Инверсия — реверсирование случайной последовательности в пределах гена. Особенно полезна в задачах комбинаторной оптимизации^[9].

Реализуются и другие операторы: однородная, двухточечная рекомбинация, перенос домена, корневая транспозиция, доменно-специфическая мутация, инверсия и др.

Для интеграции числовых констант в модели используется отдельный домен Dc для случайных числовых констант (RNC). Dc следует за хвостом, его длина равна t, а символы Dc выступают в качестве placeholder'ов для замены на значения из массива констант.

Пример хромосомы (голова 7, Dc занимает позиции 15–22):

01234567890123456789012

+?*+?**aaa??aaa68083295

Знак «?» — placeholder; каждое ? в дереве выражения заменяется по очереди значением из Dc.

Массив RNC, например:

C = {0,611; 1,184; 2,449; 2,98; 0,496; 2,286; ...}

Такое строение лежит в основе GEP-нейросетей, GEP-решающих деревьев и других разновидностей алгоритма.

Искусственная нейронная сеть (ИНС) состоит из множества взаимосвязанных узлов (нейронов), между которыми проходят взвешенные связи. Веса — основной механизм обучения.

В GEP-нейросетях (GEP-NN) архитектура кодируется в виде головы и хвоста, а веса и пороги — в отдельных доменах Dw и Dt. Формулы длин:

${\displaystyle d_{w}=hn_{\max }}$

${\displaystyle d_{t}=t}$

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

Пример сети на два входа (a и b), два скрытых и один выходной узел (числа — индексы весов):

0123456789012

DDDabab654321

Веса хранятся в массиве и подставляются в процессе экспрессии. Для задачи "исключающее ИЛИ" (XOR):

0123456789012

DDDabab393257

GEP-NN поддерживает различные типы нейронов и может решать задачи булевой логики, логистической регрессии, классификации и регрессии. Варианты возможны как с мультигенными, так и клеточными системами.

Решающее дерево — модель классификации на основе множества вопросов-ответов, отображаемых в виде узлов и направленных рёбер.

В GEP правила кодирования схожи с другими областями: гены состоят из головы (признаки и терминалы), хвоста (только терминалы), иногда — дополнительного домена Dc для случайных порогов деления в узлах. Размер хвоста определяется как

${\displaystyle t=h(n_{\max }-1)+1}$

Пример дерева («H» — влажность, «O» — облачность, «W» — ветер, «a», «b» — классы):

01234567

HOWbaaba

Аналогично строятся и деревья с числовыми атрибутами; значения порогов подставляются из Dc сверху вниз и слева направо.

GEP подвергался критике как не предоставляющий существенных преимуществ по сравнению с другими методами генетического программирования. Во многих экспериментах он не превосходил существующие алгоритмы^[10].

GeneXproTools

GeneXproTools — пакет предиктивной аналитики от Gepsoft, реализующий методы логистической регрессии, классификации, регрессии, прогнозирование временных рядов и логический синтез. В программной платформе применяются базовый алгоритм GEP и его модификация GEP-RNC.

GEP4J – GEP for Java Project

Открытая библиотека для Java, автор Джейсон Томас. Реализует различные алгоритмы GEP, включая эволюцию решающих деревьев (с номинальными, числовыми или смешанными признаками) и автоматически определяемые функции.

PyGEP – Gene Expression Programming for Python

Библиотека для Python, разработанная Райаном О’Нилом для академических нужд. Поддерживает мультигенные хромосомы и операторы мутации, кроссовера, транспозиции.

jGEP – Java GEP toolkit

Набор инструментов для быстрого создания прототипов на Java (автор Мэттью Соттил), которые затем могут быть переписаны на C или Fortran.