6.2.3.4. Локальная минимизация критерия при неизменной среде [115]

Пусть ограничения выполнены (априори или с помощью описанного выше алгоритма). Тогда задача минимизации критерия решается следующим алгоритмом.

1. Случайным образом выбирается пара сегментов с вероятностью

(тем самым стохастически выбирается максимально связанная пара сегментов).

2. Для каждого из сегментов пары определяется «запас»:

и выбирается сегмент с наименьшим запасом (пусть это сегмент, т. е.

3. Строится множество номеров элементов мента, удовлетворяющих условию

т. е. потенциальных «претендентов» на перевод в сегмент. Если это множество не пусто, то для каждого его элемента определяется прирост критерия при переводе этого элемента в

Если наименьшее приращение отрицательно, то оно и определяет номер элемента

с которым следует произвести операцию первого рода т. е. перенести его из

Если же такого элемента не найдется, т. е. не удовлетворяются условия (6.2.59) или то следует образовать множество удовлетворяющее условию

из которого выбрать элемент с номером

где

и произвести операцию первого рода

Если же элемента, обладающего свойствами (6.2.62) и не найдется, то следует обратиться к операции второго рода.

4. Для этого организуется случайный перебор всех возможных обменов между сегментами. Пусть — номер случайно выбранного элемента из — номер случайно выбранного элемента из Тогда при одновременном выполнении условий

(выведенных с использованием выражения производится операция второго рода после чего снова стохастически выбирается пара наиболее связанных сегментов (см. п. 1). Естественно, что в процессе такого случайного перебора следует отбрасывать уже проверенные варианты пар элементов,

не удовлетворяющие (6.2.65). После завершения случайного перебора следует обратиться к случайному выбору наиболее связанной, но другой случайной пары сегментов (см. п. 1).

Если ни одна из пар сегментов, проверяемых подряд, не дала улучшения критерия, то задачу локальной оптимизации можно считать решенной (точнее, локально не улучшаемой).

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

Описанный алгоритм представлен в виде блок-схемы на рис. 6.2.4. Его сходимость исследована в работе [271].

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

Рис. 6.2.4. (см. скан) Блок-схема алгоритма поиска оптимального разрезания. Пунктирная стрелка — для случая адаптивного разрезания (см. п. 6.2.3.6).

а оператор 2 случайного перебора — на выбор пары вершин, обеспечивающих наиболее интенсивное уменьшение критерия:

где определено выше (6.2.49).

Такой детерминированный алгоритм рассмотрен в работе [224]. Преимущество случайного перебора перед полным (6.2.67) в данном случае очевидно, так как условия (6.2.65) при случайном переборе выполняются в среднем раньше, чем закончится полный перебор (6.2.67).

Приведем примеры работы этого алгоритма [115].

Пример 1. Рассмотрим граф с восемью вершинами из работы [27] (рис. 6.2.5). Матрица весов этого графа имеет вид

Веса вершин графа одинаковы и равны единице Требуется разрезать граф на два подграфа по четыре вершины в каждом

Начальное разрезание выбирается случайно, например:

Полученное с помощью описанного алгоритма оптимальное разрезание имеет вид

и совпадает с полученным в работе [27], где эта задача решена методом ветвей и границ (см. рис. 6.2.5).

Пример 2. В качестве другого примера рассмотрим задачу определения оптимального сечения для устройства сопряжения двух ЭВМ одного типа с несимметричным стыком [112]. Эта задача сводится к задаче разрезания графа. Устройство

сопряжения представлено в виде неориентированного графа со взвешенными ребрами (рис. 6.2.6). Вершина 19 — первая ЭВМ, вершина 20 — вторая ЭВМ. Число вершин графа Веса вершин одинаковы и равны единице. Матрица весов В графа имеет следующий вид:

(см. скан)

Требуется разрезать граф на два подграфа так, чтобы сумма весов ребер между подграфами была минимальна, а число вершин в каждом подграфе не превышало Кроме того, вершины 19 и 20 должны находиться в разных подграфах. Начальное разрезание выбирается случайным (рис. 6.2.6):

Условие «неподвижности» вершин 19 и 20 учитывается тем, что они не входят в число вершин, претендующих на перенос.

Рис. 6.2.5. Исходный граф примера 1. Пунктиром показано оптимальное разрезание.

Рис. 6.2.6. Граф устройства сопряжения двух ЭВМ. Единичные веса связей не обозначены. Пунктиром показано исходное разрезание. Оптимальное разрезание получается включением в «пунктирную» зону вершин 1, 2, 3 и 6.

Первая структура, полученная предложенным алгоритмом, имеет

Содержательный анализ этой задачи показал, что критерий качества может иметь «площадки». Для их преодоления в выражения (6.2.61), (6.2.63) и (6.2.65) алгоритма были добавлены равенства, что обеспечило возможность движения вдоль площадок минимизируемой функции Это дало возможность получить лучшее решение, чем предыдущее:

Таким образом, предложенный алгоритм эффективно решает задачу об оптимальной агрегации (разрезании) графа.

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

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