litceysel.ru
добавить свой файл
1
УДК 681.3.001.63


Эволюционные процедуры решения комбинаторных задач на графах*

Б.К. Лебедев, О.Б. Лебедев1

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

Введение

Среди набора комбинаторно-логических задач на графах важное место занимает проблема определения паросочетаний, раскраски графа, выделения в графе внутренне устойчивого множеств вершин и клик. Эвристические алгоритмы решения данных задач применяются при проектировании инженерных сетей, коммуникаций, построения систем поддержки принятия решений в неопределенных условиях, проектировании СБИС и т.п. Задачи такого типа относятся к переборным задачам с экспоненциальной временной сложностью. В этой связи разрабатывают различные эвристики для построения алгоритмов с полиномиальной временной сложностью. Существуют алгоритмы определения паросочетаний в графе, основанные на использовании потоков в сетях [Андерсон, 2003], [Кормен и др., 2000], имитационного моделирования [Свами и др., 1984], генетического поиска [Курейчик и др., 2003] и других эвристиках. В работе предлагается новый метод определения максимального паросочетания в графе, основанный на идеях поисковой адаптации.

1. Основные положения

Одной из широко востребованных задач целочисленного программирования является задача о паросочетании максимальной мощности, рассматриваемой в комбинаторном направлении теории графов. Паросочетанием графа G=(X,U) называет подмножество таких рёбер UU, что любые два ребра uk,ul U не имеют общих вершин, т.е. не смежны. Паросочетание максимальной мощности определяется как паросочетание, состоящее из максимального числа рёбер [Андерсон, 2003].


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

Существующее в настоящее время большее количество алгоритмов нахождения максимального паросочетания обеспечивают приемлемые результаты при решении задач малой и средней сложности. Возникшие потребности в решении задач большой и очень большой размерности является побудительным мотивом исследований и разработок новых эффективных алгоритмов. Анализ литературы показывает, что наиболее успешными в этих условиях являются методы, основанные на моделировании эволюционных процессов [Лебедев и др., 2005].

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

Пусть дан граф G=(X,U) (рис. 1). U={ui| i=1,2,…,9}. Паросочетание такого графа определяется как множество рёбер, не имеющих общих вершин. Например: паросочетание P={u1, u4, u7, u9}. Построим граф Gd=(U,V) - двойственный для графа G. Вершины графа Gd - соответствуют рёбрам графа G. Пара вершин (ui, uj) в графе Gd связаны ребром в том и только в том случае, если в графе G пара рёбер (ui, uj) смежны, т.е. инциденты одной вершине.





Рис. 1. Пример графа


Для примера, представленного на рис. 1, двойственный граф Gd имеет вид, представленный на рис. 2.




Рис. 2. Двойственный граф Gd


Множество X0 вершин графа G=(X,U) называется внутренне устойчивым, если любые две вершины xi X0 и xj X0 не являются смежными. Максимальное число вершин во внутренне устойчивом множестве графа G называется числом внутренней устойчивости и обозначается как α(G). Иногда число внутренней устойчивости называют также числом независимости графа G.

Подмножество вершин P={u1, u4, u7, u9} является внутренне-устойчивым, т.к. любые две вершины подмножества P не смежны. Таким образом, паросочетанию графа G соответствует внутренне–устойчивое подмножество двойственного графа Gd.

Максимальному по мощности паросочетанию графа G соответствует предельное внутренне–устойчивое подмножество (содержащее наибольшее число вершин) двойственного графа Gd.

