6.7. Задачи раскраски, построения клик и независимых множеств графов

Рассмотрим задачу раскраски графа. Раскраской вершин графа G = = (X, U) [89, 123, 124, 159] называется разбиение множества вершин X на L непересекающихся классов (подмножеств):

таких, что внутри каждого подмножества Хі не должно содержаться смежных вершин. Если каждому подмножеству Хі поставить в соответствие определенный цвет, то вершины внутри этого подмножества можно окрасить в один цвет, а. вершины другого подмножества Xj — в другой цвет и так далее до раскраски всех подмножеств. В этом случае граф называется L-раскрашиваемым.

Основной стратегией для задач раскраски графа являются последовательные и жадные эвристики, которые дают с первой попытки результаты с локальным оптимумом.

Последовательная эвристика заключается в следующем. Сначала составляется упорядоченный в порядке убывания степеней вершин список. Первая вершина удаляется из списка и окрашивается в цвет 1. Просмат-

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

Жадный алгоритм — это оптимизационный алгоритм, который основан на. жадной стратегии. Он просматривает серию альтернатив, выбирая лучшее решение. Запишем основные жадные эвристики для раскраски [184].

Эвристика 1. «Первые наибольшие». Вершины графа упорядочиваются по убыванию локальных степеней. Затем по порядку каждая вершина после анализа связности раскрашивается в определенный цвет.

Эвристика 2. «Наименьшие последние». Построение порядка из хаоса производится следующим образом. Выбирается вершина графа с наименьшей локальной степенью и удаляется из графа вместе с инцидентными ребрами. В оставшемся графе повторяется та. же процедура. Вершины графа раскрашиваются в возможный для этой процедуры цвет в порядке, обратном порядку удаления. Затем вершины красятся в определенный цвет в порядке, обратном процессу удаления вершин.

Эвристика 3. «Разбиения по смежности». В начале алгоритма выбирается вершина графа максимальной степени и раскрашивается в цвет 1. Затем все нераскрашенные вершины разбиваются на. два подмножества: Х\ — смежные с раскрашенными и Х2 — несмежные с раскрашенными. Выбор очередной вершины для раскраски в возможный цвет осуществляется по наибольшей степени в Далее процесс продолжается аналогично до заполнения цвета 1. После этого вершины, раскрашенные цветом 1, удаляются и процедура продолжается до полной раскраски графа.

Эвристика 4. «Раскраска ранее упорядоченных вершин». Для вершины Хі выбирается цвет к, если и только если среди вершин, смежных с Хі~ вершиной, существуют уже раскрашенные вершины цветов с = 1,2,...

—    l,fc + l,fc + 2,...и нет вершин, помеченных цветом к.

Эвристика 5. «Специальная раскраска в предписанные цвета». Предварительно для каждой вершины задан набор цветов, в которые она может быть раскрашена. Упорядочение вершин производится следующим образом. Определяются вершины с минимальным числом N = р(хі) + Zi/C, где р(хі) — локальная степень вершины Хі 6 X графа G = (X, 17), Zi — число запрещенных цветов для данной вершины, С — общее число цветов. Вершина Хі с минимальным значением N удаляется из графа вместе с ребрами. Для оставшегося графа повторяется такая же процедура и так далее. Затем вершины красятся в возможный цвет в порядке, обратном порядку удаления [185].

Запишем простой алгоритм на. основе одной из рассмотренных жадных эвристик:

1.   Упорядочить вершины по убыванию локальных степеней.

2.   Каждой вершине упорядоченного списка назначать первый имеющийся цвет, если это возможно.

3.   Шаг 2 продолжать до полной раскраски графа.

4.   Конец работы алгоритма.

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

Рассмотрим, например, задачу раскраски графа (рис. 6.48) [89]. Эвристика из хаоса вершин графа создает следующий порядок: (97 1 8 6 3 2 54). Сначала раскрашивается вершина 9, алгоритм оставляет вершину 7 не раскрашенной, так как она соединена с 9, а. вершина 9 уже раскрашена. Эвристика не раскрашивает вершину 8 по той же причине. Далее раскрашивается вершина 1 и не раскрашиваются остальные. Следовательно, Х\ = {9,1}. На втором шаге получим Х2 = {7,6, 5}. Далее, Х3 = {8,3,4} и Х4 = {2}. Получим, что граф G (рис. 6.48) раскрашен 4 цветами.

