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

Пусть имеется некоторый начальный вариант компоновки, полученный одним из последовательных алгоритмов либо вручную. Основой рассматриваемых алгоритмов компоновки является использование итерационного процесса обменов местами элементов или групп элементов, принадлежащих различным узлам, с целью минимизации некоторого критерия. Поскольку структура большинства алгоритмов этого типа имеет много общего, рассмотрим процесс улучшения компоновки применительно к произвольному критерию 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, еу) принимает максимальное значение. Очевидно, что в этом случае время поиска успешного обмена возрастает, однако в результате обмена число межузловых соединений будет меньше.

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

Перейти на страницу: 1 2 3 4 5 6

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

Разработка локальной сети предприятия (на материалах ОАОТ Дабрабыт)
Локальная вычислительная сеть(Local Area Network), именуемая в дальнейшем LAN, - это совокупность компьютеров и других средств вычислительной техники (активного сетевого оборудования, пр ...

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

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

Основные разделы

Все права защищены! (с)2020 - www.generallytech.ru