Содержание к диссертации
Введение
Глава 1. Обзор искусственных иммунных систем 10
1.1. Генетические алгоритмы – основоположники искусственных иммунных систем 10
1.2. Иммунная система и ее приложения
1.3. Двойная пластичность иммунной сети для решения практических задач 26
1.4. Выводы 29
Глава 2. Модель и алгоритм искусственной иммунной системы . 30
2.1. Свойства искусственной иммунной системы 30
2.2. Модель иммунной системы. 30
2.3. Модель искусственной иммунной системы для задачи распознавания образов
2.4. Описание используемой иммунной сети в задачах распознавания образов 36
2.5. Применение распределенных искусственных иммунных систем для решения задачи символьной регрессии 38
2.5.1. Модель используемой искусственной иммунной системы 38
2.5.2. Применение модели искусственной иммунной системы для символьной регрессии при решении задачи идентификации в экологии 41
2.6. Применение искусственной иммунной системы для сбора мусора автономным роботом 45
2.6.1. Задача сбора мусора. Описание среды и робота .45
2.7. Выводы 51
Глава 3. Алгоритм и реализация искусственной иммунной системы для решения практических задач. 53
3.1. Алгоритм реализации искусственной иммунной системы для задачи распознавания образов
3.2. Точность результатов. Тестовые примеры, сравнение с существующими методами 55
3.3. Алгоритм реализации иммунной системы для задачи символьной регрессии 62
3.4. Описание распределенной версии искусственной иммунной системы для задачи символьной регрессии 65
3.5. Точность результата. Тестовые примеры, сравнение с существующими методами 68
3.6. Алгоритм сбора мусора автономным роботом 81
3.6.1. Модуль принятия решения возврата на базу .83
3.6.2. Модуль принятия решения о дальнейшем движении 84
3.7. Выводы 88
Глава 4. Программная реализация предложенных алгоритмов . 89
4.1. Реализация алгоритма распознавания образов с помощью искусственных иммунных систем 89
4.1.1. Система классов 89
4.1.2. Хранение иммунной системы в постоянной памяти 93
4.1.3. Интерфейс пользователя для задачи распознавания образов 94
4.2. Реализация алгоритма иммунной системы для решения задачи символьной регрессии 97
4.2.1. Классы представления лимфоцитов 97
4.2.2. Классы для представления искусственной иммунной системы 103
4.2.3. Классы для представления сетевого взаимодействия 109
4.2.4. Классы для тестирования логики работы и защиты программы..
4.3. Реализация алгоритма сбора мусора автономным роботом 121
4.4. Выводы 125
Заключение 126
Список используемой литературы.
- Двойная пластичность иммунной сети для решения практических задач
- Описание используемой иммунной сети в задачах распознавания образов
- Алгоритм реализации иммунной системы для задачи символьной регрессии
- Интерфейс пользователя для задачи распознавания образов
Введение к работе
Актуальность темы исследования определяется внедрением компьютерных технологий и систем искусственного интеллекта в различные сферы деятельности человека. Эти исследования опираются на фундаментальные основы современной науки такие, как распознавание образов, нейронные сети, генетические алгоритмы, искусственные иммунные системы.
В новых, бурно развивающихся, научных направлениях нейробионического и эволюционного моделирования сочетаются методы нечеткой логики, генетических алгоритмов и иммунных систем, что открывает новые возможности перед исследователем для решения трудно-формализуемых задач в условиях неопределенности. Появились нейро-нечеткие системы: нечетко-генетические, нейрогенетические и нейро-нечетко-генетические. Дополняют этот ряд искусственные иммунные системы. Данная работа посвящена построению искусственных иммунных систем и их практическому использованию в задачах распознавания образов, символьной регрессии и управлению автономным роботом.
Исследование и анализ методической, научной литературы и периодической печати показали, что в настоящее время отсутствует единая модель искусственной иммунной системы для решения практических задач 1. Следует отметить, что для решения каждой конкретной практической или технической задачи строится своя модель искусственной иммунной системы, которая часто использует не все возможности, которые может дать теория иммунных систем. В частности, не определены свойства распределенности и децентрализованности, которые могут позволить создать распределенную версию искусственной иммунной системы. Исследование направлено на ликвидацию этого пробела - на решение задачи формализации построения искусственной иммунной системы с использованием методов искусственного интеллекта. Рассмотрены следующие практические задачи:
Задача распознавания образов. Она находит применение в автоматизации производства: освобождение человека от однообразных рутинных операций для решения других более важных задач, повышение качества выполняемых работ, повышение скорости решения задач.
Задача символьной регрессии. Она применяется в эмпирических исследованиях для восстановления зависимостей в функциональном виде и прогнозирования на основе полученных экспериментальных данных; в работе рассмотрено применение в экологии.
Задача управления автономным роботом. В последнее время появляется все больше автономных роботов, функционирующих в повседневном
1 Демидова Л.А., Титов С.Б. Исследование влияния основных параметров алгоритма функционирования искусственной иммунной сети на качество кластеризации объектов // Вестник Рязанского государственного радиотехнического университета. 2012. № 40. С. 54-60.
окружении человека – в индустриальной среде и в сфере обслуживания, проблема обхода препятствий для них является самой важной.
Диссертационная работа выполнена в рамках одного из основных научных
направлений Воронежского государственного университета «Математическое
моделирование, программное и информационное обеспечение, методы
вычислительной и прикладной математики и их применение к
фундаментальным исследованиям в естественных науках».
Цель и задачи исследования. Целью диссертационной работы является
формализация, разработка и исследование единой модели и алгоритмов
искусственных иммунных систем и их применение для решения задач
распознавания. Для достижения цели работы нужно решить следующие задачи:
-
Разработать единую модель для решения задач распознавания (распознавания одиночных символов, символьной регрессии и сбора мусора автономным роботом) на основе искусственной иммунной системы, используя тот факт, что одной из основных задач иммунной системы является распознавание вредоносных организмов и молекул.
-
Разработать единый алгоритм реализации искусственной иммунной системы для решения задач распознавания (распознавания одиночных символов, символьной регрессии и сбора мусора автономным роботом), а также его улучшенную распределенную версию, использующие свойство децентрализованности иммунной системы.
-
Провести вычислительный эксперимент с помощью разработанного программного продукта, реализующего описанные алгоритмы.
Методы исследования. При решении поставленных задач использовались методы системного анализа и математического моделирования, методы и алгоритмы искусственных иммунных систем и генетических алгоритмов, методы объектно-ориентированного проектирования и программирования.
Научная новизна. В работе получены следующие результаты, характеризующиеся научной новизной:
-
Разработана единая модель искусственной иммунной системы для решения задач распознавания (распознавания одиночных символов, символьной регрессии и сбора мусора автономным роботом).
-
Разработаны алгоритмы решения задач распознавания (распознавания одиночных символов, символьной регрессии и сбора мусора автономным роботом), в том числе распределенный алгоритм, работающий в гетерогенной вычислительной среде.
Теоретическая и практическая ценность. Работа имеет теоретический и практический характер. В работе разработана единая модель искусственных иммунных систем, описаны алгоритмы для решения задач распознавания (распознавания единичных образов, символьной регрессии и сбора мусора автономным роботом). Результаты работы были внедрены в НПК ЗАО «ИРКОС» в рамках работ по теме «Архимед», новый алгоритм решения задачи символьной регрессии позволил сократить трудозатраты на решение обратных задач восстановления вида сигнала по имеющимся измерениям. Новый
алгоритм распознавания оказался эффективным при работе с
геоинформационными системами (при рассмотрении сетевых коммуникаций).
Также практическая ценность работы заключается в возможности
использования разработанного программного обеспечения для проведения лабораторных занятий по курсу «БД и экспертные системы» из Федеральной составляющей учебного плана по прикладной математике и информатике, при выполнении курсовых и дипломных работ, магистерских диссертаций. По результатам работы получены свидетельства регистрации программы на ЭВМ «Подмножества графа» № 2010615387 от 20 августа 2010г. и № 2014618209 «Решение задачи символьной регрессии с помощью распределенных иммунных систем» от 13 августа 2014 г.
Апробация работы. Результаты работы представлялись на
международных конференциях «Актуальные проблемы прикладной
математики, информатики и механики» (Воронеж, 2010 г., 2011 г., 2013г.), на международной научной конференции «Современные методы теории краевых задач», на Воронежской мат. школе «Понтрягинские чтения» (Воронеж, 2010 г.), на международной конференции «Современные методы прикладной математики, теории управления и компьютерных технологий» (Воронеж, 2014 г.), на научных сессиях Воронежского государственного университета ( 2013 г. , 2014 г.), на IX международной научно-практической конференции «Современные информационные технологии и ИТ-образование» (Москва, 2014 г.).
Публикации. Результаты диссертации опубликованы в 11 работах. Из совместных работ в диссертацию вошли только результаты, принадлежащие лично диссертанту. Списку ВАК, в котором должны быть опубликованы основные результаты диссертации, соответствуют работы [1-2].
Структура и объём диссертации
Диссертация состоит из введения, 4-х глав, заключения, списка
используемой литературы из 82 наименований. Общий объем диссертации – 135 страниц. Работа содержит 34 рисунка, 3 таблицы, 2 приложения.
Область исследования
Диссертационная работа соответствует следующим пунктам паспорта специальности 05.13.17 – Теоретические основы информатики:
П.1. Исследование, в том числе с помощью средств вычислительной техники, информационных процессов, информационных потребностей коллективных и индивидуальных пользователей.
П.7. Разработка методов распознавания образов, фильтрации,
распознавания и синтеза изображений, решающих правил. Моделирование формирования эмпирического знания.
П.13. Применение бионических принципов, методов и моделей в информационных технологиях.
На защиту выносятся:
1. Единая модель искусственной иммунной системы для решения задач
распознавания (распознавания одиночных символов, символьной регрессии и
сбора мусора автономным роботом).
-
Алгоритмы для решения задачи распознавания (распознавания одиночных символов, символьной регрессии и сбора мусора автономным роботом), в том числе распределенная версия алгоритма.
-
Программный комплекс, реализующий разработанные алгоритмы и позволяющий провести вычислительный эксперимент.
Двойная пластичность иммунной сети для решения практических задач
Многие алгоритмы и концепции в информатике были подсказаны биологией и основаны на свойствах или функциях различных организмов. Генетические алгоритмы, эволюционные алгоритмы, нейронные сети [12, 16], иммунные системы – всё это концепции, взятые из науки о живой природе. Широко используются дарвиновская теория эволюции, селекция, такие понятия из генетики как кроссинговер и мутация, концепция приспособленности организма к окружающим условиям, моделирование структуры и процессов человеческого мозга.
Рассмотрим один из первых появившихся методов, подсказанных биологией, – генетические алгоритмы. Генетический алгоритм представляет собой эвристический метод поиска и основан на селекции лучших индивидов в популяции, опираясь на одну из теорий естественного отбора, чаще всего – Дарвина, как самую проработанную. Первые похожие опыты, симулирующие эволюцию, были проведены в 1954 году Нильсом Баричелли в Институте Продвинутых Исследований Принстонского университета. Однако родоначальником и ученым, которому генетические алгоритмы обязаны своей популярностью, можно назвать Джона Холланда, выпустившего в 1975 году книгу «Адаптация в естественных и искусственных системах». Им была сформулирована и доказана теорема схем (теорема шаблонов) – основная теорема теории генетических алгоритмов, обосновывающая их эффективность [64]. С тех пор теория генетических алгоритмов существенно продвинулась вперед и использовалась для решения широкого класса практических задача.
Рассмотрим основные понятия и концепции генетического алгоритма, пользуясь терминами из [5]. Генетический алгоритм основан на модели биологической эволюции и методах рандомизированного поиска. Такой случайный поиск можно рассматривать как реализацию простейшей модели эволюции, где случайные мутации моделируются с помощью случайных шагов решения, а отбор - удаление части неудачных вариантов.
Эволюционный поиск - последовательное преобразование одного конечного нечеткого множества промежуточных решений в другое [17]. Это преобразование и является алгоритмом поиска или самим генетическим алгоритмом. Однако необходимо отметить, что генетический алгоритм не является методом случайного поиска, он использует информацию, которая была им накоплена во время работы (эволюции).
Основные отличия генетических алгоритмов от других поисковых и оптимизационных алгоритмов:
Работают с закодированным множеством параметров задачи, а не с исходными параметрами. Поиск производится не за счет улучшения одного решения, а используя несколько альтернатив из пространства поиска. Используют саму целевую функцию, а не ее приращения для оценки решений. Применяют не детерминированный, а вероятностный анализ задачи. Стартовой точкой любого генетического алгоритма является начальная популяция, содержащая всю начальную информацию. Популяция Pt = (Рі,Р2 — Pi — J JVJ,) - представляет собой множество элементов
Pi,где С = 0,1,2,... - номер поколения. Каждый элемент популяции представляет собой одну или несколько хромосом, которые также называют особями. Хромосома состоит из генов: Ре = ( ±,-,зЛ позиция гена в хромосоме называется локусом. Обычно гены представляют собой числовые значения или символы, принадлежащие некоторому алфавиту. Часто используется двоичное кодирование, в этом случае хромосома может выглядеть вот так: Pt = (1,0,0,0,1,0,1). На основе некоторых заранее
заданных правил из популяции выбираются родительские особи, которые затем скрещиваются для получения потомков. Дети и родители в результате генерации (одного цикла эволюции), образуют новую популяцию. Одна такая генерация называется поколением. Используя термины и понятия теории эволюции, можно сказать, что эволюция популяции - это процесс чередования поколений, при котором хромосомы изменяются таким образом, чтобы каждое новое поколение было лучше приспособлено к условиям окружающей среды, чем предыдущее. Общая генетическая информация популяции называется генотипом, а вся совокупность характеристик, присущих особям популяции - фенотипом.
Каждая особь в популяции имеет определенный уровень приспособленности, который характеризуется значением целевой функции (fitness function). Эта функция используется для сравнения решений между собой и выбора наилучшего. Целью генетического алгоритма является оптимизация этой целевой функции. Генетический алгоритм анализирует и преобразовывает популяцию хромосом в соответствии с принципами естественной эволюции. Так как такой алгоритм использует только значения целевой функции для выбора решения, то, в отличие от традиционных методов оптимизации, где делается большое количество допущений для целевой функции, генетические алгоритмы свободны от них и позволяют решать те задачи, которые затруднительно решить традиционными алгоритмами.
Описание используемой иммунной сети в задачах распознавания образов
Классификация отдельных клеток и молекул является важнейшим свойством естественной иммунной сети. Условно можно выделить 2 вида такой классификации: классификация «свой – чужой» и более детальный анализ тех клеток и молекул, которые были классифицированы как чужеродные. В данной задаче первый тип использоваться не будет, так как он не находит отражения в исследуемой задаче распознавания. Второй же тип, по сути, и является именно тем механизмом, который позволит распознавать различные образы. Таким образом, изображения будут играть роль антигенов, а иммунная система на основе реакции В-лимфоцитов будет определять тип этого антигена. Однако данная задача имеет существенные особенности. Отметим важнейшие из них.
В отличие от естественной иммунной системы, количество антигенов в данной задаче невелико и известно заранее. Учитывая это, каждому лимфоциту можно приписать номер антигена, на который данный лимфоцит будет реагировать. Это позволит упростить процедуру нахождения количества лимфоцитов, специфичных именно к этому антителу.
В естественной иммунной системе классификация происходит за счет химических реакций. Для искусственной иммунной системы можно предложить следующую организацию сети и представление лимфоцитов.
Представление изображения. Монохромное изображение можно представить как матрицу размера M x N булевых значений, в которых true стоит на тех местах, которые в изображении соответствуют пикселям черного цвета, которые и формируют изображение.
Представление В-лимфоцитов. Лимфоцит, в свою очередь, можно представить как массив из P пар чисел. Каждая такая пара представляет собой координаты пикселя в изображении. Однако будем использовать немного усложненное представление лимфоцитов, в котором еще хранится информация о тех пикселях, которые должны быть белыми (незаполненными). Таким образом, лимфоцит содержит два списка координат, один из которых хранит координаты черных пикселей, а другой - координаты белых. И тогда число S можно представить в виде суммы S = S± + S2, где S± -количество черных пикселей поданного изображения (антигена), которые определяются координатами из первого списка лимфоцита; S2 - количество белых пикселей поданного изображения (антигена), которые определяются координатами из второго списка лимфоцита. Структурная модель лимфоцита изображена на рис. 2.1.
Аффинность. Введем некое число S P. Будем говорить, что лимфоцит реагирует на данный антиген, если количество элементов матрицы антигена со значениями true, определяемых номерами строк и столбцов массива пар чисел лимфоцита, больше либо равно S. На основе данного определения можно посчитать количество лимфоцитов, реагирующих на данный антиген. Так как каждый лимфоцит имеет приписанный номер антигена (идеального или образцового), то можно узнать, на какой антиген должно реагировать большинство из этих лимфоцитов. В идеальном случае (если антиген подан без искажений и иммунная сеть хорошо обучена) именно идентификатор этого антигена и будет ответом. Вместо абсолютной величины S будем использовать относительную, которая будет представлять собой минимальный процент от числа P, необходимый для того, чтобы лимфоцит среагировал на данный антиген. Введем меру аффинности данному антигену для каждого лимфоцита. Она будет представлять собой отношение количества элементов матрицы антигена, которые правильно определяются координатами из списков лимфоцита, т.е. аффинность будет представлена формулой: Где S – уже рассмотренная нами величина, а N – количество пикселей в обоих списках лимфоцита (количество пикселей, о которых лимфоцит хранит информацию). 4) Состав сети. Также можно отметить следующее упрощение модели естественной иммунной системы. Будем рассматривать только В лимфоциты, причем все из них будут использоваться для классификации каждого антигена. Т-лимфоциты в данной искусственной системе рассматриваться не будут. Таким образом, получили описание используемой искусственной иммунной системы. Применение распределенных искусственных иммунных систем для решения задачи символьной регрессии 2.5.1. Модель используемой искусственной иммунной системы
Символьная регрессия — метод построения регрессионных моделей путем перебора различных произвольных суперпозиций функций из некоторого заданного набора. Суперпозиция функций при этом называется «программой», а стохастический оптимизационный алгоритм построения таких суперпозиций называется генетическим программированием. Однако вместо обычно используемых генетических алгоритмов будет использоваться искусственная иммунная система.
Задача отыскания оптимальной структуры регрессионной модели нескольких свободных переменных формулируется следующим образом. Есть множество значений свободных переменных [х1г..., хг], где %І Є R" и соответствующих им значений функции {ylf ...,уг}. Эти два множества образуют множество исходных данных - D.
Также задано множество функций, которые будут использоваться при построении суперпозиции. Будем рассматривать только непрерывно дифференцируемые функции: g:Rn - Я, такие как sin, cos, полиномы.
Рассмотрим произвольную суперпозицию /, состоящую из не более т функций д. Требуется найти такую суперпозицию, которая бы доставляла максимум (минимум) заданного функционала p(f,D). Этот функционал и определяет целевую функцию. Его выбирают таким образом, чтобы он показывал степень приближения построенной функции к искомой. Для этого можно использовать различные метрики и расстояния, относительную или абсолютную погрешность - разницу исходных значений и значений полученной функции в этих же точках.
Таким образом, входными данными для задачи является набор точек п-мерного пространства и значений функции в этой точке. Решением задачи является функция, зависящая от п переменных, наилучшим образом аппроксимирующая исходную (в заданных точках).
Для решения задачи символьной регрессии используются алгоритмы генетического программирования [58]. Генетическое программирование -способ создания программ с помощью генетических алгоритмов [61]. В данном случае программой будет функция, представленная в виде дерева, которое и является представлением хромосомы. Операторы кроссинговера и мутации происходят над этим деревом представления функции [59], функция приспособленности - мера того, насколько хорошо данная программа (функция) решает необходимую задачу.
Алгоритм реализации иммунной системы для задачи символьной регрессии
Задача символьной регрессии является оптимизационной проблемой или проблемой поиска наилучшей функции в некотором множестве функций. Рассмотрим, что представляет собой это множество в нашей задаче. Пространством поиска является множество всех функций, которые могут быть представлены в виде дерева выражения высоты, не превышающей заданную. Операции, которые могут быть использованы в таком дереве, должны входить в множество разрешенных операторов. Это множество содержит все допустимые бинарные и унарные операции, в виде суперпозиции которых и будут представлены функции, среди которых будет выбрана наилучшая (в некотором смысле). В качестве терминальных вершин могут использоваться либо переменные, либо числовые константы. Количество допустимых переменных задано размерностью искомой функции. Интервал, в котором могут находиться числовые значения, также должен сужаться исходя из эмпирических наблюдений. Таким образом, получаем, что на размерность пространства поиска оказывают влияние следующие факторы: Максимально допустимая высота дерева. Количество возможных операторов. Размерность искомой функции. Интервал, в котором находятся числовые константы. Увеличивая хотя бы один из этих параметров, размер пространства поиска возрастает многократно.
Очевидно, что в данном случае искусственная иммунная система является разновидностью эволюционного алгоритма [6]. Эволюционный алгоритм моделирует процессы естественного отбора, мутации и воспроизводства. В иммунной системе в качестве модели отбора используется алгоритм клональной селекции, мутации - гипермутация лимфоцитов, воспроизводства - создание новых лимфоцитов и мутация существующих. Таким образом, процесс решения задачи символьной регрессии с помощью искусственной иммунной системы в плане сходимости решения идентичен сходимости эволюционного алгоритма. В силу стохастичности алгоритмов, можно заметить, что эволюционный алгоритм при размере популяции, стремящейся к бесконечности, сходится [38]. В принципе, как и любой даже полностью случайный алгоритм поиска. Однако в практических целях имеет смысл говорить о вероятности нахождения решения. Ниже будут рассмотрены примеры и для них показана вероятность нахождения решения. Также на практике интересны 2 следующих вопроса: как быстро сходится алгоритм и как избежать попадания в локальный оптимум. Быстрота получения приемлемого решения зависит от задачи и от параметров используемого алгоритма. Влияние различных факторов будет также рассмотрено далее. Против преждевременной сходимости алгоритма можно бороться только с помощью сохранения и поддержания разнообразия популяции [30]. В предлагаемой модели искусственной иммунной системы разнообразие поддерживается за счет включения в сеть случайным образом сгенерированных лимфоцитов. В естественной иммунной системе костный мозг производит новые лимфоциты. В рассматриваемой модели, по прошествии какого-то заданного количества шагов, часть наименее успешных лимфоцитов заменяется вновь созданными. Таким образом, на протяжении всего времени существования иммунной системы, происходят выбросы в пространстве поиска, что позволяет избежать попадания в локальный оптимум.
Рассмотрим примеры решения задач рассматриваемой искусственной иммунной системой. Тестовые функции для различных методов решения задачи символьной регрессии выбираются различными авторами по-разному.
В качестве простых, «игрушечных» синтетических проблем зачастую используют полиномы (степени не выше 4), тригонометрические и экспоненциальные функции. При этом, имеются в виду простые тригонометрические или степенные функции, а не их суперпозиции, т.е. те функции, для которых может быть получено точное решение и дерево представления которых состоит из малого числа вершин.
При построении сложных синтетических примеров, следует обращать внимание на следующие аспекты, усложняющие поиск решения [41]: Отрезок, на котором ищется решение (проблема, которая легко решалась на отрезке [-1, 1] может стать существенно сложнее на отрезке [-10, 10]). Использование трансцендентных функций в искомой функции. Множество доступных функций.
Также следует отметить размерность данных и достаточное наличие обучающих примеров - точек, в которых известно значение искомой функции. Для функции с малым числом аргументов, алгоритм может найти точное представление. При увеличении количества аргументов, точное отыскание вида функции может стать невозможным и будет доступна только некая аппроксимация. И при большом числе аргументов, возможным может быть лишь нахождение функции, включающей некоторые из аргументов, которые и будут значимыми.
Интерфейс пользователя для задачи распознавания образов
Для удобства представления входных данных был создан класс DataFileStorageHelper, который содержит следующие 2 статические метода: @classmethod def save_to_file(cls, filename, variables, function, pointsnumber, min_point=-5.0, max_point=5.0): Данный метод сохраняет в файл с именем filename список переменных, заданный параметром variables, а также значения функции function в pointsnumber точках, которые случайно выбираются из отрезка [min_point, max_point]. @classmethod def load_from_file(cls, filename): Возвращает кортеж, состоящий из списка переменных и значений функции в точках, представленных в следующем виде: [({V: 0, у: 0}, 0), ({V: 1, у : 0}, 10)]. Параметр filename определяет имя файла, из которого считывается эта информация. 114 Ниже представлен вызов метода сохранения файла: DataFileStorageHelper.save_to_file(4est_x_y.txt , [Y, у ], lambda х, у: х х + x y math.sin(x), 100) И получившийся файл: ху 0.9654414933901956 -2.7425419097638573 8.550308435388132 1.1840839593818888 -3.8096567768932275 11.71909594307015 -2.530973690688336 3.7411302703256357 19.338873148483717 Все юнит-тесты были вынесены отдельно в файл tests.ру. В качестве фреймворка для написания и запуска юнит-тестов использовался unittest -стандартный модуль, входящий в стандартную библиотеку. Были написаны классы для тестирования следующих сущностей: OperationTest - тесты для проверки сериализации / десериализации объектов класса Operation. ExpressionNodeTest - тесты для проверки объектов ExpressionNode: создание деревьев выражений, упрощение выражений, вычисление значения в точке, сериализация / десериализация. ExpressionTest - тесты для проверки сериализации / десериализации объектов класса Expression. FitnessFunctionTest - тесты для проверки работы объекта FitnessFunction, инкапсулирующего логику вычисления значения целевой функции. ExpressionMutatorTest - тесты для проверки работы операции гипермутации. LocalhostNodesManagerTest - тесты для проверки объекта, использующегося в качестве NodesManager. ExpressionsIrnmuneSystemTest - тест работы всей искусственной иммунной системы.
Для работы искусственной иммунной системы, которая бы работала только локально, не обмениваясь лимфоцитами с другими узлами, был создан скрипт “main.py”. В этом скрипте вместо объекта класса PeerToPeerExchanger, реализующего всю логику получения и отправки лимфоцитов другим иммунным системам, используется объект класса SimpleRandomExchanger. Метод get_lymphocytes этого класса возвращает массив случайно сгенерированных лимфоцитов. Метод set_lymphocytes ничего не делает.
Программа main.py состоит из следующих основных частей: 1) Инициализация объекта ExpressionsImmuneSystemConfig. 2) Получение входных данных: списка переменных и значений функции в точках. 3) Создание объекта SimpleRandomExchanger, который будет использоваться при создании искусственной иммунной системы. 4) Основной цикл – создание нескольких иммунных систем с заданными параметрами и получение решения. До цикла и после вызываются функции замера времени, выводится общее время работы всех итераций. Во время работы этого цикла выводится строка состояния, показывающая, какой процент от общего числа итераций уже завершился.
Пример запуска скрипта main.py и внешний вид консоли во время его выполнения представлен на рисунке 4.9: C:\Windows\system32\cnrid.exe - python main.py Рис. 4.9 Пример работы приложения После того, как будут выполнены все итерации, в консоль будут выведены решения – строковые представления объектов Expression, как показано на рисунке 4.10: C:\Wi nd ows vsy stem32\cnid .же С:\Lser s\5tas\PycharmProjects\Artifі сі alImmune5ystem python mai n.py [######№##] 10 0% 1429.6912097281572 seconds
На предыдущем рисунке показаны результаты работы алгоритма для функции f(x,y) = х2 + х у- sin(x). Параметры используемой искусственной иммунной сети: maximal height = 4 - максимально допустимая высота используемых деревьев выражения. number of lymphocytes = 200 - количество используемых лимфоцитов в иммунной системе. number of iterations = 100 - количество максимально допустимых итераций алгоритма. number_of iterations to exchange = 25 - количество итераций, после которого происходит получение новых лимфоцитов. Количество точек, в которых было задано значение функции - 100. Для работы распределенной искусственной иммунной системы был написан скрипт nodemain.py, запускаемый на каждом вычислительном узле. При запуске ему передаются следующие параметры: nodenum - номер вычислительного узла на данном компьютере. numberofnodes - количество всех узлов на данном компьютере. Рассмотрим основные действия, выполняемые скриптом nodemain.py: 1) Получение параметров командной строки (и их приведение к нужному типу). 2) Создание объекта класса LocalhostNodesManager, который управляет информацией о других вычислительных узлах, работающих на данном компьютере. 3) Создание объекта класса ExpressionsImmuneSystemConfig, который загружает параметры иммунной системы из файла с настройками. Установка параметрам нужных значений. 4) С помощью статического метода loadfrom file класса DataFileStorageHelper получить список переменных и значения функции в точках из файла с входными данными. 5) Создание объекта класса PeerToPeerExchanger, который отвечает за обмен лимфоцитами между различными вычислительными узлами. Конструктору этого класса передается ранее созданный объект класса LocalhostNodesManager.