РЕШЕНИЕ ЗАДАЧИ КОМПОНОВКИ В СИСТЕМАХ АВТОМАТИЗАЦИИ ПРОЕКТИРОВАНИЯ

GROUPING PROBLEM DECISION IN THE DESIGN AUTOMATION SYSTEMS

Oksana Melikhova

candidate of Science, assistant professor, assistant professor of the Southern Federal University,

Russia, Taganrog

АННОТАЦИЯ

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

ABSTRACT

The optimal grouping algorithm, based on the branch and bound algorithm, which is more exact according to the comparison with the familiar sequential and iterative grouping algorithms is considered in the paper. Given optimal grouping algorithm may be used for the decision of the wide spectrum of practical problems so as unification of the radio electronic equipment nodes, work distribution between executors, objects and connections allocation between them.

Ключевые слова: дискретное устройство; автоматизация проектирования; компоновка; теория гиперграфов; критерий оптимизации; минимальное разрезание гиперграфа.

Keywords: discrete device; design automation; grouping; hypergraphs theory; optimization test; hypergraph minimal cut.

Введение. Одной из перспективных областей применения и использования компьютеров является автоматизация управления и проектирования. Использование автоматизированных систем позволяет резко сократить сроки проектирования, существенно повысить качество разрабатываемых проектов и снизить затраты на проектирование. Трудно найти такие области практической деятельности, в которых не применяются или не могли бы применяться компьютеры. При создании современных систем автоматизации проектирования возникает необходимость перевода творческого процесса проектирования из полуинтуитивной области в область формальных, математически строго обоснованных решений. Эффективное использование математических методов в автоматизации проектирования является залогом создания качественных систем. Эти методы позволяют строить математические модели, адекватные объектам проектирования и использовать алгоритмы оптимальных преобразований моделей, с целью повышения качества проектируемых систем.

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

Постановка задачи. Формирование определенных групп элементов дискретного устройства осуществляется путем их компоновки. Это необходимо при отборе элементов электрической схемы, помещаемых в отдельную конструктивную единицу, при сборке конструктивных элементов низшего уровня в конструктивные элементы высшего уровня, при распределении оборудования (разногабаритных элементов) по цехам, при формировании целенаправленных коллективов людей и во многих других аналогичных ситуациях. Важнейшим критерием компоновки является оптимизация суммарного числа связей, проходящих между отдельными сформированными группами элементов. Эти связи будем называть разрываемыми. При компоновке под оптимизацией часто понимается минимизация, хотя известны задачи компоновки, в которых стремятся получить максимум таких связей, это зависит от конкретной задачи. Стремление уменьшить число разрываемых связей естественно, так как в электрических схемах это число определяет и количество контактов на разъеме и число проводников соединяющего кабеля, в производственной сфере оно может соответствовать числу межцеховых передач обрабатываемых объектов, числу транспортных магистралей, числу разбиений некоторых формальных коммуникаций и т.п. Уменьшение числа связей между группами элементов в значительной степени идентично увеличению «плотности» связей внутри каждой группы. Ограничениями при решении разбиения обычно являются: количество элементов в группах, наибольшее число связей, выходящих из данной группы, различные физические ограничения, вытекающие из природы компонуемых элементов [1,2]. Остановимся на решении задачи компоновки по критерию минимизации числа разрываемых связей, если количество элементов в компонируемых группах априорно заданы.

Рассмотрим алгоритм решения задачи компоновки, сведенный к задаче минимального разрезания гиперграфа, представляющего дискретное устройство, на части. Пусть задан гиперграф,  представляющий некоторое дискретное устройство. Компоновка элементов этого устройства соответствует разбиению множества  на классы  такие, что ,  и представляет собой разрезание гиперграфа , определяемое данным разбиением.

Множество всевозможных разбиений обозначим , причем

Пусть  – произвольное фиксированное разбиение. Определим для ребра  при разбиении  величину

                                            (1)

где

 если ,

 иначе.

Число  определяет количество частей, из которых выходит ребро  при разбиении .

Гиперграф  при разбиении  характеризуется величиной

                                        (2)

которая называется суммарным числом выходящих ребер при разбиении . Можно заметить, что величина  вдвое больше числа разрываемых ребер, поскольку каждое разрываемое ребро в формуле (1) учитывается дважды [2,3].

Задача компоновки состоит в отыскании такого разбиения  гиперграфа , при котором минимизируется значение .

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

Найдем оценку снизу возможного суммарного числа выходящих ребер гиперграфа  при разбиении . Будем полагать, что все рассматриваемые гиперграфы связные. В другом случае каждую компоненту связности гиперграфа будем рассматривать отдельно, так как она, по сути, представляет независимое дискретное устройство [2,4,5].

Подставим выражение (1) в (2). Получим

.                     (3)

В выражении (3) величина

                                       (4)

