Материал: Лабораторная работа№ 3, 4 Исследование алгоритмов размещения конструктивных элементов и итерационных алгоритмов

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

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

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

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

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

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

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

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

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

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

61

АЛГОРИТМ

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

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

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

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

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

формуле

к=1

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

7.Среди множества отрицательных элементов матрицы ΔL находим

мини-мальный Δl ij. Если их несколько, тот берем любой. Осуществляем пере-становку строк и столбцов с номерами i и j

матрицы R. Переходим к 2. Конец.

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

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

а) значительные затраты машинного времени; б) возможность получения большого количества решений, если несколько

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

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

62

между двумя элементами. В то же время между другими элементами длина может увеличиваться;

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

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

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

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

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

ПРИМЕР 4.1

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

Решение

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

63

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

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

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

Δl12 = 2r12∙d12 – [(r11-r21)(d11-d21) + (r12-r22)(d12-d22) + (r13-r23)(d13-d23) + (r14-r24)(d14- d24) = 2∙1∙2 – [(0-2)(0-1) + (2-0)(1-0) + (0-1)(2-1) + (3-0)(3-2)] =-2;

Δl13 = 2r13∙d13 – [(r11-r31)(d11-d31) + (r12-r32)(d12-d32) + (r13-r33)(d13-d33) + (r14-r34)(d14- d34) = 2∙0∙2 – [(0-0)(0-2) + (2-1)(1-1) + (0-0)(2-0) + (3-1)(3-1)] = – 4; и т.д.

Рис.4.1

64