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

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

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

генетические алгоритмы искусственные иммунные системы

Источник: https://neuronus.com/stat/50-ispolzovanie-iskusstvennykh-immunnykh-sistem-dlya-resheniya-zadachi-simvolnoj-regressii.html

Генетическое программирование

Этот раздел является одним из важнейших приложений ГП. Данный термин подчеркивает то, что здесь объектом поиска является символьное описание модели, в отличие от множества коэффициентов в стандартных методах.

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

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

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

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

Как уже отмечалось, символьная регрессия на основе ГП не использует некоторую заранее предопределенную форму функции. Здесь функцияпредставляется древовидной структурой и строится эволюционным методом с использованием определенного функционального и терминального множеств.

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

Совет

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

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

Далее рассмотрим детально пример использования символьной регрессии из [5] для аппроксимации данных, представленных в табл.6.9. Необходимо найти функцию, которая аппроксимирует с заданной точностью эти “экспериментальные” данные. Для решения задачи определим в соответствии с вышесказанным:

Терминальное множество: переменная x и константы в диапазоне [-5,5];

Функциональное множество: арифметические функции(защищенное деление).

Koza [2] ввел следующую удобную и “прозрачную” форму для перечисления параметров, которая представлена в табл.6.10.

Далее приведем некоторые полученные экспериментальные данные результатов эволюции для различных запусков программ из [5]. В начальной популяции после инициализации лучшая особь представлена деревом рис.6.15, которая реализует (не минимальным образом !) функцию.В последующих рисунках рис.6.16,рис.6.17,рис.6.18,рис.6.

19,рис.6.20 представлены лучшие особи последующих поколений. Здесь в первом поколении лучшая особь реализует.В последующих рисунках рис.6.16,рис.6.17,рис.6.18,рис.6.19,рис.6.20 представлены лучшие особи последующих поколений. Здесь в первом поколении лучшая особь реализуети соответствующее дерево рис.6.16 сильно избыточно.

Таблица 6.9.

№ВходВыход
1 0.000 0.000
2 0.100 0.005
3 0.200 0.020
4 0.300 0.045
5 0.400 0.080
6 0.500 0.125
7 0.600 0.180
8 0.700 0.245
9 0.800 0.320
10 0.900 0.405

Аналогично во втором поколении лучшая особь реализует функциюи дерево тоже сильно избыточно. Наконец в третьем поколении получена лучшая особь, которая дает оптимальное решение в простейшей форме.

Рис. 6.15. Лучшая особь в поколении 0.
Рис. 6.16. Лучшая особь поколения 1

Таблица 6.10.

ПараметрыЗначения
Цель: Эволюция функции, аппроксимирующей данные Табл.6.6
Терминальное множество Переменная, Целые от –5 до +5
Функциональное множество ADD, SUB, MUL, DIV
Мощность популяции: 600
Вероятн. кроссинговера: 0.90
Вероятность мутации: 0.05
Отбор родителей: турнирный, с мощностью тура 4
Максимальное число поколений: 100
Максимальная глубина после кроссинговера: 200
Максимальная глубина мутации: 4
Метод инициализации: Растущая

Рис. 6.17. Лучшая особь поколения 2.
Рис. 6.18. Лучшая особь поколения 3.

В табл.6.11 для сравнения представлены значения функций лучших особей первых поколений (0-3).Отметим, что была выполнена еще одна итерация (4-е поколение). На рис.6.

19 представлена лучшая особь четвертого поколения, которая также реализует функцию, но избыточность соответствующего дерева выросла.

Конечно, для данного примера можно было использовать и классические методы регрессии, но он носит чисто иллюстративный характер.

Рис. 6.19. Лучшая особь поколения 4.

Обратите внимание

Интересным примером является машинный вывод третьего закона Кеплера на основе символьной регрессии. Итак, есть экспериментальные данные, которые связывают радиус и период обращения планет солнечной системы, которые представлены в табл.6.12 (в астрономических единицах).

Напомним, что согласно закону Кеплера, период обращения планеты пропорционален корню квадратному из третьей степени радиуса орбиты, где– радиус орбиты планеты (чаще используется формулировка). Для решения этой задачи с помощью символьной регрессии возможные параметры представлены в табл.6.13. На рис.6.

20 представлено полученное с помощью символьной регрессии дерево, которое представляет закон Кеплера.

Во многих работах [2,5] приведены результаты для более сложных зависимостей, но они требуют для представления результатов большого объема.

Таблица 6.11.

1 0.000000 0.000000 0.000000 0.000000 0.000000
2 0.005000 0.033333 0.017544 0.002375 0.005000
3 0.020000 0.066667 0.037037 0.009863 0.020000
4 0.045000 0.100000 0.058824 0.023416 0.045000
5 0.080000 0.133333 0.083333 0.044664 0.080000
6 0.125000 0.166667 0.111111 0.076207 0.125000
7 0.180000 0.200000 0.142857 0.1222140 0.180000
8 0.245000 0.233333 0.179487 0.188952 0.245000
9 0.320000 0.266667 0.222222 0.287024 0.320000
10 0.405000 0.300000 0.272727 0.432966 0.405000
Таблица 6.12.

ПланетаРадиус -Период –
Меркурий 0,387 0,24
Венера 0,723 0,62
Земля 1,000 1,000
Марс 1,524 1,88
Юпитер 5,203 11,86
Сатурн 9,569 29,46
Уран 19,309 84,01
Нептун 30,284 164,79
Плутон 39,781 247,69

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

Рис. 6.20. Дерево, представляющее третий закон Кеплера

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

Она широко применяется в эконометрике при решении задач моделирования и прогнозирования.

