Многоуровневая декомпозиция гиперграфовых структур

Рис. 34. Маршрут движения по области поиска закодирован в генотипе.

Для того чтобы закодировать маршрут в генотипе необходимо выбрать  символьную модель (кодировку), способы  оценки кодировки и декодирования  кодировки в решение задачи. Символьная модель представляет собой k-ичную строку длины m A=(a₁,...,a_m), где k – количество компонент разбиения, m=|E| - количество ребер гиперграфа. Ген a_iговорит о том, что все вершины, входящие в состав ребра e_i будут перемещены в a_i-ую компоненту разбиения.

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

Алгоритм декодирования  для такой кодировки может  выглядеть следующим образом:

1. i:=1.
2. Если возможно перенести все вершины ребра e_i в a_i-ую компоненту разбиения, не нарушая ограничений задачи, то осуществляем перенос.
3. i:=i+1.
4. Если i<=m, то переход на шаг 2.

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

1. i:=1.
2. Если возможно перенести все вершины ребра e_i в a_i-ую компоненту разбиения, не нарушая ограничений задачи, то осуществляем перенос.
3. i:=i+1
4. Если i<=m, то переход на шаг 2.
5. К полученному решению применяем жадный алгоритм переноса ребер.

Таким образом, декодер представляет собой управляемый улучшающий алгоритм, начальную часть пути в ОП прокладывает в соответствии с кодировкой, а оставшуюся часть – руководствуясь жадным принципом переноса ребер. На рисунке 35 изображена область поиска задачи и маршрут, проложенный описанным декодером. Часть маршрута, соответствующая управляемой работе декодера, т.е. работе шагов 1-4 алгоритма, показана сплошной линией, а часть маршрута, соответствующая работе жадного алгоритма – сплошной.

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

Рис. 35. Маршрут в области поиска, прокладываемый декодером.

Описанный выше способ кодирования  делает возможным применение классических операторов ГА для работы с k-ичными строками [DB1], что позволяет сделать структуру ГА простой и прозрачной. Еще одно преимущество этих операторов – скорость работы; она достаточно высока, поскольку над генотипом не производится никаких сложных вычислений. Единственная ресурсоемкая операция в составе предложенного ГА – оценка решения, кодируемого генотипом, поскольку для ее вычисления требуется процедура декодирования. Вычислительной сложностью, возрастающей с ростом размерности задачи, и обуславливается нецелесообразность применения ГА на последних шагах многоуровневого алгоритма, когда число ребер гиперграфа велико. Отказ от метода улучшения, основанного на ГА, в пользу жадных схем на последних стадиях работы многоуровневого алгоритма не несет в себе большой опасности, поскольку критически важными для качества получаемого в ходе работы многоуровневого алгоритма решения являются начальные стадии фазы восстановления решения, когда обработке подвергаются наиболее загрубленные графы. Действительно, улучшающий алгоритм, оперируя отдельными вершинами в терминах загрубленного графа, управляет целыми их группами в терминах исходного. Т.е. перенос вершин загрубленного графа, фактически означает перенос групп вершин, что потенциально дает существенное уменьшение веса сечения. В общем случае, по мере перехода от более загрубленного графа к менее загрубленному, способность улучшающего алгоритма значительно уменьшать вес сечения за один шаг падает. Оптимизация решения на последних стадиях фазы восстановления носит характер локального улучшения, в то время как наиболее сильная редукция веса сечения наблюдается в начале фазы. Поэтому нецелесообразно применять относительно ресурсоемкий ГА на последних этапах фазы восстановления решения.

 
12. Вычислительный эксперимент

Было решено провести тестирование описанного многоуровневого алгоритма  декомпозиции на ряде тестовых задач, при этом была выбрана следующая  конфигурация алгоритма:

1. Схема загрубления – реберное загрубление (edge coarsening, EC) [GKVK3,GKVK5]
2. Алгоритм поиска начального разбиения – случайное разбиение с последующим улучшением с помощью описанного ГА.
3. Улучшающий алгоритм, использованный в ходе фазы восстановления решения – жадный алгоритм перемещения ребер для первой серии экспериментов и ГА, если количество вершин гиперграфа менее 500, жадный алгоритм перемещения ребер, если количество вершин более 500, для второй серии.

Вычислительный эксперимент  ставился на задачах двух типов:

