<<
>>

Проблемная формулировка, термины и обозначения

Одной из важнейших задач автоматизированного монтажно­коммутационного проектирования является задача размещения элементов на коммутационном поле (КП). Именно размещение во многом определяет качество последующей трассировки. В су­ществующих алгоритмах [7.1-7.4], с одной стороны, связь между этими задачами недостаточно глубока, с другой стороны, полу­чаемые решения, с точки зрения их оптимальности, как правило, неудовлетворительны. Необходимость повышения качества про­ектирования требует поиска новых путей и подходов к решению задач размещения.

Процесс поиска решения можно представить как динамиче­скую процедуру, в которой последовательно, на каждом шаге, в соответствии со сложившейся ситуацией осуществляются опре­деленные действия: для конструктивных алгоритмов — выбор позиции и элемента, для итерационных — выбор перестановки (парной или групповой) [7.5, 7.6].

Основными факторами, в соответствии с которыми классифи­цируются существующие алгоритмы, служат постановка задачи размещения и метод поиска решений.

Характеристиками, определяющими суть постановки задачи размещения, являются:

— модель представления размещаемых (конструктивных) эле­ментов как геометрических объектов;

— модель монтажного пространства (пространство позиций);

— модель представления электрической принципиальной схе­мы;

— характер целевой функции для оценки размещения [7.7].

Чаще всего размещаемые эле­менты рассматриваются как точ­ки (вершины). Пространство по­зиций представляется в виде регулярной структуры (рис. 7.1). Для каждой позиции заданы ко­ординаты. Расстояние между по­зициями обеспечивает размеще­ния элементов в любой комбина­ции без наложения друг на друга и с учетом конструктивных огра­ничений (требования электромаг­нитной и тепловой совместимости

Пусть дано множество элементов A = {αj∙ | j = 1,2,...,n} и множество позиций П = {щ | i = 1,2,..., c} на коммутационном поле.

Для размещения всех элементов необходимо выполнение условия c ~≥ п. Произвольное размещение элементов в позициях представляет собой перестановку P = p( 1), p(2),..., p(i),..., p(c), где p(i) задает номер элемента, который назначен в позицию щ. В зависимости от выбранного критерия для оценки результатов размещения вводится целевая функция F(P).

Таким образом, задача размещения состоит в отыскании оп­тимального значения функции F на множестве перестановок P.

Основными известными критериями при размещении [7.8, 7.9] являются: суммарная длина связи, длина самой длинной связи, число возможных пересечений, число изгибов соединений,площадь кристалла и др.

В качестве модели схемы используется граф G = (X, Y) или гиперграф H = (X, E), где X = xi| i = 1,2,...,n} — множество вершин, моделирующих элементы, a U = {uj| j = 1,2,..., l}— множество ребер. Вершинах^ связана с xj∙ ребром, если соответ­ствующие элементы связаны соединением.

E = {ej∙ | ej C X, j = 1,2,..., m}— множество гиперребер, моделирующих цепи, связывающие элементы. Граф адекватно моделирует двухтерминальные соединения, а гиперграф — мно­готерминальные.

Расстояние между двумя вершинами с координатами (xi, yi) и (xj∙, yj∙) определяется по формуле

dij — ∖xi y^+xj yj

В качестве оценки j длины цепи tj∙, моделируемой гиперреб­ром ej∙, используются:

— длина минимального связывающего дерева, построенного на множестве вершин ej∙ C X;

— длина звездного графа, ребра которого инцидентны верши­нам ej∙ C X ,а корневая вершина помещена в центре «тяже­сти» множества вершин ej∙;

— длина полупериметра прямоугольника, описывающего мно­жество вершин ej∙;

— суммарная длина ребер полного графа, построенного на мно­жестве ej∙.

С учетом этого критерий оптимизации имеет вид

Для полного учета связей между задачами размещения и трассировки эффективны алгоритмы, основанные на оценках числа цепей, пересекающих заданные линии коммутационного поля. Эти линии могут быть либо прямыми, пересекающими все коммутационное поле, либо замкнутыми и ограничивающими некоторую область [7.10].

Пусть на коммутационное поле наложена опорная сетка (см. рис. 7.1).

Таким образом, имеется множество ребер сетки G = {gi| i = = 1,2,...,ng}, разбивающих коммутационное поле на дискрет­ные площадки (дискреты). Будем считать, что позиции пірас­полагаются внутри дискретов. В качестве исходных данных для коммутационного поля задается множество D = {di| i = = 1,2,...,nd}, где di— пропускная способность ребра gi, т. е. число цепей (трасс), которые могут ее пересечь. Значенияdi определяются размерами ребра и ограничениями на прокладку соединений.

