2250
.pdf
|
|
|
|
|
|
|
|
51 |
|
матрицы (рис. 4.4), а координаты |
модулей |
при |
начальном размещении запишем так : |
||||||
x1 = 1, x2 = 3, x3 = 3, x4 = 1, y1 = 3, y2 = 4, y3 = 1, y4 = 1. |
|||||||||
|
S |
|
|
2 |
|
3 |
4 |
|
|
|
|
1 |
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
1 |
|
0 |
|
2 |
|
3 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
2 |
|
0 |
|
1 |
4 |
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
3 |
|
1 |
|
0 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
1 |
|
4 |
|
2 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
Рис. 4.4. Матрица соединений
Для примера работы алгоритма оптимизацию размещения модулей схемы,
показанной на рис. 4.5, проведем ручным способом с помощью алгоритма парных перестановок.
Начнем с операции блока 2, т.е. вычислим суммарную длину соединений для начального размещения по формуле (4.6.а):
N-1 |
N |
||||||||
Wo |
Sij ( |
|
xi xj |
|
|
|
yi yj |
|
) |
|
|
|
|
|
|||||
i=1 |
j i 1 |
=S12 ( |
x1 |
x2 |
|
|
|
y1 |
y2 |
)+S13 ( |
|
x1 |
x3 |
|
|
|
|
|
|
|
y1 |
y3 |
|
) + |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||
+ S |
|
( |
x1 |
x |
4 |
|
|
|
|
y y |
) +S23 |
( |
|
x x |
|
|
|
|
|
|
|
|
y y |
) + |
||||||||||
|
14 |
|
|
|
|
|
|
|
1 |
4 |
|
|
|
|
2 |
3 |
|
|
|
|
|
2 |
3 |
|
|
|
||||||||
|
y |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
А2 |
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
А1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
2 |
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
А4 |
2 |
|
|
|
|
|
|
А3 |
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
1 |
2 |
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
x |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис. 4.5. Схема размещения модулей в начальном состоянии.
+S24 ( |
|
x x |
|
|
|
|
|
y y |
|
) + S ( |
|
x x |
|
|
|
|
|
y y |
|
) = |
|||||||||||||||||
|
|
2 |
4 |
|
|
|
|
|
2 |
4 |
|
|
|
34 |
|
|
3 |
|
4 |
|
|
|
|
3 |
4 |
|
|
||||||||||
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||
= 2 ( |
|
|
|
|
|
3 4 |
|
) + 3 ( |
|
1 3 |
|
|
|
3 1 |
|
) + |
|
|
|
||||||||||||||||||
1 3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||
+1 ( |
1 1 |
|
|
|
3 1 |
) +1 ( |
3 3 |
|
|
|
4 1 |
) + |
|
|
|
||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
52 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
+ 4 ( |
3 1 |
|
|
4 1 |
) + 2 ( |
3 1 |
|
1 1 |
) = |
|
|
|
|
|||||||||||||||||
= 2 3 3 4 1 2 1 3 4 5 2 2 = 6 + 12 + 2 + 3 + 2 0 + 4 = 47 ед., |
||||||||||||||||||||||||||||||||||
т.е. суммарная длина соединений до оптимизации равна |
47 |
единицам |
||||||||||||||||||||||||||||||||
длины. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Далее, |
выполняя |
|
|
операцию |
блока |
3, |
вычислим |
все |
значения |
Wij, т.е. |
||||||||||||||||||||||||
значения |
W12 , |
W23 , W34 , W13 , |
W14 |
и |
|
W24 . |
Эти |
значения будем |
вычислять |
|||||||||||||||||||||||||
по формуле (4.13): |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
N |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Wij |
|
( Sik |
|
|
SJK ) (| xi |
xk | |
| yi |
yk | |
| x j |
xk | |
|
| y j |
yk |) |
|
|||||||||||||||||||
|
|
|
k 1 i |
k j |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
W12 |
|
( |
S1k |
|
|
S2K ) (| x1 |
|
xk | |
| y1 |
yk | |
| x2 |
xk | |
|
| y2 |
yk |) |
|
||||||||||||||||||
|
|
k |
3 т.к.k |
1k |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
(S13 |
S23) |
(| x1 |
|
x3 | |
| |
y1 |
y3 | |
|
| x2 |
|
x3 | |
| |
y2 |
|
y3 |) |
(S14 |
S24 )(| x1 |
|
x4 | |
| y1 |
y4 | |
|||||||||||||
|
| x2 |
x4 | |
| y2 |
|
y4 |) |
(3 1)(|1 3| |
|
| 3 |
1| |
| 3 |
|
3| |
| 4 |
1|) |
(1 |
4)(|1 |
1| |
| 3 |
1| |
|
||||||||||||||
|
| 3 |
1| |
| 4 |
1|) |
11 |
|
|
ед. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Аналогично, получим |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
W23 |
(S21 |
|
S31 ) (| x2 |
|
x1 | |
|
| y2 |
|
y1 | |
| x3 |
x1 | |
|
| y3 |
y1 |) |
|
|||||||||||||||||||
|
(S24 |
S34 ) (| x2 |
x4 | |
|
| y2 |
|
|
y4 | |
|
| x3 |
|
x4 | |
| y3 |
|
y4 |) |
7 ед. |
||||||||||||||||||
W34 |
(S31 |
|
S41 ) (| x3 |
|
x1 | |
| y3 |
|
y1 | |
| x4 |
x1 | |
| y4 |
y1 |) |
|
|||||||||||||||||||||
(S32 |
S42 ) (| x3 |
|
x2 | |
|
| y3 |
|
y2 | |
| x4 |
x2 | |
| y4 |
|
y2 |) |
10 ед. |
|||||||||||||||||||||
W13 |
(S12 |
|
S32 ) (| x1 |
|
x2 | |
|
| y1 |
y2 | |
| x3 |
x2 | |
|
| y3 |
y2 |) |
|
||||||||||||||||||||
|
(S14 |
S34 ) (| x1 |
|
x4 | |
|
| y1 |
y4 | |
|
| x3 |
x4 | |
| y3 |
|
y4 |) |
0 ед. |
|
|||||||||||||||||||
W14 |
(S12 |
|
S42 ) (| x1 |
|
x2 | |
|
| y1 |
|
y2 | |
| x4 |
x2 | |
|
| y4 |
y2 |) |
|
|||||||||||||||||||
(S13 |
S43 ) (| x1 |
|
x3 | |
| y1 |
|
y3 | |
|
| x4 |
x3 | |
| y4 |
|
y3 |) |
6 ед. |
|
||||||||||||||||||||
W24 |
(S21 |
|
S41 ) (| x2 |
|
x1 | |
|
| y2 |
|
y1 | |
| x4 |
x1 | |
|
| y4 |
y1 |) |
|
|||||||||||||||||||
|
(S23 |
S43 ) (| x2 |
x3 | |
|
| y2 |
|
y3 | |
| x4 |
x3 | |
| y4 |
|
y3 |) |
0 ед. |
|||||||||||||||||||||
Таким образом, получили все 6 значений |
Wij : W12 |
= 11, |
W34 = 10, W14 = |
|||||||||||||||||||||||||||||||
6, W23 = 7, |
W13 = 0, |
W24 |
|
|
= 0. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
Далее, выполняя операцию блока 4, из всех значений |
Wij |
выбираем |
||||||||||||||||||||||||||||||||
максимальное. Им является |
|
W12 |
= 11, и |
так |
как |
оно положительное, |
то, |
согласно |
операции блока 5, производим перестановку местами модулей 1 и 2. Схема расположения модулей после перестановки показана на рис. 4.6 выпишем для нее координаты модулей : х1 = 3, х2 = 1, х3 = 3, х4 = 1, y1 = 4, y2 = 3, y3 = 1, y4 = 1.
Аналогичным образом вычислим все значения Wij уже для нового размещения
|
|
|
|
|
|
|
|
|
|
|
53 |
модулей. Заметим, что значения Sij остались прежними, |
а координаты хi , |
yj после |
|||||||||
перестановки изменились. |
|
|
|
|
|
|
|
|
|
||
W12 |
(S13 |
S32 ) (| x1 |
x3 | |
| y1 |
y3 | |
| x2 |
x3 | |
| y2 |
y3 |) |
|
|
(S14 |
S24 ) (| x1 |
x4 | |
| y1 |
y4 | |
| x2 |
x4 | |
| y2 |
y4 |) |
|
|
|
= (3 - 1)(|3 - 3| + |4 - 1| - |1 - 3| - |3 - 1|) + (1 - 4)(|3 - 1| + |4 - 1| - |1 - 1| - |3 - 1|) = -11. |
|||||||||||
Аналогично, вычислив остальные значения |
Wij, |
получим |
W23 = 0, W34 = - |
||||||||
10, W13 = -4, |
W14 = -1 |
и |
W24 = -4 и переходим |
к выполнению операции |
блока 4, |
||||||
т.е. находим ( |
Wij )max . Им является |
W23 |
= 0, переходим к |
выполнению |
операции |
||||||
блока 5, т.е. проверяем |
условие |
W23 |
0 . Условие |
выполняется, поэтому управление |
передается блоку 7. Это означает, что оптимизация наступила и необходимо вычислить суммарную длину соединений для оптимального размещения, т.е. для размещения, полученного после перестановки местами первого и второго модулей.
Вычисление суммарной |
длины |
|
соединений |
производим |
аналогичным |
||||||||||||
образом, как это делалось для начального размещения, т.е. по формуле (4.6.а): |
|||||||||||||||||
N-1 |
N |
|
|
|
|
|
|
|
|
|
|
|
|
||||
Wo |
Sij ( |
|
xi |
xj |
|
|
|
|
yi |
yj |
|
) . |
|
||||
|
|
|
|
|
|
|
|||||||||||
i=1 j |
i 1 |
|
|
|
|
|
|
|
|
|
|
|
|
||||
y |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
4 |
|
|
|
|
|
2 |
|
|
|
|
|
А1 |
|
|
|||
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
А2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
3 |
|
|
|
|
|
|||||||
2 |
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
||
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
А4 |
|
|
|
2 |
|
|
|
|
|
А3 |
|
|
||||
|
|
|
|
|
|
|
|
|
|
||||||||
0 |
|
1 |
|
|
|
2 |
|
|
|
|
|
3 |
|
|
|
x |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис. 4.6. Схема размещения модулей после перестановки местами первого и второго модулей.
Следует отметить, что в этой формуле значения Sij |
попрежнему |
|||
определяются |
элементами матрицы соединений, показанной на рис. 4.4, а |
координаты |
||
модулей xi |
и yj |
будут определяться схемой размещения модулей, |
полученной |
|
после перестановки местами первого и второго |
модулей и изображенной на рис. 4.6. |
|||
Подставив в |
формулу |
значения Sij , xi и yj |
и проведя необходимые |
вычисления, |
|
|
54 |
получим W12 = 36 ед. длины, т.е. после оптимизации |
суммарная длина соединений |
|
стала равной 36 |
ед. длины, а в начальном состоянии |
она была равна 47 ед. длины, |
т.е. уменьшилась |
на 11 ед. Это уменьшение должно равняться сумме значений Wij |
, по которым производились перестановки модулей. В нашем случае была одна перестановка и W12 = 11, что совпадает с величиной уменьшения суммарной длины соединений. Это значит, что расчеты проведены верно.
В качестве примера решения задачи размещения модулей на коммутационном поле с минимизацией суммарной длины соединений с помощью ПЭВМ рассмотрим следующий.
Исходные данные:
количество модулей = 12
схема соединений представлена матрицей смежности (табл. 4.1)
координаты начального размещения модулей представлены в табл. 4.2
Табл. 4.1. Матрица смежности.
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
1 |
0 |
4 |
1 |
0 |
0 |
2 |
2 |
0 |
0 |
0 |
1 |
0 |
2 |
4 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
3 |
1 |
0 |
0 |
4 |
2 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
4 |
0 |
0 |
4 |
0 |
1 |
0 |
0 |
1 |
1 |
2 |
1 |
1 |
5 |
0 |
0 |
2 |
1 |
0 |
0 |
0 |
4 |
3 |
1 |
0 |
2 |
6 |
2 |
0 |
0 |
0 |
0 |
0 |
4 |
0 |
0 |
1 |
3 |
1 |
7 |
2 |
1 |
0 |
0 |
0 |
4 |
0 |
0 |
0 |
0 |
0 |
0 |
8 |
0 |
0 |
1 |
1 |
4 |
0 |
0 |
0 |
1 |
0 |
0 |
2 |
9 |
0 |
0 |
0 |
1 |
3 |
0 |
0 |
1 |
0 |
4 |
0 |
3 |
10 |
0 |
0 |
1 |
2 |
1 |
1 |
0 |
0 |
4 |
0 |
3 |
1 |
11 |
1 |
1 |
1 |
1 |
0 |
3 |
0 |
0 |
0 |
3 |
0 |
0 |
12 |
0 |
0 |
0 |
1 |
2 |
1 |
0 |
2 |
3 |
1 |
0 |
0 |
Табл. 4.2. Координаты размещения модулей (в усл. ед. длины).
|
|
|
|
Номера и координаты модулей |
|
Суммарная |
|||||||||||
|
|
|
|
|
|
|
|
(от 1 до 12) |
|
|
|
|
длина |
||||
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
9 |
10 |
11 |
12 |
соединений, |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
усл.ед. |
до |
x |
2 |
3 |
|
3 |
1 |
1 |
|
2 |
1 |
1 |
|
2 |
2 |
3 |
3 |
153 |
оптимизации |
y |
1 |
2 |
|
3 |
2 |
4 |
|
4 |
3 |
1 |
|
2 |
3 |
1 |
4 |
|
|
|
|
|
55
после |
x |
2 |
1 |
3 |
3 |
1 |
3 |
1 |
2 |
1 |
2 |
2 |
1 |
91 |
|
оптимизации |
y |
1 |
1 |
4 |
3 |
4 |
2 |
1 |
4 |
3 |
3 |
2 |
2 |
||
|
В результате решения этой задачи с помощью программы, реализующей алгоритм парных перестановок, получили новое (оптимальное) размещение модулей,
указанное в табл. 4.2, с суммарной длиной соединений, равной 91 условная единица длины. До оптимизации суммарная длина составляла 157 условных единиц длины, то есть суммарная длина соединений после оптимизации уменьшилась более, чем в 1,7 раза.
4.2. Исследование зависимости эффективности алгоритма парных перестановок от
начальных исходных размещений и способы повышения его эффективности
При размещении элементов РЭС часто в качестве критерия оптимизации выбирается суммарная длина соединений, так как ее минимизация обеспечивает такие положительные эффекты, как повышение надежности соединений, снижение паразитных емкостей и взаимосвязей, снижение трудоемкости изготовления и количества используемого провода при проводном монтаже и т.д.
Одним из методов оптимизации размещения элементов является алгоритм парных перестановок /1,2/. Согласно этому алгоритму, сначала все элементы схемы произвольным образом размещаются по заданному количеству установочных позиций, а
затем производятся перестановки тех пар элементов, находящихся в разных позициях,
которые дают уменьшение суммарной длины соединений. В результате таких перестановок достигается локальный минимум. Близость его к глобальному минимуму,
т.е. степень оптимизации, существенно зависит от исходного начального (обычно произвольного) размещения элементов в позициях. В связи с этим целесообразно исследовать зависимость степени оптимизации от начальных размещений. Для этого необходимо разработать программу, реализующую алгоритм парных перестановок с
56
использованием большого количества начальных размещений. Для каждого начального размещения должна быть проведена своя оптимизация. Для создания большого количества начальных размещений можно использовать функцию рандомизации, включив эту функцию в программу. Для облегчения обработки статистических данных в программе следует предусмотреть вывод результатов оптимизации в порядке уменьшения степени оптимизации с указанием количества появлений каждого оптимума. Отдельно вывести наилучший оптимум с указанием размещения элементов по позициям. Для оценки степени оптимизации необходимо сравнить оптимумы между собой.
Поставленные задачи были нами решены. Была разработана программа оптимального размещения элементов с получением большого количества (10000-100000)
исходных начальных размещений методом рандомизации.
Исследования проводились на различных схемах соединений с различным расположением установочных позиций для элементов с использованием 10000 - 100000
исходных начальных размещений для каждой схемы.
Из многих рассмотренных примеров приведем следующий.
Исходные данные:
количество элементов = 12
количество исходных начальных размещений: 10000
матрица соединений представлена в табл. 4.3
координаты установочных позиций даны в табл. 4.4
|
|
Табл. 4.3 |
|
|
|
|
|
|
|
|
|
Табл. 4.4 |
Табл. 4.5 |
|
|||||
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 11 12 |
|
x y |
N x y |
||||||
1 |
0 |
|
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
4 |
0 |
|
5 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
0 |
|
0 |
0 |
0 |
2 |
1 |
3 |
0 |
1 |
1 |
0 |
1 |
|
1 |
4 |
2 |
2 |
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
0 |
|
0 |
0 |
2 |
1 |
1 |
0 |
2 |
1 |
0 |
0 |
1 |
|
2 |
4 |
3 |
4 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
0 |
|
0 |
2 |
0 |
0 |
0 |
0 |
4 |
0 |
0 |
0 |
2 |
|
4 |
4 |
4 |
5 |
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
1 |
|
2 |
1 |
0 |
0 |
5 |
1 |
1 |
0 |
1 |
3 |
1 |
|
5 |
4 |
5 |
2 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
1 |
|
1 |
1 |
0 |
5 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
1 |
2 |
6 |
1 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
1 |
|
3 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
2 |
2 |
7 |
1 |
4 |
8 |
1 |
|
0 |
2 |
4 |
1 |
1 |
0 |
0 |
2 |
1 |
0 |
2 |
|
4 |
2 |
8 |
5 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9 |
0 |
|
1 |
1 |
0 |
0 |
0 |
0 |
2 |
0 |
3 |
0 |
1 |
|
5 |
2 |
9 |
5 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10 |
0 |
|
1 |
0 |
0 |
1 |
0 |
1 |
1 |
3 |
0 |
3 |
0 |
|
1 |
1 |
10 |
3 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
11 |
4 |
|
0 |
0 |
0 |
3 |
1 |
0 |
0 |
0 |
3 |
0 |
0 |
|
2 |
1 |
11 |
2 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
12 |
0 |
|
1 |
1 |
2 |
1 |
1 |
0 |
2 |
1 |
0 |
0 |
0 |
|
3 |
1 |
12 |
4 |
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Результаты решения задачи приведены в табл. 4.6.
Табл. 4.6. Результаты эксперимента и их обработка
|
|
|
|
|
|
57 |
Номер |
Значение |
Количество |
Вероятность Pi |
Удаление |
|
Суммарная |
миним |
минимума |
появлений |
Появления |
минимума от |
|
вероятность |
ума |
суммарной |
минимума |
минимума |
глобального |
, |
Pi |
|
длины |
|
|
% |
|
|
|
|
|
|
|
|
|
1 |
126 |
210 |
0,0210 |
0 |
|
0,021 |
|
|
|
|
|
|
|
2 |
127 |
466 |
0,0466 |
0,8 |
|
0,068 |
|
|
|
|
|
|
|
3 |
128 |
335 |
0,0335 |
1,6 |
|
0,102 |
|
|
|
|
|
|
|
4 |
129 |
831 |
0,0831 |
2,4 |
|
0,185 |
|
|
|
|
|
|
|
5 |
130 |
147 |
0,0147 |
4,0 |
|
0,200 |
|
|
|
|
|
|
|
6 |
131 |
181 |
0,0181 |
4,8 |
|
0,218 |
|
|
|
|
|
|
|
7 |
132 |
143 |
0,0143 |
5,6 |
|
0,232 |
|
|
|
|
|
|
|
8 |
133 |
428 |
0,0428 |
6,4 |
|
0,275 |
|
|
|
|
|
|
|
9 |
134 |
389 |
0,0389 |
7,2 |
|
0,314 |
|
|
|
|
|
|
|
10 |
135 |
279 |
0,0279 |
8,0 |
|
0,342 |
|
|
|
|
|
|
|
11 |
136 |
563 |
0,0563 |
8,8 |
|
0,398 |
|
|
|
|
|
|
|
12 |
137 |
516 |
0,0516 |
9,6 |
|
0,450 |
|
|
|
|
|
|
|
13 |
138 |
536 |
0,0536 |
10,4 |
|
0,504 |
|
|
|
|
|
|
|
14 |
139 |
1041 |
0,1041 |
11,2 |
|
0,608 |
|
|
|
|
|
|
|
15 |
140 |
669 |
0,0669 |
12,0 |
|
0,675 |
|
|
|
|
|
|
|
|
Продолжение табл. 4.6 |
|
|
|
|
|
Номер |
Значение |
Количество |
Вероятность Pi |
Удаление |
|
Суммарная |
миним |
минимума |
появлений |
Появления |
минимума от |
|
вероятность |
ума |
суммарной |
минимума |
минимума |
глобального |
, |
Pi |
|
длины |
|
|
% |
|
|
|
|
|
|
|
|
|
16 |
141 |
678 |
0,0678 |
12,8 |
|
0,743 |
|
|
|
|
|
|
|
17 |
142 |
494 |
0,0494 |
13,6 |
|
0,793 |
|
|
|
|
|
|
|
18 |
143 |
619 |
0,0619 |
14,4 |
|
0,855 |
|
|
|
|
|
|
|
19 |
144 |
459 |
0,0459 |
15,2 |
|
0,901 |
|
|
|
|
|
|
|
20 |
145 |
272 |
0,0272 |
16,0 |
|
0,928 |
|
|
|
|
|
|
|
21 |
146 |
167 |
0,0167 |
16,8 |
|
0,935 |
|
|
|
|
|
|
|
22 |
147 |
170 |
0,0170 |
17,6 |
|
0,952 |
|
|
|
|
|
|
|
23 |
148 |
76 |
0,0076 |
18,4 |
|
0,960 |
|
|
|
|
|
|
|
24 |
149 |
96 |
0,0096 |
19,2 |
|
0,969 |
|
|
|
|
|
|
|
25 |
150 |
70 |
0,0070 |
20,0 |
|
0,976 |
|
|
|
|
|
|
|
26 |
151 |
35 |
0,0035 |
20,8 |
|
0,980 |
|
|
|
|
|
|
|
27 |
152 |
32 |
0,0032 |
21,6 |
|
0,983 |
|
|
|
|
|
|
|
28 |
153 |
45 |
0,0045 |
22,4 |
|
0,989 |
|
|
|
|
|
|
|
29 |
154 |
2 |
0,0002 |
23,2 |
|
0,989 |
|
|
|
|
|
|
|
30 |
155 |
19 |
0,0019 |
24,0 |
|
0,990 |
|
|
|
|
|
|
|
58
31 |
156 |
2 |
0,0002 |
24,8 |
0,990 |
|
|
|
|
|
|
32 |
157 |
9 |
0,0009 |
25,6 |
0,990 |
|
|
|
|
|
|
33 |
159 |
3 |
0,0003 |
26,4 |
0,994 |
|
|
|
|
|
|
34 |
160 |
14 |
0,0014 |
27,2 |
0,996 |
|
|
|
|
|
|
35 |
161 |
4 |
0,0004 |
28,0 |
1 |
|
|
|
|
|
|
Наилучшее размещение модулей представлено в табл. 4.5.
Минимальная суммарная длина (глобальный минимум) при данном размещении равна 126 единиц.
Особенности результатов решения.
В результате оптимизации с помощью алгоритма парных перестановок 10000
различных исходных размещений получили 35 различных минимумов суммарных длин,
различающихся в 1,3 раза, что означает существенную зависимость значения минимума от исходного начального размещения
Гистограмма распределения этих 35 минимумов с указанием их значений Wi min
и вероятности появления каждого из них Pi приведена на рис. 4.7.
Значение глобального минимума Wo min равно 126 единиц длины. Оптимальное размещение элементов для глобального минимума показано в табл. 4.5.
По результатам исследований можно отметить следующее:
1) При оптимизации любого исходного начального размещения элементов суммарная длина соединений уменьшается по сравнению с неоптимизированным в 1,3 - 3
раза.
2)Степень оптимизации, т.е. значение минимума суммарной длины соединений,
взначительной степени зависит от начального размещения элементов в установочных позициях (рис. 4.7).
3) Значение суммарной вероятности |
Pi в зависимости от величины |
η Wi min - Wo min 100 %, показывающей насколько процентов полученный результат
Wo min
оптимизации отличается от глобального, монотонно возрастает, асимптотически приближаясь к единице при значениях , равных 18-22 % (рис. 4.8). По этому рисунку можно определить суммарную вероятность появления результата оптимизации,
отличающегося от глобального на заданное значение в процентах. Суммарная вероятность Pi - это сумма вероятностей i-го и всех предыдущих (лучших) минимумов.
59
Рис. 4.7. Гистограмма распределения минимумов суммарной длины с указанием вероятности их появления
Рис. 4.8. Вероятность появления результата оптимизации, отличающегося от глобального не более, чем на процентов.
60
Таким образом проведенные исследования показали, что степень оптимизации размещения с помощью алгоритма парных перестановок в значительной мере зависит от исходного начального размещения элементов в позициях и чтобы результат оптимизации приближался к глобальному минимуму необходимо проводить оптимизацию для нескольких (не менее 10-20) исходных начальных размещений и из полученных результатов выбрать лучший. Это один из способов повышения эффективности алгоритма парных перестановок.
Вторым способом является метод, в алгоритме которго из всех возможных целесообразных перестановок пар элементов выбирается та пара элементов, перестановка которых дает максимальное уменьшение суммарной длины соединений, а не первая попавшаяся целесообразная перестановка. Как показали наши исследования при этом методе вероятность появления минимумов, расположенных ближе к глобальному,
возрастает, а самых удаленных - уменьшается (рис. 4.7).
5. АЛГОРИТМ ПАРНЫХ ПЕРЕСТАНОВОК ДЛЯ ОПТИМИЗАЦИИ РАЗМЕЩЕНИЯ С МИНИМИЗАЦИЕЙ ПЕРЕСЕЧЕНИЙ ПРОВОДНИКОВ
5.1. Метод парных перестановок
При автоматизированном размещении элементов обычно в качестве критерия оптимизации выбирается минимум суммарной длины соединений, дающий ряд положительных эффектов: повышение надежности, снижение паразитных взаимосвязей и т.д. Наряду с этим критерием оптимизации предлагается при решении задачи оптимального размещения использовать и такой критерий, как минимум числа пересечений проводников, приводящий к уменьшению числа проволочных перемычек, к
упрощению формы печатных проводников, к уменьшению суммарной длины, что в конечном итоге ведет к уменьшению трудоемкости изготовления изделия, снижению себестоимости, увеличению надежности соединений, снижению паразитных взаимосвязей и упрощению трассировки соединений.