1 * Алгоритмы эволюционного роевого интеллекта в решении задачи разбиения графа Курейчик В.М. Кажаров А.А.

* История роевых вычислений Возможность того, что вычислительная система, наделенная простыми механизмами изменчивости и отбора, могла бы функционировать по аналогии с законами эволюции в природных системах является очень привлекательной. Она стала причиной появления ряда вычислительных моделей, построенных на принципах, инспирированных природными системами. Одними из таких являются алгоритмы роевого интеллекта. Понятие роевого интеллекта (Swarm intelligence) был введен Херардо Бени и Ван Цзином в 1989 году [1]. Под роевым интеллектом понимают самоорганизующуюся систему, состоящую из множества агентов. Агенты подчиняются простым правилам поведения в окружающей среде. Их простое взаимодействие определяет коллективную адаптацию. Таким образом, на поведении простых агентов формируется роевой интеллект. Примерами таких систем могут быть муравьиная колония, пчелиный рой, стая птиц, рыб и т.д.

3 Дан граф G=(X,U) |X| = n – множество вершин (города) |U| = m – множество ребер Дана матрица смежности Di,j i, j 1, 2,…, n D i,j = 0 или 1 (наличие ребра между вершинами i и j) Даны мощности подграфов Mi |M| = s – количество подграфов Цель – минимизировать критерий критерий - число ребер между подграфами, ЦФ: где K i,j – количество ребер между подграфами i и j

4 СТАНДАРТНЫЙ МУРАВЬИНЫЙ АЛГОРИТМ

5 Данный класс алгоритмов разрабатывался в рамках научного направления «природные вычисления». Исследования в этой области начались в середине 90-х годов XX века. Автором идеи является Марко Дориго. Основная идея - моделирование поведения колонии муравьев.

6

7 Муравьиная колония – многоагентная система. Взаимодействие – феромон, откладываемый муравьями на пройденном пути. желания пройти кратчайший путь; опыта других муравьев, информацию о котором получаем непосредственно через уровень феромонов на каждом пути. При выборе направления движения муравей исходит из: Отрицательная обратная связь (локальный оптимум) – испарение феромонов.

8 Муравей обладает «памятью», в котором хранится список городов J i,k, которые необходимо посетить муравью k, находящийся в городе i. Муравьи обладают «зрением», определяемый по следующей формуле: η ij = 1/D ij. Муравей улавливает след феромона, который определяет желание муравья пройти по данному ребру. Уровень феромона в момент времени t на ребре D ij будет соответствовать τ ij (t).

9 где Q – параметр, имеющий значение порядка длины оптимального пути(задается ЛПР), L k (t) – длина маршрута T k (t). Обновление феромона определяется следующим выражением: где m – количество муравьев, p – коэффициент испарения (0 p 1). (2) (3)

10 Вероятность перехода муравья из вершины i в вершину j будет определяться следующим соотношением: где α, β – параметры, задающие веса следа феромона. Они определяют «жадность» муравья. При α=0 муравей стремиться выбирать кратчайшее ребро, при β=0 – ребро с наибольшим количеством феромона. (1)

11 Толщина ребер показывает уровень феромонов

12

13 Текущая вершина: 4Пройденный маршрут: Не пройденные вершины: 2, 3, 7, 8Муравей определяет следующую из смежных вершину: 3, 7.

14 x3x3 x2x2 x1x1 x0x0 p 01 =0.5p 02 =0.5 x3x3 x2x2 x1x1 x0x0 p 01 =0.3p 02 =0.7 x3x3 x2x2 x1x1 x0x0 p 01 =0.05p 02 =0.95 а) начальное распределениеб) промежуточное распределениев) конечное распределение

15 O(t*m*n 2 ) t – количество итераций (время жизни колонии) m – количество муравьевn – количество вершин в графе

16 МОДИФИКАЦИИ МУРАВЬИНОГО АЛГОРИТМА

17 L*(t) – длина лучшего маршрута на момент времени t A e – «авторитет» элитных муравьев Уровень феромонов на ребрах лучшего маршрута равен следующей величине: A e = 0. Полностью игнорируется влияние «элитного» муравья. A e (0, 1). В этом случае уровень феромонов на лучшем маршруте уменьшается. A e = 1. Влияние «элитных» муравьев равнозначно другим. A e (1, ). Усиливается влияние «элитных» муравьев.

18 «Одеяло» – стандартное размещение муравьев, в каждой вершине находиться по одному муравью. Тогда ВСА: O(t*n 3 ), поскольку n=m; «Дробовик» – случайное распределение муравьев на вершины графа; «Фокусировка» – вся колония находится в одной вершине; «Блуждающая колония» – в на каждой итерации, вся колония перемещается в случайно выбранную вершину.

19

20

21 Статическая Шаблон формируется перед работой муравьиного алгоритма на основе знаний о длинах ребрах – выборка K кратчайших ребер Динамическая Шаблон формируется в ходе работы муравьиного алгоритма. При этом если вероятность перехода из вершины i в j превысит заданное ограничение (Plim < 1), то ребро (i, j) заносится в шаблон.

22 Толстой линией обозначен график ВСА с использованием шаблона (P s = 0.999), тонкой – без него, прямоугольники – разность в работе по времени. Экспериментальные исследования показали, что муравьиный алгоритм с использованием шаблона работает меньше времени, чем без него Зависимость времени работы алгоритма от числа вершин

23 Толстой линией обозначен график ВСА с использованием шаблона (P s = 0.999), тонкой – без него, прямоугольники – разность в работе по времени. Экспериментальные исследования показали, что муравьиный алгоритм с использованием шаблона работает меньше времени, чем без него Зависимость времени работы алгоритма от числа итераций

