АЛГОРИТМ ОБРАТНОГО РАЗМЕЩЕНИЯ

Алгоритм включает такую последовательность действий [1, 3].

1. Вычислить матрицу расстояний D между позициями на плате. Элементы матрицы d_ij определяются по формуле:

d_ij = |x_i - x_j| + |y_i - y_j|.

2. Для каждой строки матрицы D определить суммарное значение элементов d_ij, стоящих в этой строке.

3. Для каждой строки матрицы R определить суммарное значение элементов r_ij, стоящих в этой строке. Полученные значения – локальные степени элементов.

4. Упорядочить элементы t₁ по возрастанию характеристики r_i: t_z₁, t_z₂, …, t₂_n.

5. Упорядочить позиции l_j по убыванию характеристики d_j : l_d₁, l_d₂, …, l_dn.

6. Выполнить размещение элементов в позиции p(t_k) = l_k, где k = 1, …, n.

7. Подсчитать суммарную длину по формуле (2.1).

Конец.

Ручной расчет.

Граф электрической схемы описывается матрицей связности R

1 2 3 4 5 6

1 0 2 0 0 0 1 3

2 2 0 1 0 2 0 5

3 0 1 0 1 1 0 3

4 0 0 1 0 3 0 4

5 0 2 1 3 0 0 6

6 1 0 0 0 0 0 1

1. Найдем матрицу расстоянийпо формуле:

d_ij = |x_i - x_j| + |y_i - y_j|.

1 2 3 4 5 6

1 0 1 4 3 4 5 17

2 1 0 3 2 3 4 13

3 4 3 0 1 2 3 13

4 3 2 1 0 1 2 9

5 4 3 2 1 0 1 11

6 5 4 3 2 1 0 5

Упорядочим по возрастанию R суммарное в скобках номер элемента.

1(6), 3(3), 3(1), 4(4), 5(2), 6(5)

Упорядочим D суммарное в скобках номер позиции.

17(1), 15(6), 13(3), 13(2), 11(5), 9(4)

Составим матрицу размещения Р для установленных в позиции элементов

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

7 7

L = (1/2) S S а _ij = 23.

_j=1 _j=1

Сравним результаты с результатами полученными программой

Рис. 8 Результат обратного размещения

Результат: Как мы видим данные алгоритмы позволяют достаточно точно размещать элементы РЭС .Разные алгоритмы выдают разную суммарную длин,поэтому для эффективности разумно использовать все три метода. Наименьшую длину показал алгоритм предварительного размещения она равна 18-ти.

Вывод: исследовали эффективность алгоритмов размещения элементов РЭС в коммутационном пространстве, освоили особенности алгоритмизации и программирования задачи размещения на ПЭВМ, приобрели навыки построения математических моделей монтажного пространства и схем соединения модулей, реализации и исследования их при решении задачи размещения с применением САПР.

Лабораторная работа №4

ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ ИТЕРАЦИОННЫХ

АЛГОРИТМОВ РАЗМЕЩЕНИЯ

Цель работы – исследовать эффективность итерационных алгоритмов размещения конструктивных элементов РЭС в коммутационном пространстве; освоить особенности алгоритмизации и программирования задач улучшения размещения на ПВЭМ итерационными методами.

ИТЕРАЦИОННЫЕ АЛГОРИТМЫ РАЗМЕЩЕНИЯ

Алгоритмы итерационного типа относятся к группе эвристических алгоритмов [1] и основаны на парной или групповой перестановках компонентов [2]. Они требуют начального размещения и обычно используются для улучшения результатов исходного размещения. При этом результат размещения зависит от начального размещения. Применяются итерационные алгоритмы для решения задач размещения с различными критериями оптимизации и в большинстве случаев приводят к получению локальных экстремумов целевой функции F(X). Они требуют больших затрат машинного времени.

Алгоритм парных перестановок

Сущность алгоритма парных перестановок заключается в последователь-ном целесообразном улучшении произвольного начального размещения элемен-тов на плате по выбранному критерию путем парных перестановок [2]. С этой целью на каждой итерации алгоритма производится вычисление приращений суммарной длины всех связей для всевозможных n ( n -1)/2 парных перестановок n элементов. Затем из всего множества перестановок, дающих отрицательные приращения, выбирается подмножество, которое удовлетворяет следующим требованиям:

