Материал: Laboratornaya_rabota_3i4-n

9. Содержание отчета

9.1.Цель работы.

9.2.Сведение из теории. Задача размещения, ее математическая формули-ровка. Методы оценки алгоритмов размещения.

9.3.Принципиальные электрические схемы и схемы монтажного про-странства.

9.4.Математичесие модели схемы и монтажного пространства.

9.5.Условия размещения элементов.

9.6.Эскизы схем размещения модулей в монтажном пространстве (копии экрана).

9.7.Ручные размещения элементов по алгоритмам.

9.7.Сравнительные результаты и характеристики алгоритмов.

9.8.Рекомендации по применению алгоритмов.

9.9.Выводы.

10. Контрольные вопросы

1. Сформулируйте цели задачи размещения.

2. Математическая формулировка задачи размещения.

3. Назовите основные методы оценки эффективности алгоритмов размещения.

4. Каким образом можно оценить качество размещения элементов?

5. Назовите последовательность действий метода обратного размещения.

6. Назовите последовательность действий последовательного метода размещения.

7. Назовите последовательность действий предварительного метода размещения.

8. Поясните порядок работы с программами размещения.

9. Каким образом вводятся исходные данные для работы программ?

10. Назовите достоинства и недостатки изучаемых алгоритмов.

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

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

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

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

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

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

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

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

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

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

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

АЛГОРИТМ

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

d_ij =  (x_i – x_j)² + (y_i – y_j)² или (4.1)

d_ij = x_i – x_jy_i – y_j. (4.2)

2. Составить матрицу связей R между элементами. Элементы матрицы r_ij численно равны количеству проводников, соединяющих контакты элементов. Матрицу связей составляем в каждом цикле алгоритма.

В 1-м цикле используются данные матрицы связей начального размещения элементов, во 2-м в эту матрицу заносятся результаты перестановок, выполненных в 1-м цикле.

3. Вычислить матрицу геометрии А по формуле

