ВЕСТНИК ЮЖНОГО НАУЧНОГО ЦЕНТРА РАН Том 1, №2, 2005, стр. 51-57
_________________ ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ ____
И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ
УДК 519.712.2
РЕШЕНИЕ ЗАДАЧИ ПЛАНАРИЗАЦИИ ГРАФОВ НА ОСНОВЕ БИОНИЧЕСКИХ ТЕХНОЛОГИЙ
© 2005 Л.А. Гладков1
В данной статье рассматривается проблема планаризации графовых моделей объектов оптимизации на основе бионических технологий. Приведена математическая постановка задачи планаризации. Представлен новый подход к решению проблемы планаризации на основе комплексного использования критерия Мак-Лейна, матричного алгоритма Данна-Чена и бионических методов. Разработан алгоритм планаризации, позволяющий определять планарность и строить плоскую укладку графа. Рассчитана оценка теоретической и временной сложности разработанного алгоритма, а также проведены вычислительные эксперименты, подтвердившие эффективность предложенного подхода.
Проблема планаризации графов - определение планарности и построение плоской укладки графа - относится к числу сложных оптимизационных задач. В то же время эффективное решение данной проблемы очень важно и результаты могут использоваться для решения различных практических задач науки, техники и управления. Среди них можно выделить, прежде всего, задачи автоматизированного проектирования, когда имеется необходимость построения математической модели рассматриваемого объекта, обладающей определенным набором свойств. Удобным инструментом моделирования дискретных объектов на сегодняшний день является теория графов, имеющая формальный математический аппарат и позволяющая создать математическую модель, описывающую необходимые параметры объекта проектирования. С точки зрения теории графов задача планаризации может быть описана следующим образом [1-5].
Постановка задачи. Граф О = (X, Ц) называют плоским, если существует такое изображение на плоскости его вершин и ребер, что каждая вершина х{ е X изображается на плоскости отдельной точкой и каждое ребро щ е и изображается простой кривой, имеющей концевые точки (л;,, хк), причем эти кривые пересекаются только в общих концевых точках, то есть в вершинах. Граф называется планарным, если он изомор-
1 Таганрогский государственный радиотехнический университет, г. Таганрог.
фен плоскому, то есть, существует возможность получения плоской укладки такого графа.
Существует несколько методов и критериев определения планарности графа [1]. В данной работе мы рассмотрим один из них.
Критерий Мак-Лейна. Граф в планарен тогда и только тогда, когда каждый его блок, содержащий, по крайней мере, три вершины, обладает таким базисом циклов Ъг, Хт и таким дополнительным циклом что любое ребро блока принадлежит точно двум из этих т + 1 циклов. Этот критерий основан на рассмотрении циклической структуры графа. Как следует из формулы Эйлера, все внутренние грани двусвязного плоского графа в образуют базис циклов Ъх, 2
где т - циклический ранг графа в. Кроме того, имеется также ~ внешний простой цикл графа в. Тогда любое ребро такого графа в будет принадлежать точно двум из т + 1 циклов Тг
Рассматриваемая задача относится к классу оптимизационных задач, принимающих в зависимости от полученного решения значения " Г' (в случае, если граф планарен) или "0" - в противном случае.
(200 —> шах; х е {0, 1}.
То есть, цель работы состоит в создании новых эвристических методов и процедур, сокращающих время и увеличивающих область поиска. Это, например, бионические методы и алгоритмы, позволяющие работать одновременно не с одним, а с множеством решений [6-10].
Разработка алгоритма планаризации на основе бионических технологий. Предлагаемый ал-
горитм имеет блочную структуру, где каждый блок является отдельным фрагментом, входные данные для которого предоставляет предыдущий блок (за исключением начального блока). Укрупненная (блочная) структурная схема нового генетического алгоритма представлена на рис. 1. Опишем функции каждого блока.
Первым блоком является ввода исходных данных. Исходный граф в задается в виде модифицированных списков смежности где каждой вершине ставятся в соответствие номера инцидентных ей ребер, например, запись 1 ] 2 означает, что ребро 1 инцидентно вершинам х, и х2. Причем в список смежности вершины х1 не включаются номера вершин от X! до х,_ г включительно.
Генерация циклов осуществляется на основе поиска в глубину. Таким образом, формируется множество циклов длины ку представляющих собой цепочки вида х{- ... - х^- ... - хк- хЛ. Когда сформированы все циклы, с начальной вершиной хь алгоритм переходит к следующему списку.
В результате получим множество всех циклов длины к: Ск = {С,, С2,С,}, где г - число циклов длины к. На основе этих списков формируется матрица циклов В = IIЬу где с - число циклов, а т - число ребер графа. Причем Ь^ = 1 в случае, если ребро т/ принадлежит циклу с1 {т] е с,), и Ьу = 0, в противном случае.
Полученные данные являются исходными для начала процедуры анализа. Алгоритм процесса анализа и принятия решения можно записать в следующем виде:
1. Подсчет числа циклов ДГс* = I Ск I и числа повторов NтI каждого ребра тр где ] - 1,..., М.
2. Если ]УсА £ т - п + 2 & (V/ е М)(Мт} > 2), то переход к п. 3, иначе возврат к блоку генерации циклов длины к + 1.
3. Для первых (т - п + 2) - циклов из множества Ск подсчитывается общее число ребер Ми, принадлежащих этим циклам:
Хт= ик\Ск\)
к = з
где к - длина цикла, I Ск I - мощность множества циклов длины к, К - длина самого длинного из сгенерированных циклов, вычисляемая по формуле К = к + где 5 - число шагов в блоке генерации циклов.
4. Значение N¡71 сравнивается с удвоенным числом ребер графа в. Если Мт > 2т, то граф непланарен. Для выделения максимальной пла-нарной части графа переходим к п. 6, иначе к п. 7.
Рис. 1. Укрупненная структурная схема алгоритма планери-зации
5. Если АЫ < 2т, то к множеству добавляются циклы длины к + 1. Если циклы длины к + 1 отсутствуют, то нужно вернуться к генерации циклов длины к + 2, в противном случае переход к п. 6.
6. Завершение работы блока анализа, полученные данные (множество циклов и предполагаемая схема комбинации) фиксируются.
7. Конец работы алгоритма.
Была предложена новая оригинальная методика кодирования решений. Как уже говорилось, нам необходимо в результате выделить базис циклов Вр, где р = т - п + 2. Тогда каждая хромосома имеет р + 3 разрядов (генов) и состоит из двух частей. Левая часть {р - разрядов) - это комбинация циклов, представляющая собой вариант плоской укладки графа. Правая часть (последние три разряда) несет информацию о том, какие ребра и сколько раз содержатся в выбранной комбинации (0, 1 или 2 раза соответственно для разрядовр + 1, р + 2 и р + 3). Кроме того, эти разряды используются при оценке качества полученного решения. Для чего вводится функция оценки 6(т), которая стремится к минимуму для генов р + 1 и р + 2 (/(Н) —»0) и стремится к мак-
симуму для гена р + 3(/(Н) —> т):
5(т) = (2 х Nmp + 3 + Nmp + 2)/2т,
где Nmp + 3, Nmp + 2 - число элементов в разрядах р + 3 и р + 2 соответственно.
Функция Ь(т) принимает значения на интервале [0,1], причем качество решения будет тем выше, чем больше ребер (особенно ребер, встречающихся дважды) задействовано в оцениваемом решении. Целевая функция (ЦФ) базового решения не может быть менее 0,5. В левой части хромосомы могут быть значащие и незначащие разряды. Значащие разряды это номера циклов, а незначащие - нули. Очевидно, что решение улучшается при заполнении незначащих разрядов (L0 —> 0). Итак, ЦФ хромосомы ДН) является аддитивной функцией двух переменных ДН) = (5(ги); L0) иДН) шах при 6(я?) 2т & Lq —> 0.
Методику расчета ЦФ решения покажем на следующем примере. Пусть существует произвольная комбинация циклов Ct, С2 и С3, закодированная следующим образом:
{3, 9, 10, {4, 5,
1 2 3 0 0 0 0 0 0 0 11, 12, 13, 14,15,16} 6, 7, 8} {1,2}
ЦФ данной хромосомы будет равна ДН) = (0,2613; 7): Ц = 7; 5(т) = (2x2 + 5)/(2 х х 16) = 9/32 = 0,2813. Следовательно, данное решение не может считаться базовым.
Разработано несколько вариантов стратегии создания начального базового решения, избираемых в зависимости от характера исходных данных и решения ЛПР.
Последовательность заполнения начального базового решения представлена на рис. 2.
Шаг "А". Формируем множество промежуточных решений, из числа которых будет выбран второй родитель для участия в операции скрещивания. Формирование множества происходит путем попарного объединения циклов таким образом, чтобы образующиеся в результате парные ребра были идентичны ребрам, присутствующим в разрядах р + 1, р + 2 начального базового решения. Кроме того, номера циклов множества промежуточных решений не должны совпадать с номерами циклов участвующих в базовом решении. Размер популяции промежуточных решений зависит от числа ребер в разрядах р + 1, р + 2 базового решения и от длины хромосомы Ь (т.е. размерности исследуемого графа).
Шаг "В". Оценка множества промежуточных решений. Для каждого решения были разработаны следующие правила:
Рис. 2. Структурная схема ГА (Этап № 2)
1. В генах р + 2 и р + 3 претендента, по возможности, не должно быть ребер, совпадающих с ребрами из разряда р + 3 первого родителя.
2. В генах р + 1 претендента и р + 3 первого родителя желательно иметь максимальное количество совпадающих ребер.
3. В гене р + 2 претендента должно быть максимальное число ребер, идентичных ребрам из разряда р + 2 хромосомы первого родителя.
На основе правил предложена функция пригодности промежуточных решений относительно базового решения /'(Н) = (6^;АГ,'). функция /'(Н) является аддитивной функцией двух переменных, где Ъ'т - относительное увеличение
числа ребер; № с - относительное увеличение числа циклов. Количественное значение функции пригодности рассчитывается исходя из числа совпадений ребер в соответствующих разрядах анализируемых решений, а также числа циклов, которые добавляются (удаляются) в базовом решении.
Подсчитывается значение Ь'т по формуле:
= 1 - [(2 х ЛЦ + N(¿2 + Ш3)/(2 х Л^ + N$2 +
+ М3)]. Полученное значение зависит от соотношения числа удаляемых и добавляемы
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.