Кроме этого, символьная регрессия с успехом применяется в символьных вычислениях, включая символьное дифференцирование и интегрирование, решение дифференциальных и интегральных уравнений в символьном виде и т.п.[2].

Источник: http://www.intuit.ru/studies/courses/14227/1284/lecture/24178?page=10

Применение метода искусственных иммунных систем в задачах поиска условного экстремума функций – pdf

1 202 НАУЧНЫЙ ВЕСТНИК МГТУ ГА 84 УДК 59.6 ПРИМЕНЕНИЕ МЕТОДА ИСКУССТВЕННЫХ ИММУННЫХ СИСТЕМ В ЗАДАЧАХ ПОИСКА УСЛОВНОГО ЭКСТРЕМУМА ФУНКЦИЙ А.В. ПАНТЕЛЕЕВ, Д.В. МЕТЛИЦКАЯ Рассмотрена задача поиска условного глобального экстремума функций многих переменных методом искусственных иммунных систем.

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

Введение Метод искусственных иммунных систем (ИИС) относится к метаэвристическим методам поиска и является представителем эволюционных методов. Основные принципы работы метода искусственных иммунных систем изложены в [-4]. Одной из наиболее популярных областей приложения ИИС является оптимизация многопараметрических функций [5].

Важно

Подобно другим методам эволюционных вычислений [6], ИИС не гарантируют обнаружения глобального решения, но успешно работают, когда требуется найти достаточно «хорошее» решение за приемлемое время.

Читайте также:  Нейросеть определяет уровень интеллекта человека по томографии мозга

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

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

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

При помощи разработанного комплекса решено несколько тестовых примеров, демонстрирующих эффективность метода. Метод ИИС применяется к широкому кругу прикладных задач проектирования сложных авиационно-космических систем, в том числе к задачам поиска оптимальных траекторий летательных аппаратов различных типов [7].. Постановка задачи Дана целевая функция f ( x) = f ( x, x2,…, x ), определенная на множестве допустимых решений D R. Требуется найти глобальный условный минимум функции f ( x ) на множестве D, то есть такую точку x* D, что f ( x*) = mi f ( x), () x D

2 Применение метода искусственных иммунных систем 55 где x = ( x, x2,…, x ) T, D = { x xi [ ai, bi ], i =,2,…, }. Функция f ( x ) может быть многоэкстремальной, поэтому искомое решение в общем случае неединственное. Задача поиска максимума функции сводится к задаче поиска точки x% * D, такой что f ( x% *) = mi f ( x). x D 2.

Стратегия поиска решения Поясним некоторые термины, используемые в иммунологии. Иммунной системой живого организма называется подсистема, объединяющая органы и ткани, которые защищают организм от заболеваний.

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

Совет

Для того чтобы организм смог защититься от антигенов, в нем при помощи специальных иммунных клеток вырабатываются антитела. Антителом называется вещество, которое распознает антиген и способствует его уничтожению. Если иммунные клетки выработали антитела, которые смогли распознать антиген, то информация об этих антителах сохраняется в клетках памяти.

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

В методе искусственных иммунных систем рассматриваемая целевая функция f ( x ) эквивалентна природному понятию приспособленности иммунной клетки к борьбе с антигенами, т.е. способности клетки вырабатывать антитела. Поэтому будем называть целевую функцию f ( x ) функцией приспособленности. Вектор параметров x = ( x, x2,…

, x ) T целевой функции в ИИС называется иммунной клеткой, которая вырабатывает антитела. Каждый вектор x = ( x, x2,…, x ) T D является возможным решением поставленной оптимизационной задачи.

При решении задачи () используются конечные наборы T I = x = ( x, x, K, x ), =,2,, p} D возможных решений, называемые популяциями, где { 2 K x иммунная клетка с номером ; p переменный размер популяции. Применение метода искусственных иммунных систем сводится к исследованию множества D при помощи перехода от одной популяции к другой.

Чем больше значение целевой функции f ( x ), тем более им- мунная клетка x приспособлена, т.е. способна вырабатывать необходимые антитела, и подходит в качестве решения. Метод ИИС имитирует эволюцию начальной популяции T I 0 = { x, =,2, K, Ip x = ( x, x2, K, x ) D}, где Ip начальный размер популяции представляет собой итерационный процесс.

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

3 56 А.В. Пантелеев, Д.В. Метлицкая Создание начальной популяции Клонирование Мутация Селекция, формирование новой популяции Сокращение популяции Проверка условий окончания поиска Нет Добавление новых клеток в популяцию Да Ответ (выбор решения из последней популяции) Рис.. Общая схема работы метода ИИС 3. Алгоритм Шаг. Создание начальной популяции..

Задать количество иммунных клеток в популяции, число родительских клеток, выбираемых из популяции в ходе селекции s, число клеток в популяции с наихудшим значением функции приспособленности d, максимальное количество итераций K, параметр операции клонирования β или с, параметр мутации r..2. Сгенерировать клеток начальной популяции на множестве D, используя равномерный закон распределения.

Обратите внимание

Положить k = 0 (счетчик итераций)..3. Для всех клеток в популяции найти значение их функции приспособленности f ( x ), =,…, и среднюю приспособленность популяции f k = f ( x ). = Результатом шага является сформированная начальная популяция I = { x = ( x, x 2, K, x ) T, =,2, K, } D. Шаг 2. Клонирование. 2..

Упорядочить клетки в популяции по возрастанию соответствующего им значения () ( ) () ( ) функции приспособленности: f ( x ),…, f ( x ), где f ( x ) = f mi, f ( x ) = fmax.

Выбрать из упорядоченной популяции s родительских клеток с наилучшим соответствующим им значением функции приспособленности ( s первых клеток) Для каждой родительской клетки используют два варианта клонирования: ) «пропорциональное» – для каждой клетки с номером в упорядоченной популяции генерируется клонов, где β =, =,…, p, β – параметр операции клонирования;

