birmaga.ru
добавить свой файл

1
Рамон Антоніо Родрігес Заліпиніс


Донецький національний технічний університет

(науковий напрям: Інформатика і обчислювальна техніка)

МУРАВЬИНЫЙ АЛГОРИТМ ДЛЯ РАЗБИЕНИЯ ГРАФОВ
Ключевые слова: МУРАВЕЙ, ФЕРОМОН, ГРАФ, КЛАСТЕР, РАЗБИЕНИЕ
Вступление.
Разработан новый метод укрупнения графа в многоуровневой парадигме разбиения графов, используя модель колонии муравьёв.

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

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

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

Проблема разбиения графов NP-полна [8], но поскольку она практически важна, то громадные усилия были направлены на разработку эвристик [6].

Для задач кластеризации и сортировки данных разработаны муравьиные алгоритмы [9, 10], а предложенная в них модель поведения муравьёв обобщается для задачи разбиения графов [11]. Автономные искусственные муравьи обладают некоторым объёмом памяти, функционируют в дискретном времени, способны анализировать списки смежности вершин графа и перемещаются по 2D решётке, в узлах которой расположены вершины графа.

Муравьи являются социальными насекомыми, живущими в высокоорганизованных колониях. Муравьи могут находить кратчайшие пути между источниками пищи и своим гнездом. Когда муравьи перемещаются от источника пищи к гнезду и в обратном направлении, они выделяют химическое вещество феромон, которое остаётся на земле, формируя след. Двигаясь, муравьи выбирают, с некоторой вероятностью, пути с сильными концентрациями феромона. След феромона помогает муравьям находить путь обратно к гнезду и достигать источников пищи, найденных своими собратьями. Феромон имеет свойство накапливаться и его концентрация на пути пропорциональна числу прошедших по нему муравьёв. Со временем феромон испаряется с редко посещаемых путей [12-14].


В практических задачах возникают графы с большим числом вершин (), поэтому для их разбиения успешно применяется многоуровневая парадигма [15-20]. Она позволяет получать «хорошие» решения за «разумное» время. Вначале, исходный граф обрабатывается рекурсивной функцией, результатом работы которой является последовательность графов , где каждый последующий граф получается укрупнением предыдущего графа, путём попарного стягивания вершин. Граф разбивается на требуемое число подмножеств, причём возможно применение эвристик, которые не в состоянии работать на больших графах [21, 22]. Затем выполняются обратные действия, назначая вершинам и , стянутым в вершину то же подмножество разбиения, что и для . При укрупнении стягиваются пары вершин, вероятность которых быть помещёнными в разные подмножества разбиения мала.

Метод решения проблемы конкурсантом. Самостоятельно разработан новый алгоритм, для решения задачи разбиения графов. Алгоритм позволяет улучшить качество разбиений, находимых одной из лучших и широко используемых систем для разбиения графов – METIS – вплоть до 16%.

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


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

Разработан алгоритм, состоящий из двух этапов. Этап 1 является муравьиным алгоритмом, в котором искусственные муравьи используют новую модель поведения для отыскания кластеров, по сравнению с предложенными ранее [9-11]. Цель Этапа 1 – изменить веса рёбер так, чтобы потом легко отличить кластеры. Этап 2, используя новые веса рёбер, выделяет кластеры вершин и стягивает их.

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

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


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

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

Этап 2 в модифицированном графе классифицирует вершины на граничные (), внутренние () и не принадлежащие какому-либо кластеру (). Множества , попарно не пересекаются. Ожидается, что новые веса рёбер после обработки графа Этапом 1 будут велики внутри кластеров и малы на рёбрах, не принадлежащих какому-либо кластеру. Если



(1)

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

Путь в графе положителен (), если , . Множество максимально, если для не существует положительного пути от к , если либо от к через , если , где , а (т.е. нельзя присоединить к ). Также, если и , то . Если , такое, что максимально, то избыточно. Подмножество называется кластером (с точки зрения Этапа 2), если оно максимально и не избыточно. Этап 2 выделяет кластеры из (можно доказать, если и – различные кластеры, то ).


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

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

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


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