A = (r _ij d _ij _n._n . (4.3)

4. Вычислить суммарную длину соединений L по формуле

n n

L (G) = ½  a _ij . (4.4)

i=1 j=1

5. Вычислить элементы матрицы приращений суммарной длины связей для всех возможных перестановок. Расчет элементов выполняем по формуле

n

L = 2 r _ij d _ij – r _ij – r _ijd _ij – d _ij (4.5)

к=1

6. Проверить наличие отрицательных элементов в матрице приращений. Если их нет, то идти к 8, иначе к 7.

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

Конец.

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

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

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

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

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

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

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

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

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

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

ПРИМЕР 4.1

В позиции коммутационного поля с координатами l₁=(1,1), l₂=(2,1), l₃=(3,1), l₄=(4,1) размещены четыре конструктивных элемента (рис.4.1). Схема соеди-нений элементов представлена графом (рис.4.2). Требуется по критерию мини-мума суммарной длины улучшить начальное размещение.

Решение

Вычислим матрицу расстояний D между позициями по формуле (4.2):

1 2 3 4

1 0 1 2 3

D =2 1 0 1 2

3 2 1 0 1

4 3 2 1 0 .

По графу (рис.4.2) электрической схемы составим матрицу связей R₀ между элементами

1 2 3 4

1 0 2 0 3

R₀ = 2 2 0 1 0

3 0 1 0 1

4 3 0 1 0 .

Вычислим длину соединений начального размещения

1 2 3 4

1 0 2 0 9

A₀ = 2 2 0 1 0

3 0 1 0 1 L₁=13.

4 9 0 1 0 .

Определим по формуле (4.5) элементы матрицы приращения:

Δl₁₂ = 2r₁₂∙d₁₂ – [(r₁₁-r₂₁)(d₁₁-d₂₁) + (r₁₂-r₂₂)(d₁₂-d₂₂) + (r₁₃-r₂₃)(d₁₃-d₂₃) + (r₁₄-r₂₄)(d₁₄-d₂₄) = 2∙1∙2 – [(0-2)(0-1) + (2-0)(1-0) + (0-1)(2-1) + (3-0)(3-2)] =-2;

Δl₁₃ = 2r₁₃∙d₁₃ – [(r₁₁-r₃₁)(d₁₁-d₃₁) + (r₁₂-r₃₂)(d₁₂-d₃₂) + (r₁₃-r₃₃)(d₁₃-d₃₃) + (r₁₄-r₃₄)(d₁₄-d₃₄) = 2∙0∙2 – [(0-0)(0-2) + (2-1)(1-1) + (0-0)(2-0) + (3-1)(3-1)] = – 4; и т.д.

1 2 3 4

1 0 -2 -4 3

ΔL₀ = 2 -2 0 3 -2

3 -4 3 0 -2

4 3 -2 -2 0 .

l₁ l₂ l₃ l₄

Рис.4.1

t₁ t₂

t₄ t₃

Рис.4.2

l₁ l₂ l₃ l₄

Рис. 4.3

Поскольку минимальный элемент Δl₁₃, переставим 1-е и 3-и строки и столбцы в матрице R₀, а конструктивные элементы 1-й и 3-й поменяем местами (см. рис. 4.3). Получим матрицу

3 2 1 4

3 0 1 0 1

R₁ = 2 1 0 2 0

1 0 2 0 3

4 1 0 3 0 .

По матрице геометрии

3 2 1 4

3 0 1 0 3

А₁ =2 1 0 2 0

1 0 2 0 3

4 3 0 3 0

определим длину соединений: L₁ = 9.

Снова вычислим матрицу приращения

3 2 1 4

3 0 1 4 4

ΔL₁ = 2 1 0 4 0

1 4 4 0 1

4 4 0 1 0 .

Все элементы матрицы ΔL₁ положительные. Следовательно, процесс пере-становки окончен, и полученный результат (рис.4.3) окончательный.

2. Домашнее задание

2.1. Ознакомится с итерационными методами решения задачи размещения конструктивных элементов РЭС.

2.2. Изучить алгоритм парных перестановок.

2.3. Подготовить данные к эксперименту.

2.4. Провести вручную улучшение размещения одного из узлов методом парных перестановок.

3. Порядок работы с программой «размещение» в режиме парных перестановок

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

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

- элементы, которые переставляются путём парных обменов;

- местоположение конструктивных элементов в монтажном пространстве по критерию минимальной суммарной длины соединений;

- суммарную длину соединений элементов, размещённых в заданные позиции монтажного пространства.

Запуск программы «Размещение» см. лабораторная работа №3.

Появится рабочее поле графического редактора «Размещение». Выбрать алгоритм с парными перестановками. После расчётов по алгоритму начального размещения (например, обратного размещения) (рис.4.4), следует трансляция о начале парных перестановок.

Рис.4.4

После нажатия клавиши Enter на экран выводится информация о размещенных элементах, матрицы приращений L и связности R. В нижней части экрана указывается суммарная длина соединений предыдущего размещения ЭРЭ и номера ЭРЭ участвующие в парном обмене (рис.4.5).

Рис.4.5

Рис.4.6

После того, как очередной расчёт матрицы приращений не обнаруживает ЭРЭ для перестановок, следует сообщение о том, что менять местами ничего не надо (рис.4.6).

Нажатием клавиши Enter на экран выводятся результат парных перестановок ЭРЭ и суммарная длина получившихся соединений (рис.4.7).

Рис.4.7

4. Задания к лабораторной работе

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

4.2. Начертить эскизы улучшенных размещений.

4.3. Результаты размещений оценить с точки зрения формальных крите-риев (минимальной суммарной длины соединений, равномерности рисунка платы, протяженности длинных трасс и т.д.) и с точки зрения требований к математическому обеспечению САПР.

4.4. Один из вариантов начального размещения (по указанию преподава-теля) улучшить путём ручного расчёта по методу парных перестановок.

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