В. И. Литвиненко1, П. И. Бидюк2, А. А. фефелов3, и. В. баклан4
Скачать 151.04 Kb.
|
- Навигация по данной странице:
- ГИБРИДНАЯ ИММУННАЯ СЕТЬ ДЛЯ РЕШЕНИЯ ЗАДАЧ СТРУКТУРНОЙ ИДЕНТИФИКАЦИИ Аннотация
- Ag - Ab affinity
- Ag-Ab
- 3. Гибридная иммунная система
- 3.1. Алгоритм гибридной иммунной сети
- Вычисление аффинности каждого антитела.
- 3.2. Гибридная иммунная сеть и задачи идентификации
СЕКЦИЯ 9 В.И. Литвиненко1, П.И. Бидюк2, А.А. фефелов3, и.В. баклан4 1,3Херсонский государственный технический университет, Украина Национальный технический университет Украины «Киевский политехнический институт»
В работе приводится описание разработанного авторами алгоритма, использующего механизмы идиопатической сети и эволюционной вычислительной парадигмы – программирование экспрессии гена. На основе предложенного алгоритма создан комплекс программ предназначенный для решения задач структурной идентификации и выявление эмпирических закономерностей в структурах данных. 1. Введение Естественная иммунная система, обладает мощными и гибкими способностями обработки информации представляя собой децентрализованную интеллектуальную систему, которая обеспечивает превосходную адаптацию на локальном уровне и эмерджементность поведения на глобальном уровне. Следует заметить, что если механизмы обработки информации нервной системы уже давно используются в информатике, то экстраординарные способности обработки информации естественной иммунной системой в полной мере были оценены только недавно[1]. Основными стандартными блоками иммунной системы [2] являются лимфоциты. Существует два основных класса лимфоцитов: В-лифоциты, синтезируемые в костном мозге в ходе так назвыаемого клонального отбора, и Т-лимфоциты, получаемые процессе обработки в Тимусе. В-лифоциты выделяют антитела. Среди В-лимфоцитов выделяют клетки «памяти», живущие относительно долго и «помнящие» чужеродные белки. С другой стороны, T-клетки обеспечивают клеточный иммунитет: они функционируют, взаимодействуя с другими клетками. T-клетки делятся на T-клетки хелперы и лимфоциты, называемые T-клетки киллеры, которые устраняют внутриклеточные антигены. Одной из теорий образования антител является клонально-селекционная теория, разработанная Бернетом [3]. Основное положение ее состоит в том, что способность индивидуума распознавать антиген, связана с определенными иммунологически реактивными лимфоцитами или генетически идентичными линиями лимфоцитов (клонами). Когда B-клетки распознают антиген, они стимулируются, после чего клонируются и синтезируют антитела с той же специфичностью. Этот процесс стимулирует только те клетки, которые синтезируют полезный тип антител, и называется клональным отбором. Число клонов, произведенных лимфоцитом пропорционально уровню его стимуляции. Иммунная система обладает двумя типами ответа: первичный и вторичный. Первичный ответ возникает при первом контакте с антигеном. Для изучения структуры антигенных эпитопов, используется процесс созревания аффинности. Первичный ответ может занять некоторое время (обычно приблизительно 3 недели), для уничтожения антигена. Если организм повторно инфицируется антигеном, с которым предварительно сталкивался, то он будет иметь адаптированную подпопуляцию B-клеток, позволяющую обеспечить очень специфический и быстрый вторичный ответ. С точки зрения информатики первичный ответ соответствует идентификации в группе данных обучения, в то время как вторичный ответ - задаче распознавания образа, то есть отнесению новых данных в одну из существующих групп. Интересно, что вторичный ответ вызывается не только повторным введением тех же самых антигенов, но также и инфекцией с новыми антигенами, которые являются схожими с уже предварительно распознанными антигенами. Именно поэтому мы говорим, что иммунная память является ассоциативной. Заключительным принципом иммунный системы, который играет полезную роль в проектировании искусственных иммунных систем является теория идиотипической (иммунной) сети, сформулированной Ерне [4], и далее развитый Перельсоном [5]. Согласно этой теории иммунная система динамически меняется, а иммунный ответ базируется не только на взаимодействии В-клеток и антигенов, но также, и на взаимодействии В-клеток с другими В-клетками. Данные клетки обеспечивают и стимуляцию и эффект супрессии друг друга, это взаимодействие частично объясняет память иммунной системы Иммунная система находится в постоянном движении. Целая сеть подвергается структурным волнениям вследствие появления и исчезновения некоторых разновидностей клеток. Введение новых разновидностей вызвано соматической мутацией, апоптозом (запрограммированной смертью клеток) или комбинаторным разнообразием (например, генетическими операциями). Важным фактом является то, что сама сеть, а не внешняя среда регулирует селекцию новых видов антител, которые объединяются в сети. Таким образом, иммунная сеть самоорганизуется, потому что именно она определяет выживание созданных клонов и ее собственный размер. Этот процесс называется метадинамикой системы [6]. 2. Искусственные иммунные системы Молекулы рецепторов, содержащихся на поверхности антител, имеют специальные области, называемыми идиотопами. Идиотопы могут распознаваться рецепторами других антител. Способность клеток соединяться по принципу «ключ-замок» называется комплементарностью друг к другу (рис. 1). Биологический прототип используемого нами механизма заключается в следующем. Допустим, что антитело Ab1 распознает антиген Ag. Антиген – чужеродное тело, то с чем борется иммунная система. Допустим, также, что то же антитело Ab1 распознает идиотоп на антителе Ab2. В этом случае говорят, что Ab2 – это внутренний образ антигена Ag. Таким образом, распознавая друг друга, антитела образуют области соединенных клеток, что ведет к сжатию (suppression) иммунной сети. С другой стороны, распознавание антигенов антителами ведет к активации (activation) сети и увеличению количества антител. При активации иммунная сеть формирует иммунный ответ, подобно механизму клонального отбора, т.е. можно сказать, что клональный отбор является частью поведения иммунной сети. 
Рис. 1. Теория иммунной сети Применительно к задачам распознавания в качестве популяции антигенов иммунной сети выступает набор данных (векторов), которые нужно распознать. Назовем этот набор  . Каждый вектор  состоит из p элементов. Элементами вектора могут являться набор переменных, атрибутов или характеристик распознаваемого объекта. Таким образом, каждый вектор  представляет собой точку в p-мерном пространстве, и, следовательно, для моделирования связей «антиген-антитело» и «антитело-антитело» все антитела должны быть также представлены в форме p-мерных строк или векторов. Значит, наша иммунная сеть математически может быть представлена в виде графа, причем необязательно полносвязного, который состоит из множества узлов (клетки сети) и множества взвешенных ребер, означающих связи между клетками. Значение веса ребра соответствует силе связи клеток друг с другом (т.е. близости или степени комплементарности клеток), называемой аффинностью. В иммунных сетях различают два вида аффинности: аффинность связи «антиген-антитело» (Ag-Ab affinity) – степень различия; аффинность связи «антитело-антитело» (Ab-Ab affinity) – степень подобия. Формально алгоритм иммунной сети можно представить следующим образом:
 ,
