Введение

Эволюционный алгоритм

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

Предыстория

Эволюционные алгоритмы используют популяции индивидуумов, отбирают индивидуумов в соответствии с приспособленностью и вводят генетическое разнообразие с помощью одного или нескольких генетических операторов. Их применение в искусственных вычислительных системах началось в 1950-х годах, когда они использовались для решения задач оптимизации (например, Box, 1957 и Friedman, 1959). Однако популярность эволюционные алгоритмы приобрели с появлением стратегий эволюции, предложенных Рехенбергом в 1965 году. Книга Митчелла "Введение в генетические алгоритмы" (1996) является хорошим обзором эволюционных алгоритмов. Программирование экспрессии генов относится к семейству эволюционных алгоритмов и тесно связано с генетическими алгоритмами и генетическим программированием. От генетических алгоритмов оно унаследовало линейные хромосомы фиксированной длины, а от генетического программирования – выразительные деревья разбора различного размера и формы. В программировании экспрессии генов линейные хромосомы выступают в роли генотипа, а деревья разбора – в роли фенотипа, формируя систему генотип/фенотип. Эта система генотип/фенотип является мультигенной, кодируя, таким образом, несколько деревьев разбора в каждой хромосоме. Это означает, что компьютерные программы, создаваемые GEP, состоят из нескольких деревьев разбора. Поскольку эти деревья разбора являются результатом экспрессии генов, в GEP они называются деревьями выражений. Масуд Некоеи и др. использовали этот стиль программирования выражений в оптимизации ABC для проведения ABCEP, как метода, превосходящего другие эволюционные алгоритмы. ABCEP

Мультигенные хромосомы

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

Повторное использование ячеек и кода

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

Гомеотические гены и клеточная система

Гомеотические гены имеют абсолютно такую же структурную организацию, как и нормальные гены, и создаются с использованием идентичного процесса. Они также содержат головной и хвостовой домены, с той разницей, что головные домены содержат связывающие функции и особый тип терминалов – геновые терминалы – представляющие собой нормальные гены. Экспрессия нормальных генов, как обычно, приводит к различным суб-ЭТ, которые в клеточной системе называются ADF (автоматически определяемые функции). Что касается хвостовых доменов, то они содержат только геновые терминалы, то есть производные признаки, генерируемые алгоритмом в процессе работы. Например, хромосома на рисунке содержит три нормальных гена и один гомеотический ген и кодирует основную программу, которая вызывает три различные функции в общей сложности четыре раза, связывая их определенным образом. Из этого примера становится ясно, что клеточная система не только допускает неограниченную эволюцию связывающих функций, но и повторное использование кода. И реализовать рекурсию в этой системе не должно быть сложно.

Многочисленные основные программы и многоклеточные системы

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

Другие уровни сложности

Домен "голова/хвост" генов GEP (как нормальных, так и гомеотических) является основным строительным блоком всех алгоритмов GEP. Однако программирование экспрессии генов также исследует другие хромосомные организации, более сложные, чем структура "голова/хвост". По сути, эти сложные структуры состоят из функциональных блоков или генов, имеющих базовый домен "голова/хвост" и один или несколько дополнительных доменов. Эти дополнительные домены обычно кодируют случайные числовые константы, которые алгоритм непрерывно настраивает для поиска оптимального решения. Например, эти числовые константы могут представлять собой веса или коэффициенты в задаче аппроксимации функций (см. алгоритм GEP RNC ниже); веса и пороги нейронной сети (см. алгоритм GEP NN ниже); числовые константы, необходимые для построения деревьев решений (см. алгоритм GEP DT ниже); веса, необходимые для полиномиальной индукции; или случайные числовые константы, используемые для определения значений параметров в задаче оптимизации параметров.

Популяции программ

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

Функции фитнеса и среда отбора

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

Окружающая среда отбора или данные о обучении

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

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

В регрессии зависимая переменная является числовой (обычно непрерывной), и, следовательно, выход регрессионной модели также непрерывен. Поэтому довольно просто оценить пригодность развивающихся моделей, сравнивая выход модели со значением зависимой переменной в обучающих данных. Существует несколько основных функций пригодности для оценки производительности модели, наиболее распространенные из которых основаны на ошибке или остатке между выходом модели и фактическим значением. К таким функциям относятся среднеквадратичная ошибка, корень из среднеквадратичной ошибки, средняя абсолютная ошибка, относительная квадратичная ошибка, корень из относительной квадратичной ошибки, относительная абсолютная ошибка и другие. Все эти стандартные меры обеспечивают высокую детализацию или гладкость пространства решений и, следовательно, хорошо подходят для большинства задач. Однако для некоторых задач может потребоваться более грубая эволюция, например, определение, попадает ли предсказание в определенный интервал, скажем, менее 10% от фактического значения. Даже если интересует только подсчет попаданий (то есть предсказаний, находящихся в выбранном интервале), эволюция популяций моделей, основанная исключительно на количестве попаданий, обычно неэффективна из-за грубой гранулярности ландшафта пригодности. Поэтому решение обычно заключается в комбинировании этих грубых мер с какими-либо гладкими функциями, такими как стандартные меры ошибки, перечисленные выше. Функции пригодности, основанные на коэффициенте корреляции и R-квадрате, также очень гладкие. Для регрессионных задач эти функции лучше всего работают в сочетании с другими мерами, поскольку сами по себе они, как правило, измеряют только корреляцию, не учитывая диапазон значений выхода модели. Комбинируя их с функциями, которые стремятся аппроксимировать диапазон целевых значений, можно получить очень эффективные функции пригодности для поиска моделей с хорошей корреляцией и хорошим соответствием между прогнозируемыми и фактическими значениями.