Проведены эксперименты с использованием METIS [23, 24] на графах из архива C. Walshaw [25]. После Этапа 1 обработки графа он посылался в METIS для нахождения бисекции. Находилась также другая бисекция, обрабатывая вначале тот же граф Этапом 1, затем Этапом 2 и METIS. Лучшая из этих двух бисекций сравнивалась с бисекцией, полученной непосредственным применением METIS к исходному графу.

Основные результаты работы. Для графа «data» из [25] получено разбиение на 5% лучше, но с ухудшением баланса на 2%. Для графа «add32» из [25] разбиение улучшено на 16%, а баланс на 2.78%. Это разбиение совпало с лучшим из известных на сегодняшний день.

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

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


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

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

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

Дальнейшее совершенствование алгоритма состоит в разработке более чувствительных схем построения кластеров на Этапе 2. Для ускорения работы возможно распараллеливание Этапа 1 и реализация его в компьютерной кластерной сети.
Использованные источники и литература


  1. Olson E. et al., Single-Cluster Spectral Graph Partitioning for Robotics Applications, Massachusetts Institute of Technology.

  2. Douglas et al., Cache Optimization for Structured and Unstructured Grid Multigrid, 2000.

  3. A Parallel Structured Flow Solver – URANUS, Russian-German School on HPC Systems, Novosibirsk, 2005.

  4. Spatial Color Component Matching of Images, 2001.

  5. Zabih R., Kolmogorov V., Spatially Coherent Clustering Using Graph Cuts, 2004.

  6. Chamberlain B., Graph Partitioning Algorithms for Distributing Workloads of Parallel Computations, 1998.

  7. Yelick K., CS 267: Applications of Parallel Computers. Graph Partitioning, 2004.
  8. Гери М., Джонсон Д., Вычислительные машины и труднорешаемые задачи, М.: Мир, 1982.


  9. Cong J., Smith M., A Parallel Bottom-up Clustering Algorithm with Applications to Circuit Partitioning in VLSI Design.

  10. Vizine A., Towards Improving Clustering Ants: An Adaptive Ant Clustering Algorithm, 2004.

  11. Dorigo M., Real Ants Inspire Ant Algorithms, 2004.

  12. Ramos V., Merelo J., Self-organized Stigmergic Document Maps, 2002.

  13. Dorigo M., Maniezzo V., Colorni A., The Ant System: Optimization by a Colony of Cooperative Agents, 1996.

  14. Dorigo M., Caro G., Gambardella L., Ant Algorithms for Discrete Optimization, 1999.

  15. Shloegel K., Karypis G., Kumar V., Parallel multilevel algorithms for multi-constraint graph partitioning, 1999.

  16. Soper A.J, Walshaw C., Cross M., A Combined Evolutionary Search and Multilevel Optimization Approach to Graph Partitioining, 2004.

  17. Karypis G., Kumar V., A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, 1998.

  18. Karypis G., Kumar V., Multilevel k-way Partitioning Scheme for Irregular Graphs, 1998.

  19. Walshaw С., Multilevel Refinement for Combinatorial Optimization Problems, 2004.

  20. Mohiuddin W., Multilevel Graph Partitioning and Fiduccia-Mattheyses.

  21. Kernighan B.W., Lin S., An Efficient Heuristic Procedure for Partitioning Graphs, The Bell Sys. Tech. Journal, vol. 49, no.2, pp. 291-307, 1970.

  22. Fiduccia C., Mattheyses R., A Linear Time Heuristic for Improving Network Partitions, In Proc. 19th ACM/IEEE Design Automation Conference, 175-181, 1982.

  23. http://www.cs.umn.edu/~karypis/metis

  24. Karypis G., Kumar V., METIS: A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices. Version 4.0.
  25. http://staffweb.cms.gre.ac.uk/~c.walshaw