4 Применение метода искусственных иммунных систем 57 2) «равномерное» – для каждой клетки генерируются клонов, где = с, с – параметр операции клонирования. Результатом шага 2 является популяция, состоящая из первоначальных клеток и клонов s s родительских клеток, т.е. всего + клеток. = Шаг 3. Мутация.

Для каждой родительской клетки с номером выполнить процедуру мутации для всех ее, клонов. Для этого каждую координату c c c x i клона заменить на y, i : ) используя равномерный закон распределения на отрезке [0;], сгенерировать число u ; 2) если u > 0.5, то положить c, c, i i i i x, y = x + U (0; b x ) r, если u 0.5, то y = x U(0; x a ) r, c, c, i i i i где =,…

,, c =,…,, i =,…,, U ( a; b) – случайная величина, равномерно распределенная на отрезке [ a; b ], r – параметр мутации; c, 3) если yi [ ai ; bi ], то процедуру повторить. Результатом шага 3 является популяция, состоящая из первоначальных клеток и клоновмутантов s родительских клеток, т.е. всего + s клеток. = Шаг 4. Селекция, формирование новой популяции. с, 4..

Вычислить значение функции приспособленности для каждого клона-мутанта f ( y ), c =,…,, =,…, p Для каждой родительской клетки x,,…, = s, среди ее клонов-мутантов найти клетку с наименьшим значением функции приспособленности f ( ) mi y.

Если ( ) ( f ) mi y < f x, то заменить в новой популяции родительскую клетку клоном-мутантом у, а иначе - оставить ро- дительскую клетку x Положить k = k +. Результатом шага 4 является новая популяция из клеток. Шаг 5. Сокращение популяции. Удалить из популяции d клеток с наихудшим значением функции приспособленности.

Результатом шага 5 является сокращенная популяция, состоящая из d клеток. Шаг 6. Проверка условий окончания поиска. Если k = K, то поиск завершить, перейти к шагу 8. Если k < K, то поиск продолжить, перейти к шагу 7. Шаг 7. Добавление новых клеток в популяцию. 7..

Важно

Сгенерировать d клеток начальной популяции на множестве D, используя равномерный закон распределения Вычислить значение функции приспособленности новых клеток и среднюю приспособленность популяции f = f ( x ). k = 7.3. Перейти к шагу 2. Результатом шага 7 является дополненная популяция, состоящая из клеток. Шаг 8. Выбор решения из последней популяции.

5 58 А.В. Пантелеев, Д.В. Метлицкая Закончить работу алгоритма. В качестве решения (приближенного) задачи f x * ( ) = mi f ( x) x D выбрать клетку с наименьшим значением функции приспособленности из текущей популяции x x% = arg mi f ( x ). =,…, 4.

Программное обеспечение На основе изложенного алгоритма сформирован комплекс программных средств. Среда разработки Microsoft Visual Studio 200, язык программирования C#.

Комплекс позволяет: ) выбирать тип оптимизируемой функции из заданного списка и область ее определения; 2) задавать параметры метода; 3) получать результаты работы метода сразу или выполнять работу по шагам; 4) получать графические результаты после окончания работы метода или при работе по шагам, после выполнения очередного шага; 5) получать график изменения средней и наилучшей приспособленности популяции при переходе от одной популяции к другой; 6) сравнивать результаты работы метода с точным решением; 7) настраивать параметры изображения результатов; 8) генерировать и сохранять отчет работы. Возможности комплекса позволяют изучить алгоритм работы метода искусственных иммунных систем, а также влияние параметров метода на результаты его работы. В список выбираемых функций включены стандартные многоэкстремальные тестовые функции двух переменных, для которых известно точное решение. 5. Примеры работы алгоритма Пример. Рассмотрим функцию Швефеля f ( x, y) = xsi( x ) + y si( y ) (рис. 2а). Функция имеет глобальный экстремум f ( x ; y ) = 837,9658 в точке ( x*; y *) = (42,9687;42,9687). Зададим область определения ( x, y) [ 500;500]. Выберем следующие параметры алгоритма: размер популяции Ip = 00 ; максимальное количество популяций K = 00 ; тип клонирования «равномерное»; количество клонируемых клеток s = 00 ; параметр клонирования β = 0 ; параметр мутации r = 0, 0; количество удаляемых клеток с наихудшей приспособленностью d = 0. а б Рис. 2. Изображение: а – функции Швефеля; б – функции Аклея На рис. 3 представлена начальная ( k = 0 ), промежуточные ( k = 40, k = 50) и конечная ( k = 00 ) популяции клеток.

6 Применение метода искусственных иммунных систем 59 Результаты работы метода ИИС: клетка с наилучшей приспособленностью ( x ; y ) = (42,0005; 42,005) ; наилучшая приспособленность f ( x ; y ) = 837,9654 ; отклонение от точного решения = 0, k = 0 k = 40 k = 50 k = 00 Рис. 3.

Начальная, промежуточные и конечная популяции в примере ( s = 00, d = 0 ) Изменим параметры алгоритма. Пусть теперь количество удаляемых клеток с наихудшей приспособленностью d = 50 и количество клонируемых клеток s = 50. На рис.

4 представлена начальная ( k = 0 ), промежуточные ( k = 0, k = 60 ) и конечная ( k = 00 ) популяции клеток.

