2020-01-15
298
Для решения задач декомпозиции графов создан диалоговый комплекс, включающий в себя как средства проектирования графов (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 приведет к последовательному выполнению всего списка операций. Отлаженные программы-макросы можно сохранять в виде специальных файлов.
Пример
Требуется: 1) создать случайный регулярный не взвешенный граф с локальной степенью для всех вершин равной 3 на 100 вершинах; 2) на данном графе поставить задачу k -разбиения графа со следующими параметрами: k=3, n 1= n 2=30, n 3=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.
