ПРИМЕНЕНИЕ ИСКУССТВЕННЫХ ИММУННЫХ СИСТЕМ К РЕШЕНИЮ ЗАДАЧИ О КОММИВОЯЖЕРЕ
Авторы: А.С.Заруцкий, А.Н.Аверкин, Y.Matsunaga
Источник: http://www.raai.org/...
Аверкин А.Н., к.ф.-м.н., в.н.с.
ВЦ им. А.А. Дородницына РАН
e-mail: averkin2003@inbox.ru
Заруцкий А.С., аспирант
Международный университет общества,
природы и человека «Дубна»
e-mail: 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, Universite de Technologie de Belfort-Montbeliard, 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.