Результаты работы метода ИИС: клетка с наилучшей приспособленностью ( x ; y ) = (420,9497; 420,9956) ; наилучшая приспособленность f ( x ; y ) = 837,9656 ; отклонение от точного решения = 0, k = 0 k = 0 k = 60 k = 00 Рис. 4. Начальная, промежуточные и конечная популяции в примере ( s = 50, d = 50 )

Совет

7 60 А.В. Пантелеев, Д.В. Метлицкая Анализируя работу метода ИИС, следует отметить, что при сокращении популяции на каждой итерации алгоритма клетки в популяции постепенно выходят из глобальных экстремумов, в то время как при отсутствии сокращения, метод находит локальные экстремумы функции.

Однако, сравнивая результаты работы метода с точным решением, в обоих случаях можно сделать вывод, что метод ИИС эффективно справляется с данной задачей. Пример 2. Рассмотрим функцию Аклея, имеющую более острый пик в глобальном экстремуме (рис. 2б): 2 2 ( x + y ) (cos(2 π x) + cos(2 π y)) f ( x, y) = 20 e + 20e + e.

Функция имеет глобальный экс- тремум f ( x ; y ) = 0 в точке ( x*; y *) = (0;0). Зададим область определения ( x, y) [ 0;0].

Выберем следующие параметры алгоритма: размер популяции Ip = 50 ; максимальное количество популяций K = 500 ; тип клонирования «равномерное»; количество клонируемых клеток в первом случае s = 50, а во втором s 2 = 30 ; параметр клонирования β = 0 ; параметр мутации r = 0,0; количество удаляемых клеток с наихудшей приспособленностью в первом случае d = 0, а во втором d 2 = 20. Результаты работы метода ИИС в первом случае представлены на рис. 5. Отклонение от точного решения = 5,382. Результаты работы метода ИИС во втором случае представлены на рис. 6. Отклонение от точного решения = 0, Как видно из приведенного примера, при сокращении популяции на каждой итерации метод ИИС работает гораздо эффективнее. При отсутствии сокращения в течение работы алгоритма к популяции не добавляются новые особи, а клонируются и мутируют только те, которые были созданы в начальной популяции. Это приводит к тому, что область определения функции слабо исследуется, поэтому на примерах, подобных функции Аклея, где глобальный экстремум находится на остром пике, метод ИИС без сокращения популяции работает неэффективно. Если же на каждой итерации проводить сокращение и добавлять новые клетки в популяцию, то это приведет к лучшему исследованию области определения функции и более эффективной работе алгоритма. Рис. 5. Конечная популяция в примере 2 ( s = 50, d = 0 ) Рис. 6. Конечная популяция в примере 2 ( s 2 = 30, d 2 = 20 ) Заключение Сформирован пошаговый алгоритм для метода искусственных иммунных систем, на основе которого разработан комплекс программных средств. При помощи разработанного комплекса решено несколько тестовых примеров, демонстрирующих эффективность метода. Комплекс позволяет изучить работу метода ИИС, исследовать влияние параметров на результаты работы, а также исследовать эффективность метода при поиске глобального экстремума сложных многоэкстремальных функций двух переменных.

8 Применение метода искусственных иммунных систем 6 ЛИТЕРАТУРА. Ishida Y., Hirayama H., Fuita H., Ishiguro A., Mori K., Immuity-Based Systems-Itelliget Systems by Artificial Immue Systems, Coroa Pub., Co. Japa, Дасгупт Д. Искусственные иммунные системы и их применение. М.: ФИЗМАТЛИТ, de Castro L.., Vo Zube F. J.

, Learig ad Optimizatio Usig the Cloal Selectio Priciple, IEEE Trasactios o Evolutioary Computatio, Special Issue o Artificial Immue Systems, vol. 6,. 3, pp , de Castro L., Timmis J., A Artificial Immue etwork for Multimodal Fuctio Optimizatio, Proceedigs of IEEE Cogress o Evolutioary Computatio, vol., pp , Пантелеев А. В., Летова Т.А. Методы оптимизации в примерах и задачах. – М.

Читайте также:  Тестирование искусственного интеллекта microsoft тау с треском провалилось

: Высшая школа, Пантелеев А.В. Метаэвристические алгоритмы поиска глобального экстремума. – М.: Изд-во МАИ-ПРИНТ, Остославский И.В., Стражева И.В. Динамика полета. Траектории летательных аппаратов. – М: Машиностроение, 969. APPLYIG OF THE METHOD OF THE SYTHETIC IMMUE SYSTEMS I A PROBLEMS OF SEARCHIG COMDITIOAL EXTREMUM OF THE FUCTIO Pateleev A.V., Metlitskaya D.V.

The problem of searchig coditioal local extremum of the fuctio o may variables by usig the method of the sythetic immue systems is cosidered. The algorithm to solve this problem is formed, the software based o this algorithm is developed. The examples to show the efficiecy of the formed algorithm are give.

Key words: a method of the sythetic immue systems, coditio local extremum of the fuctio, algorithm. Сведения об авторах Пантелеев Андрей Владимирович, 955 г.р., окончил МВТУ им. Н.Э.

Баумана (978), доктор физико-математических наук, профессор, заведующий кафедрой математической кибернетики МАИ, автор более 50 научных работ, область научных интересов методы синтеза оптимальных нелинейных систем управления, методы оптимизации. Метлицкая Дарья Вадимовна, окончила МАИ (20), аспирантка МАИ, автор научных работ, область научных интересов методы оптимизации, численные методы, математическая статистика.

