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

Нижегородский государственный университет им. Н.И. Лобачевского

Факультет вычислительной математики и кибернетики
Кафедра информатики и автоматизации
научных исследований
Методические указания по проведению лабораторных работ

«Задачи декомпозиции графов»

по курсу «
Эволюционно-генетические

алгоритмы решения оптимизационных задач»

специальность «
Прикладная информатика»

Н.Новгород, 2001

УДК. 681.3.015

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

/Нижегородский государственный университет, 2001, 13 c.

Методические указания содержат основные понятия из области подходов к решению экстремальных задач переборного типа на графовых структурах. Дается содержательное описание объекта исследования, строится общая математическая модель, ставятся оптимизационные задачи на графах, предлагаются алгоритмы решения поставленных оптимизационных задач. Приводится описание диалогового программного комплекса “Задачи декомпозиции графов”.

Считаю, что данное методическое пособие необходимо опубликовать по желанию авторов либо в электронном варианте, либо через типографию.

Методическое пособие подготовлено профессором Д.И. Батищевым и аспирантом Н.В. Старостиным.

Рецензент профессор, д.т.н. Гергель В.П.

Содержание

1. Содержательная постановка задачи. 4

2. Задача разбиения графа на фиксированное число подграфов заданных порядков. 5

3. Задачи оптимальной правильной раскраски графов. 6

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

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

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

7. Пример. 12

8. Задания по лабораторной работе. 13

Литература. 13

1. Содержательная постановка задачи

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

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

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

При разработке топологии многослойных схем возникает задача распределения “конфликтующих” соединений по отдельным слоям (задача расслоения цепей). Расслоение до трассировки основано на анализе схемы соединений для выявления тех соединений или их групп, которые не могут быть расположены на одной плоскости из-за неизбежности “сложных” ситуаций трассировки. В частности, усложняется форма соединений, увеличивается их длина, растет время поиска трасс при реализации алгоритма трассировки на ЭВМ.

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

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

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

Задачи декомпозиции имеют следующий набор основных критериев:

1. Число внешних соединений между подграфами

2. Число подграфов

3. Число типов подграфов

Первый критерий определяется функционалом внешних связей. Смысл второго критерия очевиден: он просто равен числу подграфов разбие­ния. Третий критерий зависит от характера оптимизационной задачи. Чтобы описать этот кри­те­рий, нужно задать понятие подграфа или, точнее, понятие однотипности графов. При определении однотипности графов исходят из того, что каждой вершине графа присваивается один тип из конечного набора. Математически это означает, что ис­ход­ный граф хроматический, то есть его вершины раскрашены, при этом цвет вер­шины соответствует типу.

Постановки задач могут варьироваться в зависимости от свойств графа, ко­то­­рые задаются моделируемым объектом.

2. Задача разбиения графа на фиксированное число подграфов заданных порядков

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

Требуется определить разбиение множества вершин X
графа G
(X
,V
,w
) на k
– подмножеств (X
1
,…,Xk
) таким образом, чтобы для кусков графа G
1
(X
1
,V
1
,w
1
),…, Gk
(Xk
,Vk
,wk
) выполнялись следующие требования:

Xi ÇXj =Æ, для " i ¹j , где i ,j =; ; |X 1 |=n 1 ,…, |Xk |=nk , n 1 +…+n k =n ,

(1)

Сечением
разбиения C
(X
1
,…,Xk
) будем называть совокупность ребер, соединяю­щих вершины, которые принадлежат разным подграфам.

В качестве критерия оптимальности
Q, определяющего эффективность би-разбиения (X
1
,…,Xk
) будем рассматривать вес сечения
- сумма весов всех ребер сече­ния:

(2)

В этом случае оптимальным
k-раз­биением
является решение (X
1
*
,…,Xk
*
) экстре­маль­ной задачи (2), то есть разбиение (X
1
*
,…,Xk
*
) с минимальным весом сечения C
(X
1
*
,…,Xk
*
).

Частным случаем задачи k
-разбиения является задача (1) биразбиения графа
– когда граф разбивается на два подграфа (k
=2). В этом случае решение задачи биразбиения графа (X
1
,X
2
) будем называть биразбиением
.

Система требований (2), предъявленных к разбие­нию (X
1
,…,Xk
), опре­деля­ет область поиска D
задачи разбиения графа. Данная задача относится к задачам переборного типа и общее число допус­ти­мых решений |D
| можно вычислить из выражения:

