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

Доброго времени суток, уважаемое хабро-сообщество!

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

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

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

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

Рис. 1

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

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

Рис. 2

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

В качестве мутаций используются следующие действия над деревьями выражений:

• Мутация числового значения 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 итераций. Причем, конечно, не с одним и тем же, а с разными. Таким образом, параллельная версия нашего алгоритма примет следующий вид:

Рис. 3

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

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

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