определяет число ребер, выходящих из части гиперграфа , порождаемой множеством  при разбиении . Множество таких ребер обозначим . Поскольку малое удаление всех ребер  из гиперграфа  приводит к отделению части гиперграфа, порождаемой вершинами , то есть к увеличению числа компонент связности гиперграфа , то множество  является реберным разбиением гиперграфа .

Значение величины  всегда больше или равно , где  – число ребер гиперграфа, образующих наименьшее реберное разбиение , то есть – наименьшее число ребер гиперграфа , удаление которых увеличивает количество компонент связности гиперграфа .

Исходя из определения величины  и выражений (3), (4), приходим к нижней оценке возможного суммарного числа выходящих ребер гиперграфа  в виде

.                                      (5)

Теперь покажем метод определения наименьшего разбиения  для гиперграфа . Наименьшее разбиение  находится как минимальное по мощности из всех минимальных реберных разбиений гиперграфа . Разбиение называется минимальным, если оно перестает быть разбиением при удалении из него, хотя бы одного ребра [2,6].

Справедлива следующая теорема.

Теорема 1. Если наименьшее реберное разбиение  для связного гиперграфа  содержит  ребер, то любая пара вершин в данном гиперграфе, по крайней мере, -сплетаема.

Покажем это. Вершины  гиперграфа  называются -сплетаемыми, если существует система из  цепей попарно без общих ребер с началом  и концом . При любом  отношение -сплетаемости вершин на множестве  есть эквивалентность. Если вершины  -сплетаемы, то для того, чтобы они оказались в разных компонентах связности, необходимо, чтобы реберное разбиение, разделяющее эти вершины, содержало в своем составе, по крайней мере,  ребер.

Пусть теперь в гиперграфе  имеется пара вершин  и  -сплетаемых, причем . По определению -сплетаемости вершин слабое удаление  ребер из гиперграфа  приведет к разделению вершин  и , то есть к увеличению числа компонент связности. Тогда  - число ребер наименьшего разбиения, то есть получили противоречие. Теорема доказана.

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

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

Модифицированный реберный граф  получается следующим образом. К графу  добавляются две вершины . Вершина  соединяется ребром  с вершиной , если в исходном гиперграфе  вершина  и ребро  инцидентны. Аналогично для вершины .

Нетрудно видеть, что задача определения минимального реберного разбиения в гиперграфе  между вершинами  однозначно сведена к задаче определения минимального вершинного разбиения в графе . Граф , представляющий собой ориентированный граф, преобразуется в сеть. Для этого вершины  принимаются за полюса сети, ребра, инцидентные вершине , заменяются дугами, направленными от вершины , а ребра, инцидентные вершине  – дугами, направленными к вершине . Каждое из оставшихся ребер  заменяется двумя противоположно направленными дугами. Всем дугам приписывается бесконечная пропускная способность. Каждая вершина  заменяется парой вершин  и дугой . Концы дуг, входящие в , переносятся в , а начала дуг, исходящих из , переносятся в . Дугам вида  приписывается пропускная способность, равная единице [2,7].

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

Рассмотрим основанный на методе ветвей и границ алгоритм разбиения множества  на такие классы , при которых значение целевой функции (2) минимально. Выражение (5) позволяет находить нижнюю границу возможного суммарного числа выходящих ребер гиперграфа  для всего множества  решений задачи разбиения. Необходимо получить оценки суммарного числа выходящих ребер для подмножеств  множества решений и способ нахождения таких подмножеств, называемый ветвлением дерева возможных решений.

Как уже отмечалось, число возможных решений, если порядок классов существен, априорно составляет . Пусть на каком-либо шаге алгоритма формируется класс , а классы  уже сформированы. Обозначим  множество вершин, уже вошедших в класс , а  – множество вершин, вошедших в классы  и в , то есть . Тогда  – вершины, не размещенные еще в каких-либо классах разбиения. Получаем подмножество  множества решений , содержащее  решений. Очевидно, что чем больше элементов содержит множество , тем меньше решений в . Таким образом, ветвление дерева возможных решений заключается в последовательном присоединении каждой вершины из  к классу  и, следовательно, к множеству . После заполнения множества  начинает формироваться множество  и так далее до получения множества . При этом не один из сформированных классов не удаляется из гиперграфа [1,2,6].

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

Найдем нижнюю оценку числа выходящих ребер для класса . Относительно вершин  сформируем множество ребер  следующим образом:

 – множество ребер, инцидентных вершинам из ;

 – множество ребер, инцидентных одновременно вершинам из  и вершинам из ;

 – множество ребер, инцидентных одновременно вершинам из  и вершинам из .

Из ребер множества  образуем множество  следующим образом.

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

Взаимно-однозначно сопоставим каждому ребру  число , причем . Тогда множеству  можно поставить во взаимно-однозначное соответствие невозрастающий ряд чисел