1. k-декомпозиция специально сконструированных тестовых гиперграфов, назовем их кластерными гиперграфами, содержащих k достаточно сильносвязанных компонент (кластеров) со слабыми связями между кластерами. Так каждый тестовый граф размера n содержал k подграфов,   вершин и ребер в каждом, каждое ребро содержало от 2 до 6 вершин и имело вес от 20 до 50, и k ребер веса 1, соединяющих подграфы в кольцо, т.е. первый со вторым, второй с третьим,…, k-ый с первым. Таким образом, задача k-декомпозиции гарантированно имела решение с весом сечения k. Параметры L_i и U_i задачи (1)-(3) были соответственно 0 и  , где   – суммарный вершинный вес гиперграфа.
2. 2-декомпозиция сеток различных размеров. Для таких задач тоже известны гарантированные минимумы. Так для сетки  , где  , гарантированный минимум –  . Параметры L_i и U_i задачи (1)-(3) были соответственно 0 и  , где   – суммарный вершинный вес гиперграфа.

На рисунке 35 представлен  пример кластерного гиперграфа, содержащего 100 вершин и 10 кластеров.

Рис. 35. Кенигово представление кластерного гиперграфа (слева) и графа-сетки (справа). Большие точки соответствуют вершинам, малые – гиперребрам. 

 

Таблицы 1 и 2 содержат результаты вычислительных экспериментов. Все  эксперименты проводились на компьютере P4-2400 / 1GB DDR333 / ОС Windows XP. Результаты для каждой тестовой задачи получены как среднее значение 10 запусков.

Таблица 4.1.

Размер гиперграфа (n)

Количество компонент  разбиения   (k)

Вес полученного сечения Время работы  (чч:мм:cc, 0) без ГА с ГА без ГА с ГА

100	2	2	2	00:00:00,1	00:00:13,6
100	5	16,3	5	00:00:00,1	00:00:22,9
100	10	93,4	10	00:00:00,1	00:00:22,7
1000	2	2	2	00:00:01,6	00:10:44,6
1000	5	5	5	00:00:01,3	00:19:04,5
1000	10	10	10	00:00:01,3	00:34:54,9
10000	2	2	2	00:01:27,7	00:03:48,8
10000	5	5	5	00:00:43,7	00:04:41,0
10000	10	10	9,9	00:00:43,5	00:04:13,2
100000	2	2	2	02:07:16,1	01:38:14,9
100000	5	5	5	01:49:00,8	01:20:03,0
100000	10	10	9.8	01:23:34,4	01:11:14,7

Результаты вычислительного  эксперимента над кластерными графами  

 

 

 

Таблица 4.2.

Размер сетки  ( )

Вес полученного сечения Время работы (чч:мм:cc,0) без ГА с ГА без ГА с ГА

5x10	7,4	5	00:00:00,01	00:00:13,8
10x20	20,4	10,7	00:00:00,2	00:04:42,9
20x50	53,1	25,2	00:00:01,4	00:46:25,9
50x100	116	74,6	00:00:13,2	00:53:55,2
100x200	263,4	174	00:02:08,1	00:09:16,7
200x500	888,9	450,5556	00:40:11,6	00:36:34,7

Результаты вычислительного  эксперимента над графами-сетками

Не следует рассматривать  полученные времена работы алгоритма  как характеристику самого алгоритма, поскольку существенное влияние  оказывают методы реализации этого  алгоритма. Так, например, реализация алгоритма  с использованием C++ с последующей компиляцией в native-код могла бы увеличить скорость алгоритма в разы, хотя, безусловно, сказалась бы и на времени реализации, поскольку .NET и C# предоставляют большое количество готовых компонент, которые пришлось бы реализовывать самостоятельно при использовании C++.

Следует так же отметить, что самая ресурсоемкая операция в составе многоуровневого алгоритма  – загрубление, которое занимает около 80% от всего времени работы алгоритма. 

 

Заключение

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

Представлены различные  способы визуализации гиперграфов, выявлены преимущества и недостатки каждого из способов.

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

Поставлена задача k-разбиения гиперграфа с минимизацией веса сечения. Для решения задачи разработан и реализован многоуровневый алгоритм декомпозиции гиперграфа. Предложено несколько схем загрубления гиперграфа и алгоритмов улучшения решения в ходе фазы восстановления.

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