Р.А. Родригес Залепинос "Многоуровневая, эволюционная и муравьиная парадигмы для решения проблемы разбиения графов", IV международная конференция студентов, аспирантов и молодых учёных "Компьютерный мониторинг и информационные технологии", г. Донецк, 13-14 мая, 2008 г.

МНОГОУРОВНЕВАЯ, ЭВОЛЮЦИОННАЯ И МУРАВЬИНАЯ ПАРАДИГМЫ ДЛЯ РЕШЕНИЯ ПРОБЛЕМЫ РАЗБИЕНИЯ ГРАФОВ
Р.А. Родригес Залепинос
Донецкий национальный технический университет

Проблема разбиения графов NP-полна [1]. Она возникает в различных формах в data mining, робототехнике, искусственном интеллекте, переупорядочивании разреженных матриц, обработке изображений, компьютерных сетях, параллельных вычислениях, оптимизации кэширования, проектировании СБИС, базах данных, операционных системах и других областях.

В докладе предлагается новый подход для разбиения графов, основанный на многоуровневой и муравьиной парадигмах, позволяющий улучшить качество разбиений, находимых METIS [2] - одной из самых быстрых и лучших систем для разбиения графов - вплоть до 40% для некоторых графов.

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

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

Многоуровневый алгоритм разбиения графов из [3], начиная с исходного графа, строит последовательность графов, в которой каждый последующий граф получается укрупнением предыдущего путём попарного стягивания вершин. Находится разбиение наименьшего графа, после чего выполняются обратные действия, назначая вершинам и , стянутым в вершину то же подмножество разбиения, что и для . Алгоритм реализован в системе METIS.

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

В [4] описан эволюционный алгоритм, который для большинства графов из [5], находит лучшие на сегодняшний день разбиения. Индивиды посылаются в многоуровневый алгоритм разбиения графов, чтобы быстро получить разбиение. Далее выполняются генетические операторы, которые присваивают вершинам новые веса, равные + , где - случайная величина в интервале [0,0.1], =0.1 для кроссинговера и 2.0 для мутации. При кроссинговере, если у более, чем двух предков ребро разрезано, то =0, иначе =1. При мутации =0, если в разбиении в некоторой окрестности данной вершины находится разрезанное ребро. Таким образом, многоуровневый алгоритм разбиения графов будет пытаться помещать вершины на концах тяжёлых рёбер в одно подмножество, производя поиск поблизости предыдущих хороших решений в пространстве решений.

Хотя данный алгоритм часто находит лучшие по качеству разбиения (по количеству разрезанных рёбер), время его работы измеряется днями. При наблюдении за муравьями, была обнаружена высокая степень организации их колоний по сравнению с относительно простым поведением отдельных муравьёв. Муравьи способны находить кратчайшие пути между источниками пищи и гнездом, сортировать личинки по размеру, кластеризовать объекты. Муравьи выделяют химическое вещество - феромон, которое при перемещении остаётся на земле, формируя след. Двигаясь, муравьи выбирают, с некоторой вероятностью, пути с сильными концентрациями феромона [6].

В докладе предлагается новый муравьиный алгоритм разбиения графов. Его основная идея заключается в модификации веса ребра (v, w) так, чтобы его вес стал пропорционален нахождению вершин v и w в одном подмножестве разбиения. Целесообразно помещать плотно связанные между собой области вершин в одно подмножество разбиения. Муравьи перемещаются из вершины в вершину в поисках таких областей, наращивая феромон на посещённых ими рёбрах. Области вершин с тяжёлыми рёбрами стягиваются в одну. Полученный новый, укрупнённый граф, передаётся в METIS, который быстро находит хорошие разбиения, однако их качество можно улучшить вплоть до 40% для некоторых графов, применяя описанную схему.

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

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

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

Литература

1. Гери М., Джонсон Д., Вычислительные машины и труднорешаемые задачи, М.: Мир, 1982.
2. Программный пакет METIS, http://www.cs.umn.edu/~karypis/metis
3. Karypis G., Kumar V., Multilevel k-way partitioning scheme for irregular graphs, 1998.
4. Soper A.J., Walshaw C., Cross M., A combined evolutionary search and multilevel optimisation approach to graph-partitioning, 2004
5. Архив разбиений C. Walshaw, http://staffweb.cms.gre.ac.uk/~c.walshaw/partition
6. Dorigo M., Maniezzo V., Colorni A., The ant system: optimization by a colony of cooperative agents, 1996.