Материал: Автоматизация оптимальной компоновки модулей РЭС. методические указания к выполнению лабораторных работ по дисциплине «Основы автоматизированного проектирования РЭС». Макаров О.Ю., Бобылкин И.С
парных перестановок дает значительное уменьшение времени решения задачи, а часто более высокую степень оптимизации, то есть повышает эффективность работы алгоритма парных перестановок.
Статистические исследования показали, что использование этого алгоритма начального распределения дает улучшение степени оптимизации в среднем на 10 - 20%, а в 5 - 10% случаев уже дает глобальный оптимум. Кроме того, использование этого алгоритма дает значительное сокращение времени решения задачи, так как значительно сокращается число парных перестановок для достижения оптимальности распределения, а так же, включение его в программу оптимизации освобождает оператора от необходимости составления произвольного начального распределения элементов.
1.3 Пример решения задачи минимизации межблочных соединений с помощью ЭВМ
Пусть требуется схему из 12 элементов (рис. 5), матрица соединений которой представлена в таблице 2, разделить оптимальным образом на 2 блока по 6 элементов
Таблица 2
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
1 |
0 |
5 |
0 |
0 |
0 |
0 |
2 |
2 |
0 |
0 |
0 |
0 |
2 |
5 |
0 |
8 |
0 |
0 |
0 |
0 |
3 |
2 |
0 |
0 |
0 |
3 |
0 |
8 |
0 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
0 |
0 |
2 |
0 |
4 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
5 |
0 |
0 |
0 |
4 |
0 |
5 |
0 |
0 |
0 |
0 |
0 |
0 |
6 |
0 |
0 |
0 |
0 |
5 |
0 |
0 |
0 |
0 |
0 |
2 |
3 |
7 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
0 |
0 |
0 |
8 |
2 |
3 |
0 |
0 |
0 |
0 |
2 |
0 |
4 |
0 |
0 |
0 |
9 |
0 |
2 |
0 |
0 |
0 |
0 |
0 |
4 |
0 |
3 |
0 |
0 |
10 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
0 |
4 |
0 |
11 |
0 |
0 |
0 |
2 |
0 |
2 |
0 |
0 |
0 |
4 |
0 |
4 |
12 |
0 |
0 |
0 |
0 |
0 |
3 |
0 |
0 |
0 |
0 |
4 |
0 |
Для данной схемы при следующем произвольном начальном распределении:
Блок 1 |
1 |
3 |
4 |
6 |
8 |
11 |
Блок 2 |
2 |
5 |
7 |
9 |
10 |
12 |
Число соединений между блоками до оптимизации равно 44.
Результаты работы алгоритма парных перестановок при произвольном начальном распределении, указанном выше; таковы:
Блок 1 |
3 |
4 |
|
5 |
6 |
11 |
12 |
Блок 2 |
1 |
2 |
|
7 |
8 |
9 |
10 |
|
|
|
11 |
|
|
|
|
Число соединений между блоками равно 12.
Результаты работы только алгоритма начального распределения
Блок 1 |
2 |
3 |
1 |
8 |
9 |
10 |
Блок 2 |
5 |
6 |
4 |
12 |
11 |
7 |
Число соединений между блоками равно 10.
Результаты работы алгоритма парных перестановок с использованием алгоритма начального распределения:
Блок 1 |
2 |
3 |
1 |
8 |
9 |
7 |
Блок 2 |
5 |
6 |
4 |
12 |
11 |
10 |
Число соединений между блоками равно 5.
Результаты работы алгоритма полного перебора (глобальный оптимум):
Блок 1 |
2 |
3 |
1 |
8 |
9 |
7 |
Блок 2 |
5 |
6 |
4 |
12 |
11 |
10 |
Число соединений между блоками равно 5 (рис. 6).
Рис. 5 Схема соединений
12
Рис. 6. Схема соединений после оптимизации (глобальный минимум – 5 межблочных соединений)
1.4 Вопросы к домашнему заданию
1 Пояснить блок-схему алгоритма парных перестановок для минимизации межблочных соединений.
2 Какой критерий чаще всего выбирается при оптимизации межблочных соединений и чем обусловлен этот выбор?
3 Каким образом определяется целесообразность перестановки пар модулей? Привести пример расчета.
4 Пояснить работу алгоритма начального распределения. Привести при-
мер.
5 Рассказать метод парных перестановок для оптимизации межблочных соединений.
6 Каким образом вычисляется число соединений между блоками? Привести пример.
7 Каким образом можно повысить эффективность работы алгоритма парных перестановок?
13
2 ЛАБОРАТОРНЫЕ ЗАДАНИЯ И МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ИХ ВЫПОЛНЕНИЮ
2.1 Лабораторное задание № 1
Целью лабораторного задания является закрепление знаний по оптимизации межблочных соединений при компоновке РЭС с помощью алгоритма парных перестановок. Студент должен с помощью указанного алгоритма, используя формулу (2), произвести ручным способом оптимальное распределение шести модулей на два или три блока (по указанию преподавателя), схема их соединений показана на рис. 7, а конкретные значения числа соединений а, б, в, г, д, е, ж, и, з, к для каждого варианта приведены в таблице 3, номер варианта выдается преподавателем.
|
|
|
|
|
|
|
|
|
|
|
Таблица 3 |
|
|
Варианты данных к лабораторному заданию N1 |
|
|
|
||||||||
Номер ва- |
|
|
|
Количество соединений |
|
|
|
|||||
рианта |
а |
б |
в |
г |
д |
е |
ж |
з |
|
и |
к |
|
1 |
3 |
2 |
6 |
4 |
1 |
0 |
1 |
2 |
|
3 |
1 |
|
2 |
3 |
2 |
5 |
1 |
9 |
0 |
3 |
4 |
|
6 |
7 |
|
3 |
0 |
3 |
1 |
4 |
2 |
8 |
0 |
5 |
|
6 |
9 |
|
4 |
4 |
0 |
3 |
1 |
3 |
8 |
7 |
0 |
|
5 |
6 |
|
5 |
7 |
5 |
0 |
3 |
1 |
2 |
4 |
6 |
|
0 |
8 |
|
6 |
9 |
3 |
2 |
0 |
3 |
4 |
1 |
5 |
|
8 |
0 |
|
7 |
9 |
4 |
0 |
5 |
0 |
3 |
1 |
2 |
|
6 |
4 |
|
8 |
7 |
0 |
4 |
2 |
0 |
8 |
3 |
1 |
|
3 |
7 |
|
9 |
0 |
4 |
2 |
9 |
0 |
1 |
8 |
8 |
|
3 |
1 |
|
10 |
2 |
4 |
5 |
0 |
6 |
4 |
2 |
8 |
|
3 |
1 |
|
11 |
1 |
5 |
4 |
0 |
3 |
1 |
9 |
5 |
|
2 |
3 |
|
12 |
2 |
9 |
0 |
7 |
5 |
1 |
6 |
2 |
|
3 |
4 |
|
13 |
2 |
0 |
4 |
6 |
2 |
7 |
2 |
3 |
|
9 |
1 |
|
14 |
0 |
2 |
5 |
3 |
8 |
2 |
3 |
6 |
|
1 |
1 |
|
15 |
2 |
0 |
4 |
9 |
2 |
3 |
1 |
1 |
|
7 |
7 |
|
16 |
1 |
5 |
1 |
2 |
3 |
0 |
6 |
6 |
|
8 |
8 |
|
17 |
6 |
2 |
2 |
3 |
1 |
1 |
0 |
8 |
|
7 |
2 |
|
18 |
3 |
2 |
3 |
7 |
1 |
3 |
4 |
0 |
|
5 |
2 |
|
19 |
2 |
3 |
4 |
8 |
1 |
7 |
2 |
1 |
|
0 |
9 |
|
20 |
3 |
2 |
5 |
9 |
1 |
0 |
3 |
5 |
|
4 |
0 |
|
21 |
9 |
3 |
2 |
6 |
1 |
1 |
4 |
4 |
|
0 |
3 |
|
22 |
4 |
5 |
3 |
2 |
7 |
1 |
5 |
0 |
|
4 |
2 |
|
23 |
1 |
4 |
4 |
3 |
2 |
8 |
0 |
7 |
|
7 |
6 |
|
24 |
2 |
6 |
1 |
3 |
3 |
2 |
9 |
0 |
|
4 |
1 |
|
25 |
1 |
5 |
4 |
7 |
2 |
3 |
1 |
3 |
|
0 |
3 |
|
14
Рис. 7. Схема соединений
Студент проводит оптимизацию сначала используя произвольное начальное распределение, а потом используя алгоритм начального распределения. Число межблочных соединений каждый раз определяется до и после оптимизации. Результаты сравниваются, делаются выводы, показываются преподавателю и заносятся в отчет.
2.2 Лабораторное задание № 2
Целью этого задания является получение навыков оптимизации распределения модулей между блоками с помощью ПЭВМ. Каждому студенту преподавателем указывается номер варианта схемы, модули которой необходимо с помощью ЭВМ оптимальным образом распределить между двумя или тремя блоками. Схема по номеру варианта выбирается из «Сборника схем для лабораторных работ и курсовых проектов» (часть 1) или выдается преподавателем. По полученной схеме студент составляет матрицу соединений, в которой каждый ее элемент указывает число соединений между соответствующей парой модулей. Цепи, идущие на разъем или соединяющие контакты одного и того же модуля не учитываются. Цепи питания, идущие к каждому модулю, можно не учитывать.
Исходными данными для решения задачи оптимизации компоновки являются: количество модулей, количество блоков, матрица соединений и начальное произвольное распределение элементов. Варианты начального произвольного распределения элементов представлены в таблице 4. Номер варианта каждому студенту указывается преподавателем.
Порядок выполнения лабораторного задания № 2 следующий. Все исходные данные полученного варианта заносятся в «Бланк исходных данных для оптимизации распределения модулей». В верхней части бланка указать: фамилия исполнителя, номер группы, номер варианта схемы, номер варианта начального распределения и количество распределяемых модулей.
Ниже располагается матрица соединений, представляющая информацию о количестве соединений между каждой парой модулей схемы. Матрица соединений должна иметь не более 50 элементов в строке.
15