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

Ульяновский государственный технический университет

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

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

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

Выполнил:                                                                                         Проверил:

Студент гр.Рд-32                                                                               преподаватель

Асташин А.Г.                                                                                    Мактас М.Я.

Ульяновск 2004

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

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 по формуле

nn

L (G) = ½ å å a _ij  .                                                (4.4)

i=1  j=1

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

n

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