Программирование экспрессии генов - Gene expression programming

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

Фон

Эволюционные алгоритмы используют популяции индивидов, отбирают индивидов в соответствии с приспособленностью и вводят генетические вариации с использованием одного или нескольких генетических операторов . Их использование в искусственных вычислительных системах восходит к 1950-м годам, когда они использовались для решения задач оптимизации (например, Box 1957 и Friedman 1959). Но именно с введением Рехенбергом в 1965 году эволюционных стратегий эволюционные алгоритмы приобрели популярность. Хорошим обзорным текстом по эволюционным алгоритмам является книга Митчелла «Введение в генетические алгоритмы» (1996).

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

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

Кодировка: генотип

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

012345678012345678

L+a-baccd**cLabacd

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

Деревья экспрессии: фенотип

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

Например, математическое выражение:

${\ Displaystyle {\ sqrt {(ab) (с + d)}} \,}$

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

где «Q» представляет функцию квадратного корня.

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

01234567

Q*-+abcd

что представляет собой прямое чтение дерева выражений сверху вниз и слева направо. Эти линейные строки называются k-выражениями (из нотации Карвы ).

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

01234567890

Q*b**+baQba

состоит из двух разных терминалов (переменные «a» и «b»), двух разных функций двух аргументов («*» и «+») и функции одного аргумента («Q»). Его выражение дает:

К-выражения и гены

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

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

Для генов GEP длина хвоста определяется формулой:

${\ Displaystyle т = час (п _ {\ макс} -1) +1}$

где h - длина головы, а n _max - максимальная арность. Например, для гена, созданного с использованием набора функций F = {Q, +, -, ∗, /} и набора терминалов T = {a, b}, n _max = 2. И если мы выберем длину головы из 15, то t = 15 (2–1) + 1 = 16, что дает длину гена g, равную 15 + 16 = 31. Случайно сгенерированная строка ниже является примером одного такого гена:

0123456789012345678901234567890

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

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

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

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

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

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

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

Экспрессия генов GEP как суб-ET. а) Трехгенная хромосома, хвосты которой выделены жирным шрифтом. б) Суб-ЕТ, кодируемые каждым геном.

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

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

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

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

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

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

Выражение одноклеточной системы с тремя ADF. а) Хромосома, состоящая из трех обычных генов и одного гомеотического гена (выделены жирным шрифтом). б) ADF, кодируемые каждым обычным геном. в) Основная программа или ячейка.

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

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

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

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

Выражение многоклеточной системы с тремя ADF и двумя основными программами. а) Хромосома, состоящая из трех обычных генов и двух гомеотических генов (выделены жирным шрифтом). б) ADF, кодируемые каждым обычным геном. c) Две разные основные программы, выраженные в двух разных клетках.

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

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

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

Базовый алгоритм экспрессии генов

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

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

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

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

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

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

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

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

Среда выбора или данные обучения

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

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

Фитнес-функции

Вообще говоря, существует три различных типа проблем, основанных на типе прогнозов:

1. Задачи, связанные с числовыми (непрерывными) прогнозами;
2. Проблемы, связанные с категориальными или номинальными предсказаниями, как биномиальными, так и полиномиальными;
3. Проблемы, связанные с двоичными или логическими предсказаниями.

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

Фитнес-функции для регресса

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

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

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

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

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

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

Один из способов улучшить этот тип фитнес-функции на основе совпадений состоит в расширении понятий правильных и неправильных классификаций. В задаче двоичной классификации правильными классификациями могут быть 00 или 11. Представление «00» означает, что отрицательный регистр (представленный «0») был правильно классифицирован, тогда как «11» означает, что положительный регистр (представленный «1») ») Был правильно классифицирован. Классификации типа «00» называются истинно отрицательными (TN) и «11» истинно положительными (TP).

Также существует два типа неправильных классификаций, представленных 01 и 10. Они называются ложными срабатываниями (FP), когда фактическое значение равно 0, а модель предсказывает 1; и ложноотрицательные (FN), когда целью является 1, а модель предсказывает 0. Подсчеты TP, TN, FP и FN обычно хранятся в таблице, известной как матрица неточностей .

Таким образом, подсчитывая TP, TN, FP и FN и затем присваивая разные веса этим четырем типам классификаций, можно создать более плавные и, следовательно, более эффективные фитнес-функции. Некоторые популярные фитнес-функции, основанные на матрице путаницы, включают чувствительность / специфичность , отзыв / точность , F-меру , сходство Жаккара , коэффициент корреляции Мэтьюса и матрицу затрат / выигрыша, которая объединяет затраты и выгоды, присвоенные 4 различным типам классификаций.

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