Рассмотрим второй граф, изображенный на рис. 6.49. Это колесо W7 содержит 7 вершин. Первые шесть вершин расположены в виде кольца, а. седьмая вершина расположена в центре кольца и соединена со всеми остальными вершинами. Жадная эвристика из хаоса вершин графа создает следующий порядок: (7 6 543 2 1). Алгоритм раскрасит вершины следующим образом: Х1 = {7}; Х2 = {6,4,2} и Х3 = {5,3,1}. Получим, что колесо W7 (рис. 6.49) раскрашено 3 цветами. Отметим, если в графе, аналогично колесу, имеется одна вершина, смежная всем остальным, то она раскрашивается одним цветом и удаляется из упорядоченного списка.

Так как жадная и последовательная эвристики раскраски графа достаточно быстрые, то предлагается совместить их с ГА с учетом концепций ЭМ. Стратегия совмещения предполагает, что используется кодирование нашего алгоритма для гибридного ГА. Кодировка, используемая в жадной эвристике, основана на упорядочивании вершин графа. Она упорядочивает вершины по уменьшению значений локальных степеней вершин и затем декодирует эту последовательность, назначая каждой вершине по порядку первый реальный цвет, где реальность основана на использовании цветов при раскраске предыдущих вершин. Такой способ кодировки при решении проблемы раскраски графа упорядочивает вершины графа определенным способом, а. затем декодирует их в соответствии с жадной эвристикой.

Первое, что необходимо изменить в ГА — это замена бинарной ЦФ на ЦФ раскраски вершин. Согласно ЦФ выбираем первый ген (вершину) в хромосоме и присваиваем ей первый реальный цвет, если это возможно.

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

На следующем шаге осуществляется замена инициализации на случайную или основанную на знаниях о решаемой задачи перестановку. В ГА будем генерировать случайным и заданным образом переставленный список вершин. Жадная эвристика генерирует только одну хромосому, но эта хромосома имеет шанс оказаться лучше, чем средняя. Такая процедура гарантирует, что с помощью ГА мы как минимум не ухудшим результат жадной эвристики, так как используется элитная и другие процедуры селекции для создания начальной популяции. В результате изменений порядка элементов в упорядоченном списке получим измененный список вершин графа. Упорядоченный список и список с изменениями и будут в дальнейшем использоваться. Применяя к полученным хромосомам генетические операторы, определяем ЦФ. В рассматриваемом алгоритме применяются элитная селекция и генетические операторы, описанные выше. Процесс совмещения связан с изменениями репродукционного модуля, где используются генетические операторы, работающие с упорядоченным представлением.

В [89] описан однородный универсальный ОК, приспособленный для области упорядоченных генетических операторов. Рассмотрим модификацию данного оператора. Этот оператор сохраняет основную часть первого родителя, а. также добавляет информацию о втором. Информация, которая здесь закодирована, не имеет фиксированного значения, связанного с его позицией в хромосоме. Модифицированный универсальный ОК позволяет второму родителю «сказать» первому родителю, какие элементы следует упорядочить no-друшму. Сетевой эффект модифицированного универсального ОК состоит в совмещении относительного порядка вершин двух родителей с хромосомами двух потомков.

Запишем алгоритм реализации этого ОК. Пусть заданы альтернативные решения, как родитель-1 и родитель-2, тогда потомок-1 получается следующим образом:

1.   Генерируется бинарная строка-шаблон, количество элементов в которой совпадает с длиной родителей.

2.   Гены из родителя-1, соответствующие единицам в строке шаблона, копируются на следующий шаг.

3.   Создается список генов из родителя-1, соответствующих 0 в бинарной строке.

4.   Последовательно просматривая элементы родителя-2, помещают в пустые позиции хромосомы еще не вошедшие гены.

5.   Объединяя эти элементы без повторений, получаем потомка-1.

6.   Конец работы алгоритма.

Построение потомка-2 производится аналогичным образом.

Рассмотрим пример для графа., приведенного на рисунке 6.48. Пусть альтернативные решения закодированы следующим образом:

Результат после шага два:

Окончательный результат:

Здесь БС — бинарная строка, показывающая смежность соответствующих вершин в рі и р2. То есть, 1 в БС показывает, что вершины 5 и 9 (рис. 6.48) связаны между собой. Если смежных вершин в заданных родителях нет, тогда бинарная строка заполняется 0 и 1 случайным образом. Выполнив жадное декодирование, получим, что хромосома рз соответствует следующей задаче раскраски графа (рис. 6.51): Х\ = {9,2,4}, Х2 = {5,3,7}, Х3 = {1,6} и Х4 = {8}. Для р4 получим задачу раскраски графа: Хі = = {9,3,4}, Х2 = {8,2,1}, Х3 = {7,6} и Х4 = {5}. Здесь часть структуры каждого родителя зафиксирована одним родителем (как указано в битовой строке). Остальные переупорядочены так, что элементы остаются в том же порядке, в котором они были в другом родителе. Заметим, что основная проблема здесь — декодирование ОК. Эта операция имеет временную сложность алгоритма 0(п2), где п — размер хромосомы.

В [89] описан оператор частичной мутации. Он выбирает часть родительской хромосомы, и, произведя перестановки внутри нее, переносит эту часть в потомка, а. остальную оставляет без изменений. Такой тип мутации не имеет параметров, хотя для длинных хромосом полезно ограничивать длину секции. Все генетические операторы такого вида имеют сложное декодирование. Опишем жадную стратегию с одновременным декодированием хромосом. Пусть для графа G (рис. 6.48) задана популяция Р = = {Рі,Р2,Рз,Ра}'

В хромосоме рі выбирается ген, соответствующий вершине с максимальной степенью. Если таких вершин несколько, то они анализируются последовательно в произвольном порядке. В первой хромосоме выбираем

элемент 9. Согласно жадному ОК следующей выбирается вершина 1. Дальнейшие шаги жадного ОК на всей популяции приводят к тупиковым ситуациям. Следовательно, определен первый цвет Х\ = {9,1}. Элементы 9,1 исключаются из всех хромосом популяции Р. Далее в рі выбирается элемент 7. Согласно жадному ОК получим второй цвет Х2 = {7,6,4}. Продолжая, аналогично определим, что Х3 = {8,2,5} и Х4 = {3}. Следовательно, граф (рис. 6.48) раскрашивается четырмя цветами. Данная методика позволяет сокращать размер хромосом (альтернативных решений) на каждом шаге и соответственно время раскраски графа.

Кроме генетических операторов необходимо также определить тип селекции. Для задачи раскраски графа наиболее применима модифицированная элитная селекция, которая реализуется по следующей схеме [17,89]. Все хромосомы t-ro поколения упорядочиваются в порядке убывания значений степеней вершин (приспособленности к внешней среде). Выживают только первые г из упорядоченных хромосом, т. е. те, для которых ранг г(р\), равный к-й позиции в упорядоченной последовательности хромосом, меньше или равен і, то есть, г(р\) <С г.

Структура гибридного ГА, используемого для задачи раскраски графа, представлена на рис. 6.50.

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

Задача, раскраски графа, тесно связана, с построением независимых или внутренне устойчивых подмножеств, а. также определением клик графа.. Если две любые вершины подмножества. X' графа. G = (X, 17), X' С X, не смежны, то оно называется внутренне устойчивым. Подмножество Фі С С X графа. G = (X, 17) называется максимальным внутренне устойчивым подмножеством или независимым, если добавление к нему любой вершины Хі С X делает его не внутренне устойчивым. Подмножество Фі будет независимым, если

Здесь Ті — подмножество вершин, смежных Хі.

Независимые подмножества, различаются по числу входящих в них элементов. В произвольном графе G можно выделить семейство всех независимых подмножеств вида. Ф^ = {Фі, Ф2,..., Ф5} или его части [159]. Жадные стратегии, используемые для задачи раскраски графа., также эффективно применяются для построения семейства, независимых подмножеств. Например, построим семейство независимых подмножеств для графа. G, представленного на. рисунке 6.51. Здесь предварительно произведем упорядочивание вершин по возрастанию, начиная с наименьшей локальной степени. Работу модифицированного жадного ОК покажем на. примере.

