Материал: Lab 4 Z Рбд-31

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ федеральное государственное бюджетное образовательное учреждения высшего образования «УЛЬЯНОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Радиотехнический факультет Кафедра «Проектирование и технология электронных средств»

Дисциплина: «Математическое обеспечение САПР»

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

«ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ ИТЕРАЦИОННЫХ АЛГОРИТМОВ РАЗМЕЩЕНИЯ»

Работу выполнил: Проверил: Студент группы Рбд-31 профессор Зарипов Т.Р. Мактас М.Я.

Ульяновск 2021

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

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%.

Практические решения:

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

Рис. 4.1. Коммутационное поле

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

D=

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

Рис. 4.2. Граф соединений.

построим матрицу связности R:

R₀=

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