Источник: https://docplayer.ru/58975197-Primenenie-metoda-iskusstvennyh-immunnyh-sistem-v-zadachah-poiska-uslovnogo-ekstremuma-funkciy.html

Литвиненко В.И., Дидык А.А., Захарченко Ю.А. Компьютерная система для решения задач классификации на основе модифицированных иммунных алгоритмов

Введение. Искусственные иммунные системы (ИИС) являются новым направлением в исследованиях вычислительного интеллекта (ВИ).

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

Среди различных механизмов биологической иммунной системы при разработке ИИС наиболее часто используются модель иммунной сети и клональный отбор [2].

Целью работы является разработка  компьютерной системы для решения задач распознавания и классификации с учителем, предназначенной для исследования свойств алгоритмов клонального отбора и искусственной иммунной сети.

Искусственные иммунные системы для решения задач распознавания. В настоящее время существует ряд компьютерных систем предназначенных для решения задач классификации на основе иммунных алгоритмов.

К наиболее известным можно отнести WEKA (Waikato Environment for Knowledge Analysis) [5]. Система, основанная на использовании нейронной сети и искусственной иммунной сети для решения задач классификации (http://wekaclassalgos.sourceforge.

Обратите внимание

net/), также включает реализованный на данной платформе Джейсоном Браунли [6] алгоритм клонального отбора. Система реализована на языке Java.

В предлагаемой авторами системе реализована способность иммунной системы распознавать и обучаться для решения задач классификации и распознавания.

Постановка задачи классификации. Для формальной постановки задачи классификации вектор признаков  является описанием объектов, которое является модулем преобразования.

Классом называется некоторое подмножество  множества . Обучающей выборкой называется набор , для которых , то есть это известная информация об отображении .

Задача классификации заключается в построении функции классификации, приближающей отображение , основываясь на обучающей выборке .

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

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

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

– евклидово расстояние  (используется при вещественном или целочисленном кодировании атрибутов)

; (1)

– манхэттенское расстояние  (также используется при вещественном или целочисленном кодировании)

. (2)

Более детально теория  клонального отбора и искусственной иммунной сети, их формальное представление и алгоритмы описаны в работах [2,3,4].

Модифицированный алгоритм клонального отбора. Пошаговая реализация алгоритма клонального отбора представлена на рис.1. Основным отличием данной реализации алгоритма от классической для решения задач классификации есть оператор мутации. В связи с большим объемом данных при решении задач распознавания мы столкнулись с проблемой быстроты работы алгоритма.

Рис. 1 Алгоритм клонального отбора для решения задач классификации

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

(3)
(4)

Формула (3) используется в случае, если расстояние между антителом и антигеном вычисляется как Евклидово расстояние, формула (4) – если расстояние вычисляется как Манхеттеновское расстояние.

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

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

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

, (5)

где Nc – общая сумма клонов, произведенных для каждого из антигенов; b – фактор умножения; N – общая сумма антител; round – оператор, который округляет аргумент к самому близкому целому числу.

Каждый слагаемый этой суммы соответствует размеру клона каждого отобранного антитела, например, для N=100 и b=1, антитело с самой высокой афинностью (i=1) производит 100 клонов, в то время как второе по афинности антитело производит 50 клонов и т.д.

Модифицированный алгоритм иммунной сети.

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

– аффинность связи «антиген-антитело» (Ag-Ab) – степень различия;

– аффинность связи «антитело-антитело» (Ab-Ab) – степень подобия.

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

– ввод данных;

– вывод информации о результатах тестирования;

– управление процессом тестирования;

– настройку параметров подсистемы обучения искусственной иммунной сети.

Блок формирования искусственной иммунной сети для решения задачи классификации. Данный блок получает на вход записи, содержащие значения индивидуумов для конкретной задачи классификации. В соответствии с заданными оператором настройками и выбранным алгоритмом обучения, осуществляет формирование пула памяти искусственной иммунной сети согласно входному пулу индивидуумов.

Блок обработки результатов обучения ИИС. Осуществляет формирование статистической отчетности по результатам обучения искусственной иммунной сети на всех его этапах и созданию пула клеток памяти. К такой отчетности относится статистика созревания аффинности на каждой итерации обучения сети, количество клеток памяти сети и т.д.

Рис. 2 Алгоритм искусственной иммунной сети для решения задач классификации.

База данных ИИС. База данных хранит следующие элементы:

– клетки памяти искусственной иммунной сети для соответствующей задачи классификации;

– статистические данные, полученные в процессе обучения искусственной иммунной сети.

Блок диспетчера тестирования ИИС. Блок имеет следующие функциональные характеристики:

– загрузка тестирующих записей из внешней базы данных;

– прогонка работы ИИС на загруженных данных;

– формирование отчетности по результатам решения задачи классификации.

Модульная структура системы. На рис. 4 показана модульная структура ИС для решения задачи классификации.

Рис. 3 Концептуальная структура компьютерной системы

Рис. 4 Модульная структура системы

Модуль ais.dll содержит библиотеку классов ИИС. Каждый контролируемый параметр системы использует отдельный экземпляр ИИС. Модуль td.dll выполняет задачу проведения проверки работы ИИС на решение задачи классификации.

В его функции входит получение и обработка записей для классификации из внешней базы данных и формирование результатов тестирования. Данные накапливаются в базе и выбираются оттуда по мере необходимости посредством запросов из модуля ais.dll. Модуль ui.dll является графическим интерфейсом ИС.

Для хранения баз данных используются электронные таблицы в формате CSV.

Функционирование программы и параметры настройки. Используются следующие параметры для обучения :

Thesizeofpopulation – размер популяции антител, формируемый на каждом шаге итерации для каждого индивидуума из обучающей выборки;

