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

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

С точки зрения ОП процесс  восстановления решения условно  показан на рисунке 33. До этого, на стадии поиска начального разбиения алгоритмом было найдено начальное разбиение (стадия H₃), отмеченное на рисунке 33 одной крупных точек. Затем полученное решение было спроецировано на граф H₂, в результате чего ОП расширилась (область H₂ на рис 33), и улучшено (маленькая точка в области H₂). После этого улучшенное решение было спроецировано еще раз, что повлекло расширение ОП до областиH₁ (см. рис. 33), и опять улучшено (вторая маленькая точка в области H₁). Наконец, полученное решение спроецировано на исходный граф H₀ и еще раз улучшено. В результате получено решение исходной задачи декомпозиции (вторая крупная точка в области H₀).

Рис. 33. Процесс восстановления решения с точки зрения  
исследования области поиска.

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

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

1. Ребра гиперграфа сортируются по неубыванию веса и неубыванию размера. Пусть E=(e₁,...,e_m) – вектор отсортированных ребер.
2. i:=0; f:=0
3. Из k подграфов разбиения выбирается тот, при перемещении в который всех вершин ребра e_i не нарушаются ограничения задачи декомпозиции, и достигается наибольшее уменьшение веса сечения.
4. Если на шаге 3 перемещение состоялось, то f:=1.
5. i:=i+1
6. Если i £m, то переход на шаг 3.
7. Если f=1, то переход на шаг 2.

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

10. Использование концепции  «фильтр-вид» для построения многоуровневого  алгоритма декомпозиции

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

10.1. Фаза загрубления

Рассмотрим процесс загрубления гиперграфа H_s(V_s,E_s)с точки зрения концепции «фильтр-вид» на примере реализации схемы гиперреберного загрубления. Следует напомнить, что суть схемы гиперреберного загрубления состоит в выделении множества наиболее тяжелых и больших, попарно неинцидентных гиперребер и их ликвидации путем стягивания всех вершин таких ребер в одну вершину. Как было сказано выше, необходимо определить атрибуты элементов гиперграфа. Для вершин определим атрибут m:

1. Отсортируем гиперребра в порядке неубывания веса и размера, пусть  – сортированный вектор гиперребер.
2. i:=1.
3. Если  , то 
4. i:=i+1.
5. Если i≤m, то переход на шаг 3.

Итак, алгоритм работает следующим  образом: для вершин первого, самого тяжелого и большого ребра определяется атрибут m со значением, соответствующим e₁, затем, если второе ребро не содержит общих с первым вершин, то для его вершин также определяется атрибут m со значением e₂, если ребро e₃ не инцидентно e₁ и e₂, то для его вершин атрибут m определяется аналогичным образом и т.д. Очевидно, что эта процедура гарантирует, что будут помечены вершины попарно неинцидентных гиперребер.

Если теперь применить  к гиперграфу H объединяющий фильтр вида

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

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

Итак, мы получили загрубленный гиперграф H_s+1, который может быть загрублен еще раз или передан алгоритму отыскания начального разбиения.

После проведения серии загрублений мы имеем гиперграф H_s(V_s, E_s), достаточно малой размерности, на котором возможно отыскание начального разбиения. Пусть мы отыскали начальное разбиение, представленное в виде вектора P=(p₁,…p_n), p_i=1..k, i=1..n, где k – количество компонент разбиения, n – количество вершин H_s. Для того чтобы эффективно использовать преимущества концепции «фильтр-вид» необходимо представить информацию о разбиении в виде атрибутов, для этого определим атрибут pследующим образом:

Таким образом, каждая вершина  имеет информацию о том, какой  компоненте разбиения она принадлежит, определенную атрибутом p. В силу того, что загрубленный гиперграф H_s является видом H_s-1 и между ними существует атрибутивная связь, атрибут p, определенный для H_s будет установлен для соответствующих вершин H_s-1. Для примера, приведенного на рис. 2.2 и 2.3 определение атрибута p=1 для вершины V₁ (рис 2.3) загрубленного гиперграфа будет означать определение атрибута p с тем же значением для вершин v₁, v₂, v₃, v₄ незагрубленного гиперграфа. Это, фактически, означает, что разбиение, полученное для H_s будет автоматически перенесено на H_s-1. Затем атрибут p будет определен для H_s-2, т.к. он является видом H_s-1 и далее, до исходного графа H₀. Ранее говорилось, что загрубление должно быть реализовано таким образом, что отыскание начального разбиения должно означать также отыскание некоторого решения для исходной задачи. Эта цель достигнута применением фильтров и порождением видов без необходимости описания дополнительных процедур переноса решения.

10.2. Фаза восстановления  решений

Описанная ранее процедура  загрубления гарантирует, что получение решения задачи H_s означает получение некоторых решений задач H_l l<s. Поэтому, отыскание начального разбиения означает нахождение решения всех задач, построенных на стадии загрубления. Как уже отмечалось, фаза загрубления состоит из двух процессов: проецирование решения и улучшение его на каждом этапе. Применение фильтров и видов избавляет нас от описания и реализации отдельной процедуры проецирования решения, поскольку способ кодирования решения в атрибутах вершин и наличие атрибутивной связи между гиперграфом-видом и гиперграфом-прообразом гарантирует передачу информации о разбиении от более загрубленного гиперграфа к менее загрубленному.

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

11. Многоуровневый алгоритм  с элементами эволюционно-генетического  поиска

Методика улучшения решения (см. п. 9.5), основанная на перемещении  вершин, принадлежащих одному гиперребру, целиком в какую-либо компоненту разбиения работает достаточно быстро. Однако она не содержит никаких средств преодоления локальных экстремумов, что сказывается на качестве находимых ею решений. В эвристики типа KL и FM интегрированы механизмы, направленные на предотвращение преждевременной сходимости, но, не смотря на это, такие алгоритмы не обеспечивают широкого исследования области поиска в силу своей жадности и работают значительно медленнее предложенной методики.

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

Классический генетический алгоритм (ГА) [LG1, LG3, DB1, DB2, DBNS1, DBNS2, DBNS3, DBNS4, DBNS5, DBNS6, DBNS7, DBSI, LG3, PKKW, NS1, NS2], в том числе работающий с графовыми или гиперграфовыми моделями [LG1, LG3, PKKW, DB1, DBNS3, DBNS4, NS1, NS2], подразумевает манипулирование так называемыми кодировками (генотипами). Каждая кодировка представляет собой некоторое представление решения задачи в форме, удобной для применения различных операторов ГА. Каждая кодировка имеет оценку, называемую приспособленностью, которая характеризует качество решения, соответствующего данной кодировке. В результате процесса, эмулирующего эволюцию набора кодировок, определяется «кодировка-победитель», обладающая наилучшей приспособленностью, которой соответствует решение задачи с наивысшим качеством.

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

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

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

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