(3)

где t
– общее число подграфов, имеющих одинаковые размерности.

3. Задачи оптимальной правильной раскраски графов

Пусть задан неориентированный граф без петель G
(X
,V
) порядка n
, X
={x
1
,… …,xn
} – множество вершин; V
ÍX
´X
– множество ребер.

Под раскраской вершин
графа понимается процедура приписывания цветов (меток) вершинам графа G
(X
,V
). Правильной раскраской
графа в k
цветов (k
-раскраской графа) считается такая раскраска вершин графа G
(X
,V
), при которой никакие две смежные вершины x
i
, xj
ÎX
, x
i
¹xj
не получают одинакового цвета.

Наименьшее число k
, такое, что граф G
(X
,V
) является k
-раскрашиваемым, называется хроматическим числом
графа G
(X
,V
).

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

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

Пусть задан неориентированный взвешенный граф G
(X
,V
,d
) порядка n
, где X
={x
1
,…,xn
} – множество вершин; 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
1
,…,Xk
– множества одноцветных классов k
-хрома­тического гра­фа; si
– суммарный вес вершин множества X
i
(т.е. суммарный вес независимых вершин):

;

(5)

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

.

(6)

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

.

(7)

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

.

(8)

Также для выравнивания весов одноцветных классов можно максимиз

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

.

(9)

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

.

(10)

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

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

Требуется определить разбиение множества вершин X
графа G
(X
,V
,w,
d
) на k
подмножеств (X
1
,X
2
,…,Xk
) таким образом, чтобы для кусков графа G
1
(X
1
,V
1
,w
1
,d
1
), G
2
(X
2
,V
2
,w
2
,d
2
), …, Gk
(Xk
,Vk
,wk
,dk
) выполнялись требования (1).

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

(11)

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

(12)

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

(13)

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

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

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

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

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

Рисунок 1

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

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

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

Программная система Graph
Builder
позволяет создавать, редактировать и сохранять в виде файлов графовые структуры. На рисунке 2 изображен общий вид главной панели редактора.

Рисунок 2

Главное меню включает в себя следующие пункты: File
– открытие, создание и сохранение файлов графовых структур; Edit
– опции по установке режимов редактирования и автоматического создания случайных графов; Options
– опции по настройке программы и вызов краткой статистической информации об особенностях редактируемой структуре графа; View
– включение (отключение) панели режимов; Actions
– операции автоматического расположения на плоскости элементов редактируемых графовых структур; Window
– опции по управлению несколькими окнами редактирования; Help
– справочная система.

Другая программная система Evolution
ориентирована на работу с готовыми графовыми структурами, на которых можно ставить и исследовать различные задачи разбиения и раскраски графов (в том числе бикритериальные задачи разбиения). На рисунке 3 представлен общий вид главной панели Evolution
v3.01
.

Рисунок 3

Цифрами обозначены: 1– кнопки управления режимами визуализации структуры графа; 2 – панель визуализации структуры графа; 3 – сплиттер для изменения пропорций панелей визуализации; 4 – панель статистических диаграмм и таблиц; 5 – переключатели между различными типами статистических данных; 6 – информационная панель; 7 – основные кнопки управления программой (запуск/останов алгоритма, инициализация начальной популяции, загрузка файла структуры графа, автоматический подбор параметров алгоритма, отображение дополнительных средств визуализации, выход из программы, вызов справочной информации); 8 – панель переключения задач (задачи k
-разбиения, комплект задач оптимальной раскраски, бикритериальные задачи разбиения); 9 – панель основных параметров алгоритма; 10 – курсор установки параметров; 11 – кнопки переключения панелей (панель описания и задания параметров задачи, панель основных параметров алгоритма, панель по управлению программой в командном режиме, панель создания, загрузки, сохранения и редактирования макросов); 12 – панель по управлению параметрами останова алгоритма (остановка по числу итераций, по числу различных генотипов в текущей популяции, по проделанному комплекту вычислений, по значению критерия наилучшего найденного решения, по среднему значению критерия по популяции, по времени работы алгоритма); 13 – индикатор прогресса работы алгоритма.

Имеется возможность управления системой при помощи функциональных клавиш: “F1” – вызов контекстной помощи; “F2” – инициализация начальной популяции; “F3” – загрузка новой графовой структуры; “F9” – запуск алгоритма; “F10” – выход из программы; “Esc” – прерывание работы алгоритма; “Tab” –переход от одной панели к другой.

