|
|
|
Родригес Залепинос Рамон Антонио |
raro@ua.fm
|
|||||||||
|
|
|
|||||||||||||||||||||||||||
|
|
Разработан новый метод укрупнения графа в многоуровневой парадигме разбиения графов, используя модель колонии муравьёв. Удалось повысить качество решений, находимых METIS - одной из лучших и самых быстрых систем для разбиения графов - вплоть до 40% для некоторых графов. ВведениеАктуальностьПроблема разбиения графов возникает в различных формах в data mining, робототехнике, искусственном интеллекте, переупорядочивании разреженных матриц, обработке изображений, компьютерных сетях, параллельных вычислениях, оптимизации кэширования, проектировании СБИС, базах данных, операционных системах и других областях [1-7]. Например, при проведении вычислений на параллельном компьютере, они должны быть разбиты на задачи, которые назначаются разным процессорам. Для эффективного использования машины им нужно дать примерно одинаковый объём работы, стремясь минимизировать число межпроцессорных взаимодействий [6]. Проблема разбиения графов NP-полна [8], поэтому для нахождения глобального оптимума необходимо выполнить полный перебор всех возможных разбиений. Уже для нахождения оптимальной бисекции графа из 1000 вершин (одинакового веса) нужно просмотреть такое число решений, которое примерно в октиллион раз превосходит число атомов в наблюдаемой части вселенной на сегодняшний день. Поскольку проблема разбиения графов практически важна, то громадные усилия были направлены на разработку эвристик [6]. Научная новизнаОписаны разработанные автором поведение и структура муравьёв, способ использования феромона, новая распределенная схема испарения феромона, непрямая методика оценки качества решений, находимых муравьями, эвристические схемы и критерии поиска кластеров в графе, модифицированном с помощью феромона. Предложен подход для задания графов, снятия результатов и проведения экспериментов с помощью PowerPoint. Подход позволяет в наглядной форме наблюдать за работой алгоритма, исключает ручное рутинное задание графов в текстовых файлах, при котором легко допустить ошибку, а также упрощает загрузку структуры графа в программу с помощью классов PowerPoint. Сформулированы выводы и основные результаты, в которых проанализирована эффективность предложенного алгоритма, протестированного на реальных графах из всемирно известного архива графов. Основная частьПостановка задачиДля неориентированного графа с весами на вершинах и рёбрах необходимо найти разбиение множества его вершин на сбалансированные подмножества, минимизировав при этом суммарный вес рёбер, соединяющих вершины из разных подмножеств. Подмножество сбалансировано, если сумма весов входящих в него вершин лежит в заданном интервале. Обзор существующих исследованийМуравьиная парадигмаМуравьи являются социальными насекомыми, живущими в высокоорганизованных колониях. Муравьи могут находить кратчайшие пути между источниками пищи и своим гнездом. Когда муравьи перемещаются от источника пищи к гнезду и в обратном направлении, они выделяют химическое вещество феромон, которое остаётся на земле, формируя след. Двигаясь, муравьи выбирают, с некоторой вероятностью, пути с сильными концентрациями феромона. След феромона помогает муравьям находить путь обратно к гнезду и достигать источников пищи, найденных своими собратьями. Феромон имеет свойство накапливаться и его концентрация на пути пропорциональна числу прошедших по нему муравьёв. Со временем феромон испаряется с редко посещаемых путей [12-14]. Для задач кластеризации и сортировки данных разработаны муравьиные алгоритмы [9, 10]. Автономные искусственные муравьи обладают некоторым объёмом памяти, функционируют в дискретном времени, способны анализировать списки смежности вершин графа и перемещаются по 2D решётке, в узлах которой расположены вершины графа. В зависимости от алгоритма определяются для незагруженного муравья вероятность подобрать элемент (p_p), а для загруженного муравья вероятность бросить его (p_d). Для пороговых констант k1 и k2: при f << k1 -> p_p приблизительно равна 1, f >> k1-> p_p приблизительно равна 0, при f << k2 -> p_d приблизительно равна 0, f >> k2-> p_d приблизительно равна 1, где f - число элементов, встреченных муравьём за Т шагов, делённое на Т. Приведенная модель поведения муравьёв обобщается для задачи разбиения графов при не фиксированном k [11]. Для всех вершин графа ставится во взаимно однозначное соответствие случайно выбранная точка на двумерной решётке. Муравьи реорганизуют точки так, чтобы: расположить вершины графа из одного кластера в общей области 2D пространства; минимизировать сумму весов межкластерных рёбер; чётко отделить кластера друг от друга. Полученные кластеры задают разбиение графа. На рис. 1 схематично показан пример размещения вершин в узлах 2D решётки, при котором вершины пространственно образуют различимые кластера.
Многоуровневая парадигма разбиения графовТрадиционные алгоритмы разбиения графов находят разбиение, работая непосредственно с исходным графом, как показано на рис. 2. Зачастую эти алгоритмы очень медленны либо генерируют разбиения низкого качества.
В практических задачах возникают графы с большим числом вершин (от 2,000 до 7,000,000), поэтому для их разбиения успешно применяется многоуровневая парадигма [15-20, 26]. Она позволяет получать "хорошие" решения за "разумное" время. Схематически многоуровневая парадигма разбиения графов показана на рис. 3.
Вначале, исходный граф G обрабатывается рекурсивной функцией, результатом работы которой является последовательность графов G, G1, G2, G3, ..., Gn, где каждый последующий граф получается укрупнением предыдущего графа, путём попарного стягивания вершин. Граф Gn разбивается на требуемое число подмножеств, причём возможно применение эвристик, которые не в состоянии работать на больших графах [21, 22]. Затем выполняются обратные действия, назначая вершинам v и w, стянутым в вершину u то же подмножество разбиения, что и для u. При укрупнении стягиваются пары вершин, вероятность которых быть помещёнными в разные подмножества разбиения мала. Программные системы для разбиения графовНаписаны пакеты на GNU лицензии с открытым кодом, реализующие алгоритмы разбиения графов для последовательных и параллельных машин. Они применяются на разных этапах во многих областях. Наиболее широко используемыми (порядка в 1000 организациях) системами являются: Chaco, Zoltan (B. Hendrickson, R. Leland) [27, 28], Party (Preis) [29], Jostle (C. Walshaw) [30], Scotch (Pellegrini) [31]. Один из вариантов многоуровневой парадигмы разбиения графов реализован в программном пакете METIS [23] для разбиения больших нерегулярных графов и сеток. METIS имеет большие преимущества по сравнению с другими подобными пакетами. Эксперименты на большом количестве графов, возникающих в различных областях, включая метод конечных элементов, линейное программирование, проектировку СБИС показывают, что METIS генерирует существенно лучшие разбиения, чем другие широко используемые алгоритмы, демонстрируя при этом скорость на один либо два порядка выше [23, 24]. В [18] сообщается, что граф из 7.5 миллионов вершин был разбит на 128 частей с помощью многоуровневого алгоритма на Cray T3E из 128 процессоров за 7 секунд. Эволюционное вычислениеЭволюционное вычисление является популярной оптимизационной парадигмой. Генетический алгоритм состоит из популяции индивидуумов (множества решений), которая эволюционирует на протяжении нескольких поколений с применением эволюционных правил. В алгоритме определяются следующие основные компоненты: способ представления решения и получения начальных решений, функция соответствия, критерий отбора, условие останова, генетические операторы - кроссинговер и мутация. В [16] описан эволюционный алгоритм, который для большинства графов из [25], находит лучшие на сегодняшний день разбиения. Индивиды посылаются в многоуровневый алгоритм разбиения графов, чтобы быстро получить разбиение. Далее выполняются генетические операторы, которые присваивают вершинам новые веса, равные a*b+c, где c- случайная величина в интервале [0,0.1], b=0.1 для кроссинговера и 2.0 для мутации. При кроссинговере, если у более, чем двух предков ребро разрезано, то a=0, иначе a=1. При мутации a=0, если в разбиении в некоторой окрестности данной вершины находится разрезанное ребро. Таким образом, многоуровневый алгоритм разбиения графов будет пытаться помещать вершины на концах тяжёлых рёбер в одно подмножество, производя поиск поблизости предыдущих хороших решений в пространстве решений. Хотя данный алгоритм часто находит лучшие по качеству разбиения (по количеству разрезанных рёбер), время его работы измеряется днями. Собственные разработкиПроцесс попарного стягивания вершин при укрупнении графа в многоуровневой парадигме имеет некоторую природу случайности и локальность, поэтому зависит от нумерации вершин [18]. Имеет место стягивание в одно подмножество разбиения тех вершин, которые следовало бы поместить в разные подмножества. Это приводит к ухудшению качества решения. В разработанном алгоритме предлагается при укрупнении графа стягивать сразу несколько вершин (кластеры). Кластер отличается от соседних вершин своей связностью либо суммарным весом входящих в него рёбер. Данный подход устраняет зависимость от нумерации вершин и повышает качество решения. Пусть муравей находится в вершине v и за единичное время перемещается только в вершину w из Adj[v] без простоев, где Adj[v] - множество смежных вершин v. Пусть A(T) - множество посещённых вершин на предыдущих T шагах, v принадлежит A(T). Тогда вероятность перехода из v в w равна we({w}, A(T))/ we(Adj[v], A(T)), где we(v, w)= вес ребра (v,w)*интенсивность феромона на ребре (v, w). Предполагается, что если C - кластер из вершин, а v в C, то вероятность попасть из v в q из C крайне высока. Значит, C захватывает муравьёв, и они начинают циркулировать в нём, причём за продолжительное время число покинувших его агентов много меньше прибывших и находившихся в кластере за это время. Муравей хранит вершины за последние t2 шагов, ему запрещено возвращаться в вершину, посещённую менее t1 шагов назад (t1< t2). Когда он находит цикл из t вершин (t2<=t<=t2), то из них выделяется подграф и на всех его рёбрах наращивается значение феромона на некоторую константу. Число рёбер и их вес является косвенной мерой качества найденного решения. Цель - изменить веса рёбер так, чтобы потом легко отличить кластеры. Искусственные муравьи используют новую модель поведения для отыскания кластеров, по сравнению с предложенными ранее [9-11]. Используя новые веса рёбер, можно выделить кластеры вершин и стянуть их в одну вершину.
Разработан новый вид муравьёв - трофо муравьи. Их поведение и структура отличаются от обычных муравьёв тем, что они не наращивают феромон на рёбрах найденного кластера, а потребляют его. Работа трофо муравьёв является новой уникальной распределённой схемой испарения феромона. Некоторые рёбра большого кластера могут получить много больше феромона чем другие. Трофо муравьи более равномерно распределяют феромон по рёбрам таких кластеров, повышая вероятность нахождения кластера целиком за одно укрупнение, а не по частям за несколько. Если область избыточествует феромоном, то она может надолго захватить обычного муравья. Поскольку поведение трофо муравья эквивалентно, то он тоже стремиться в ту область, циркулируя в ней, пока не потребит такое количество феромона, что вероятность выпустит и его и обычного муравья из той области, предотвращая зацикливание в ней муравьёв и сверхвыделение феромона. Обычные муравьи пойдут наращивать другие части кластера (либо другие кластеры), а трофо муравьи пойдут искать пищу (избыточествующие рёбра). Использование powerpointДля задания графа в пакетах разбиения графов используются текстовые файлы. В них построчно помещаются списки смежности вершин графа. Если для изображённого на бумаге графа выполнять это вручную, то легко допустить ошибку. Существуют утилиты, позволяющие задать граф визуально, однако они хранят описание графа в файлах, форматы которых специфичны для каждой утилиты. Для проведения экспериментов, визуального наблюдения за процессом работы алгоритма и снятия результатов в наглядной форме используется PowerPoint. Преимущество данного подхода в том, что он является COM-сервером, которым можно управлять непосредственно из собственного приложения и получать доступ к изображённому на слайде графу (с помощью эллипсов и соединительных линий) через соответствующие классы. Это приводит к бесформатному заданию графа, как если бы граф был уже загружен из файла. После выполнения заданного числа итераций, можно визуализировать интенсивность феромона на рёбрах через толщину соединительных линий. Если граф обрабатывает один муравей, то можно проследить пошагово его перемещение из вершины в вершину (текущая вершина и вершины очереди выделяются особыми цветами). Экспериментальные исследованияПроведены эксперименты с использованием METIS на графах из архива C. Walshaw [25]. В архиве доступна коллекция всевозможных графов, возникающих в различных областях. Также для этих графов в архиве собраны лучшие известные на сегодняшний день разбиения, полученные с помощью разных алгоритмов. Разбиения упорядочены по стоимости (количеству разрезанных рёбер), балансу и количеству частей, на которые разбит граф. На графах из этого архива принято тестировать алгоритмы разбиения графов. Вначале исходный граф разбивался с помощью METIS и находилась бисекция А. Затем исходный граф обрабатывался муравьиным алгоритмом и посылался в METIS для нахождения бисекции В.
Основные результаты сведены в табл. 1.
В таблице Cut(A) и Cut(B) - число разрезанных рёбер в бисекциях А и В соотвественно. Предлагаемый алгоритм действительно стягивает вершины, которые должны быть в одном подмножестве разбиения (в лучших найденных на сегодняшний день разбиениях из архива C. Walshaw стянутые вершины муравьиным алгоритмом находятся в одном подмножестве). Все эксперименты заняли около 5 часов и проводились на машине с Microsoft Windows Server 2003, процессором Intel Core 2 Duo с тактовой частотой одного ядра 1868 Mhz (фактически работало только одно ядро) и доступным объёмом оперативной памяти 477.50 MB. ВыводыВ работе исследована проблема разбиения графов. Для укрупнения графа в многоуровневой парадигме разработан муравьиный алгоритм. Он стягивает группы вершин (кластеры), вероятность которых быть помещёнными в разные подмножества разбиения мала. Для поиска кластеров разработаны новые эвристики по сравнению с известными. Удалось добиться получения качественных решений, всего за несколько часов для многих графов. Некоторые эволюционные схемы демонстрируют лучшие результаты [16], однако они работают несколько дней на одном графе. Дальнейшее совершенствование алгоритма состоит в его распараллеливании и реализация в компьютерной кластерной сети. Поскольку магистерская работа ещё не завершена, то распараллеливание алгоритма является новым этапом в её развитии в ближайшее будущее. Литература
|
|
