В компьютерном программировании программирование экспрессии генов (GEP) — это эволюционный алгоритм , который создает компьютерные программы или модели. Эти компьютерные программы представляют собой сложные древовидные структуры , которые обучаются и адаптируются, изменяя свои размеры, формы и состав, подобно живому организму. И подобно живым организмам, компьютерные программы GEP также закодированы в простых линейных хромосомах фиксированной длины. Таким образом, GEP — это система генотипа-фенотипа , использующая простой геном для хранения и передачи генетической информации и сложный фенотип для исследования окружающей среды и адаптации к ней.
Эволюционные алгоритмы используют популяции особей, выбирают особей в соответствии с приспособленностью и вводят генетическую изменчивость с помощью одного или нескольких генетических операторов . Их использование в искусственных вычислительных системах восходит к 1950-м годам, где они применялись для решения задач оптимизации (например, Box 1957 [1] и Friedman 1959 [2] ). Но именно с введением эволюционных стратегий Рехенбергом в 1965 году [3] эволюционные алгоритмы приобрели популярность. Хорошим обзорным текстом по эволюционным алгоритмам является книга «Введение в генетические алгоритмы» Митчелла (1996). [4]
Программирование экспрессии генов [5] принадлежит к семейству эволюционных алгоритмов и тесно связано с генетическими алгоритмами и генетическим программированием . От генетических алгоритмов оно унаследовало линейные хромосомы фиксированной длины; а от генетического программирования оно унаследовало выразительные деревья синтаксического анализа различных размеров и форм.
В программировании экспрессии генов линейные хромосомы работают как генотип, а деревья разбора как фенотип, создавая систему генотипа/фенотипа . Эта система генотипа/фенотипа является мультигенной , таким образом кодируя несколько деревьев разбора в каждой хромосоме. Это означает, что компьютерные программы, созданные GEP, состоят из нескольких деревьев разбора. Поскольку эти деревья разбора являются результатом экспрессии генов, в GEP они называются деревьями экспрессии . Масуд Некои и др. использовали этот стиль программирования выражений в оптимизации ABC для проведения ABCEP как метода, который превзошел другие эволюционные алгоритмы. ABCEP
Геном программирования экспрессии генов состоит из линейной символической строки или хромосомы фиксированной длины, состоящей из одного или нескольких генов одинакового размера. Эти гены, несмотря на свою фиксированную длину, кодируют деревья экспрессии разных размеров и форм. Примером хромосомы с двумя генами, каждый размером 9, является строка (позиция ноль указывает на начало каждого гена):
012345678012345678L+a-baccd**cLabacdгде «L» представляет функцию натурального логарифма, а «a», «b», «c» и «d» представляют переменные и константы, используемые в задаче.
Как показано выше, гены программирования экспрессии генов имеют одинаковый размер. Однако эти строки фиксированной длины кодируют деревья экспрессии разных размеров. Это означает, что размер кодирующих областей варьируется от гена к гену, что позволяет адаптации и эволюции происходить плавно.
Например, математическое выражение:
также может быть представлено в виде дерева выражений :
где «Q» представляет собой функцию квадратного корня.
Этот вид дерева экспрессии состоит из фенотипической экспрессии генов GEP, тогда как гены представляют собой линейные строки, кодирующие эти сложные структуры. Для этого конкретного примера линейная строка соответствует:
01234567Q*-+abcdчто является прямым чтением дерева выражений сверху вниз и слева направо. Эти линейные строки называются k-выражениями (из нотации Карва).
Переход от k-выражений к деревьям выражений также очень прост. Например, следующее k-выражение:
01234567890Q*b**+baQbaсостоит из двух различных терминалов (переменные «a» и «b»), двух различных функций двух аргументов («*» и «+») и функции одного аргумента («Q»). Его выражение дает:
K-выражения программирования экспрессии генов соответствуют региону генов, который экспрессируется. Это означает, что в генах могут быть последовательности, которые не экспрессируются, что действительно верно для большинства генов. Причина этих некодирующих регионов заключается в предоставлении буфера терминалов, чтобы все k-выражения, закодированные в генах GEP, всегда соответствовали действительным программам или выражениям.
Гены программирования экспрессии генов, таким образом, состоят из двух различных доменов – головы и хвоста – каждый из которых имеет различные свойства и функции. Голова используется в основном для кодирования функций и переменных, выбранных для решения поставленной задачи, тогда как хвост, хотя он также используется для кодирования переменных, по сути, предоставляет резервуар терминалов для обеспечения того, чтобы все программы были безошибочными.
Для генов GEP длина хвоста определяется по формуле:
где 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 могут быть связаны сложением или какой-либо другой функцией, поскольку нет ограничений на тип функции связывания, которую можно выбрать. Некоторые примеры более сложных линкеров включают взятие среднего значения, медианы, середины диапазона, пороговое значение их суммы для создания биномиальной классификации, применение сигмоидальной функции для вычисления вероятности и т. д. Эти функции связывания обычно выбираются априори для каждой проблемы, но они также могут быть элегантно и эффективно развиты клеточной системой [6] [7] программирования экспрессии генов.
В программировании экспрессии генов гомеозисные гены контролируют взаимодействия различных подпрограмм или модулей основной программы. Экспрессия таких генов приводит к различным основным программам или клеткам, то есть они определяют, какие гены экспрессируются в каждой клетке и как подпрограммы каждой клетки взаимодействуют друг с другом. Другими словами, гомеозисные гены определяют, какие подпрограммы вызываются и как часто в какой основной программе или клетке и какие связи они устанавливают друг с другом.
Гомеозисные гены имеют точно такую же структурную организацию, как и нормальные гены, и они построены с использованием идентичного процесса. Они также содержат головной домен и хвостовой домен, с той разницей, что головки теперь содержат связующие функции и особый вид терминалов — генные терминалы — которые представляют нормальные гены. Экспрессия нормальных генов приводит, как обычно, к различным суб-ET, которые в клеточной системе называются ADF (автоматически определяемые функции). Что касается хвостов, они содержат только генные терминалы, то есть производные признаки, генерируемые на лету алгоритмом.
Например, хромосома на рисунке имеет три нормальных гена и один гомеозисный ген и кодирует основную программу, которая вызывает три различные функции в общей сложности четыре раза, связывая их определенным образом.
Из этого примера ясно, что клеточная система не только допускает неограниченную эволюцию связывающих функций, но и повторное использование кода. И не должно быть сложно реализовать рекурсию в этой системе.
Многоклеточные системы состоят из более чем одного гомеотического гена. Каждый гомеотический ген в этой системе собирает различную комбинацию деревьев субэкспрессии или ADF, создавая несколько клеток или основных программ.
Например, программа, показанная на рисунке, была создана с использованием клеточной системы с двумя клетками и тремя нормальными генами.
Области применения этих многоклеточных систем многочисленны и разнообразны, и, как и мультигенные системы, их можно использовать как в задачах с одним выходом, так и в задачах с несколькими выходами.
Домен «голова/хвост» генов GEP (как нормальных, так и гомеозисных) является основным строительным блоком всех алгоритмов GEP. Однако программирование экспрессии генов также исследует другие хромосомные организации, которые являются более сложными, чем структура «голова/хвост». По сути, эти сложные структуры состоят из функциональных единиц или генов с базовым доменом «голова/хвост» плюс один или несколько дополнительных доменов. Эти дополнительные домены обычно кодируют случайные числовые константы, которые алгоритм неустанно настраивает, чтобы найти хорошее решение. Например, эти числовые константы могут быть весами или факторами в задаче аппроксимации функции (см. алгоритм GEP-RNC ниже); они могут быть весами и пороговыми значениями нейронной сети (см. алгоритм GEP-NN ниже); числовые константы, необходимые для проектирования деревьев решений (см. алгоритм GEP-DT ниже); веса, необходимые для полиномиальной индукции; или случайные числовые константы, используемые для обнаружения значений параметров в задаче оптимизации параметров.
Основные этапы базового алгоритма экспрессии генов перечислены ниже в псевдокоде:
Первые четыре шага готовят все ингредиенты, необходимые для итеративного цикла алгоритма (шаги с 5 по 10). Из этих подготовительных шагов решающим является создание начальной популяции, которая создается случайным образом с использованием элементов функций и терминальных множеств.
Как и все эволюционные алгоритмы, программирование экспрессии генов работает с популяциями особей, которые в данном случае являются компьютерными программами. Поэтому для начала работы необходимо создать некую начальную популяцию. Последующие популяции являются потомками, полученными путем отбора и генетической модификации, начальной популяции.
В системе генотипа/фенотипа программирования экспрессии генов необходимо создавать только простые линейные хромосомы особей, не беспокоясь о структурной надежности программ, которые они кодируют, поскольку их экспрессия всегда приводит к синтаксически правильным программам.
Функции пригодности и среды отбора (называемые наборами данных обучения в машинном обучении ) являются двумя гранями пригодности и поэтому они тесно связаны. Действительно, пригодность программы зависит не только от функции стоимости, используемой для измерения ее производительности, но и от данных обучения, выбранных для оценки пригодности
Среда выбора состоит из набора записей обучения, которые также называются случаями пригодности. Эти случаи пригодности могут быть набором наблюдений или измерений, касающихся некоторой проблемы, и они формируют то, что называется набором данных обучения.
Качество данных для обучения имеет важное значение для разработки хороших решений. Хороший набор данных для обучения должен быть репрезентативным для рассматриваемой проблемы, а также хорошо сбалансированным, в противном случае алгоритм может застрять на каком-то локальном оптимуме. Кроме того, также важно избегать использования ненужно больших наборов данных для обучения, поскольку это приведет к ненужному замедлению процесса. Хорошее практическое правило — выбирать достаточно записей для обучения, чтобы обеспечить хорошее обобщение в данных для проверки, и оставлять оставшиеся записи для проверки и тестирования.
Вообще говоря, существует три различных типа проблем в зависимости от типа прогноза:
Первый тип задач называется регрессией ; второй известен как классификация , при этом логистическая регрессия является частным случаем, где помимо четких классификаций, таких как «Да» или «Нет», каждому результату также присваивается вероятность; а последний связан с булевой алгеброй и логическим синтезом .
В регрессии ответ или зависимая переменная является числовой (обычно непрерывной), и поэтому выход регрессионной модели также непрерывен. Поэтому довольно просто оценить пригодность развивающихся моделей, сравнивая выход модели со значением ответа в обучающих данных.
Существует несколько основных функций пригодности для оценки производительности модели, наиболее распространенные из которых основаны на ошибке или остатке между выходными данными модели и фактическим значением. Такие функции включают среднеквадратичную ошибку , среднеквадратичную ошибку , среднюю абсолютную ошибку , относительную квадратичную ошибку, относительную квадратичную ошибку, относительную абсолютную ошибку и другие.
Все эти стандартные меры обеспечивают тонкую гранулярность или гладкость пространства решений и поэтому работают очень хорошо для большинства приложений. Но некоторые проблемы могут потребовать более грубой эволюции, например, определения того, находится ли прогноз в пределах определенного интервала, например, менее 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 и меру ранга.
Также с этим новым измерением моделей классификации связана идея назначения вероятностей выходным данным модели, что и делается в логистической регрессии . Затем также можно использовать эти вероятности и оценить среднеквадратичную ошибку (или какую-либо другую подобную меру) между вероятностями и фактическими значениями, а затем объединить это с матрицей путаницы для создания очень эффективных функций приспособленности для логистической регрессии. Популярные примеры функций приспособленности, основанных на вероятностях, включают оценку максимального правдоподобия и потерю шарнира .
В логике нет структуры модели (определенной выше для классификации и логистической регрессии) для исследования: область и диапазон логических функций включают только 0 и 1 или ложь и истину. Таким образом, функции пригодности, доступные для булевой алгебры, могут быть основаны только на совпадениях или на матрице путаницы, как объяснено в разделе выше.
Отбор с помощью колеса рулетки , пожалуй, самая популярная схема отбора, используемая в эволюционных вычислениях. Она включает в себя сопоставление приспособленности каждой программы с частью колеса рулетки, пропорциональной ее приспособленности. Затем рулетка раскручивается столько раз, сколько программ в популяции, чтобы поддерживать постоянный размер популяции. Таким образом, при отборе с помощью колеса рулетки программы отбираются как в соответствии с приспособленностью, так и с удачей, что означает, что иногда лучшие черты могут быть потеряны. Однако, комбинируя отбор с помощью колеса рулетки с клонированием лучшей программы каждого поколения, можно гарантировать, что по крайней мере самые лучшие черты не будут потеряны. Этот метод клонирования лучшей программы поколения известен как простой элитизм и используется большинством схем стохастического отбора.
Воспроизведение программ подразумевает сначала отбор, а затем воспроизведение их геномов. Модификация генома не требуется для воспроизведения, но без нее адаптация и эволюция не будут иметь места.
Оператор выбора выбирает программы для копирования оператором репликации. В зависимости от схемы выбора количество копий, создаваемых одной программой, может варьироваться, некоторые программы копируются более одного раза, а другие копируются только один раз или не копируются вообще. Кроме того, выбор обычно настраивается таким образом, чтобы размер популяции оставался постоянным от поколения к поколению.
Репликация геномов в природе очень сложна, и ученым потребовалось много времени, чтобы открыть двойную спираль ДНК и предложить механизм ее репликации. Но репликация строк тривиальна в искусственных эволюционных системах, где для передачи всей информации в геноме из поколения в поколение требуется только инструкция по копированию строк.
Репликация выбранных программ является фундаментальной частью всех искусственных эволюционных систем, но для того, чтобы произошла эволюция, она должна быть реализована не с обычной точностью инструкции копирования, а скорее с несколькими внесенными ошибками. Действительно, генетическое разнообразие создается с помощью генетических операторов, таких как мутация , рекомбинация , транспозиция , инверсия и многих других.
В программировании экспрессии генов мутация является наиболее важным генетическим оператором. [8] Она изменяет геномы, заменяя один элемент другим. Накопление множества небольших изменений с течением времени может создать большое разнообразие.
В программировании экспрессии генов мутация полностью не ограничена, что означает, что в каждом домене гена любой символ домена может быть заменен другим. Например, в головах генов любая функция может быть заменена терминалом или другой функцией, независимо от количества аргументов в этой новой функции; а терминал может быть заменен функцией или другим терминалом.
Рекомбинация обычно включает две родительские хромосомы для создания двух новых хромосом путем объединения различных частей родительских хромосом. И пока родительские хромосомы выровнены, а обмененные фрагменты гомологичны (то есть занимают одно и то же положение в хромосоме), новые хромосомы, созданные путем рекомбинации, всегда будут кодировать синтаксически правильные программы.
Различные виды кроссинговера легко реализуются либо путем изменения количества вовлеченных родителей (нет причин выбирать только двух); количества точек разделения; или способа, которым вы выбираете обмен фрагментами, например, случайным образом или в некотором упорядоченном порядке. Например, рекомбинация генов, которая является частным случаем рекомбинации, может быть выполнена путем обмена гомологичными генами (генами, которые занимают одно и то же положение в хромосоме) или путем обмена генами, выбранными случайным образом из любого положения в хромосоме.
Транспозиция подразумевает введение последовательности вставки где-то в хромосоме. В программировании экспрессии генов последовательности вставки могут появляться в любом месте хромосомы, но они вставляются только в головы генов. Этот метод гарантирует, что даже последовательности вставки с хвостов приводят к безошибочным программам.
Для правильной работы транспозиции необходимо сохранить длину хромосомы и структуру гена. Таким образом, в программировании экспрессии генов транспозиция может быть реализована двумя различными методами: первый создает сдвиг в месте вставки, за которым следует удаление в конце головы; второй перезаписывает локальную последовательность в целевом месте и поэтому проще в реализации. Оба метода могут быть реализованы для работы между хромосомами или внутри хромосомы или даже внутри одного гена.
Инверсия — интересный оператор, особенно эффективный для комбинаторной оптимизации . [9] Он заключается в инвертировании небольшой последовательности внутри хромосомы.
В программировании экспрессии генов это может быть легко реализовано во всех доменах генов, и во всех случаях полученное потомство всегда синтаксически правильно. Для любого домена гена последовательность (от двух элементов до самого домена) выбирается случайным образом в пределах этого домена, а затем инвертируется.
Существует несколько других генетических операторов, и в программировании экспрессии генов, с его различными генами и доменами генов, возможности безграничны. Например, такие генетические операторы, как одноточечная рекомбинация, двухточечная рекомбинация, рекомбинация генов, равномерная рекомбинация, транспозиция генов, транспозиция корней, доменно-специфическая мутация, доменно-специфическая инверсия, доменно-специфическая транспозиция и т. д., легко реализуются и широко используются.
Числовые константы являются важнейшими элементами математических и статистических моделей, поэтому важно обеспечить их интеграцию в модели, разработанные с помощью эволюционных алгоритмов.
Программирование экспрессии генов решает эту проблему очень элегантно с помощью использования дополнительного домена гена – Dc – для обработки случайных числовых констант (RNC). Объединив этот домен со специальным конечным заполнителем для RNC, можно создать богато выразительную систему.
Структурно Dc следует за хвостом, имеет длину, равную размеру хвоста t , и состоит из символов, используемых для представления НКРЯ.
Например, ниже показана простая хромосома, состоящая только из одного гена с размером головки 7 (Dc простирается на позиции 15–22):
01234567890123456789012+?*+?**aaa??aaa68083295где терминальный знак «?» представляет собой заполнитель для RNC. Этот тип хромосомы выражается точно так же, как показано выше, что дает:
Затем знаки вопроса в дереве выражения заменяются слева направо и сверху вниз символами (для простоты представленными цифрами) в Dc, что дает:
Значения, соответствующие этим символам, хранятся в массиве. (Для простоты число, представленное цифрой, указывает порядок в массиве.) Например, для следующего массива из 10 элементов RNC:
приведенное выше дерево выражений дает:
Эта элегантная структура для обработки случайных числовых констант лежит в основе различных систем GEP, таких как нейронные сети GEP и деревья решений GEP.
Как и базовый алгоритм экспрессии генов, алгоритм GEP-RNC также является мультигенным, и его хромосомы декодируются как обычно, путем экспрессии одного гена за другим, а затем связывания их всех вместе с помощью того же самого процесса связывания.
Генетические операторы, используемые в системе GEP-RNC, являются расширением генетических операторов базового алгоритма GEP (см. выше), и все они могут быть напрямую реализованы в этих новых хромосомах. С другой стороны, базовые операторы мутации, инверсии, транспозиции и рекомбинации также используются в алгоритме GEP-RNC. Кроме того, специальные операторы, специфичные для Dc, такие как мутация, инверсия и транспозиция, также используются для более эффективной циркуляции RNC среди отдельных программ. Кроме того, существует также специальный оператор мутации, который позволяет вносить постоянные изменения в набор RNC. Начальный набор RNC создается случайным образом в начале прогона, что означает, что для каждого гена в начальной популяции случайно генерируется указанное количество числовых констант, выбранных из определенного диапазона. Затем их циркуляция и мутация включаются генетическими операторами.
Искусственная нейронная сеть (ИНС или NN) — это вычислительное устройство, состоящее из множества простых связанных единиц или нейронов. Связи между единицами обычно взвешиваются с помощью действительных весов. Эти веса являются основным средством обучения в нейронных сетях, и для их настройки обычно используется алгоритм обучения.
Структурно нейронная сеть имеет три различных класса единиц: входные единицы, скрытые единицы и выходные единицы. Шаблон активации представлен на входных единицах и затем распространяется в прямом направлении от входных единиц через один или несколько слоев скрытых единиц к выходным единицам. Активация, поступающая в одну единицу от другой единицы, умножается на веса на связях, по которым она распространяется. Затем вся входящая активация суммируется, и единица активируется только в том случае, если входящий результат превышает порог единицы.
Подводя итог, можно сказать, что основными компонентами нейронной сети являются блоки, связи между блоками, веса и пороги. Таким образом, для того, чтобы полностью смоделировать искусственную нейронную сеть, необходимо каким-то образом закодировать эти компоненты в линейной хромосоме, а затем суметь выразить их осмысленным образом.
В нейронных сетях GEP (GEP-NN или GEP-nets) архитектура сети закодирована в обычной структуре домена голова/хвост. [10] Голова содержит специальные функции/нейроны, которые активируют скрытые и выходные блоки (в контексте GEP все эти блоки более уместно называть функциональными блоками) и терминалы, которые представляют входные блоки. Хвост, как обычно, содержит только терминалы/входные блоки.
Помимо головы и хвоста, эти гены нейронной сети содержат два дополнительных домена, Dw и Dt, для кодирования весов и порогов нейронной сети. Структурно Dw следует за хвостом, а его длина d w зависит от размера головы h и максимальной арности n max и оценивается по формуле:
Dt следует за Dw и имеет длину d t , равную t . Оба домена состоят из символов, представляющих веса и пороги нейронной сети.
Для каждого NN-гена веса и пороги создаются в начале каждого запуска, но их циркуляция и адаптация гарантируются обычными генетическими операторами мутации, транспозиции, инверсии и рекомбинации. Кроме того, специальные операторы также используются для обеспечения постоянного потока генетической вариации в наборе весов и порогов.
Например, ниже показана нейронная сеть с двумя входными блоками ( i 1 и i 2 ), двумя скрытыми блоками ( h 1 и h 2 ) и одним выходным блоком ( o 1 ). Всего она имеет шесть соединений с шестью соответствующими весами, представленными цифрами 1–6 (для простоты все пороговые значения равны 1 и опущены):
Это представление является каноническим представлением нейронной сети, но нейронные сети также могут быть представлены в виде дерева, которое в данном случае соответствует:
где «a» и «b» представляют два входа i 1 и i 2 , а «D» представляет функцию со связностью два. Эта функция складывает все свои взвешенные аргументы, а затем порогирует эту активацию, чтобы определить пересылаемый выход. Этот выход (ноль или единица в этом простом случае) зависит от порога каждой единицы, то есть, если общая входящая активация равна или больше порога, то выход равен единице, в противном случае — нулю.
Приведенное выше NN-дерево можно линеаризировать следующим образом:
0123456789012DDDabab654321где структура в позициях 7–12 (Dw) кодирует веса. Значения каждого веса хранятся в массиве и извлекаются по мере необходимости для выражения.
В качестве более конкретного примера ниже показан ген нейронной сети для задачи «исключающее ИЛИ» . Он имеет размер головы 3 и размер Dw 6:
0123456789012DDDabab393257Результатом его выражения является следующая нейронная сеть:
что для набора весов:
это дает:
что является идеальным решением для функции «исключающее ИЛИ».
Помимо простых булевых функций с бинарными входами и бинарными выходами, алгоритм GEP-сетей может обрабатывать все виды функций или нейронов (линейный нейрон, тангенциальный нейрон, атанговый нейрон, логистический нейрон, предельный нейрон, радиально-базисные и треугольные базисные нейроны, все виды ступенчатых нейронов и т. д.). Также интересно то, что алгоритм GEP-сетей может использовать все эти нейроны вместе и позволить эволюции решить, какие из них лучше всего подходят для решения поставленной задачи. Таким образом, GEP-сети можно использовать не только в булевых задачах, но и в логистической регрессии , классификации и регрессии . Во всех случаях GEP-сети можно реализовать не только с мультигенными системами, но и с клеточными системами, как одноклеточными, так и многоклеточными. Кроме того, задачи полиномиальной классификации также можно решать за один раз с помощью GEP-сетей как с мультигенными системами, так и с многоклеточными системами.
Деревья решений (ДР) — это модели классификации, в которых ряд вопросов и ответов отображается с помощью узлов и направленных ребер.
Деревья решений имеют три типа узлов: корневой узел, внутренние узлы и конечные или терминальные узлы. Корневой узел и все внутренние узлы представляют собой тестовые условия для различных атрибутов или переменных в наборе данных. Конечные узлы определяют метку класса для всех различных путей в дереве.
Большинство алгоритмов индукции дерева решений включают выбор атрибута для корневого узла, а затем принятие такого же обоснованного решения относительно всех узлов в дереве.
Деревья решений также могут быть созданы с помощью программирования экспрессии генов [11], с тем преимуществом, что все решения, касающиеся роста дерева, принимаются самим алгоритмом без какого-либо человеческого участия.
В основном существуют два различных типа алгоритмов DT: один для индукции деревьев решений только с номинальными атрибутами и другой для индукции деревьев решений как с числовыми, так и с номинальными атрибутами. Этот аспект индукции дерева решений также распространяется на программирование экспрессии генов, и существует два алгоритма GEP для индукции дерева решений: алгоритм эволюционируемых деревьев решений (EDT) для работы исключительно с номинальными атрибутами и EDT-RNC (EDT со случайными числовыми константами) для обработки как номинальных, так и числовых атрибутов.
В деревьях решений, индуцированных программированием экспрессии генов, атрибуты ведут себя как узлы функций в базовом алгоритме экспрессии генов, тогда как метки классов ведут себя как терминалы. Это означает, что узлы атрибутов также связаны с ними определенной арностью или числом ветвей, которые будут определять их рост и, в конечном счете, рост дерева. Метки классов ведут себя как терминалы, что означает, что для задачи классификации k классов используется набор терминалов с k терминалами, представляющий k различных классов.
Правила кодирования дерева решений в линейном геноме очень похожи на правила, используемые для кодирования математических выражений (см. выше). Таким образом, для индукции дерева решений гены также имеют голову и хвост, причем голова содержит атрибуты и терминалы, а хвост содержит только терминалы. Это снова гарантирует, что все деревья решений, разработанные GEP, всегда являются допустимыми программами. Более того, размер хвоста t также диктуется размером головы h и числом ветвей атрибута с большим количеством ветвей n max и оценивается уравнением:
Например, рассмотрим приведенное ниже дерево решений, чтобы решить, играть ли на улице:
Его можно линейно закодировать следующим образом:
01234567HOWbaabaгде «H» представляет атрибут Влажность, «O» — атрибут Перспектива, «W» — Ветрено, а «a» и «b» — метки классов «Да» и «Нет» соответственно. Обратите внимание, что ребра, соединяющие узлы, являются свойствами данных, указывающими тип и количество ветвей каждого атрибута, и поэтому не должны кодироваться.
Процесс индукции дерева решений с программированием экспрессии генов начинается, как обычно, с начальной популяции случайно созданных хромосом. Затем хромосомы выражаются в виде деревьев решений, и их пригодность оценивается по обучающему набору данных. Затем в соответствии с пригодностью они отбираются для воспроизведения с модификацией. Генетические операторы точно такие же, как и в обычной унигенной системе, например, мутация, инверсия, транспозиция и рекомбинация.
Деревья решений с номинальными и числовыми атрибутами также легко индуцируются с помощью программирования экспрессии генов, используя описанную выше структуру для работы со случайными числовыми константами. Хромосомная архитектура включает дополнительный домен для кодирования случайных числовых констант, которые используются в качестве порогов для разделения данных в каждом узле ветвления. Например, ген ниже с размером головы 5 (Dc начинается с позиции 16):
012345678901234567890WOTHabababbbabba46336кодирует дерево решений, показанное ниже:
В этой системе каждый узел в голове, независимо от его типа (числовой атрибут, номинальный атрибут или терминал), имеет связанную с ним случайную числовую константу, которая для простоты в приведенном выше примере представлена цифрой 0–9. Эти случайные числовые константы кодируются в домене Dc, и их выражение следует очень простой схеме: сверху вниз и слева направо элементы в Dc назначаются один за другим элементам в дереве решений. Итак, для следующего массива RNC:
Приведенное выше дерево решений приводит к следующим результатам:
что также можно представить более красочно в виде обычного дерева решений:
GEP критиковали за то, что он не является серьезным улучшением по сравнению с другими методами генетического программирования . Во многих экспериментах он не показал лучших результатов, чем существующие методы. [12]