7.2.  Разбиение графа на части по критерию числа внешних ребер

Приведем интерфейс программы разбиения. При запуске программы на экране появляется главное окно программного комплекса. Его внешний вид представлен на рис. 7.8.

Это окно делится на две части. В правом верхнем углу расположены поля для ввода подграфов разбиения. Сумма введенных значений должна соответствовать общему количеству вершин графа. Ниже расположена область окна, в которой показан график изменения ЦФ от количества итераций алгоритма. Под ней расположены окна вывода значений ЦФ для разных типов алгоритмов (последовательный, итерационный, ПГА, ГА с подсистемой самоорганизации), а также окно для ввода числа итераций алгоритма. Под ГА с подсистемой самоорганизации понимают алгоритмы, использующие модели совместных эволюций, принцип синергетики, блоки адаптации, экспертные системы и т. п. (например, рис. 6.1, 6.13, 6.17).

В верхней части главного окна расположено меню, состоящее из следующих пунктов: «файл»; «алгоритмы»; «параметры»; «операции»; «справка».

Пункт главного меню «файл» содержит стандартный набор команд для работы с введенными данными (создание нового, сохранение, открытие и

т. д.). Пункт меню «алгоритмы» позволяет выбрать алгоритм, используемый при разбиении графа. Он содержит четыре блока для разных типов алгоритмов. Пункт меню «параметры» состоит из двух подпунктов: вероятности операторов и подсистема самоорганизации (рис. 7.9).

Подпункт «вероятности генетических операторов» (рис. 7.10) позволяет задавать шкалы (вероятности) операторов в процентах. Подпункт «подсистема самоорганизации» (рис. 7.11) позволяет подключать блок самоорганизации для выполнения различных операторов на основе методов дихотомии, золотого сечения, Фибоначчи и др., а также строить порядок из хаоса при повторном запуске.

Меню «операции» содержит команды для построения графов: добавить/удалить вершину; добавить/удалить ребро; переместить вершину. В нижней части окна комплекса расположена панель инструментов. Она содержит: индикатор состояния выполнения алгоритма; кнопку запуска алгоритма разбиения; кнопку вывода графиков. После выполнения алгоритма вершины графа окрашиваются в цвет, соответствующий подграфу, которому они принадлежат. На рис. 7.12 показано лучшее разбиение графа, полученное на основе описанного алгоритма (ЦФ = 39 за 900 итераций). На рис. 7.13 приведено окно с графиками ПГА и ГА с подсистемой самоорганизации.

Проанализируем влияние размера популяции на получаемые результаты. При этом будем варьировать вероятность всех операторов, а также менять количество итераций ГА. Построим следующую таблицу (табл. 7.1),

 

 

в которой приведем результаты проведенных экспериментов. В таблице приведены различные данные разбиения графа, содержащего п = 450 вершин и ш = 1000 ребер, на три части по 150 вершин в каждой с минимизацией количества внешних ребер. В первом столбце таблицы указываются номера проведенных экспериментов, во втором — количество вершин. Отметим, что в таблице приведены данные по исследованию разбиения одного нестандартного трудного теста. Здесь изменялись размер популяции, количество итераций ГА, шкалы ОК, ОМ, оператора инверсии и процедура селекции. В третьем столбце указан размер популяции, в четвертом — количество итераций, в пятом, шестом и седьмом — вероятности применения операторов кроссинговера, мутации и инверсии. В восьмом столбце записан тип проведенной селекции (С — случайная, Э — элитная). В девятом столбце приведены данные для ПГА (время, затраченное на получение лучшего решения и значение ЦФ, т. е. количества внешних ребер для заданного разбиения), а в десятом указаны аналогичные данные для приведенного алгоритма. Для исследования стандартного графа были реализованы такие классические методы разбиения, как последовательные, итерационные, поиска в глубину. При этом значение ЦФ в первом случае составило 530 условных единиц, во втором — 500, а в третьем 510.

По результатам экспериментов, сведенных в таблице, построим график зависимости времени {t) получения лучшего решения от количества итераций Ng (рис. 7.14). Из графика следует, что для ПГА время решения практически линейно зависит от числа генераций ГА. Размер популяции, как видно из таблицы, влияет на время решения и на получение оптимальных результатов.

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

На рис. 7.15 приведены графики зависимости времени решения от значения ЦФ для итерационного (ПП), последовательного (КН) алгоритмов, ПГА и ГА с подсистемой самоорганизации.

Из графика и таблицы следует, что описанные ГА дают лучшие решения по качеству при одинаковом или незначительном увеличении времени

работы. До попадания в локальный оптимум управление параметрами генетического поиска позволяет получать лучшие решения. На рис. 7.16 приведен график зависимости времени получения лучшего решения от размера популяции для ПГА.

В таблице 7.2 приведены результаты экспериментов с тем же алгоритмом разбиения, но проанализировано разбиение не одного графа, а набора тестовых задач.

Исследовано поведение алгоритма разбиения при использовании различных модифицированных операторов. В шестом, седьмом и восьмом столбцах таблицы указаны величины шкал модифицированных операторов кроссинговера, мутации и сегрегации (Р(МОК), Р(МОМ), Р(МОС)). Значение условной ЦФ (см. 11 столбец таблицы) определяется отношением количества внешних ребер к количеству внутренних ребер при разбиении. Необходимо стремиться к такому разбиению, чтобы ЦФ ^ 0. Селекция выбрана элитная. Размер популяции зафиксирован постоянный. Но в процессе решения после каждой генерации размер популяции менялся в основном в сторону уменьшения, оставляя лучшие с точки зрения ЦФ хромосомы. На рис. 7.17 показан график зависимости времени получения лучшего решения от числа вершин исследуемого графа.

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

Из приведенных статистических данных следует, что в общем случае время решения линейно зависит от количества генераций и временная сложность описанных алгоритмов подтверждает теоретические предпосылки и приближенно равна 0{п logn)^O(n^). Следует заметить, что с увеличением числа итераций в ГА время получения результата разбиения повышается, но это повышение незначительное и компенсируется получением множества локально-оптимальных решений. Анализ графиков и приведенных таблиц позволяет отметить, что описанные ГА требуют больших затрат времени, чем ПГА. Они позволяют получать набор локально-оптимальных решений, решать в общем случае проблему предварительной сходимости. Для каждого конкретного теста (как следует из таблиц) условная ЦФ, в описанных алгоритмах, принимает лучшие значения, причем эти алгоритмы имеют большее быстродействие, чем метод ветвей и границ, метод моделирования отжига и другие аналогичные методы.