Методические указания по проведению лабораторных работ «Задачи декомпозиции графов» по курсу (стр. 2 из 3)

На практике чаще приходится с несколько иной задачей, связанной с правильной вершинной раскраской – задачей выделения максимального k-хроматического подграфа. Данная задача формулируется следующим образом.

Пусть задан неориентированный взвешенный граф G(X,V,d) порядка n, где X={x₁,…,x_n} – множество вершин; VÍX´X – множество ребер; d:X®R⁺ – отображение, определяющее вес каждой вершины, где R⁺ – множество действительных неотрицательных чисел. Требуется для заданного числа цветов k выделить в исходном графе G(X,V,d) k-хроматический подграф с максимальным весом:

(4)

где W – множество всевозможных k-раскрашиваемых подграфов исходного графа G(X,V,d).

В качестве варьируемых параметров здесь выступают: во-первых, распределение множества вершин исходного графа на k+1 подмножества (k-одноветных класса раскрашиваемого подграфа и одно не раскрашиваемое); во-вторых, размерности цветовых классов. Таким образом можно трактовать поставленную задачу как однокритериальную с двумя степенями свободы.

Еще ряд задач из рассматриваемого класса, выбранные в качестве тестовых графовых проблем, заключаются в равномерном разбиении множества вершин графа. Под равномерностью здесь понимается приблизительно равное соотношение весов (суммарный вес вершин из одного класса) одноцветных классов. Задачи такого рода уже имеют три типа варьируемых параметров. Во-первых, распределение множества вершин исходного графа на k одноцветных классов. Во-вторых, размерности цветовых классов. В качестве третьего варьируемого параметра выступает k – число цветов.

Потребуем, чтобы исходный граф G(X,V,d) был полностью правильно раскрашен. Данное условие определяет область поиска D – множество всевозможных правильных раскрасок исходного графа. Так, если в качестве критерия оптимальности использовать минимизацию числа используемых цветов в правильных раскрасках, то получим классическую задачу раскраски графа.

Обозначим через X₁,…,X_k – множества одноцветных классов k-хроматического графа; s_i – суммарный вес вершин множества X_i (т.е. суммарный вес независимых вершин):

;

(5)

– средний вес одноцветных классов:

.

(6)

Потребуем, чтобы суммарный вес вершин для всех одноцветных классов отличался от среднего как можно меньше. То есть необходимо осуществить правильную раскраску вершин графа G(X,V,d) таким образом, чтобы минимизировать целевую функцию:

.

(7)

Тогда оптимальным решением будет правильная раскраска (X₁^*,…,X_k^*)ÎD графа G(X,V,d) такая, что

.

(8)

Также для выравнивания весов одноцветных классов можно максимизировать вес минимального из получившихся одноцветных классов:

.

(9)

В этом случае оптимальной будет правильная раскраска (X₁^*,…,X_k^*)ÎD графа G(X,V,d) такая, что

.

(10)

4. Постановка бикритериальной задачи разбиения

Пусть задан неориентированный взвешенный граф G(X,V,w,d) порядка n, где X={x₁,…,x_n} – множество вершин; VÍX´X – множество ребер; w:V®R⁺ – отображение, определяющее вес каждого ребра; d:X ®R⁺ – отображение, определяющее вес каждой вершины, где R⁺ – множество действительных неотрицательных чисел.

Требуется определить разбиение множества вершин X графа G(X,V,w,d) на k подмножеств (X₁,X₂,…,X_k) таким образом, чтобы для кусков графа G₁(X₁,V₁,w₁,d₁), G₂(X₂,V₂,w₂,d₂), …, G_k(X_k,V_k,w_k,d_k) выполнялись требования (1).

В качестве первого критерия оптимальности F₁, определяющего эффективность k-разбиения (X₁,…,X_k), будем рассматривать суммарный вес всех ребер, целиком попавших в один из подграфов разбиения:

(11)

Суммарный вес вершин, принадлежащих одному подграфу, будем называть весом подграфа. Вес некоторого подграфа X_i будем обозначать через W(X_i). Для уравнивания весов получаемых подграфов будем использовать следующий критерий оптимальности F₂:

(12)

Таким образом имеем бикритериальную задачу:

(13)

Система требований (1), предъявленных к разбиению (X₁,…,X_k), определяет область поиска D задачи k-разбиения графа. В этом случае решением экстремальной задачи (13) является Парето-область из компромиссных решений. Данная задача относится к задачам переборного типа и общее число допустимых решений |D| также можно вычислить из выражения (3).

5. Подход к решению задач декомпозиции графа

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

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

Общая схема гибридного алгоритма при прямом представлении

Рисунок 1

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

6. Программный комплекс по разработке графов и решению задач декомпозиции графов

Для решения задач декомпозиции графов создан диалоговый комплекс, включающий в себя как средства проектирования графов (Graph Builder v4.04), так и программную систему (Evolution v3.01) принятия оптимальных и компромиссных решений, позволяющую решать заявленный класс графовых проблем.