Функции пригодности для классификации и логистической регрессии

При разработке функций пригодности для классификации и логистической регрессии используются три различных характеристики классификационных моделей. Самое очевидное – это просто подсчет правильных классификаций, то есть, если запись классифицирована верно, она засчитывается как правильная классификация. Эта функция пригодности очень проста и хорошо работает для простых задач, но для более сложных задач или сильно несбалансированных наборов данных она дает плохие результаты. Один из способов улучшения такого типа функции пригодности на основе правильных классификаций заключается в расширении понятия правильной и неправильной классификации. В задаче бинарной классификации правильными классификациями могут быть 00 или 11. Обозначение "00" означает, что отрицательный случай (представленный "0") был классифицирован правильно, в то время как "11" означает, что положительный случай (представленный "1") был классифицирован правильно. Классификации типа "00" называются истинно отрицательными (TN) и "11" – истинно положительными (TP). Существует также два типа неправильных классификаций, которые обозначаются как 01 и 10. Они называются ложноположительными (FP), когда фактическое значение равно 0, а модель предсказывает 1; и ложноотрицательными (FN), когда целевое значение равно 1, а модель предсказывает 0. Количество TP, TN, FP и FN обычно заносится в таблицу, известную как матрица ошибок. + Матрица ошибок для задачи биномиальной классификации. Предсказанный класс ✔ rowspan="2" ✔ TP FN FP TN

Таким образом, подсчитывая TP, TN, FP и FN и дополнительно присваивая различные веса этим четырем типам классификаций, можно создать более плавные и, следовательно, более эффективные функции пригодности. Некоторые популярные функции пригодности, основанные на матрице ошибок, включают чувствительность/специфичность, полноту/точность, меру F, сходство Жаккара, коэффициент корреляции Мэтьюса и матрицу затрат/выигрышей, которая объединяет затраты и выгоды, присвоенные четырем различным типам классификаций. Эти функции, основанные на матрице ошибок, достаточно сложны и адекватны для эффективного решения большинства задач. Но есть и другое измерение классификационных моделей, которое является ключевым для более эффективного исследования пространства решений и, следовательно, приводит к обнаружению лучших классификаторов. Это новое измерение включает в себя изучение структуры самой модели, которая включает не только область определения и область значений, но и распределение выходных данных модели и запас классификатора. Исследуя это другое измерение классификационных моделей и затем объединяя информацию о модели с матрицей ошибок, можно разработать очень сложные функции пригодности, которые позволяют плавно исследовать пространство решений. Например, можно объединить некоторую меру, основанную на матрице ошибок, со среднеквадратичной ошибкой, рассчитанной между исходными выходными данными модели и фактическими значениями. Или объединить меру F с R-квадратом, рассчитанным для исходных выходных данных модели и целевого значения; или матрицу затрат/выигрышей с коэффициентом корреляции и так далее. Более экзотические функции пригодности, которые исследуют гранулярность модели, включают площадь под кривой ROC и ранговую меру. Также связанным с этим новым измерением классификационных моделей является идея присвоения вероятностей выходным данным модели, что и делается в логистической регрессии. Затем также можно использовать эти вероятности и рассчитать среднеквадратичную ошибку (или другую аналогичную меру) между вероятностями и фактическими значениями, а затем объединить это с матрицей ошибок, чтобы создать очень эффективные функции пригодности для логистической регрессии. Популярные примеры функций пригодности, основанных на вероятностях, включают оценку максимального правдоподобия и функцию потерь шарнира.

Функции соответствия для булевых задач

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

Отбор и элитаризм

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

Воспроизведение с модификацией

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

Репликация и отбор

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

Мутация

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

Рекомбинация

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

Трансплантация

Транспозиция включает в себя введение вставочной последовательности в хромосому в определенном месте. В программировании экспрессии генов вставочные последовательности могут появляться в любом месте хромосомы, но они вставляются только в начало генов. Этот метод гарантирует, что даже вставочные последовательности, происходящие из концов генов, приводят к безошибочным программам. Для корректной транспозиции необходимо сохранять длину хромосом и структуру генов. Следовательно, в программировании экспрессии генов транспозиция может быть реализована двумя различными способами: первый создает сдвиг в месте вставки, за которым следует делеция в конце начала гена; второй перезаписывает локальную последовательность в целевом участке и, следовательно, проще в реализации. Оба способа могут быть реализованы для работы между хромосомами, внутри одной хромосомы или даже внутри одного гена.

Инверсия

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

Другие генетические операторы

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

Критика

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

Коммерческие применения

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

Библиотеки с открытым исходным кодом

GEP4J – GEP для Java-проектов. Созданный Джейсоном Томасом, GEP4J – это реализация с открытым исходным кодом программирования экспрессии генов на Java. Он реализует различные алгоритмы GEP, включая эволюцию деревьев решений (с номинальными, числовыми или смешанными атрибутами) и автоматически определяемые функции. GEP4J размещен на Google Code. PyGEP – Программирование экспрессии генов для Python. Созданный Райаном О’Нилом с целью создания простой библиотеки, подходящей для академического изучения программирования экспрессии генов на Python, ориентированной на простоту использования и быструю реализацию. Он реализует стандартные мультигенные хромосомы и генетические операторы мутации, кроссинговера и транспозиции. PyGEP размещен на Google Code. jGEP – Java GEP toolkit. Созданный Мэтью Сотилом для быстрой разработки прототипов Java-кода, использующего GEP, который затем может быть переписан на языках, таких как C или Fortran, для достижения высокой производительности. jGEP размещен на SourceForge.