позволяет максимально уменьшить длину всех связей;

подмножество образует лишь независимые перестановки, то есть такие парные перестановки, в которые входят элементы, не связанные с элементами других переставляемых пар.

Далее выполняются перестановки выделенных таким образом пар элементов, и осуществляется переход к следующей итерации.

Рчной расчет

1) Используем матрицу расстояний D и матрицу связности R из предыдущей работы. Для примера возьмем матрицы последовательного алгоритма размещения.

2) Вычислим матрицу приращений L DL = 2 r _ij d _ij – å (r _ij – r _ij) (d _ij – d _ij) .

1 2 3 4 5 6

1 0 4 0 7 4 -6

2 4 0 -2 2 -5 -4

3 0 -2 0 3 0 -2

4 7 2 3 0 2 0

5 4 -5 0 2 0 1

6 -6 -4 -2 0 1 0

3) Проверить наличие отрицательных элементов в матрице приращений. Среди множества отрицательных элементов матрицы L находим минимальный Δl _ij. Если их несколько, тот берем любой. Осуществляем перестановку строк и столбцов с номерами i и j матрицы R. Изменяем Матрицу R. Получим

1 2 3 4 5 6

1 0 0 0 0 0 1

2 0 0 1 2 0 2

3 0 1 0 1 1 0

4 0 2 1 0 3 0

5 0 0 1 3 0 0

6 1 2 0 0 0 0

Меняем местами элементы в позициях 1 и 6. Результат вычисления прикладной программы САПР можно увидеть на рисунке 4. Суммарная длина равна 26.

Результат: Как мы видим даны тип подстановки не изменил конечного результата, это означает что алгоритм, использованный для размещения произвел точный расчет. Однако метод парных перестановок может существенно уменьшить суммарную длину при других условиях.

Вывод:

Достоинствами алгоритма парных перестановок являются: возможность значительного улучшения начального решения, простота и наглядность.

К недостаткам следует отнести:

а) значительные затраты машинного времени;

б) возможность получения большого количества решений, если несколько пар элементов имеют одинаковые минимальные значения Δl_ij. В этом случае переставляться могут элементы любой пары;

в) алгоритм уменьшает суммарную длину соединений, но не приводит её к минимальной. Объясняется это тем, что уменьшение длины происходит только между двумя элементами. В то же время между другими элементами длина может увеличиваться;

г) возможен случай, когда перестановка отдельных элементов не приводит к уменьшению суммарной длины, хотя ее можно сократить групповой перестановкой элементов (парами, тройками и т.д.);

д) результат работы алгоритма зависит от первоначального размещения элементов в монтажном пространстве.

Для получения более точных результатов целесообразно сочетать быстрый обратный алгоритм с улучшающим размещение итерационным.

Среди итерационных алгоритмов наиболее эффективны методы, основанные на парных перестановках элементов, при этом оказывается нецелесообразным рассматривать перестановки элементов в усеченных окрестностях, что приводит к существенным сокращениям времени при той же точности результата. Алгоритмы парных перестановок позволяют уменьшить длину межсоединений от 1% до 50% в зависимости от начального размещения. Наибольшая скорость уменьшения длины соединений наблюдается на первых итерациях, монотонно уменьшаясь к значениям, близким к 1% при числе итераций К>5.

Важной характеристикой алгоритма парных перестановок является число успешных обменов среди общего числа просмотренных. Этот коэффициент минимален при использовании всех возможных n(n-1)/2 перестановок на каждой итерации и не превышает 5%. При усечении окрестности исследуемых перестановок, например, обмене лишь соседних элементов в «хорошем» начальном размещении, указанный коэффициент может достигать 50%.

ЛАБОРАТОРНАЯ РАБОТА № 5

Дата добавления: 2019-07-17; просмотров: 885; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 1 2 3 456 7 Следующая ⇒

Мы поможем в написании ваших работ!