Итерационные алгоритмы улучшения компоновки

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

Обозначим через К0 некоторый исходный вариант компоновки элементов. Ему соответствует значение функции-критерия F0. В некотором смысле структура итерационного процесса улучшения варианта К0 аналогична градиентным методам оптимизации, в которых на каждой итерации осуществляется движение в области определения функции в направлении уменьшения ее значений. Изменениям переменных в данном случае соответствует перестановка элементов между различными узлами.

Пусть задано некоторое разбиение К0 множества элементов Е на узлы T1,…. Ti,…, Tj,…, Тг.

Предположим, что произведен выбор пары элементов exTi и eyTj и они взаимно меняются местами. В этом случае получаем новый вариант разбиения К1 с узлами

, (4.1).

которому соответствует значение критерия F1.

Если ДF=F0-F1>0, то происходит уменьшение функции-критерия F и обмен, соответствующий данному случаю, считается успешным.

Рассматривая вариант компоновки K1 снова как исходный, можно осуществить поиск другой пары элементов, обмен которых приведет к уменьшению значения F1, и т.д. Таким образом, в ходе указанного итерационного процесса образуется последовательность вариантов компоновки K0, K1, К2,…, Кs, которым отвечает монотонно убывающая последовательность значений критерия: F0>F1>F2>… >Fs (рисунок 5). Поскольку значения функции F на множестве допустимых вариантов компоновки {К} ограничены снизу величиной абсолютного минимума функции F*, естественно, что на некотором шаге процесс минимизации закончится, причем Fs≥F*, т.е. мы получим вариант компоновки Ks, отвечающий локальному минимуму функции F.

Рисунок 5 - Изменение критерия F

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

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

Одна из них состоит в следующем. Выбирается некоторый узел Ti и в нем произвольный элемент ех. Осуществляются попытки обмена этого элемента последовательно со всеми элементами еу, не принадлежащими рассматриваемому узлу, и рассчитывается приращение ДF(ех, еу). Для обмена выбирается первый элемент еу, для которого ДF(ex, ey) >0.

Другой способ состоит в подборе такой пары элементов, для которой ДF(ex, еу) принимает максимальное значение. Очевидно, что в этом случае время поиска успешного обмена возрастает, однако в результате обмена число межузловых соединений будет меньше.

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

Читайте также

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

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

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