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

Формирование З-областей в матрице 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).

матрица r после 1,1 шага рис. 6. матрица r после 1,2 шага

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

матрица r после 2,1 шага рис. 8. матрица r после 2,2 шага

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

матрица r после 3,1 шага рис. 10. матрица r после 3,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). Сравнение с известными алгоритмами показало, что при меньшем времени работы новый алгоритм дает более качественные решения.

Похожие статьи




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

Предыдущая | Следующая