Построим для двойственного графа Gd матрицу смежности R (рис. 3). Переставим все столбцы и строки помеченные элементами некоторого внутренне–устойчивого подмножества P таким образом, чтобы они располагались рядом друг с другом начиная с левой (верхней) стороны матрицы. Для нашего примера модифицированная матрица R имеет вид, представленный на рис. 4. Анализ состояния матрицы смежности показывает что если столбцы матрицы с номерами от l до l+m помечены элементами, образующими внутренне-устойчивое подмножество, то симметрично относительно главной диагонали матрицы R на пересечении столбцов и строк матрицы с номерами от l до (l+m -1) формируется область Pi квадратной формы размером m*m, элементы которой имеют нулевое значение. Назовем такую область -областью. В приведенном примере -область – это область, образованная при пересечении 1-4 столбца с 1-4 строкой. Столбцы и строки помечены элементами 1,4,7,9. Pi=Pi(l,m), где l – номер первого столбца (и первой строки), с которого начинается -область Pi, m - число столбцов и строк, на пересечении которых образована -область Pi. Для нашего примера P1=P1(1,4).






Рис. 3. Исходная матрица смежности Рис.4. Матрица смежности с

построенной -областью


Таким образом, если в результате некоторой перестановки строк и столбцов матрицы смежности образуется -область Pi(l,m), то это значит, что элементы, которыми помечены столбцы и строки с номерами от l до (l+m-1), образуют внутренне-устойчивое подмножество Ui. И если операция производилась на графе Gd, двойственном к G, то подмножеству Ui соответствует паросочетание в G. Отсюда схема нахождения в графе G паросочетания максимальной мощности выглядит так.

Строится граф Gd , двойственный к графу G. Путём перестановок строк и столбцов матрицы смежности R графа Gd формируется -область Pi(l,m) с максимально возможным значением параметра m. Множество элементов Ui, которыми в матрице смежности R помечены столбцы с номерами от l до (l+m-1), будут составлять максимальное паросочетание в графе G.

Раскраской графа называется такое приписывание цветов его вершинам, что никакие две смежные вершины не получают одинакового цвета. Минимальное число цветов, в которое можно раскрасить граф G, называется хроматическим числом и обозначается χ(G) [Курейчик, 1990].


Будем считать, что -область Pi(l,m) покрывает строки и столбцы матрицы смежности R с номерами от l до (l+m-1). Назовём две -области Pi(li,mi) и Pj(lj,mj) смежными друг к другу, если lj=li+mi. Пересечение двух смежных -областей равно . Если в результате перестановок столбцов и строк матрицы R образуется цепочка из s последовательно прилегающих друг к другу, то есть смежных -областей, объединение которых покрывает все столбцы и строки матрицы R, то можно считать, что в графе G выделено s внутренне-устойчивых подмножеств вершин и, следовательно, граф можно раскрасить в s цветов.

Таким образом задача раскраски графа сводится к задаче формирования в матрице смежности графа цепочки -областей с вышеперечисленными свойствами. Формирование цепочки с минимальным числом -областей соответствует раскраске в минимальное число цветов.

На рис. 4 в матрице R сформирована цепочка из 3-х областей. Следовательно, граф раскрашивается в 3 цвета. {u1, u4, u7, u9} – 1 цвет, {u5, u2, u8} – 2 цвет, {u3, u6} – 3 цвет.


Рассмотрим задачу о клике. Кликой графа G называется максимальное по включению множество X0 вершин графа, любые две из которых являются смежными. Нетрудно видеть, что при переходе от графа G к его дополнению каждая клика в G переходит в независимое множество в . Отсюда следует, что задача выделения клики в графе G сводится к задаче выделения независимого множества вершин в графе , являющегося дополнением графа G.

Таким образом в основе процедур построения максимального паросочетания, раскраски графа, выделения в графе внутренне устойчивого множеств вершин и клик лежит одна общая процедура формирования η-областей в матрице смежности графа.

2. Эволюционные механизмы формирования η-областей

Формирование η-областей в матрице R осуществляется в процессе её эволюционной модификации. Эволюционная модификация матрицы R производится путём выборочных групповых перестановок соседних столбцов и строк, что обеспечивает направленное последовательное перемещение элементов матрицы R с нулевым значениями и объединение их в η-области.

Адаптивный процесс состоит из повторяющихся шагов, каждый из которых представляет собой переход от одного решения (состояния матрицы R) к другому – лучшему [Лебедев, 1999].