где Алгоритм работает следующим образом: 1. Случайным образом сгенерировать сеть 2. Цикл для каждого поколения: 2.1. Цикл для каждого антигена 2.1.1. Вычислить Ag-Ab аффинность (с антигеном 2.1.2. Выбрать 2.1.3. Клонировать выбранные клетки. Количество клонов каждой клетки сети пропорционально ее Ag-Ab аффинности: выше аффинность (лучше клетка) – больше клонов; 2.1.4. Подвергнуть мутации все полученные клоны; 2.1.5. Вычислить Ag-Ab аффинность (с антигеном 2.1.6. Повторно выбрать 2.1.7. Удалить из популяции 2.1.8. Вычислить Ab-Ab аффинности полученной популяции 2.1.9. Удалить из популяции 2.1.10. Конкатенировать исходную сеть 2.2. Вычислить Ab-Ab аффинности всей вновь полученной сети 2.3. Заменить r % худших клеток сети 2.4. Проверить условие останова. 2.5. В зависимости от результата предыдущего шага вернуться к шагу 2.1. или перейти к шагу 3. 3. Конец.
Рис. 2. Многопиковая поверхность, образованная функцией В этом случае иммунная сеть учится распознавать оптимумы целевой функции и в конце обучения образуется примерно такая картина (рис. 2, б). Применительно к задачам оптимизации процедура сжатия сети реализует еще одно очень важное ее свойство – способность к мультимодальному поиску. 3. Гибридная иммунная система Мягкие вычисления заинтересованы главным образом в интеграции различных парадигм вычислительного интеллекта, для создания гибридов с выгодным объединением сильных сторон различных парадигм. Нами разработан гибридный алгоритм иммунной сети, позволяющей строить аналитические модели различных объектов и процессов при помощи вычислительной парадигмы программирования экспрессии генов [7], ранее нами была представлена работа о гибридной системе на основе парадигмы экспрессии генов и механизма клонального отбора [8, 9]. 3.1. Алгоритм гибридной иммунной сети Стандартная иммунная сеть (ИС) оперирует строками данных и используется для решения задач классификации, распознавания и оптимизации. Каждая строка данных (антитело) представляет собой одно решение поставленной задачи. В классическом варианте задачи оптимизации сводились к поиску решений в многомерном пространстве с наперед заданной целевой функцией. Решением такой задачи является набор (картеж) переменных, подстановка которых в целевую функцию дает оптимальное значение. В случае гибридной иммунной сети антитела представляют собой не просто вектор переменных, а связанные конструкции, которые можно рассматривать как деревья аналитической зависимости или как компьютерные программы. Причем в первом случае в качестве задачи чаще всего выступает аппроксимация некоторой зависимости, обычно задаваемой в табличной форме. Например, когда требуется свести воедино результаты серии экспериментов и получить зависимость выхода эксперимента от его входа. Кодирование антител. Все антитела гибридной ИС представляют собой строки фиксированной длины, состоящие из символов. Символы выбираются из конечного алфавита символов, который в свою очередь состоит из двух частей: функционального алфавита и терминального алфавита. Символьная строка антитела есть не что иное, как последовательная запись древовидной структуры, отображающей математическую зависимость и использующей в качестве символов функционального алфавита знаки математических операций и функций:  . В данном множестве буквы Q, S и C означают соответственно операцию взятия квадратного корня, функцию синуса и косинуса. В качестве терминальных символов используются символы, обозначающие переменные-аргументы функции и специальный символ константы «?»: . Дерево преобразуется в строку путем последовательной записи всех узлов и листьев, начиная с корневого узла слева направо и сверху вниз (рис. 3). Начальная популяция антител создается случайным образом, т.е. строки символов инициализируются символами из функционального и терминального алфавита. Во избежание построения неправильных выражений строки символов делятся условно на две части: голову и хвост. Голова может содержать как терминальные, так и функциональные символы, хвост – только терминальные символы. Идея заключается в том, чтобы избежать ситуации, синтаксически неправильного выражения, даже в том случае, когда голова полностью состоит из функциональных символов. На этой основе вычисляется общая длина антитела:
 ,
где t – общая длина индивидуума; h – длина головы; n – максимальное количество аргументов используемых в функциональном наборе. В нашем случае n = 2. 
Рис. 3. Преобразование математической формулы в символьную строку антитела: а) исходная формула; б) дерево выражения; в) разделение дерева по уровням; г) последовательная запись элементов уровней в строку Вычисление аффинности каждого антитела. Аффинность антитела – это скалярная величина оценки, показывающая близость результата к оптимальному значению. В зависимости от того решается ли задача максимизации или минимизации, лучшим по популяции считается антитело с самым высоким или низким значением аффинности соответственно. Аффинность антител – главный критерий отбора индивидуумов в алгоритме иммунной сети. Аффинность в гибридном алгоритме иммунной сети вычисляется исходя из таблицы значений аппроксимируемой функции. Эта таблица представляет собой матрицу наборов значений аргументов исследуемой функции и соответствующих им значений самой функции (рис. 4). Во время оценки антитела символьная строка его генетического кода преобразуется в дерево математического выражения, и аргументы из таблицы подставляются в это выражение. Полученные в результате значения функции сравниваются с соответствующими им табличными (реальными) значениями и, исходя из степени близости значений друг к другу, строится суждение о качестве аппроксимации антителом заданной функции. 
Рис. 4. Оценка антитела при помощи таблицы значений функции При этом аффинность антитела может быть представлена в виде одной из ошибок (среднеквадратической:  , либо средней относительной:  ). В этом случае мы имеем дело с задачей минимизации, так как ошибка должна быть сведена к нулю. В нашей реализации в качестве меры аффинности использованы информационный критерий Акайке, который учитывает сумму квадратов ошибок, число измерений N и число оцениваемых параметров p:  , критерий Байеса-Шварца (BSC), который дополнительно учитывает длину выборки с помощью члена :   .
В качестве дополнительных генетических операторов в алгоритм добавлены два вида транспозиции. Транспозиция – это внутрихромосомное перемещение части генетического кода определенной длины. Различают IS-транспозиции (Insertion Sequences transposition) и RIS-транспозиции (Root Insertion Sequences transposition). IS-транспозиция – цепочка символов определенной длины перемещается из любого места индивидуума в головную часть, но не в корень (рис. 5, а); RIS-транспозиция – цепочка символов определенной длины во главе с функциональным символом перемещается в начало (корень) индивидуума (рис. 5, б).
Рис. 5. IS-транспозиция (а); RIS-транспозиция (б) Проведенные эксперименты показали, что транспозиции существенно улучшают эффективность работы AIS. 3.2. Гибридная иммунная сеть и задачи идентификации Специфика задач прогнозирования состоит в том, что при построении математических моделей динамических процессов нам необходимо одновременно использовать как распознающие, так и оптимизационные способности иммунной сети. С одной стороны задачу прогнозирования можно рассматривать как задачу оптимизации: нам необходимо построить оптимальную модель, которая бы наиболее точно описывала исследуемый процесс. Алгоритм осуществляет поиск в пространстве структур и выбирает одну или еще лучше несколько наиболее подходящих. С другой стороны модель должна быть достаточно общей, чтобы быть способной не только интерполировать, но и экстраполировать данные. Модификация иммунной сети, предложенная нами, предполагает следующее: используя свои способности к мультимодальной оптимизации, иммунная сеть генерирует несколько альтернативных математических структур, из которых затем выбирает наиболее общую модель, которая и будет оптимальной. Вся модификация сосредоточена в структуризации обучающих данных (антигенов) сети. Рассмотрим это подробнее. Со стороны задачи оптимизации, в нашем случае целевая функция состоит в минимизации среднеквадратической ошибки (RMSE) на обучающей выборке данных. Если всю сеть обучать на одной обучающей выборке (случай одного антигена или обычная задача оптимизации), то мы получим одну или несколько математических структур, которые достаточно хорошо аппроксимируют обучающую выборку, но совершенно необязательно способны к экстраполяции и прогнозированию. Конечно, вполне возможно, что среди полученного набора моделей окажется одна, наиболее адекватная прогнозируемому процессу, но это будет лишь случайность, к тому же вероятнее всего эта модель окажется одним из локальных оптимумов целевой функции. Поэтому, для того чтобы задействовать обобщающие свойства иммунных сетей, проявляемые в задачах распознавания, можно разделить обучающую выборку на несколько необязательно непересекающихся и в общем случае непостоянного размера сегментов, т.е. создать популяцию антигенов (как в задачах распознавания), но каждый антиген будет представлять собой «кусочек» обучающей выборки и таким образом неявно задавать целевую функцию в виде RMSE (как в задачах оптимизации). Далее следуя алгоритму иммунной сети антитела будут учиться распознавать одновременно все антигены, т.е. оптимизировать одновременно все целевые функции, а этого можно достичь только путем обобщения. Кроме того, можно сказать, что данная методика не противоречит основным принципам самоорганизации моделей, так как формируемые «антигены – целевые функции» опять же неявно выступают одновременно в роли внешних и внутренних критериев. И, наконец, известная проблема противоречивости обучающих выборок, возможно, теряет свою актуальность в случае увеличения популяции антигенов. Большая популяция антигенов улучшает качество распознавания («противоречивые» антигены остаются за пределами основного класса), а возможность пересечения сегментов обучающей выборки при формировании популяции антигенов исключает необходимость использования огромных обучающих выборок. Выводы В работе описан разработанный авторами гибридный алгоритм иммунной сети для решения задач структурной идентификации. В предложенном алгоритме удалось объединить лучшие качества алгоритмов иммунной сети (сочетание глобального и локального поиска) и алгоритма программирования экспрессии гена (способ кодирования хромосом и возможность преодоления порога фенотипа, что позволяет осуществлять мультимодальный поиск, чего лишены все другие эволюционные алгоритмы). Проведенные эксперименты показали, что алгоритм является весьма эффективным при осуществлении краткосрочного прогноза финансовых показателей, а также при осуществлении структурной идентификации гидробиологических систем. Осуществлена программная реализация предложенного алгоритма. Как показали исследования, алгоритм обладает большими возможностями в его дальнейшем развитии и использовании в решении задач прогнозирования, экстраполяции и интерполяции. Проведенные опыты по прогнозированию показали повышение качества прогнозов с учетом хаотических свойств временных рядов. Однако представленный алгоритм требует дальнейшего исследований о влиянии тех или иных параметров настройки на скорость сходимости алгоритма, качество получаемых решений. Целесообразно проведение сравнительных исследований разработанного алгоритма с алгоритмами МГУА, нейронными сетями с различной топологией, классическими регрессионными моделями. Список литературы
УДК 004.032.26(06) Нейронные сети Каталог: data -> scientific-sessions -> 2005 -> nero data -> «Сотовый телефон и безопасность здоровья» data -> Фонограммы как доказательства по гражданским делам data -> Психология индивидуальности data -> Аспергиллез (aspergillosis) data -> Реферат тема: "Урология". План История развития урологии 2 data -> Примерные темы, проблемы и направления курсовых работ nero -> Молекулярные механизмы памяти: управление консолидацией кластеров метаботропных рецепторов scientific-sessions -> Визуализация плазмоиндуцированных процессов проекционным микроскопом с усилителем яркости на основе лазера на парах меди Скачать 151.04 Kb. Поделитесь с Вашими друзьями:
|
– набор данных, состоящий из 
векторов размерности p – популяция антигенов; 
– матрица, содержащая все клетки (антитела) сети (
) – популяция антител; 
– матрица, состоящая из N клеток памяти (
); 
– общее количество клонов, создаваемых стимулируемыми клетками в каждом поколении (при активации сети); 
– матрица элементов 
Ag-Ab аффинностей; 
–- матрица элементов 
Ab-Ab аффинностей; 
– количество лучших клеток, отбираемых из 
– процент улучшенных клеток, отбираемых из популяции клонов для последующей обработки; 
– пороговый коэффициент гибели или стимуляции клетки в зависимости от ее Ag-Ab аффинности; 
– пороговый коэффициент сжатия сети.
) всех клеток сети 
клеток памяти;
, что приведет к уменьшению размера 
.
те клетки, аффинность которых (
);
. Предположим 
, тогда проекция поверхности на плоскость 
может выглядеть следующим образом (рис. 2, а).
(а); иммунная сеть способна находить глобальный и локальные оптимумы (б)