Пусть для графа G (рис. 6.51) задана популяция Р = {рі, р2, рз, Р4, Рб } •

Работа алгоритма начинается с выбора в упорядоченной хромосоме р$ первого элемента—5. Далее выбираем вершину 6, так как она соседняя вер™

шине 5 в хромосоме р$ и не смежна ей. Аналогично выбираем 7 — вершину в этой хромосоме. После этого, анализируя популяцию Р, в хромосоме рз выбираем вершину 9. Дальнейший анализ популяции Р показывает, что построено первое независимое подмножество Фі = {5, б, 7,9}.

Существует большое число стратегий построения независимых подмножеств. Одна из них состоит в построении независимых строительных блоков на две, три, четыре и так далее вершин с дальнейшим объединением этих, строительных блоков в независимое подмножество. Другая стратегия (в ширину) предусматривает нахождение всех независимых подмножеств, в которые входит первая рассматриваемая вершина (в нашем случае вершина 5) с дальнейшим анализом других вершин на предмет создания новых независимых подмножеств. Третья стратегия (в глубину) предусматривает последовательный анализ всех вершин в упорядоченном списке (хромосома р§) до получения семейства независимых подмножеств. Четвертая стратегия является комбинацией первых трех. Применяя четвертую стратегию для графа G (рис. 6.51), получим набор независимых подмножеств Ф2 = {6,7,8}, Фз = {7,8,2}, Ф4 = {8,1,3}, Ф5 = {9,2,4,5}, Ф6 = {1,2,5}, Ф7 = = {2, 5, 7,9}, Ф8 = {3,5, 7,9}, Фд = {4, 5,6,9}. Очевидно, что данный набор не полный. Для получения полного семейства независимых подмножеств необходимо продолжить реализацию данных стратегий.

Описанная методика эффективно используется для задачи раскраски графа. Например, пусть Ф5 задает первый цвет Х\ = {9, 2,4, 5}, Ф2 задает второй цвет Х2 = {6, 7,8}, а. Фз задает третий цвет Х3 = {1,3}. Следовательно, граф G (рис. 6.51) раскрашен тремя красками. Временная сложность алгоритма построения, семейства независимых подмножеств лежит в пределах 0(п2)^0(п4).

Заметим, что обратной для построения независимого подмножества является задача построения клик графа [123, 159]. Подмножество из максимального числа смежных между собой вершин в графе называется кликой. В графе можно выделить некоторое семейство клик: К = {кі, к2,..., kz}. Очевидно, что стратегии, описанные выше, могут быть применены для определения семейства клик. Покажем на примере графа G (рис. 6.52) упрощенную схему работы ГА для определения клик графа.

Пусть для графа G (рис. 6.52) задана популяция Р = {рі, р2, рз, Р4, Рб }:

Применим следующую схему поиска, основанную на ГА и жадной стратегии:

1. 1.

2. 1, 2 — образовано полное подмножество на две вершины.

3.1, 2, 3 ♦(тупик).

4.   1, 3 ♦.

5.   1, 5 ♦.

6.   1, 10, 11 ♦.

7.   1, 10, 9,11#.

8.   1, 10, 9, 8 #.

9.   1, 10, 9, 2,3#.

10.  1, 10, 9, 2,4#.

11.  1, 10, 9, 2,6#.

Построена первая клика к\ = {1,10,9,2}. Элементы, соответствующие вершинам к\, удаляются из всех хромосом популяции. Получаем новую популяцию с хромосомами меньшей длины:

Продолжая далее:

1.   3.

2.   3,4.

3.   3,4,5.

4.   3,4,5, 6f.

5.   3,4,5, 12 f.

6.   3,4,5, 7,8, 11 f.

7.   3,4,5, 7,8, 6f.

8.   3, 4, 5, 7, 8, 12 f.

Построена вторая клика к2 = {3,4, 5, 7,8}. Далее, продолжая аналогично, построим третью клику кз = {6,11,12}. Отметим, что за 21 элементарный шаг на основе жадной модифицированной стратегии генетического поиска получены основные три клики графа. Временная сложность алгоритма в лучшем случае О(п), в самом худшем случае 0(п\). В среднем для реальных графов имеем 0(п2)^0(п3).