На каждом шаге анализируются пары (i, i+1) соседних строк матрицы. Анализ осуществляется в два такта. На первом такте анализируются все пары (i, i+1), у которых первый элемент i-нечетное число. На втором такте анализируются пары, у которых первый элемент i-четное число.


Например: пусть n=9, тогда на первом такте рассматриваются пары строк {(1,2),(3,4),(5,6),(7,8)}. На втором такте - {(2,3),(4,5),(6,7),(8,9)}.

Пары строк анализируются независимо друг от друга. По результатам анализа принимается решение о перестановке соседней пары строк.

Локальная цель перестановок - перемещение нулевых элементов матрицы снизу-вверх и справа-налево. Глобальная цель - формирование η-области Pi(l,m) с максимальным значением параметра m, то есть выделение максимального внутренне-устойчивого множества.

Пусть для анализа выбрана пара строк (i, i+1) матрицы R=||rij|| размером n*n .В строках выделяют две части: 1 - (j=1÷i-1); 2 - j=i+2÷n).Суть анализа заключается в определении истинностного значения трёх нижеприведенных условий.

1. > - 1-я часть.

2. = - 1-я часть, и> - 2-я часть.

3.= - 1-я часть, и= - 2-я часть.


Ответ «да», то есть – переставлять, вырабатывается, если выполняются условия 1 и 2 . В случае выполнения условия 3 ответ «да» вырабатывается с вероятностью P, задаваемой априорно. В остальных случаях вырабатывается ответ «нет».

Адаптивная поисковая процедура продолжается, пока существуют пары, для которых выполняются условия 1 и 2. в результате будет сформирована η-область P1(1,m) и в графе Gd определено максимальное внутренне-устойчивое подмножество X1d.

Если целью поиска было нахождение максимального паросочетания, то работа алгоритма на этом завершается.

Если же решается задача раскраски, то в графе Gd удаляется подмножество вершин X1d, а из матрицы R удаляются m столбцов и строк, покрывающих область P1(1,m). Образуя граф G1d и матрицаR. Далее над полученной матрицей R1 производится аналогичные действия, то есть в G1d выделяется максимальное внутренне-устойчивое подмножество X2d .Выше перечисленные действия продолжаются, пока матрица смежности не станет пустой, т.е. все вершины будут окрашены.

Пример. Пусть дан граф G , представленный на рис. 1. Двойственный к графу G граф Gd представлен на рис. 2.

Матрица смежности графа Gd представлена на рис. 3.

На каждом шаге, на первом такте рассматриваются пары {(1,2),(3,4),(5,6), (7,8)}, на втором такте - пары {(2,3),(4,5),(6,7), (8,9)}. Пара строк и столбцов переставляется, если выполняется одно из трёх вышеперечисленных условий. В исходной матрице R столбцы и строки помечены номерами вершин графа Gd. Перестановка соседней пары строк (i, i+1) или столбцов приводит также к перестановке их меток. Будем в дальнейшем для идентификации строк и столбцов использовать их метки.


Шаг 1, такт 1: (1,2) - нет; (3,4) -да (по условию 1); (5,6) - нет, (7,8) - нет. Итак, на 1-м такте 1-го шага осуществляется перестановка пары (3,4). Модифицированная матрица R после шага 1,1 представлена на рис. 5.

Шаг 1, такт 2: (2,4) - да (по условию 1), (3,5) - да (по условию 1), (6,7) - да (по условию 1), (8,9) - да (по условию 1). Модифицированная матрица R после шага 1,2 представлена на рис. 6.

Шаг 2, такт 1: (1,4) - нет; (2,5 ) - да (по условию 1); (3,7) - да (по условию 1); (6,9) – да (по условию 1). Модифицированная матрица R после шага 2,1 представлена на рис. 7.

