<<
>>

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

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

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

На каждом шаге анализируются пары (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 = ∖∖rjjIl размером n* п. В строках выделяют две части: 1 — (j = 1 ÷ i — 1); 2 — (j = i + 2 ÷ п).Суть анализа заключается в определении истинностного значения трех нижеприведенных условий.

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

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

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

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

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

Матрица смежности графа Gdпредставлена на рис. 12.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 представлена на рис. 12.5.

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

Шаг 2, такт 1: (1,4) — «нет»; (2,5) — «да» (по условию 1);

(3.7) — «да» (по условию 1); (6,9) — «да» (по условию 1). Модифицированная матрица Rпосле шага 2,1 представлена на рис. 12.7.

Шаг 2, такт 2: (4,5) — «нет»; (2,7) — «да» (по условию 1);

(3.9) — «да» (по условию 1); (6,8) — «да» (по условию 1). Модифицированная матрица R после шага 2,2 представлена на рис. 12.8.

Шаг 3, такт 1: (1,4) — «нет»; (5,7) — «да» (по условию 1);

(2.9) — «да» (по условию 1); (3,8) — «да» (по условию 1). Модифицированная матрица R представлена на рис. 12.9.

Шаг 3, такт 2: (4,7) — «нет»; (5,9) — «да» (по условию 1),

(2.8) — «нет»; (3,8) — «нет». Модифицированная матрица R представлена на рис. 12.10.

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

Сформированные области 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(-AF/FT), где T — температура, AF — разница между суммами значений элементов анализируемых строк [12.10].

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

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

<< | >>
Источник: Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с.. 2006

Еще по теме Эволюционные механизмы формирования ^-областей:

  1. Механизмы образования OA в кристаллах.
  2. 3.1. Формирование стратегии развития системы персональных финансов
  3. §1.4 Психологические особенности формирования профессионально-личностной компетентности менеджера коммерческой организации
  4. Алгоритм формирования тремерной рабочей сцены при использовании нескольких оптико-электронных датчиков
  5. Метод формирования тремерной рабочей сцены при использовании нескольких оптико-электронных датчиков
  6. Коэффициент формы области с выпуклым контуром
  7. 2. Органы исполнительной власти в области безопасности
  8. 2.14.2 Построение аналитических зависимостей для ограниченных подмножеств областей
  9. 1. Правовое регулирование в области безопасности. Основные понятия
  10. 1. Содержание управления в области внутренних дел
  11. ХАЛЫН АННА ЮРЬЕВНА. ФОРМИРОВАНИЕ СИСТЕМЫ СТРАТЕГИЧЕСКОГО УЧЕТА НА ИННОВАЦИОННЫХ ПРЕДПРИЯТИЯХ. ДИССЕРТАЦИЯ на соискание ученой степени кандидата экономических наук. Ростов-на-Дону - 2014, 2014
  12. Тема 20. Управление в области внутренних дел