Изучая это другое измерение моделей классификации и затем комбинируя информацию о модели с матрицей неточностей, можно разработать очень сложные функции приспособленности, которые позволяют беспрепятственно исследовать пространство решений. Например, можно объединить некоторую меру, основанную на матрице неточностей, со среднеквадратической ошибкой, оцененной между исходными результатами модели и фактическими значениями. Или объедините F-меру с R-квадратом, оцененным для необработанных выходных данных модели и цели; или матрица затрат / выгод с коэффициентом корреляции и так далее. Более экзотические фитнес-функции, которые исследуют детализацию модели, включают область под кривой ROC и меру ранга.

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

Фитнес-функции для логических задач

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

Отбор и элитарность

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

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

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

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

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

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

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

Мутация

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

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

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

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

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

Транспонирование

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

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

Инверсия

Инверсия - интересный оператор, особенно эффективный для комбинаторной оптимизации . Он состоит из инвертирования небольшой последовательности в хромосоме.

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

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

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

Алгоритм GEP-RNC

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

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

Структурно Dc идет после хвоста, имеет длину, равную размеру хвоста t , и состоит из символов, используемых для представления RNC.

Например, ниже показана простая хромосома, состоящая только из одного гена с размером головы 7 (Dc простирается на позиции 15–22):

01234567890123456789012

+?*+?**aaa??aaa68083295

где терминал "?" представляет собой заполнитель для RNC. Этот тип хромосомы выражается точно так, как показано выше , что дает:

Затем символы? В дереве выражений заменяются слева направо и сверху вниз на символы (для простоты, представленные цифрами) в Dc, что дает:

Значения, соответствующие этим символам, хранятся в массиве. (Для простоты число, представленное цифрой, указывает порядок в массиве.) Например, для следующего 10-элементного массива RNC:

C = {0,611, 1,184, 2,449, 2,98, 0,496, 2,286, 0,93, 2,305, 2,737, 0,755}

приведенное выше дерево выражений дает:

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

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

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

Нейронные сети

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

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

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

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

Помимо головы и хвоста, эти гены нейронной сети содержат два дополнительных домена, Dw и Dt, для кодирования весов и пороговых значений нейронной сети. Конструктивно Dw идет после хвоста, а его длина d _w зависит от размера головы h и максимальной арности n _max и оценивается по формуле:

${\ displaystyle d_ {w} = hn _ {\ max}}$

Dt идет после Dw и имеет длину d _t, равную t . Оба домена состоят из символов, представляющих веса и пороги нейронной сети.

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

Например, ниже показана нейронная сеть с двумя модулями ввода ( i ₁ и i ₂ ), двумя скрытыми модулями ( h ₁ и h ₂ ) и одним модулем вывода ( o ₁ ). Он имеет в общей сложности шесть соединений с шестью соответствующими весами, представленными цифрами 1–6 (для простоты все пороги равны 1 и опущены):

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

где «a» и «b» представляют два входа i ₁ и i _2, а «D» представляет функцию с возможностью подключения _2. Эта функция складывает все свои взвешенные аргументы, а затем пороговое значение этой активации, чтобы определить пересылаемый выход. (ноль или единица в этом простом случае) зависит от порога каждой единицы, то есть, если общая входящая активация равна или превышает пороговое значение, то выход равен единице, в противном случае - нулю.

Приведенное выше NN-дерево можно линеаризовать следующим образом:

0123456789012

DDDabab654321

где структура в позициях 7–12 (Dw) кодирует веса. Значения каждого веса хранятся в массиве и извлекаются по мере необходимости для выражения.

В качестве более конкретного примера ниже показан ген нейронной сети для проблемы « исключающее ИЛИ». Он имеет размер головы 3 и размер DW 6:

0123456789012

DDDabab393257

Его выражение приводит к следующей нейронной сети:

что для набора весов:

W = {-1,978, 0,514, -0,465, 1,22, -1,686, -1,797, 0,197, 1,606, 0, 1,753}

это дает:

что является идеальным решением для функции исключающее ИЛИ.

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

Деревья решений

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

Деревья решений имеют три типа узлов: корневой узел, внутренние узлы и листовые или конечные узлы. Корневой узел и все внутренние узлы представляют условия тестирования для различных атрибутов или переменных в наборе данных. Узлы-листы определяют метку класса для всех различных путей в дереве.

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

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

