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

Программная система 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₁=n₂=30, n₃=40; 3) используя гибридный алгоритм найти решение задачи, из расчета что комплект вычислений алгоритма должен быть равен 500. Гибридный алгоритм должен иметь следующий набор параметров: случайное формирование начальной популяции; панмексия генотипов; случайная рулетка среди трех типов классических кроссоверов (одноточечный, двухточечный, равномерный); компонентная коррекция; мутации и генетические всплески отсутствуют; элитарный отбор с вытеснением генотипов; численность популяции и число брачных пар – 10; полная прижизненная адаптация.

1. Для решения поставленной задач при помощи редактора графа Graph Builder v4.04 создаем (опция Edit\Create 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.