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

Автор: 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


генетические алгоритмы искусственные иммунные системы
Гость, оставишь комментарий?
Имя:*
E-Mail:


 
Свежее новое
  • Искусственный интеллект смог визуализировать 2D изображения.
  • Ученые из Вашингтона разработали модель, которая способна воссоздавать движения человека на фотографиях и картинах. Она создает для него 3D модель и
  • Искусственный интеллект, робот Вера, получил 226 млн рублей
  • ФРИИ и Кировский завод вкладывают 226 миллионов рублей в представителя «Сколкова» — компанию «Стафори», создавшую робота-рекрутера. Искусственный
  • В Москве состоялся финал PicsArt AI Hackathon, с самым крупным призовым фондом в истории
  • 30 ноября-2 декабря, в Москве прошел крупнейший хакатон в сфере искусственного интеллекта и компьютерного зрения - PicsArt AI Days. На хакатон было
  • В следующем году в Москве, заработает видеоконтроль, способный обнаружить преступников
  • Как рассказал в своем сообщении Сергей Собянин, новая система будет способна анализировать записи с видеокамер. Быстрая обработка данных позволит
  • В Москве пройдет один из крупнейших хакатонов в мире в сфере искусственного интеллекта
  • PicsArt, ведущая творческая платформа для создания контента и визуализации историй в социальных сетях с более чем 100 миллионами активных
Последние комментарии
Как работает Любовь? Квантовая связь нейронной активности Людей
Как вы считаете, возможно ли образование квантовых взаимодействий между человеком и ИИ? 
Сильный Искусственный Интеллект «Smart-MES» как основа Технологической Сингулярности России
А почему бы сразу СИИ не запустить в другую галактику, может там нет коррупции, воровства, плебейства и прочей муры, которая не только мешает
Искусственный Интеллект. Концепция развития и внедрения Искусственного Интеллекта (Искусственной Аналитики)
Согласен. проблема ИИ не в наборе задач. Главная проблема - познание процесса мышления как феномена физиологии головного мозга человека.
Сильный Искусственный Интеллект «Smart-MES» как основа Технологической Сингулярности России
Господа - непубликация моего вполне невинного предложения о пересборке Win-10  в удобопользуемый вид, со 146% вероятностью характеризует "ценность"
Сильный Искусственный Интеллект «Smart-MES» как основа Технологической Сингулярности России
Если Ваш SM столь замечателен-могуч-адаптивен, что вот-вот пристроит нам сингулярность, то нельзя-ли ему решить ничтожную, но практическую задачу -
Мы в социальных сетях
Статистика
1  
Всего статей 1538
3  
Всего комментариев 72
0  
Пользователей 63