Камбулов Д.А., Дьяченко Н.В., Акушуев Р.Т.
Донской государственный технический университет
Анализ существующих алгоритмов искусственной иммунной системы
Аннотация
В данной статье рассматривается бурно развивающуюся отрасль бионспирированных систем – искусственные иммунные системы (ИИС). А также были рассмотрены алгоритмы и принципы работы ИИС.
Ключевые слова: искусственная иммунная система, иммунная память, искусственные сети, иммунные детекторы.
Keywords: artificial immune system, immune memory, artificial networks, immune detectors.
На сегодняшний день, миру известно несколько биологических самоорганизующихся систем – иммунная и нервная, каждая такая система обладает способностью интеллектуальной обработки информации: самообучение, принимать решения относительно ранее неизвестных ситуаций. Исследования в области информационных технологий показывают, что искусственные иммунные системы в задачах распознавания образов обладают высоким потенциалом в вычислительном плане, так как иммунная сеть сложнее в своей организации в сравнении с нейронной.
Искусственная иммунная система (ИИС) — это адаптивная компьютерная система, которая использует модели, принципы, механизмы и функции, описанные в теоретической иммунологии, для решения прикладных задач.
Естественные иммунные сети в настоящее время недостаточно развиты, функциональную часть таких сетей определяют три теории:
- теория отрицательного отбора;
- теория клонального отбора;
- теория иммунной сети.
Именно эти теории стали основой для функционирования алгоритмов ИИС.
Алгоритм отрицательного отбора.
Алгоритм негативного отбора основан на принципах «своего» и «чужого» распознавания в системе. В иммунной системе этот тип распознавания является функцией Т-клеток и других клеток с определенным типом рецептора, с помощью которого они могут обнаруживать антитела.
Рецепторы создаются на основе псевдослучайного генетически обусловленного процесса перегруппировки. Это происходит во время образования Т-клеток в тимусе. Там Т-клетки подвергаются цензурированию и получают название «отрицательный отбор». Этот отбор уничтожает любую клетку, которая так или иначе реагирует с дружественными белками или со своими подобными клетками. Впоследствии Т-клетки покидают тимус и начинают циркулировать в системе, пока не обнаружат антиген, с которым они немедленно реагируют. Согласно этому принципу, алгоритм отрицательного отбора работает в ИИС. Детекторы, которые должны быть обнаружены, генерируются случайным образом, а затем те, которые распознают «своё» в системе, исключаются. Затем эти детекторы начинают циркулировать как Т- лимфоциты в системе. Они организованы так, что понимают, что не все «свое». Этот подход может быть формализован следующим образом:
- Мы определяем «своё» как набор из S строк длинны l над конечным алфавитом, который должен быть защищен или контролироваться. Например, S может быть программой, файлом данных или обычной формой деятельности, разделенной на подстроки различной длины.
- Образуем детекторы R, каждый из которых не должен соответствовать любой строке в S. Вместо точного, или идеального соответствия, используем правило частичного соответствия, при котором две строки соответствуют друг другу, только и только если они совпадают по крайне мере в r следующих друг за другом позициях, где r некоторый численный параметр.
- Проверим S на предмет изменений путем непрерывного сравнения детекторов из R с элементами S. Если хотя бы один из детекторов окажется соответствующим, значит произошло изменение, поскольку детекторы по определению подобраны так, чтобы не соответствовать любой строке S.
В этом описании алгоритма кандидаты-детекторы генерировались случайным образом. Затем они подвергаются цензурированию, на соответствие любой строки «своего». В случае соответствия кандидата со «своим». Этот процесс повторяется до тех пор, пока весь детектор не будет отличаться от защищаемой системы. Однако также необходимо собрать достаточное количество детекторов.
Основным недостатком этого метода является сложность расчета процессов. Количество детекторов увеличивается экспоненциально по отношению к размеру защищаемого объекта, что требует невероятных вычислительных ресурсов. В настоящее время устранение этого недостатка привело к значительным результатам, однако сложность расчетов еще не достигла оптимального уровня.
Приведённый алгоритм основан на трех основных принципах:
- Каждый вариант алгоритма уникален и неповторим.
- Процесс обнаружения изменений является вероятностной характеристикой.
- Надежная система должна распознавать не только ранее известные варианты, но и сторонние действия.
Алгоритм иммунной сети.
Иммунная сеть представляет собой регулируемую сеть моделей и клеток, которые распознают себя даже в отсутствие антигенов. Такие структуры называются идиотипическими сетями и служат математической основой для изучения поведения иммунной системы. Эти сети реализуются в виду системы дифференциальных уравнений, описывающих динамику концентрации клонов лимфоцитов и соответствующих молекул. Теория идиотипической регуляции основана на предположении, что разные клоны лимфоцитов не изолированы друг от друга, но поддерживают коммуникацию.
Следовательно, распознавание антигена осуществляется не в одноклеточном клоне, а во всей системе, включая несколько клонов, которые взаимодействуют в одном матриксе посредством реакций антиген-антитело.
Во время иммунного ответа антиген вызывает только выработку первого набора антител. ab1. Эти антитела в качестве антигенов затем приводят к выработке второго «анти идиотипического» антитела. ab2, распознавание идиотипов в антителах ab1. Аналогичным образом получают третий набор антител.
Ключевой принцип этого алгоритма заключается в том, что одна клетка продуцирует только один тип антител. Это приводит к нескольким выводам.
- Существует аллельное исключение.
- Все антитела — подобны рецепторам на поверхности лимфоцитов, должны быть одинаковыми или, по крайней мере, иметь одинаковые легкие цепи.
- Все антитела, продуцируемые этой клеткой и ее потомками, должны иметь одинаковый идиотип.
Этот класс алгоритмов сфокусирован на сетевом графе структур, где антителами (или продуцируемыми клетками) являются узлы, а алгоритм обучения предполагает рост или сокращение расстояний между узлами на основе близости (сходства в пространстве представления проблемы).
Иммунные сетевые алгоритмы использовались в кластеризации, визуализации данных, контроле и оптимизации областей, а некоторые — для разработки искусственных нейронных сетей.
Клональный алгоритм отбора.
Теория клональной селекции объясняет, как иммунная система противодействует антигенам-противникам. Когда бактерия проникает в организм, она начинает вести деструктивную деятельность. Клетки, способные распознавать чужеродные антигены, размножаются асексуальным способом, пропорционально степени их навыков распознавания: чем лучше эти навыки, тем большее число клонов будет сгенерировано.
Во время процесса размножения клетки их отдельные образцы подвергаются мутации, которая допускает большее аффинностью с узнаваемым антигеном: чем больше сродство материнской клетки, тем меньше мутирует и наоборот. Эффективность системы гарантируется популяцией клеток с высоким аффинностью. В то же время клетки с низким аффинностью разрушаются.
Обобщенный алгоритм клонального отбора:
- Инициализация: генерация случайного начального репертуара (популяции) атрибутов строк ( иммунных клеток).
- Популяционный цикл: для каждого антигена выполнить:
2.1. Отбор: отобрать клетки, имеющие наиболее высокую аффинность к антигену.
2.2. Репродукция и генетическая изменчивость: создать копии иммунных клеток, при этом, чем лучше каждая клетка распознает, тем больше создается ее копий.
2.3. Осуществить процедуру мутации в каждой клетке инверсивно-пропорционально их аффинности: чем выше аффинность, тем меньше уровень мутации.
- Цикл: повторять шаг2, пока не будет достигнут заданный критерий останова.
В клональном алгоритме, если вы решаете конкретную проблему, вы можете использовать различные методы для представления операторов, вычисления сродства и параметров в алгоритме клонирования. Кроме того, они универсальны для решения различных типов задач, облегчая поиск решений и полностью автоматизируя поиск оптиума.
Таким образом, клональный алгоритм работает с серией «антител» (набором решений), совокупностью, которая является решением каждой конкретной проблемы. Каждая популяция оценивается по его аффинности, то есть по соответствию решению проблемы. Антитела с более низкой аффинностью смешиваются со случайно генерируемыми антителами, что позволяет нам не приближаться к локальным крайностям, а изучать целевую функцию в целом. Таким образом, происходит интерактивный процесс размножения новых популяций лучших представителей предыдущего поколения.
В последнее время ИИС активно применяются только в малом числе приложений. Применение ИИС пока еще находятся пока еще находится на начальном этапе разработке, но несмотря на это имеет большой потенциал и представляет большой интерес при решение различного вида задач, таких как: идентификация, распознавание, классификация и т.д. На сегодняшний день остается огромная часть неизученный алгоритмов, схем и механизмов ИИС, что позволяет окончательно понять принципы классификации на «своих» и «чужих».
Литература
- Брюхомицкий Ю.А. Предпосылки создания моделей компьютерной безопасности на принципах функционирования иммунных систем / Изв. ЮФУ. Технические науки. – Таганрог: Изд-во ТТИ ЮФУ, 2012.-№1.-С.159-165.
- Обухов А. В., Петренко С. А., Беляев А. В. Метод иммунного ответа на вторжения // Защита информации. INSIDE. 2009. № 4. С. 44–54.
- Чернышев Ю. О. Искусственные иммунные системы: обзор и современное состояние // Программные продукты и системы. 2014. № 4. С. 136–142