Рис.5 Общий вид интерфейса системы

Numberofthebestindividums – число антител с наилучшей афинностью из популяции антител, которое не будет заменено на следующем шаге итерации случайными числами. Расачитывается как процентное соотношение от размера популяции антител.

Numberofgenerations – число генераций для каждого антитела из обучающей выборки.

Mutationfactor – фактор мутации антитела, который влияет на скорость приближения генерируемого антитела к обучающему. Допускается значение фактора в пределе 1-30. Чем больше значение фактора мутации, тем больше значение, на которое изменяется антитело на шаге мутации:

(5)

где ρ – параметр контролирующий сглаживание инверсии экспоненциала, D* – норамлизированная афинность, расчитанная как D*=D/Dmax.

Inpute – нормированный порог аффинности.

Mutationpercent – параметр, задающий процент гипермутации антитела. Задается в процентном соотношении. Указывает число генов антитела, которые подлежат мутации. Количество изменяемых генов расчитывается следующим образом:

(6)

где MG – количество изменяемых генов, МР – заданный процент от общего количества генов антитела, round – оператор, который округляет аргумент к самому близкому целому числу.

Betakoef – фактор умножения для операции клонирования. Общее количество клонов, сгенерированных для всех n выбранных антител, устанавливалась в соответствии с формулой (5).

Mutationupdating – включатель процедуры модифицированной мутации антител. Для ускорения процесса мутации было предложено для каждого гена антитела устанавливать весовой коэффициент формулы (3) и (4).

Рис.6 Интерфейс настройки основных параметров
клонального алгоритма и искусственной иммунной сети

Affinityupdating – включатель процедуры модифицированного расчета афинности антител. Афинность расчитывается по следующей формуле:

(10)

где – афинность между i-м антителом и j-им антигеном; – расстояние между i-м антителом и j-им антигеном (нормированное от 0 до 1: 0 – максимально возможное расстояние, 1 – полное совпадение координат); – количество антигенов, попавших в область охвата i-ого антитела, у которых ключевой класс совпадает с j-ым антигеном; – общее количество антигенов, в которых ключевой класс совпадает с j-ым антигеном;  – количество антигенов, попавших в область охвата i-ого антитела, у которых ключевой класс не совпадает с j-ым антигеном.

Distance – вычисление расстояний между антителами:

Evklid – Эвклидово расстояние (1); Manhetten – Манхеттеновское расстояние (2).

Themutationformula – формула, по которой производится мутация антитела. Имеет следующие варианты выбора:

– Fast convergence : ;

– Affinity proportional mutation: ;

– Somatic mutation : ;

где сj – мутируемый антиген, α – коэффициент мутации, N(0, α) – функция случайного распределения в диапазоне (0, α); Td () – порог смертности для антител в клетках памяти иммунной сети; Ts () – порог суппрессии.

Выводы. Разработаны модифицированные алгоритмы и компьютерная система, предназначенные для решения задач классификации и исследования свойств алгоритмов для решения задач классификации на основе клонального отбора и искусственной иммунной сети.

Система позволяет исследовать влияние операторов замещения, суппрессии, гипермутации и их модификаций на скорость сходимости и качество классификации.

Важно

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

In article the computer system for the decision of problems of classification on the basis of the modified algorithms of an immune network and algorithm clonal selection is described. The architecture of system, program modules and parametres of adjustment of algorithms of training is described.

1.         De Castro, L. N. & Timmis, J. I. Artificial Immune Systems: A New Computational Intelligence Approach, , London: Springer-Verlag 200o), September,  357 p.

2.         Бідюк П.І. Литвиненко В.І. Фефелов. А.О. Формалізація методів побудови штучних імунних мереж// Наукові вісті НТУУ “КПІ”. 2007 р.–C.29-41

3.         Литвиненко В.И. Искусственные иммунные системы как средство индуктивного построения оптимальных моделей сложных объектов // Проблемы управления и информатики. –. 2008.– № 3.– с. 43-61.

4.         Литвиненко В. И.  Иммунный классификатор для решения задач бинарной классификации (теоретические основы) //Системні технології. Регіональний міжвузівський збірник наукових праць. Випуск 1(42). –Дніпропетровськ, 2006. с.114-130.

Читайте также:  Теперь и у роботов есть инстинкты

5.         http://sourceforge.net/projects/weak

6.         Brownlee J. Clonal Selection Theory & CLONALG – The Clonal Selection Classification Algorithm (CSCA) // Victoria, Australia: Centre for Intelligent Systems and Complex Processes (CISCP), Faculty of Information and Communication Technologies (ICT), Swinburne University of Technology; 2005 Jan; Technical Report ID: 2-01.

Источник: http://aaecs.org/litvinenko-vi-didik-aa-zaharchenko-yua-kompyuternaya-sistema-dlya-resheniya-zadach-klassifikacii-na-osnove-modificirovannih-immunnih-algoritmov.html

Применение искусственных иммунных систем к решению задачи о коммивояжере

Сохрани ссылку в одной из сетей:

ПРИМЕНЕНИЕ ИСКУССТВЕННЫХ ИММУННЫХ СИСТЕМ К РЕШЕНИЮ ЗАДАЧИ О КОММИВОЯЖЕРЕ

Аверкин А.Н., к.ф.-м.н., в.н.с.

ВЦ им. А.А. Дородницына РАН

email: averkin2003@inbox.ru

Заруцкий А.С., аспирант

Международный университет общества,

природы и человека «Дубна»

email: primat.isu@gmail.com

1. ВВЕДЕНИЕ

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

