Учебное пособие 1530
.pdf61
Для иллюстрации решения этой задачи представим схему в виде графа (рис. 5.1),
в котором вершинами являются элементы (модули) схемы, а ребрами – соединения между элементами. Размещение позиций , в которые устанавливаются вершины графа, задается их координатами x и y, а соединения между элементами задаются матрицей связей (табл.
5.1).
Табл. 5.1. Матрица смежности.
|
|
|
1 |
2 |
3 |
4 |
|
|
|
|
1 |
0 |
0 |
1 |
1 |
|
|
|
|
2 |
0 |
0 |
1 |
1 |
|
|
|
|
3 |
1 |
1 |
0 |
1 |
|
|
|
|
4 |
1 |
1 |
1 |
0 |
|
|
1 |
2 |
|
|
|
|
4 |
2 |
4 3 1 3
Рис. 5.1. |
Рис. 5.2. |
|
Минимизацию числа пересечений графа можно провести методом парных перестановок его вершин. Этот метод можно проиллюстрировать следующим образом:
пусть граф, представленный на рис. 5.1 имеет пересечение ребер. Осуществим парную перестановку первой и четвертой вершин графа, в результате чего получим граф без пересечений (рис. 5.2).
Общее количество пересечений для графа с n вершинами можно определить по формуле :
|
1 n |
n |
n |
n |
|
|
S |
|
|
|
|
p[(i, j);(k, l)]mij mkl, |
(5.1) |
8 i 1 |
|
|
||||
|
j 1 |
k 1 |
l 1 |
|
где n – число вершин графа;
1, если между ребром (i,j) и ребром (k,l) есть пересечение
p[(i,j);(k,l)] =
0, в противном случае;
mij, mkl - элементы матрицы смежности.
В другой форме можно записать :
|
|
|
|
|
62 |
n 1 |
n |
n 1 |
|
n |
|
S |
|
|
|
p[(i, j);(k,l)]mij mkl, |
(5.2) |
i 1 |
j i |
1 k 1 |
l |
k 1 |
|
При парной перестановке вершин A и B могут исчезнуть только пересечения ребер, инцидентных этим вершинам, а число пересечений ребер, инцидентных неподвижным вершинам, не изменяется.
Пусть в некотором графе ребра, инцидентные вершине A, имеют следующее число пересечений с остальными ребрами графа:
n |
|
n 1 |
|
n |
|
SA |
|
|
|
p[(A, j);(k,l)]mA jmkl, где j |
B |
j |
1 k 1 |
l k 1 |
|
||
Аналогично, для вершины B |
|
||||
n |
|
n 1 |
|
n |
|
SB |
|
|
|
p[(B, j);(k,l)]mB j mkl, где j |
A |
j |
1 |
k 1 |
l |
k 1 |
|
После перестановки местами вершин A и B число пересечений изменится и станет равным:
|
n |
n 1 |
|
n |
|
|
|
|
|
S'A |
|
|
|
|
p[(A, j); (k, l)]mB jmkl, где j |
B . |
|||
j |
1 |
k 1 |
l |
k |
1 |
|
|
|
|
n |
n 1 |
|
n |
|
|
|
|
|
|
S' |
|
|
|
|
p[( |
, j);(k, l)]m |
m |
где j |
A |
B |
|
|
|
|
B |
A j |
kl, |
|
|
j |
1 |
k 1 |
l |
k |
1 |
|
|
|
|
Тогда изменение числа пересечений в результате перестановки вершин A и B
выразится формулой :
|
|
|
S |
AB |
(S |
S ) |
(S ' |
S ' ) |
|
|
|
|
|
A B |
A |
B |
|
n |
n 1 |
|
n |
|
|
|
|
|
|
|
|
{p[(A, j);(k, l)] |
p[(B, j);(k, l)]} |
(mA j mB j ) mkl, где j A, j B |
|||
j 1 |
k 1 |
l |
k 1 |
|
|
|
|
|
Если SAB > 0, то перестановка вершин A и B целесообразна, так как ведет к уменьшению числа пересечений.
Определить наличие пересечений p[(i,j);(k,l)] между ребрами (i,j) и (k,l) можно следующим образом в соответствии с рис. 5.3, 5.4
Ребра А1А2 и В1В2 являются отрезками прямых линий. Прямая линия описывается уравнением /8/:
y = kx + b.
Прямая, на которой лежит отрезок А1А2 описывается уравнением :
y = a1x+b1, где a |
yA1 |
yA2 |
, b |
y |
a x |
|
|
|
A1 |
||||
1 |
xA1 |
1 |
A1 |
1 |
||
|
xA2 |
|
|
|
Аналогично для В1В2:
63
y = a2x+b2, где a |
|
yB1 |
yB2 |
, b |
|
y |
a |
x |
2 |
|
|
2 |
|||||
|
xB1 |
xB 2 |
B1 |
|
2 B1 |
|||
|
|
|
|
|
|
Точка Z пересечения этих прямых имеет координаты :
x* |
b2 |
b1 |
; y* |
a1b2 |
a2b1 |
; |
|
|
|
|
|||
|
a1 |
a2 |
a1 |
a2 |
Необходимо далее определить, принадлежит ли точка Z(x*,y*) обоим отрезкам А1А2, В1В2 в соответствии с рис. 5.3.
y |
y |
B1 |
B1 |
A2 |
A2 |
Z |
B2
Z |
B2 |
|
A1 |
A1 |
|
0 |
x |
0 |
x |
|
|
|
|
|
Рис. 5.3. Пересечение ребер. |
Рис. 5.4. Область пересечения |
|
|
Если точка Z принадлежит заштрихованной области, значит она принадлежит |
||
обоим отрезкам : |
|
|
|
|
Z [A1,A2], Z |
[B1,B2], |
|
|
следовательно является точкой пересечения отрезков (A1,A2), (В1,В2), т.е. |
|
|
|
Z = (A1,A2) |
(B1,B2), |
|
Это значит, что xmin < x* < xmax, ymin < y* < ymax, для каждого отрезка, где
хmin – большее значение из двух минимальных значений координаты х отрезков А1А2 и В1В2;
ymin – большее значение из двух минимальных значений координаты y отрезков А1А2 и В1В2;
хmax – меньшее значение из двух максимальных значений координат х отрезков А1А2 и В1В2;
ymax – меньшее значение из двух максимальных значений координат y отрезков А1А2 и В1В2.
64
Выполнение этого условия равноценно тому, что расстояние от обоих концов каждого отрезка до точки пересечения прямых меньше длины отрезка. Этот способ
определения принадлежности точки пересечения отрезкам А1А2 |
и В1В2 был реализован в |
|||||||||||||||||||||||||
программе. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Кроме такого общего случая расположения прямых на плоскости относительно |
||||||||||||||||||||||||||
координатных осей, возможны частные случаи : |
y |
A1 |
|
|||||||||||||||||||||||
1. xA1 = xA2, xB1 |
xB2; (рис. 5.5) |
|
|
|
|
|
B1 |
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|||||||||||||||||||
Тогда x* = xA1; y* = a2x*+b2, |
|
|
|
|
|
|
|
|
|
|||||||||||||||||
где a2 |
|
|
yB1 |
yB2 |
|
, |
b2 |
yB1 |
a2 xB1 |
|
|
B2 |
||||||||||||||
|
|
xB1 |
xB 2 |
|
A2 |
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис. 5.5. |
x |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
2. xB1 = xB2, xA1 |
xA2; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
Тогда x* = xB1; y* = a1x*+b1, |
|
|
|
|
|
|
|
|
|
|||||||||||||||||
где a |
|
|
yA1 |
yA2 |
, |
|
b |
1 |
y |
|
a x |
A1 |
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
1 |
|
xA1 |
xA2 |
|
|
|
A1 |
|
1 |
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
3. yA1 = yA2, yB1 |
yB2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
Тогда y* = yA1; x* |
|
y * |
b2 |
|
; |
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
a2 |
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
где a |
|
|
yB1 |
yB2 |
, |
b |
|
y |
|
a |
|
x |
|
|
|
|||||||||||
2 |
|
|
|
|
|
2 |
|
2 |
|
|
|
|||||||||||||||
|
|
xB1 |
xB 2 |
|
|
|
|
B1 |
|
|
|
B1 |
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
4. yВ1 = yВ2, yA1 |
yA2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
Тогда y* = yB1; x* |
|
y * |
b1 |
; |
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a1 |
|
|
|
|
|
|
|
|
|
|||
где a |
|
yA1 |
yA2 |
, b |
|
|
|
y |
|
a x |
|
|
|
|
|
|||||||||||
|
|
|
|
|
1 |
|
A1 |
|
|
|
||||||||||||||||
1 |
xA1 |
xA2 |
|
|
A1 |
|
1 |
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5.xA1 = xA2,
,тогда x* = xA1, y* = yB1
yB1 = yB2
6.xB1 = xB2,
,тогда x* = xB1, y* = yA1
yA1 = yA2
7.xA1 = xA2,
xB1 = xB2 , тогда пересечение отсутствует
xA1 xB1
65
8.yA1 = yA2,
yB1 = yB2 , тогда пересечение отсутствует
yA1 yB1
9.к1 = к2,
,тогда пересечение отсутствует (рис. 5.6)
b1 b2
10.xA1 = xA2, тогда оба отрезка находятся на xB1 = xB2, одной вертикальной прямой
xA1 = xB1 |
(рис 5.7) |
11.yA1 = yA2, тогда оба отрезка находятся на yB1 = yB2, одной горизонтальной прямой
yA1 = yB1
12.к1 = к2,
,тогда оба отрезка находятся на одной наклонной прямой (рис. 5.8)
b1 = b2
|
|
|
|
|
|
y |
B2 |
|
|
|
|
|
|
|
|
|
|
y |
|
A1 |
y |
B2 |
|
|
A2 |
|
|
|
B1 |
|
|
|
|
||
|
|
|
|
|
|
|
||
|
|
|
|
|
|
B1 |
|
|
|
|
|
|
A2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A2 |
|
|
|
|
|
|
|
b1 |
|
|
|
B1 |
|
b1 |
A1 |
|
|
|
|
|
|
|
|||
b2 |
B2 |
|
|
|
|
|
|
|
|
|
|
A1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис. 5.6. |
|
x |
Рис. 5.7. |
x |
|
Рис. 5.8. |
x |
Для случаев 10, 11, 12, когда оба отрезка находятся на одной прямой, они могут иметь общие точки или не иметь их. Если отрезки имеют более одной общей точки, то будем считать отрезки условно пересекающимися. В таком случае при минимизации числа пересечений будет минимизироваться также число условнопересекающихся отрезков, сто соответствует требованию: при разработке печатных плат желательно иметь минимальное количество случаев наложения проводников друг на друга.
Для определения прохождения одного отрезка по другому с наличием более одной общей точки, кроме указанных в пунктах 10, 11, 12 условий необходимо выполнение следующего условия: расстояние между самой дальней точкой одного отрезка и самой дальней точкой другого отрезка должно быть меньше суммы длин этих отрезков.
Это условие выражается следующим неравенством:
dmax < dA1A2 + dB1B2,
66
где dmax - расстояние между самой дальней точкой одного отрезка и самой дальней точкой другого отрезка;
dA1A2 – длина отрезка А1А2; dB1B2 – длина отрезка B1B2.
Длины отрезков вычисляются по формуле: d = |xi - xj| + |yi - yj|
Все эти условия и ограничения были реализованы программно для оптимизации размещения элементов на коммутационном поле с минимизацией числа пересечений.
В качестве примера решения задачи минимизации числа пересечений при оптимизации размещения модулей на коммутационном поле с помощью ПЭВМ рассмотрим следующий.
Исходные данные:
количество модулей = 10
схема соединений представлена матрицей смежности (табл. 5.2)
координаты начального размещения модулей представлены в табл. 5.3
На рис. 5.9 показана схема соединений модулей, расположенных в исходных (до оптимизации) позициях с числом пересечений 129.
|
Табл. 5.2. Матрица смежности. |
|
|
|
Табл. 5.3 |
Табл. 5.4 |
|
||||||||||
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
x y |
N x y |
||||
1 |
|
0 |
4 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
|
5 |
4 |
1 |
5 |
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
4 |
0 |
1 |
4 |
1 |
1 |
0 |
0 |
0 |
0 |
|
1 |
3 |
2 |
6 |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
|
5 |
2 |
3 |
5 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
0 |
4 |
1 |
0 |
1 |
0 |
3 |
0 |
1 |
0 |
|
3 |
3 |
4 |
6 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
|
6 |
1 |
5 |
3 |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
|
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
3 |
|
6 |
3 |
6 |
2 |
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
|
0 |
0 |
1 |
3 |
0 |
0 |
0 |
4 |
1 |
0 |
|
1 |
1 |
7 |
3 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8 |
|
0 |
0 |
0 |
0 |
1 |
1 |
4 |
0 |
1 |
1 |
|
2 |
4 |
8 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9 |
|
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
|
3 |
2 |
9 |
3 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10 |
|
0 |
0 |
0 |
0 |
1 |
3 |
0 |
1 |
1 |
0 |
|
3 |
1 |
10 |
1 |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
В результате решения этой задачи с помощью программы, реализующей алгоритм парных перестановок, получили новое (оптимальное) размещение модулей,
указанное в табл. 5.4, с числом пересечений, равным 10 (локальный минимум; глобальный
67
минимум, как будет показано в следующем разделе, равен 6). До оптимизации число пересечений было равно 129, то есть число пересечений уменьшилось после оптимизации почти в 13 раз. Схема соединений модулей, расположенных в позициях, после оптимизации показана на рис. 5.10. На рис. 5.9 и 5.10 цифра у линии показывает число соединений между модулями. Цифра 1 не проставляется.
5.2. Исследование зависимости эффективности алгоритма парных перестановок от
исходных начальных размещений и способы повышения его эффективности
Одним из методов оптимизации размещения элементов с минимизацией числа пересечений является алгоритм парных перестановок /1,2/. Согласно этому алгоритму,
сначала все элементы схемы произвольным образом размещаются по заданному количеству установочных позиций, а затем производятся перестановки тех пар элементов,
находящихся в разных позициях, которые дают уменьшение числа пересечений трасс. В
результате таких перестановок достигается локальный минимум. Близость его к глобальному минимуму, т.е. степень оптимизации, существенно зависит от исходного начального (обычно произвольного) размещения элементов в позициях. В связи с этим целесообразно исследовать зависимость степени оптимизации от начальных размещений.
Для этого необходимо разработать программу, реализующую алгоритм парных перестановок с использованием большого количества начальных размещений. Для каждого начального размещения должна быть проведена своя оптимизация. Для создания большого количества начальных размещений можно использовать функцию рандомизации, включив эту функцию в программу. Для облегчения обработки статистических данных в программе следует предусмотреть вывод результатов оптимизации в порядке уменьшения степени оптимизации с указанием количества появлений каждого оптимума. Отдельно вывести наилучший оптимум с указанием размещения элементов по позициям. Для оценки степени оптимизации необходимо сравнить оптимумы между собой.
Поставленные задачи были нами решены. Была разработана программа оптимального размещения элементов с получением большого количества исходных начальных размещений методом рандомизации.
Y |
|
|
|
4 |
8 |
4 |
1 |
|
|
|
3 |
2 |
4 |
4 |
6 |
|
|
|
|
3
68
Y |
|
|
|
|
4 |
4 |
|
2 |
|
|
4 |
3 |
4 |
3 |
2 |
|
9 |
|
3 |
|
1 |
7 |
8 |
|
|
4 |
1 |
5 |
6 |
3
10 |
0 |
1 |
2 |
3 |
4 |
5 |
X |
Рис. 5.10. Схема соединений модулей, расположенных в позициях после оптимизации (количество пересечений 10).
69
Исследования проводились на различных схемах соединений с различным расположением установочных позиций для элементов с использованием 500 - 5000
исходных начальных размещений для каждой схемы.
Из многих рассмотренных примеров приведем следующий.
Исходные данные:
количеcтво элементов = 10;
количеcтво исходных начальных размещений: 500;
схема соединений представлена матрицей смежности (табл. 5.2)
координаты начального размещения модулей представлены в табл. 5.3
На рис. 5.9 показана схема соединений модулей, расположенных в исходных (до оптимизации) позициях с числом пересечений 129.
Результаты решения задачи приведены в табл. 5.5.
Табл. 5.5. Результаты эксперимента и их обработка
Номер |
Значение |
Количество |
Вероятность Pi |
Удаление |
Суммарная |
миним |
минимума |
появлений |
Появления |
минимума от |
вероятность |
ума |
числа |
минимума |
минимума |
глобального , |
Pi |
|
пересечений |
|
|
% |
|
|
|
|
|
|
|
1 |
6 |
14 |
0,028 |
0 |
0,028 |
|
|
|
|
|
|
2 |
7 |
22 |
0,044 |
16,6 |
0,072 |
|
|
|
|
|
|
3 |
8 |
89 |
0,178 |
33,3 |
0,250 |
|
|
|
|
|
|
4 |
9 |
12 |
0,024 |
50,0 |
0,274 |
|
|
|
|
|
|
5 |
10 |
43 |
0,086 |
66,6 |
0,360 |
|
|
|
|
|
|
6 |
11 |
31 |
0,062 |
83,3 |
0,422 |
|
|
|
|
|
|
7 |
12 |
22 |
0,044 |
100,0 |
0,466 |
|
|
|
|
|
|
8 |
13 |
40 |
0,080 |
116,6 |
0,546 |
|
|
|
|
|
|
9 |
14 |
65 |
0,130 |
133,3 |
0,676 |
|
|
|
|
|
|
10 |
15 |
39 |
0,078 |
150,0 |
0,754 |
|
|
|
|
|
|
11 |
16 |
18 |
0,036 |
166,6 |
0,790 |
|
|
|
|
|
|
12 |
17 |
29 |
0,058 |
183,3 |
0,848 |
|
|
|
|
|
|
70
13 |
18 |
11 |
0,022 |
200,0 |
0,870 |
|
|
|
|
|
|
14 |
19 |
25 |
0,050 |
216,6 |
0,920 |
|
|
|
|
|
|
15 |
20 |
7 |
0,014 |
233,3 |
0,934 |
|
|
|
|
|
|
16 |
21 |
12 |
0,024 |
250,0 |
0,958 |
|
|
|
|
|
|
17 |
22 |
3 |
0,006 |
266,6 |
0,964 |
|
|
|
|
|
|
18 |
23 |
2 |
0,004 |
283,3 |
0,968 |
|
|
|
|
|
|
19 |
24 |
5 |
0,010 |
300,0 |
0,978 |
|
|
|
|
|
|
20 |
25 |
4 |
0,008 |
316,6 |
0,986 |
|
|
|
|
|
|
21 |
26 |
3 |
0,006 |
333,3 |
0,992 |
|
|
|
|
|
|
22 |
27 |
2 |
0,004 |
350,0 |
0,996 |
|
|
|
|
|
|
23 |
29 |
1 |
0,002 |
366,6 |
0,998 |
|
|
|
|
|
|
24 |
32 |
1 |
0,002 |
383,3 |
1,000 |
|
|
|
|
|
|
Особенности результатов решения.
1) При оптимизации любого исходного начального размещения модулей число пересечений уменьшается по сравнению с неоптимизированным в несколько раз. В нашем примере число пересечений уменьшилось со 129 до 6 (глобальный минимум), то есть в
21,5 раза; схема соединений для наилучшего размещения представлена на рис. 5.11.
2) Степень оптимизации, т.е. значение минимума пересечений, в значительной степени зависит от начального размещения элементов в установочных позициях (рис.
5.12).
3) Значение суммарной вероятности |
Pi в зависимости от величины |
η Wi min - Wo min 100 %, показывающей насколько процентов полученный результат
Wo min
оптимизации отличается от глобального, монотонно возрастает, асимптотически приближаясь к единице при значениях , равных 290-300 % (рис. 5.13). По этому рисунку можно определить суммарную вероятность появления результата оптимизации,
отличающегося от глобального на заданное значение в процентах. Суммарная вероятность Pi - это сумма вероятностей i-го и всех предыдущих (лучших) минимумов.
Y |
|
|
4 |
|
6 |
|
|
3 |
3 |
10 |
5 |
2 |
9 |
1 |
4
2 |
3 |
4 |
|