Существует два основных типа алгоритмов DT: один для создания деревьев решений только с номинальными атрибутами, а другой для создания деревьев решений с числовыми и номинальными атрибутами. Этот аспект индукции дерева решений также относится к программированию экспрессии генов, и есть два алгоритма GEP для индукции дерева решений: алгоритм эволюционирующих деревьев решений (EDT) для работы исключительно с номинальными атрибутами и EDT-RNC (EDT со случайными числовыми константами) для обработка как номинальных, так и числовых атрибутов.

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

Правила кодирования дерева решений в линейном геноме очень похожи на правила, используемые для кодирования математических выражений (см. Выше ). Итак, для индукции дерева решений у генов также есть голова и хвост, причем голова содержит атрибуты и терминалы, а хвост - только терминалы. Это снова гарантирует, что все деревья решений, разработанные GEP, всегда являются действительными программами. Кроме того, размер хвоста t также определяется размером головы h и количеством ветвей атрибута с большим количеством ветвей n _max и оценивается по формуле:

${\ Displaystyle т = час (п _ {\ макс} -1) +1 \,}$

Например, рассмотрите приведенное ниже дерево решений, чтобы решить, играть ли на улице:

Его можно линейно закодировать как:

01234567

HOWbaaba

где «H» представляет атрибут Humidity, «O» - атрибут Outlook, «W» представляет Windy, а «a» и «b» - метки класса «Yes» и «No» соответственно. Обратите внимание, что ребра, соединяющие узлы, являются свойствами данных, определяя тип и количество ветвей каждого атрибута, и поэтому их не нужно кодировать.

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

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

012345678901234567890

WOTHabababbbabba46336

кодирует дерево решений, показанное ниже:

В этой системе каждый узел в заголовке, независимо от его типа (числовой атрибут, номинальный атрибут или терминал), имеет связанную с ним случайную числовую константу, которая для простоты в приведенном выше примере представлена ​​цифрой 0–9. Эти случайные числовые константы кодируются в области Dc, и их выражение следует очень простой схеме: сверху вниз и слева направо элементы в Dc назначаются один за другим элементам в дереве решений. Итак, для следующего массива RNC:

C = {62, 51, 68, 83, 86, 41, 43, 44, 9, 67}

приведенное выше дерево решений приводит к:

которое также можно представить более красочно в виде обычного дерева решений:

Критика

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

Программное обеспечение

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

GeneXproИнструменты

GeneXproTools - это пакет прогнозной аналитики, разработанный Gepsoft . Структуры моделирования GeneXproTools включают логистическую регрессию , классификацию , регрессию , прогнозирование временных рядов и логический синтез . GeneXproTools реализует базовый алгоритм экспрессии генов и алгоритм ГЭПА-RNC , как используется во всех рамках моделирования GeneXproTools.

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

GEP4J - GEP для проекта Java

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

PyGEP - Программирование экспрессии генов для Python

Создан Райаном О'Нилом с целью создать простую библиотеку, подходящую для академического изучения программирования экспрессии генов на Python , с целью простоты использования и быстрой реализации. Он реализует стандартные мультигенные хромосомы и генетические операторы мутации, кроссовера и транспозиции. PyGEP размещен в Google Code .

jGEP - набор инструментов Java GEP

Создан Мэтью Соттилем для быстрого создания кодов прототипов Java , использующих GEP, которые затем могут быть написаны на таком языке, как C или Fortran для реальной скорости. jGEP размещен на SourceForge .

дальнейшее чтение

• Феррейра, К. (2006). Программирование экспрессии генов: математическое моделирование с помощью искусственного интеллекта . Springer-Verlag. ISBN 3-540-32796-7.
• Феррейра, К. (2002). Программирование экспрессии генов: математическое моделирование с помощью искусственного интеллекта . Португалия: Ангра-ду-Эроижму. ISBN 972-95890-5-4.

Смотрите также

• Символическая регрессия
• Искусственный интеллект
• Деревья решений
• Эволюционные алгоритмы
• Генетические алгоритмы
• Генетическое программирование
• GeneXproИнструменты
• Машинное обучение
• Нейронные сети

использованная литература

внешние ссылки

• Домашняя страница GEP , поддерживаемая изобретателем программирования экспрессии генов.
• GeneXproTools , коммерческое программное обеспечение GEP.