Для нахождения приближенных решений применяется множество алгоритмов, три из которых рассматриваются в данной работе: генетический алгоритм, муравьиный алгоритм и новый подход, основанный на искусственных иммунных системах. Все три метода относятся к направлению «природных вычислений», т.

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

2. ГЕНЕТИЧЕСКИЙ АЛГОРИТМ

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

Совет

Принцип работы генетического алгоритма основан на теории эволюции Чарльза Дарвина.

Основателем генетических алгоритмов считается Джон Холланд (John Holland), опубликовавший в 1975 году первую книгу в этой области исследований под названием “Адаптация в естественных и искусственных системах” (“Adaptation in Natural and Articial Systems”) [7].

В классическом генетическом алгоритме решение кодируется двоичной последовательностью. Такой способ подходит для случаев, когда изменение одного бита в решении в большинстве случаев приводит к незначительному изменению целевой функции.

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

Кроме того, для эффективной работы алгоритма стоит использовать оператор мутации, учитывающий семантику задачи [1].

Помимо стандартного изменения случайного элемента в хромосоме он выполняет четыре дополнительных действия: удаление случайного узла из маршрута, включение случайного узла в случайное место в маршруте, включение случайного узла из окрестности некоторого случайного узла маршрута, смена мест двух случайных узлов маршрута.

Оператор кроссовера выполняет стандартную функцию – создает новый маршрут на основе частей двух других маршрутов. Стоит отметить, что оператор кроссовера неэффективен при соединении маршрутов, множества вершин которых значительно отличаются.

Выбор особей для новой популяции осуществляется одним из стандартных способов, например т. н. “механизмом рулетки”, при котором вероятность попадания особи в новую популяцию пропорциональна значению функции приспособленности для этой особи.

Обратите внимание

Одна из проблем, возникающая при использовании генетических алгоритмов, – «застревание» по процесса поиска в локальных максимумах. Решение, найденное в локальном максимуме, постепенно вытесняет все остальные варианты решений из популяции.

Части решить эту проблему позволяет использование нескольких параллельных потоков поиска, которые могут либо вообще не пересекаться, либо пересекаться через заданное количество итераций для обмена лучшими вариантами решений [2].

Однако, использование параллельных популяций отрицательно сказывается на производительности алгоритма.

3. МУРАВЬИНЫЙ АЛГОРИТМ

Муравьиные алгоритмы основаны на моделировании взаимодействия муравьев в муравьиной колонии. Муравьиные алгоритмы эффективны при решении различных комбинаторных задач на графах, включая задачу о коммивояжере. Их исследование началось в начале 90-х годов Марко Дориго в Университете Брюсселя [4].

Муравьиная колония представляет собой сложную распределенную не централизованную систему.

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

Однако вся система в целом решает сложные задачи оптимизации маршрутов, находя очень близкие к оптимальным решения, адаптируясь к внешним изменяющимся условиям.

Взаимодействие между муравьями происходит по средствам прямого и непрямого обмена информацией.

Важно

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

На основе непрямого обмена и моделируются муравьиные алгоритмы. Для изменения окружающей среды муравьи распыляют феромон, запах которого остается в почве некоторое время.

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

Те муравьи, которые раньше всех достигнут цели, соответственно вернуться обратно раньше всех тем же путем, увеличив содержание феромонов на этом маршруте. Через несколько итераций кратчайший маршрут будет сильно отличаться от всех остальных вариантов пути [6].

Адаптивность к внешним изменениям осуществляется за счет испарения феромонов. Если на кратчайшем пути встречается препятствие, муравей случайным образом выбирает другой путь, таким образом через некоторое время находится новый кратчайший маршрут.

Муравьиный алгоритм, в отличие от генетического, гораздо быстрее адаптируется к изменению внешних условий. Также существуют варианты интеграции этих двух алгоритмов [9], [10].

4. ИСКУССТВЕНЫЕ ИММУННЫЕ СИСТЕМЫ

Биологическая иммунная система представляет собой сложную распределенную адаптивную систему интеллектуальной обработки информации. ИС защищает организм от инородных вирусов и инфекций.

Иммунная система способна к обучению, обладает памятью, решает задачи поиска и классификации.

Совет

ИС обрабатывает огромные объемы информации, поэтому алгоритмы, созданные природой, оказались эффективными и в математических задачах поиска и распознавания.

Отдельные статьи по ИИС начали появляться в 1980-х годах, однако в отдельно направление ИИС выделились только в середине 90-х годов с появлением работ Форреста, Дасгупты, Ханта и Кука. Первая книга про искусственные иммунные системы вышла в 1998 году под редакцией Дипанкара Дасгупты [3].

Чужеродные агенты, находясь в организме, производят молекулы, называемые антигенами. Большая часть антигеном может быть распознана специальными клетками – B-лимфоцитами, которые циркулируют в кровеносной и лимфатической системах в ожидании столкновения с антигенами.

B-лимфоциты имеют рецепторы, а точнее специальные молекулы, называемые антителами, на своей поверхности для распознавания антигенов, каждый вид которых имеет уникальную форму. Для распознавания каждого вида антигенов в системе циркулируют соответствующие виды B-лимфоцитов.

После того как антиген взаимодействует с антителами B-лимфоцита, стимулируется процесс клонирования лимфоцита. Этот процесс называется клональным отбором. Полученные в результате клонирования лимфоциты могут незначительно отличаться от исходного. Лимфоциты, не взаимодействующие с антигенами постепенно отмирают.

Процесс клонирования B-лимфоцитов в результате взаимодействия с антигенами называется иммунным ответом [5].

Также в функционировании иммунной системы участвуют два процесса – положительный и отрицательный отбор.

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

