Использование искусственных иммунных систем для решения задачи символьной регрессии

Автор: JustStas

Представляю на ваш суд статью, написанную по мотивам моей магистерской работы (факультет прикладной математики, информатики и механики Воронежского ГосУниверситета). Ее тема «Применение распределенных искусственных иммунных систем для решения задачи символьной регрессии». Постараюсь коротко (но содержательно) рассмотреть основные понятия искусственных иммунных систем и мой подход к их реализации для решения задачи символьной регрессии – восстановления символьного представления функции по заданному множеству ее значений в некоторых точках. Программа была написана на языке Python (версии 3.3), исходники доступны на Github.

Основные понятия и описание иммунной системы

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

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

Лимфоциты – клетки, из которых состоит иммунная система. В организме различают B-лимфоциты, которые являются и основными носителями иммунной памяти, и основными «боевыми единицами», обеспечивающими отпор врагу (антигену), и Т-лимфоциты, которые могут усиливать или подавлять реакцию B-клеток. В подавляющем большинстве работ рассматриваются только В-лимфоциты, мы тоже будем рассматривать только их. Очевидно, что в зависимости от решаемой задачи лимфоциты могут представлять собой различные объекты рассматриваемой области. В нашей задаче (поиска символьного представления функции) лимфоцит будет представлять собой одно из возможных решений задачи – некоторую функцию, представленную деревом выражения (например, таким как на рисунке 1). В этом дереве могут использоваться различные операции (+, -, *, /, sin, cos), числа, переменные, максимальное количество которых задано (чтобы ограничить глубину поиска). Если пользоваться терминами генетических алгоритмов, лимфоцит – это просто особь.

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

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

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

  • Мутация числового значения 2*x →2,23*x

  • Мутация переменной 2*(x+y)*x →2*(x+y)*y

  • Мутация унарного оператора sin(x)*y→cos(x)*y

  • Мутация бинарного оператора x+y →x-y

  • Мутация подвыражения (поддерева дерева выражения) 2*(x+y)→2*sin(x)

Добавим параллелизм

Конечно, хотелось бы добавить возможность распараллелить эту систему для функционирования на нескольких машинах. В этом случае от OpenMP пришлось отказаться именно по этой причине (запуск нужен на нескольких машинах), от MPI – по другой: хотелось бы, чтобы вычислительные узлы могли добавляться / выходить из строя / выключаться во время работы всей системы, и при этом система продолжала бы функционировать. Добиться такого можно с помощью создания такой «топологии», какая используется в p2p. Один узел знает о нескольких соседях, обменивается только с ними. Конечно, похоже на велосипед, но для проверки самой возможности распараллеливания данной модели – самый раз.

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

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

Реализация и код

Я не Python программист (а очень даже C#), но Python мне близок и очень нравится, сдавал на нем задачи для численных методов (спасибо numpy, scipy, matplotlib), писал скрипты для себя. Пару книжек прочитал (Lutz, Dive into python), PEP-8, конечно же, но думаю, что код для хороших Python программистов выглядит не очень аппетитно. По времени вышло где-то столько же, сколько я писал бы это на C#. Использовал unittest, для проверки работоспособности есть скрипты main.py, local_node.py и local_server.py. Все замечания / дополнения / советы очень приветствуются, хотелось бы получить хоть какую-нибудь обратную связь.

Проект на Github

Вот так выглядит работа программы (для функции x*x+sin(sin(x))*x*y, значения функции заданы в 100 точках, 4 вычислительных узла, 200 итераций алгоритма, обмен после каждых 30 итераций):

Литература и ссылки:

  1. Искусственные иммунные системы и их применение / [под ред. Дасгупты] – М.: Физматлит 2006 – 344 с.
  2. Colin G. Johnson Artificial Immune Systems Programming for Symbolic Regression / Colin G. Johnson // Genetic Programming: 6th European Conference. – 2003. – P. 345–353 – ISBN=3-540-00971-X


генетические алгоритмы искусственные иммунные системы
Если у вас есть статья, заметка или обзор, которыми вы хотите поделиться с аудиторией нашего сайта, присылайте информацию на: neuronus.com@yandex.ru.
Гость, оставишь комментарий?
Имя:*
E-Mail:


Последние комментарии
Дрон-камикадзе и ракеты с искусственным интеллектом: как в России создали умные боеприпасы и планируют применять в деле
Современная микроэлектроника, включая микроконтроллеры и процессоры для современных ПК, является продуктом высокотехнологического производства и
Как работает Любовь? Квантовая связь нейронной активности Людей
ребят,вот вам смешно,а квантовая связь влюбленных то существует.и я не шучу. мой парень видел глюки и в этих глюках присутствовала я.(если что,в
Почему космос не имеет начала и конца: комментарии учёных
Земля находится трёх слонах, которые стоят на черепахе
Судьба ледокола «Арктика» остается неопределенной после повреждения одного из двигателей
Народ теперь что бы накачать мышцы и убрать лишний жир можно без спорта и диет, просто надел и забыл. Опробовал лично и результат удивил уже через
Сообщение о покупке водородной яхты Билом Гейтсом оказалось ложным
Народ теперь что бы накачать мышцы и убрать лишний жир можно без спорта и диет, просто надел и забыл. Опробовал лично и результат удивил уже через
Мы в социальных сетях
Статистика
0  
Всего статей 2562
0  
Всего комментариев 1031
0  
Пользователей 264