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

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

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

Фон

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

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

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

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

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

012345678012345678

L + a-baccd ** cLabacd

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

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

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

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

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

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

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

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

01234567

Q * - + abcd

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

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

01234567890

Q * b ** + baQba

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

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

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

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

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

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

куда час длина головы и п_{Максимум} это максимальная арность. Например, для гена, созданного с использованием набора функций F = {Q, +, -, *, /} и набора терминалов T = {a, b}, п_{Максимум} = 2. А если выбрать длину головы 15, то т = 15 (2–1) + 1 = 16, что дает длину гена грамм of 15 + 16 = 31. Случайно сгенерированная строка ниже является примером одного из таких генов:

0123456789012345678901234567890

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Выберите набор функций;

2. Выбрать терминал;

3. Загрузить набор данных для оценки пригодности;

4. Случайным образом создать хромосомы исходной популяции;

5. Для каждой программы в населении:

а) экспресс-хромосома;

б) Выполнить программу;

c) Оценить пригодность;

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 и ранговая мера.

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

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

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

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

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

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

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

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

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

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

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

Мутация

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

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

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

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

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

Транспозиция

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

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

Инверсия

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

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

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

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

Алгоритм GEP-RNC

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

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

Конструктивно Dc идет после хвоста, имеет длину, равную размеру хвоста. т, и состоит из символов, используемых для представления 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 создается случайным образом в начале цикла, что означает, что для каждого гена в исходной популяции случайным образом генерируется определенное количество числовых констант, выбранных из определенного диапазона. Затем их циркуляция и мутация активируются генетическими операторами.

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

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

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

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

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

Помимо головы и хвоста, эти гены нейронной сети содержат два дополнительных домена, Dw и Dt, для кодирования весов и пороговых значений нейронной сети. Конструктивно Dw следует за хвостом и его длиной. d_ш зависит от размера головы час и максимальная арность п_{Максимум} и оценивается по формуле:

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

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

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

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

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

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

Приведенное выше 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) - это модели классификации, в которых ряд вопросов и ответов отображается с помощью узлов и направленных ребер.

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

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

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

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

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

Правила кодирования дерева решений в линейном геноме очень похожи на правила, используемые для кодирования математических выражений (см. над ). Итак, для индукции дерева решений у генов также есть голова и хвост, причем голова содержит атрибуты и терминалы, а хвост - только терминалы. Это снова гарантирует, что все деревья решений, разработанные GEP, всегда будут действительными программами. Кроме того, размер хвоста т также продиктовано размером головы час и количество ветвей атрибута с большим количеством ветвей п_{Максимум} и оценивается по уравнению:

${ 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 критиковали за то, что он не является значительным улучшением по сравнению с другими генетическое программирование техники. Во многих экспериментах он не работал лучше существующих методов.^[12]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рекомендации

внешняя ссылка

• Домашняя страница GEP, поддерживаемый изобретателем программирования экспрессии генов.
• GeneXproИнструменты, коммерческое ПО GEP.