.

Определим теперь множество вершин , образующих все ребра из , как объединение соответствующих ребер.

.

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

                                             (6)

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

,

а  находится по (6).

Таким образом, можно сделать вывод о том, что нижняя оценка  числа выходящих ребер для класса  составляет

.                                   (7)

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

Справедлива следующая теорема.

Теорема 2. Нижняя оценка  суммарного числа выходящих ребер гиперграфа  для подмножества решений  составляет

.                          (8)

Доказательство. В приведенной формуле первое слагаемое определяет суммарное число выходящих ребер из сформированных классов  в соответствии с (3) и (1). Второе слагаемое представляет собой нижнюю оценку числа выходящих ребер для формируемого класса  и определяется по (7). Третье слагаемое является нижней оценкой числа выходящих ребер из несформированных классов . Поскольку сумма точного значения и нижних оценок является нижней оценкой, то теорема доказана.

Покажем, что сокращение числа вариантов решений задачи разбиения гиперграфа, то есть получение подмножества , не приводит к уменьшению нижней границы суммарного числа выходящих ребер гиперграфа . Иначе говоря, при ветвлении дерева решений, заключающемся в присоединении к множеству  вершин из , нижняя граница не убывает [2,7].

Теорема 3. .

Доказательство. Очередной элемент из может быть помещен в формируемый класс  либо в качестве первого элемента во вновь формируемый класс . В первом случае первое и третье слагаемые в (8) остаются неизменными, а второе слагаемое не уменьшится, так как не уменьшается число ребер, инцидентных вершинам, помещенным в формируемый класс . Во втором случае третье слагаемое в (8) уменьшится на величину , но при этом появляется новое второе слагаемое , которое по (7) не меньше, чем . Величина, не меньшая величины прежнего второго слагаемого, войдет в новое первое  слагаемое в качестве фактического числа ребер, выходящих из класса . Теорема доказана.

В соответствии с доказанными теоремами строится алгоритм минимального разбиения.

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

Поскольку сформированные классы  не удаляются из гиперграфа, величина  определяется один раз. Возможно переформирование классов в случае, когда на каком-либо шаге имеются ветви с более перспективной оценкой, но с меньшим числом сформированных классов. При этом происходит возврат по дереву решений, так как вновь рассматривается вершина дерева, содержащая большее число решений [4,6].

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

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

Заключение. При решении практических задач часто имеются такие элементы дискретных устройств, которые заранее фиксированы в тех или иных классах разбиения. Этот факт существенно сокращает число возвратов при следовании по дереву решений и, следовательно, увеличивает скорость работы алгоритма и уменьшает размерность решаемой задачи. Если отсутствует необходимость в получении минимального разбиения, а удовлетворительным является локальный минимум при решении этой задачи, то рассмотренный алгоритм можно существенно упростить, исключив возвраты, на которых возможно переформирование классов. При этом отпадает также необходимость в определении наименьшего разбиения, так как величина  участвует в дифференцировании нижних оценок только при различных количествах ранее сформированных классов. Следовательно, алгоритм превращается в последовательный алгоритм разбиения с нижней оценкой для каждой вершины, помещаемой в формируемый класс, отражающей возможный окончательный результат разбиения.

Список литературы:

1. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой. Учебное пособие. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2014. – 446с.
2. Мелихова О.А. Алгоритмы компоновки элементов дискретных устройств // Инновации в науке / Научный журнал – №3(64). Новосибирск: Изд. АНС «СибАК», 2017. – С.42-46.
3. Мелихова О.А., Пустовалова О.В. Проблемы оптимизации при решении задачи размещения элементов СБИС // Информатика, вычислительная техника и инженерное образование [Электронный ресурс]. – №2(26), 2016. – Режим доступа: http://digital-mag.tti.sfedu.ru (дата обращения: 09.03.2017)
4. Мелихова О.А., Дагаев А.В., Бородянский Ю.М. Оптимизация обслуживания автоматизированной системы // Информатика, вычислительная техника и инженерное образование [Электронный ресурс]. – №3(18), 2014. – Режим доступа: http://digital-mag.tti.sfedu.ru (дата обращения: 10.03.2017)
5. Мелихова О.А. Эволюционные вычисления в задачах поиска, оптимизации, обучения // Информатика, вычислительная техника и инженерное образование [Электронный ресурс]. – №4(11), 2013. – Режим доступа: http://digital-mag.tti.sfedu.ru (дата обращения: 14.03.2017)
6. Норенков И.П. Основы автоматизированного проектирования. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2006. – 360с.
7. Полупанов А.А., Полупанова Е.Е. Обзор современных методов и алгоритмов решения задачи компоновки // Труды конгресса по интеллектуальным системам и информационным технологиям «AISIT’11». Научное издание в 4-х томах. – М.: Физматлит, 2011. – Т3. – С. 123-127.