Обратите внимание

В результате этих двух процессов поддерживается необходимое состояние и разнообразие рецепторов B-лимфоцитов.

5. РЕАЛИЗАЦИЯ АЛГОРИТМА ИИС ДЛЯ ЗАДЧИ О КОММИВОЯЖЕРЕ

Итак, для решения задачи о коммивояжере с помощью алгоритмов искусственной иммунной системы необходимо сопоставить биологические объекты и процессы их математическим аналогам.

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

Агент начинает свой путь в начальной вершине, при каждой итерации алгоритма он имеет возможность клонировать себя. Попадая в вершину, которую он уже посещал, агент уничтожает себя согласно правила положительного отбора.

После завершение обхода по правилу отрицательного отбора выбирается агент с наименьшей длиной пути.

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

Для сокращения количества бесполезных агентов, длина маршрутов которых превысили текущий наилучший результат до завершения пути, будем записывать текущую минимальную длину пути при создании нового агента.

Если путь агента превышает это значение, он самоуничтожается.

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

Алгоритм действий одного агента в псевдокоде выглядит следующим образом:

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

  2. Если агент уже был в этой вершине – самоуничтожиться;

  3. Увеличить длину на размер пройденного пути;

  4. Если длина превышает известный агенту минимум – самоуничтожится;

  5. Если в популяции есть свободные места – клонировать себя, изменив последнюю вершину у клона на случайную;

  6. Перейти к шагу 1.

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

6. ТЕСТИРОВАНИЕ ПРОИЗВОДИТЕЛЬНОСТИ АЛГОРИТМОВ

Для тестирования также реализованы генетический и муравьиный алгоритмы. Тестирование производилось на одном персональном компьютере. Поскольку время выполнения алгоритма зависит от производительности компьютера, в таблицы приведены значения в условных единицах, которых достаточно для сравнения алгоритмов.

В таблице 1 приведены средние значения, полученные в результате выполнения серии тестов.

Таблица 1. Результаты сравнения алгоритмов

Кол-во

вершин

ГА

МА

ИИС

Время

Длина

Время

Длина

Время

Длина

20

76

385

84

391

17

311

50

1039

599

967

584

41

530

100

3944

729

2305

714

293

645

300

1503627

1295

619238

1072

3478

966

700

4658125

1872

3589351

1545

11705

1447

1000

7834380

2946

5843482

2580

160367

1817

7. ЗАКЛЮЧЕНИЕ

Рассмотренный в данной работе алгоритм, основанный на искусственных иммунных системах, применительно к классической задачи о коммивояжере показал хорошие результаты в сравнении с генетическим и муравьиным алгоритмами. В дальнейшем планируется продолжить исследование применения ИИС к задачам маршрутизации, их динамическим и распределенным вариантам.

Литература

  1. Bryant K., Benjamin A., Genetic Algorithms and the Traveling Salesman Problem, Department of Mathematics, HarveyMudd College, 2000.

  2. Cantu-Paz E., Efficient and Accurate Parallel Genetic Algorithms, Lawrence Limermore National Lab, 2000.

  3. Dasgupta D., Artificial Immune Systems and Their Applications, Springer-Verlag, 1998.

  4. Dorigo M., Gambardella, L.M., Ant Colonies for the Traveling Salesman Problem, Universite Libre de Bruxelles, 1996.

  5. Gaber J., Bakhouya M., An Immune Inspired-based Optimization Algorithm: Application to the Traveling Salesman Problem, Université de Technologie de Belfort-Montbéliard, 2007.

  6. Gambardella L.M. Ant Colony Optimization, Istituto Dalle Molle di Studi sull’Intelligenza Artificiale Galleria 2, Manno, Switzerland, 2002.

  7. Holland J., Adaptation in Natural and Articial Systems, University of Michigan Press, Ann Arbor, 1975.

  8. Lid M. Traveling Salesman Problem Domain Application of a Fundamentally New Approach to Utilizing Genetic Algorithms, Technical report, Air Force Oce of Scientic Research and Oce of Naval Research, 1991.

  9. White T., Pagurek B., Oppacher F. ASGA: Improving the Ant System by Integration with Genetic Algorithms, Systems and Computer Engineering, Carleton University, 1998.

  10. Wei P., Xiong W., Zhao J. An Improved Ant Colony Algorithm for TSP, Coll. of Sci. & Technol., Ningbo Univ., China, 2004.

  1. Публичный отчет

    О РАЗВИТИИ государственного образовательного учреждения высшего профессионального образования Московской области МЕЖДУНАРОДНОГО УНИВЕРСИТЕТА ПРИРОДЫ, ОБЩЕСТВА И ЧЕЛОВЕКА «ДУБНА»

  2. Лекция

    Целью данного курса является рассмотрение такого понятия как «Искусственный интеллект» (ИИ), а если быть конкретней – основных направлений развития систем искусственного интеллекта (СИИ) и задач, которые данные системы способны решать.

  3. Документ

    45. Роль менеджера по работе с клиентами в процессе установления договорных отношений и исполнении заказа. Причины неправильной коммуникации между рекламным агентством и клиентом.

  4. Закон

    Развитие – это необратимое, направленное, закономерное изменение материи и сознания, их универсальное свойство; в результате развития возникает новое качественное состояние объекта – его состава или структуры.

  5. Документ

    Перед вами работа классиков психологической науки — издание, которое можно использовать в качестве основного или дополнительного пособия в рамках курса по социальной психологии и проводить на ее основе семинарские занятия.

Источник: https://refdb.ru/look/1415872.html

Ссылка на основную публикацию
Adblock
detector