Шаг 2, такт 2: (4,5) - нет; (2,7) - да (по условию 1); (3,9) - да (по условию 1); (6,8) - да (по условию 1). Модифицированная матрица R после шага 2,2 представлена на рис. 8.

Шаг 3, такт 1: (1,4) - нет; (5,7) - да (по условию 1); (2,9) - да (по условию 1); (3,8) - да ( по условию 1). Модифицированная матрица R представлена на рис. 9.

Шаг 3, такт 2: (4,7) - нет; (5,9) - да (по условию 1), (2,8) - нет; (3,8) - нет. Модифицированная матрица R представлена на рис. 10.

После выполнения трёх шагов в модифицированной матрице сформировано три -области: P1(1,4), P2(5,3), P3(8,2). Поскольку в исходном графе G содержится 8 вершин, то максимальное паросочетание может включать четыре ребра. -области P1(1,4) соответствуют четыре вершины графа Gd , которым в исходном графе G соответствует паросочетание из четырех ребер - (1,4,7,9).



Рис. 5. Матрица R после 1,1 шага Рис. 6. Матрица R после 1,2 шага





Рис. 7. Матрица R после 2,1 шага Рис. 8. Матрица R после 2,2 шага





Рис. 9. Матрица R после 3,1 шага Рис. 10. Матрица R после 3,2 шага


Сформированные области P1(1,4), P2(5,3), P3(8,2) покрывают все столбцы и строки матрицы R. Следовательно, граф Gd можно раскрасить в 3 цвета: 1 цвет - вершины 1,4,7,9; 2 цвет - вершины 5,2,8; 3 цвет – вершины 3,6.

Для преодоления локального барьера, используются подходы, основанные на сочетании различных видов эволюции.

В первом подходе используются идеи метода моделирования отжига. Если в процессе анализа обнаруживается, что условия 1,2,3 не выполняются, то перестановка осуществляется с вероятностью P=exp(-∆F/kT), где T - температура, Fразница между суммами значений элементов анализируемых строк.

Во втором подходе используется одна из структур генетического поиска [Лебедев, 2000]. Популяция представляет собой множество матриц смежности (закодированных в виде хромосом). Декодирование, т.е. получение решения, осуществляется с помощью вышеописанной адаптивной процедуры.

Временная сложность адаптивной процедуры на одном шаге – О(n). Сравнение с известными алгоритмами показало, что при меньшем времени работы новый алгоритм дает более качественные решения.


Список литературы

[Андерсон, 2003] Андерсон Д. Дискретная математика и комбинаторика. М.: Вильямс, 2003.

[Курейчик и др., 2003] Курейчик В.В., Курейчик В.М. Генетический алгоритм определения паросочетаний графа. Труды 10-ой международной конференции “Knowledge-dialogue-solution”, 2003.

[Курейчик, 1990] Курейчик В.М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР. М.: Радио и связь, 1990.

[Кормен и др., 2000] Кормен К., Лейзерсон Ч., Ривест Р. Алгоритмы построение и анализ. М.: МЦМНО, 2000.

[Лебедев, 1999] Лебедев Б.К. Адаптация в САПР. Таганрог: Изд-во ТРТУ, 1999.

[Лебедев, 2000] Лебедев Б.К. Методы поисковой адаптации в задачах автоматизированного проектирования СБИС. Таганрог: Изд-во ТРТУ, 2000.

[Лебедев и др., 2005] Лебедев Б.К., Лебедев О.Б. Эволюционный алгоритм нахождения максимального паросочетания. 3-й Международный НТС “Интегрированные модели и мягкие вычисления в искусственном интеллекте”, 2005.

[Макконнел, 2004] Дж. Макконнел. Основы современных алгоритмов. М.: Техносфера, 2004.

[Свами и др., 1984] Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984.



*Работа выполнена при финансовой поддержке программ развития научного потенциала высшей школы РНП.2.1.2.2238 и РНП.2.1.2.3193

1Таганрогский государственный радиотехнический университет, lbk@tsure.ru