В программе предусмотрена возможность получения справки о любом элементе (достаточно щелкнуть правой клавишей мышки по соответствующему элементу) и любой управляющей команде (общий список включает 115 команд для вер­сии 3.010415).

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

Результаты решения задачи могут быть отражены в следующем виде:

· визуализация решений задачи декомпозиции посредством раскраски графовой струк­туры (подграфы разбиения окрашиваются в разные цвета);

· решения задачи в текстовом виде (команда result
);

· имеется возможность просмотреть все решения текущей популяции;

· предусмотрен режим графической визуализации текущих решений относительно друг друга как в пространстве поиска, так и в пространстве критериев (для построения области компромиссных решений);

· разнообразная статистическая информация в виде диаграмм и сводных таблиц.

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

7. Пример

Требуется: 1) создать случайный регулярный не взвешенный граф с локальной степенью для всех вершин равной 3 на 100 вершинах; 2) на данном графе поставить задачу k
-разбиения графа со следующими параметрами: k=3, n
1
=n
2
=30, n
3
=40; 3) используя гибридный алгоритм найти решение задачи, из расчета что комплект вычислений алгоритма должен быть равен 500. Гибридный алгоритм должен иметь следующий набор параметров: случайное формирование начальной популяции; панмексия генотипов; случайная рулетка среди трех типов классических кроссоверов (одноточечный, двухточечный, равномерный); компонентная коррекция; мутации и генетические всплески отсутствуют; элитарный отбор с вытеснением генотипов; численность популяции и число брачных пар – 10; полная прижизненная адаптация.

1. Для решения поставленной задач при помощи редактора графа Graph
Builder
v4.04
создаем (опция EditCreate subgraph) требуемый граф на 100 вершинах (см. рис. 4). Сохраняем структуру графа в виде файла.

2. Запускаем программу Evolution
v3.01
и загружаем ранее сохраненный файл со структурой графа. При помощи панели переключения задач (см. рис. 3) устанавливаем тип задачи: задача k
-разбиения (GPP_
MinC
). В панели описания и задания параметров задачи устанавливаем параметры разбиения: 30, 30, 40. При помощи панели основных параметров алгоритма устанавливаем требуемый набор параметров. При помощи панели управления параметрами останова алгоритма задаем требуемые условия останова (calculations
- 500).

Рисунок 4	Рисунок 5

Гибридный алгоритм нашел разбиение графа с весом сечения, равным 6 (см. рис. 5). Алгоритм выполнил требуемый комплект вычислений за 24 итерации, что составило 26 секунд машинного времени.

Вычисления проводились на компьютере со следующей конфигурацией: Intel Pentium 100/24mb/Windows 98.

8.
Задания по лабораторной работе

Задание 1
. Создать взвешенный граф заданного порядка и с заданными структурными особенностями.

Задание 2
. На графе поставить задачу одну из задач декомпозиции графа.

Задание 3
. Настроить параметры гибридного алгоритма.

Задание 4
. Найти решение поставленной задачи.

Литература

1. Батищев Д.И., Коган Д.И.. Вычислительная сложность экстремальных задач переборного типа. Н.Новгород, ННГУ, 1994.

2. Батищев Д.И. Генетические алгоритмы решения экстремальных задач / Под ред. Львовича Я.Е.: Учеб. пособие, Воронеж, 1995.

3. Батищев Д.И., Старостин Н.В. Применение генетических алгоритмов к решению зада­чи дихотомического разбиения графа. Воронеж. Межвузовский сборник науч. тру­дов «Оптимизация и моделирование в автоматизированных системах», 1998 г., с.3 – 10.

4. Батищев Д.И., Старостин Н.В. Способы повышения эффективности генетического поиска оптимального k
-разбиения графа. Воронеж. Межвузовский сборник н. трудов “Прикладные задачи моделирования и оптимизации”, 2000 г., Часть 2, стр. 4-17.

5. Батищев Д.И., Старостин Н.В, Дроздова Е.П. Экстремальные задачи правильной раскраски графа. Воронеж. Межвузовский сборник научных трудов “Прикладные задачи моделирования и оптимизации”, 2000 г., Часть 2, стр. 49-60.

6. Батищев Д.И., Старостин Н.В. k
-разбиение графов. Вестник ННГУ “Математическое моделирование и оптимальное управление”, Н.Новгород, 2000 г., стр. 27-35.