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

Отсюда непосредственно следует первое из соотношений (4.39). Остальные соотношения могут быть проверены аналогично.

Использование (4.39) и (4.40) существенно сокращает трудоемкость вычислений характеристик D при расчете приращений ДL (x, y) на каждой итерации. Для времени поиска пары элементов с ДL (x, y)>0 можно предварительно упорядочить характеристики D (сортировка).

Расположим характеристики D элементов из узлов Ti и Tj следующим образом:

. (4.41)

Организуем процесс вычисления ДL (x, y) так, чтобы в первую очередь кандидатами для обмена были элементы, находящиеся в начале последовательностей x и y в (4.41), тогда если меньше, чем максимальное из ранее найденных значений ДL (x, y), то по (4.15) среди оставшихся элементов {xs: s>s*} и {yl: l>l*} нет пары с большим значением ДL (x, y), поэтому поиск может быть прекращен.

Таким образом, предварительная сортировка D позволяет сократить количество просмотров для вычисления ДL (x, y)max по сравнению с k2 просмотрами при обычном переборе.

После окончания процесса минимизации числа соединений между узлами Ti и Tj (малая итерация) аналогичная процедура может быть применена к другой паре узлов. Так как имеется г узлов, то в принципе возможно осуществить р=г (г-1)/2 малых итераций. Совокупность малых итераций составляет одну большую. После окончания большой итерации минимизацию числа межузловых соединений можно продолжить, начиная снова с первой пары узлов. Процесс заканчивается, когда либо обмены элементов между двумя любыми узлами не приводят к уменьшению целевой функции, либо было проведено р* больших итераций.

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

Идея первого метода состоит в следующем. Для упрощения предположим, что число компонуемых узлов г=2л. В качестве начального варианта используем какой-либо вариант разбиения п элементов на две группы А и В по n/2 элементов. Далее применяем основной алгоритм парных перестановок для узлов А и В. Полученные узлы снова разделяем на два и т.д. до получения узлов требуемого размера. Рисунок 7 иллюстрирует процесс разделения.

Рисунок 7 - Последовательное разделение

Вначале минимизируются связи между группами А и В, затем связи между группами A1 и A2 B1, и В3. Результат, полученный для одного уровня разделения, не ухудшается при последующих разделениях. Данный метод имеет наибольшую эффективность для схем, содержащих сильно связанные группы элементов, причем размеры этих групп приблизительно одинаковы.

Другой метод состоит в последовательном выделении (рисунок 6) из исходного множества n элементов групп по k элементов с использованием итерационного процесса обменов элементов, входящих в выделенную группу Тi элементами из множества

(4.42)

Рисунок 8 - Последовательное выделение

Рассмотрим рисунок 8. Пусть получено разбиение исходного множества элементов на две группы Т1 и T’1=E\T1. Указанное разбиение может быть, например, произведено с помощью алгоритма последовательной компоновки. Обычным образом производится минимизация числа соединений между узлом Ti и множеством элементов Т’1. Далее из множества T’1 выделяется следующая группа T2 из k элементов и осуществляется аналогичная процедура минимизации для множеств T’2 и T’2=T’1\T2 и т.д. Процесс продолжается до тех пор, пока не будут выделены г узлов.

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

Оценка производительности каналов и мониторинг корпоративной сети
В последнее время всё чаще документооборот и передача корпоративной информации совершается в электронном виде тем или иным способом. Для этого уже существует множество протоколов и метод ...

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

Разработка приемника УКВ-радиостанции
Радиоприемное устройство - одно из важнейших и необходимых элементов радиотехнической системы передачи сообщений. Оно обеспечивает: улавливание энергии электромагнитного поля, нес ...