24 Данная модификация основана на использовании частичного перебора; Для перебора используется метод «ветвей и границ»;Перебор применяется к случайной части решения, т.е. к подмаршруту; Количество вершин в подмаршруте незначительна, составляет порядка «Выпрямитель» - интеллектуальный блок, принимающий на входе множество вершин и ребра между ними, и выдающий их кратчайший обход; Можно выделить два вида «выпрямителей»: промежуточный и дополнительный.

25

26

27 ВСА по М.Дориго зависит от числа вершин n, размера колонии m и числа итераций T (время жизни колонии) – O(T*m*n 2 ). Из (1) следует, что ВСА зависит и от параметров α и β, т.к. возведение в степень – операция, ВСА которого O(log(α)), где α – значение степени. Тогда ВСА выражается следующей зависимостью: O(T*m*n 2 *(log(α)+log(β))) Отметим, что η ij и β являются константой, следовательно η ij β – константа. Тогда для повышения быстродействия η ij удобно вычислять как η ij = (1/D ij ) β. Тогда ВСА: O(T*m*n 2 *log(α))

28 783, ,447

29 Данный класс алгоритмов разрабатывался в рамках научного направления «природные вычисления». Исследования в этой области начались в начале XXI века. Авторами идеи являются Lučić P., Teodorović D. Основная идея – моделирование поведения колонии пчел.

30 Пчёлы, основываясь на полученной информации от другой пчелы, начинают летать к указанному источнику нектара. Положительная обратная связь Пчела, основываясь на информации, полученной от других пчёл, может решить, что найденный ею источник значительно хуже по сравнению с другими найденными источниками. Отрицательная обратная связь Пчёлы-разведчики выполняют случайный поиск новых источников ресурсов Неустойчивость Информация об источнике ресурсов, найденного одной пчелой, доступна для всех других в улье посредством выполнения, так называемого, виляющего танца Множественность взаимодействия

i-я пчела сообщает колонии только о лучшем источнике h i на участке p i 31 i-я пчела способна по танцу j-й определить количество нектара F(h j ) в источнике h j i-я пчела, найдя новый источник h i, может сменить роль на фуражира или разведчика i-я пчела осуществляет случайный поиск на участке p i радиусом r

32 p – число фуражировl – число разведчиковm=p+l – размер колонииk – кол-во участков для фуражировкиr – размер участкаT – число итераций

33 Колония Фуражиры Разведчики Пчела Поиск источника нектара Танец Участок Источник

34 Фуражир Выбор элитного участка Поиск Возврат в улей Разведчик Случайный выбор участка Поиск Возврат в улей Вербовка Фуражировка на прежнем участке Вернувшись в улей пчела либо меняет роль, либо вербует, информируя о найденном источнике

35 При решении задач нахождения глобальных экстремумов сложных многомерных функций границы участка определяются как [x 1 -r; x 1 +r][x 2 -r; x 2 +r]…[x n -r; x n +r], где x i – координата пчелы (параметр функции), r – радиус (размер) участка, n – количество параметров функции r Пчела (x i,y i ) источники участок x y 0 r r источник 1 источник 2 Реальная модельМатематическая модель

36 Решение находится в координатах (0; 0) Целевая функция: f(x,y) = x 2 +y 2. Цель: минимизация ЦФ.

37 Пчелы постепенно скапливаются вокруг одного лучшего решения. Красные точки - пчелы, нашедшие лучшие решения. Желтые точки - выбранные решения Черные точки - пчелы- разведчики Целевая функция: f(x,y) = x 2 +y 2. Цель: минимизация ЦФ.

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

39 i подграф 1подграф 2подграф 3 AiAi i123 |Mi||Mi|454 Мощности подграфов M i : Решение представляется в виде перестановки вершин А i, причем первые M 1 вершин относятся к первому подграфу, следующие M 2 вершин относятся ко 2 подграфу и т.д.: F=8

40 Пространство поиска нектара будет представлять собой всевозможные перестановки A из n чисел, а его размерность равна n!. Количество нектара в источнике A обратно пропорционально ЦФ F(A). Источник нектара определяется одним решением из пространства поиска и представляется в виде некоторой перестановки. Два источника (A, B) находятся на одном участке, если расстояние L(A, B) r, где r – заданный параметр ПА. Расстояние L между перестановками A и B определяется как расстояние Хемминга и равно числу различий в позициях между ними.

41 i подграф 1подграф 2подграф 3 AiAi BiBi AiBiAiBi L(A,B)3 r = 4 L(A,B)

42 i AiAi BiBi Пространство поиска Участок AB

43 Начало Генерация участков для поиска нектара Отправка фуражиров Выбор участков для поиска в их окрестности Оценка полезности участков Поиск в окрестностях источников нектара Отправка пчёл-разведчиков условие останова? Окончание да нет Случайный поиск Оценка полезности новых участков Инициализация пчелиной колонии

44 Временная сложность пчелиного алгоритма: O(T*m*r*n 2 ), где T – число итерацийm – размер колонииr – размер участкаn – количество вершин

45 Реализованные алгоритмы ИтерационныйЭволюционныйГенетическийМуравьиныйПчелиный

46 График зависимости ЦФ от числа фуражиров. Размерность графа – 125 вершин

47 График зависимости ЦФ от размера участков. Размерность графа – 125 вершин

48 График зависимости ЦФ от числа фуражиров. Размерность графа – 125 вершин

49 Зависимость ЦФ от числа исследуемых источников нектара. Размерность графа – 125 вершин

50 Зависимость ЦФ от числа фуражиров и разведчиков. Размерность графа – 125 вершин

51 Сравнения алгоритмов разбиения для тестов различной размерности Число вершин Число подграфов Результат МА Результат ПА hMetis

52