Материал: Алгоритм парных перестановок для решения задач оптимизации компоновки и размещения элементов РЭС. Муратов А.В., Скоробогатов В.С
41
-второй (локальный) дает 30 межблочных соединений с вероятностью 0,32;
-третий (локальный) дает 31 межблочное соединение с вероятностью 0,11;
-четвертый (локальный) дает 32 межблочных соединений с вероятностью 0,04;
-пятый (локальный) дает 33 межблочных соединений с вероятностью 0,03;
-отношение числа связей наихудшего минимума к числу связей наилучшего -
1,18
вероятность появления каждого последующего минимума убывает монотонно
(рис. 3.8). |
P |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0,6 |
|
|
|
|
|
|
|
|
0,5 |
|
N1min |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0,4 |
|
|
N2min |
|
|
|
|
|
|
|
|
|
|
|
||
|
0,3 |
|
|
|
|
|
|
|
|
0,2 |
|
|
|
|
|
|
|
|
0,1 |
|
|
N3min |
|
N4min |
N5min |
|
|
|
|
|
|
|
|
|
|
|
0 |
28 |
29 |
31 |
32 |
33 |
34 |
Nmin |
Nmin - число межблочных связей в точке минимума, N1min - глобальный
минимум; N2min, N3min, N4min, N5min - локальные минимумы.
Рис. 3.8. График зависимости вероятности ( Р ) появления минимумов от их значений
Контрольный пример N5
Исходные данные:
количество элементов = 12
количество блоков = 2
количество элементов в блоке 1 = 6
количество элементов в блоке 2 = 6
количество начальных распределений = 10000
матрица связей:
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
1 |
0 |
4 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
2 |
4 |
0 |
4 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
3 |
0 |
4 |
0 |
6 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
4 |
0 |
0 |
6 |
0 |
5 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
42
5 |
0 |
0 |
0 |
5 |
0 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
6 |
0 |
0 |
0 |
2 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
7 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
0 |
0 |
0 |
8 |
0 |
1 |
0 |
0 |
0 |
0 |
2 |
0 |
3 |
0 |
0 |
0 |
9 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
3 |
0 |
1 |
0 |
0 |
10 |
0 |
0 |
0 |
0 |
3 |
0 |
0 |
0 |
1 |
0 |
3 |
0 |
11 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
0 |
2 |
12 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
Результаты оптимизации:
Наилучшая матрица распределения
Блок N1 с элементами:(8)(11)(12)(9)(10)(7)
Блок N2 с элементами:(6)(1)(2)(5)(4)(3)
Наименьшее количество межблочных соединений при данном распределении=5
кол-во связей - 5 встречается 4844 раз кол-во связей - 7 встречается 4493 раз кол-во связей - 9 встречается 663 раз
Особенности результатов решения :
-число минимумов - 3 (из них первый глобальный);
-наилучший минимум (глобальный) дает 5 межблочных соединений с
вероятностью 0,48;
-второй (локальный) дает 7 межблочных соединений с вероятностью 0,45;
-третий (локальный) дает 9 межблочных соединений с вероятностью 0,07;
-отношение числа связей наихудшего минимума к числу связей наилучшего - 1,8
-вероятность появления каждого последующего минимума убывает монотонно.
По результатам исследований можно отметить следующее.
1) При оптимизации любого исходного начального распределения число межблочных связей снижается по сравнению с неоптимизированным в 1.5 - 4 раза.
2) Для 1000-10000 начальных распределений после оптимизации каждого из них число минимумов обычно равно 3 - 5 в зависимости от схемы соединений.
3) Вероятность появления глобального минимума равна 0.4 - 0.8 в зависимости от схемы соединений.
4) Значение локального минимума обычно отличается от глобального в несколько раз (в 2 - 4 раза), но в некоторых случаях это отличие составляет 15 - 20 . Чем
43
выше значение отношения наихудшего минимума к наилучшему (то есть глобальному) и
чем меньше их отличия по вероятности появления, тем меньше степень оптимизации.
5) В большинстве случаев, вероятность появления каждого последующего по эффективности минимума монотонно убывает (рис. 3.8).
6)График зависимости вероятности появления наилучшего (обычно
глобального) минимума от количества назначений начальных исходных распределений
(рис. 3.9), построенный для случая с наихудшей вероятностью P = 0,4 (P - вероятность появления наилучшего минимума) показывает, что для получения такого минимума с вероятностью, равной 0.99, достаточно десяти назначений.
Таким образом проведенные исследования показали, что степень оптимизации компоновки с помощью алгоритма парных перестановок в значительной мере зависит от исходного начального распределения элементов и чтобы результат оптимизации приближался к глобальному минимуму необходимо проводить оптимизацию для нескольких (не менее 10-20) исходных начальных распределений (рис. 3 ) и из полученных результатов выбрать лучший.
Pn 1 0,9
0,8
0,7
0,6
0,5
0,4
0,3
0,2
0,1
0 1 2 3 4 5 6 7 8 9 10 n
Рис. 3.9. График зависимости вероятности ( Рn ) появления наилучшего оптимума
(глобального минимума) от количества назначений n - начальных распределений.
44
Из изложенного выше можно отметить следующие способы повышения эффективности алгоритма парных перестановок при решении задач компоновки :
а) введение алгоритма начального распределения в программу, реализующую метод парных перестановок для достижения более глубокого оптимума распределения элементов, кроме того, использование алгоритма начального распределения освобождает оператора от необходимости составления произвольного начального распределения элементов, а также значительно сокращает время решения задачи вследствие уменьшения числа парных перестановок при поиске оптимального распределения.
б) в связи с тем, что степень оптимизации компоновки с помощью алгоритма парных перестановок в значительной мере зависит от исходного начального распределения элементов между блоками, для повышения эффективности необходимо проводить оптимизацию для нескольких (не менее 10 – 20) исходных начальных распределений и из полученных результатов выбрать лучший.
4. АЛГОРИТМ ПАРНЫХ ПЕРЕСТАНОВОК ДЛЯ ОПТИМИЗАЦИИ
РАЗМЕЩЕНИЯ С МИНИМИЗАЦИЕЙ СУММАРНОЙ ДЛИНЫ СОЕДИНЕНИЙ
4.1. Метод парных перестановок
Под оптимальным размещением обычно понимается такое местоположение модулей, при котором наилучшим образом удовлетворяются некоторые требования. В
качестве модулей могут быть выбраны как отдельные радиоэлементы ( микросхемы,
транзисторы, диоды, резисторы и т. д. ), так и типовые элементы замены ( ТЭЗы), блоки,
панели и т. д. При этом предполагается , что модули определенным образом ( согласно электрической схемы ) соединяются между собой.
Вобщем случае задача оптимального размещения носит многоцелевой характер
ипри еѐ решении оптимизация должна проводиться по совокупности критериев качества.
Учет многих критериев резко усложняет решение задачи, поэтому в каждом конкретном случае обычно выделяют наиболее важный критерий, а остальные не учитывают или используют в качестве ограничений задачи. Таким наиболее важным критерием
45
оптимизации при размещении модулей чаще всего выбирают минимизацию суммарной
длины соединений между размещаемыми модулями.
Выбор этого критерия обусловлен тем, что он обеспечивает такие
положительные эффекты, как повышение надежности соединений,
снижение паразитных емкостей и взаимосвязей, снижение трудоемкости изготовления и количества используемого провода при проводном монтаже, уменьшение времени, затрачиваемого на трассировку как при ручном, так и при машинном способе проведения трасс, увеличение процента проведенных трасс при машинной трассировке и
некоторые другие.
Решение задач оптимального размещения модулей ( одинаковых или примерно одинаковых по размерам ) может быть осуществлено с помощью алгоритма парных
перестановок модулей /1/. Суть этого алгоритма состоит в следующем.
Сначала по заданной исходной схеме составляется матрица связей , в которой каждый элемент показывает количество связей между i-м и j-м модулями. По заданному исходному размещению модулей в позициях составляется матрица расстояний , в которой каждый элемент показывает в условных единицах длины расстояние между i-м и j-м
модулями. После этого по специально выведенной формуле производится вычисление значений Wij - величин, показывающих изменение суммарной длины соединений при
перестановке местами i-го и j-го модулей. Если |
Wij меньше или равно нулю, то |
перестановка считается нецелесообразной. Если же |
Wij - ,больше нуля, то перестановка |
считается целесообразной, i-й и j-й модули переставляются местами и вычисление значений Wрк для нового размещения модулей в позициях производится вновь и так до тех пор, пока не наступит оптимизация, т. е. все значения Wрк будут отрицательными
или равными нулю. Для достижения оптимизации часто бывает достаточно 2-4
перестановок, снижение суммарной длины соединений после оптимизации по сравнению с исходной происходит обычно в 1,5 - 2 раза.
Рассмотрим эту задачу математически и выведем формулу для вычисления
значений величины Wij.
Пусть имеется какое-либо коммутационное поле с N установочными позициями для N модулей. Каждая позиция, а значит каждый установленный в эту позицию модуль
характеризуется двумя координатами xi |
и yi (рис. 4.1). |
|
|
|||||
Y |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
y3 |
А3 |
|
|
А4 |
|
Аi+2 |
|
АN |
y2 |
|
|
|
|
|
|
||
А2 |
|
|
А5 |
|
Аi+1 |
|
АN-1 |
|