Назовем цикл Lk, составленный из ребер сетки и ограничи­вающий некоторую область, границей области. Под пропускной способностью PSk границы Lkбудем понимать суммарную про­пускную способность ребер сетки, входящих в состав Lk, т. е. PSk = ∑ di (∀i | gi ∈Lk).

Пусть Нк— число цепей, связывающих элементы, располо­женные внутри области, ограниченной Lk, с элементами, распо­ложенными вне этой области. Введем характеристику границы области, ограниченной контуром:

Чем большее значение имеет ук, тем легче осуществить проклад­ку связей через границу Lk.

Пусть задано некоторое множество областей, для которых определено множество границ L= {Lk| k = 1,2,..., kL}.

В качестве критерия оптимизации используется величина FF = γmin. Задача оптимизации состоит в максимизации значе­ния γmιn.

Известно, что при одной и той же площади (а, следовательно, при одном и том же числе позиций) наименьшую длину имеет контур квадратной формы. Следовательно, такая граница будет наиболее «чувствительна» к пересекающим ее цепям, так как для одного и того же множества элементов PSk будет иметь наименьшую оценку, а следовательно, и γs. Поэтому в работе используется система контуров, имеющих квадратную форму или, по возможности, близкую к ней.

Формирование множества контуров (границ) производится следующим образом [7.Ю]. Пусть имеется коммутационное поле размером C ? D, C ≤ D. Единицей измерения служит длина одного ребра опорной сетки (рис. 7.1). Выбираем контур с раз­мерами c ? c, причем c ≤ C. Сначала он помещается в левый угол коммутационного поля, а затем путем сканирования (по­следовательного сдвига на один шаг вправо или вниз) форми­руется набор контуров. Число таких контуров определяется так: пк= (C — c + 1) ? (d— c + 1).

Для того чтобы контролировать все ребра giопорной сетки, т. е. чтобы они все входили в составы контуров опорного набора, необходимо соблюдение правила: для КП с размерами C ? D, C ≤ D, необходимо чтобы c ≤ C/2.

Чем больше размер c, т. е. чем ближе c к C/2, тем меньше контуров в составе множества контуров L. С другой стороны, контур, у которого c близок к C/2, наиболее чувствителен к плотности размещения. Это связано с тем, что на единицу длины контура приходится наибольшее число элементов, ограниченных этим контуром.

Существует большое число алгоритмов размещения. Все ал­горитмы можно условно разделить на две группы: непрерывно­дискретные и дискретные. К первой группе относятся алгоритмы, основанные на построении механических аналогов, градиентные методы, методы последовательного сдвига и т. д. Ко второй отно-

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

Приведенные в работах [7.1-7.4] обзоры, сравнение и анализ разработанных алгоритмов размещения (последовательных, ите­рационных и т. д.) показывает, что для создания эффективного алгоритма размещения, отвечающего современным требованиям, необходимы новые технологии и подходы. Среди разработанных в последние годы алгоритмов размещения наилучшие результа­ты показали алгоритмы, построенные на основе моделирования отжига [7.11-7.13] и генетического поиска [7.14-7.16]. В книге описывается технология, принципы и механизмы решения задачи размещения, основанные на моделировании процессов эволюци­онной и альтернативной коллективной адаптации [7.17].

7.2.

<< | >>
Источник: Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с.. 2006

Еще по теме Проблемная формулировка, термины и обозначения:

  1. ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ
  2. Основные обозначения и соотношения, используемые в работе
  3. 1. Понятие государственного управления
  4. § 1. Генезис принципа зависимости в теории и международной практике
  5. 1. Понятие и правовое положение органа исполнительной власти
  6. Приложение 8.
  7. Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с., 2006
  8. СОДЕРЖАНИЕ
  9. §1.4 Психологические особенности формирования профессионально-личностной компетентности менеджера коммерческой организации
  10. 1.4.1 Интегральная геометрическая характеристика формы области (коэффициент формы)
  11. 2.15 Выбор аппроксимирующей функции для пластинок с жестко защемленным и шарнирно опертым контуром
  12. § 2. Сущность производства в суде надзорной инстанции
  13. § 5. Основания к отмене или изменению судебных постановлений, вступивших в законную силу
  14. Индикаторы сбалансированного развития системы персональных финансов
  15. Выводы по первой главе:
  16. 1. Производство по делам об административных правонарушениях: общая характеристика
  17. 49. Договор перевозки пассажиров и багажа.
  18. 3. Классификация органов исполнительной власти. Факторы, влияющие на построение системы органов
  19. 3. Основы административно-правового статуса граждан