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

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

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

Проектирование и разработка интернет-магазина Компьютерная техника
Разработка сайтов для компаний является актуальной и востребованной сферой деятельности, т.к. сайт фирмы в сети Интернет представляет собой достаточно дешевый и массовый способ рекл ...

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

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