Алгоритмы компоновки элементов дискретных устройств

 ELEMENTS GROUPING ALGORITHMS OF THE DISCRETE SYSTEMS

Oksana Melikhova

candidate of Science, assistant professor,

assistant professor of the Southern Federal University,

Russia, Taganrog

АННОТАЦИЯ

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

ABSTRACT

Two sequential grouping algorithms by the minimization test of the number of disconnected relations at the given number of elements in the grouping clusters are considered. The iterated algorithm is offered to use for the improvement of grouping result, received with the help of one of the sequential algorithms. Use of the examined algorithms is allow to reduce the working time of grouping problem solution and also is simplify the process automation of scheme receiving of inside groups and between groups unions, necessary for following steps of the elements allocation and unions tracing of the discrete systems.

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

Keywords: intellectual computer-aided system; elements grouping; optimization test; hypergraphs theory; goal function; mathematical model.

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

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

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

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

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

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

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

                                                    (1)

где

 если ,

 иначе.

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

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

                                                  (2)

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

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

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

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

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

                                          (3)

где

,                        ,

,                        .

Выражение (3) получается из выражения (2) подстановкой  вместо ,  вместо  и введением обозначений  и .

Нетрудно видеть, что произведение  равно единице, если связь (равнопотенциальная цепь), представляемая ребром , разрывается при формировании класса . Следовательно, выражение (3) представляет собой удвоенное число разрываемых при данном разрезании ребер гиперграфа.

Опишем первый последовательный алгоритм, суть которого состоит в последовательном выборе вершин из множества , пригодных по выбранному критерию для включения в множество . С этой целью необходимо ввести оценку каждой вершины гиперграфа относительно уже сформированной части множества . Для формализации получения оценок вершин удобно использовать матрицу инциденций гиперграфа [1,3,5].

Пусть некоторые вершины  уже вошли в множество . Тогда для произвольной вершины  предлагается оценка  следующего вида:

                                           (4)

где  – элемент матрицы,

 если ,

 иначе.

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

.                                     (5)

Сформулируем первый последовательный алгоритм решения задачи компоновки:

1. Включаем в подмножество  любую вершину , пусть, например, .

2. Используя выражение (4) для всех , определяем .

3. В соответствии с условием (5) определяем вершину  и включаем ее в подмножество .

4. Если , где  – выделяемое число элементов, то алгоритм завершает работу, иначе переходим к пункту 2.

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

,                                           (6)

где

 если ,

 иначе.

Из выражения (6) видно, что величина  определяет число разрываемых ребер при условии, что отделяются вершины . Отсюда следует, что для помещения в множество  необходимо выбирать такую вершину , для которой

.                                              (7)

Если таких вершин несколько, то для определенности будем выбирать вершину с меньшим индексом [4,5,6].

Сформулируем второй последовательный алгоритм решения задачи компоновки:

1. Принимаем , по формулам (6), (7) находим вершину  и помещаем ее во множество .

2. Определяем следующую вершину , выбирая вершины из множества , и помещаем ее во множество .

3. Если , где  – выделяемое множество вершин, то алгоритм завершает работу, иначе переходим к пункту 2.

Отметим, что на первом шаге алгоритма в соответствии с формулами (6), (7) выбирается вершина с минимальной степенью, так как все ребра, инцидентные ей, разрываются.

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

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

,                                (8)

где  – элемент матрицы  данного гиперграфа,

 если ,

 иначе.

Кроме того, вводится оценка пары , как число ребер, которым вершины  и  принадлежат одновременно

,

 если

 иначе.

.                                             (9)

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

Теорема. Взаимная перестановка вершин  и  приводит к уменьшению целевой функции , если

.                     (10)

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

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

.                                                 (11)

Имеем

.                       (12)

Из определения оценок вершин (4), (8) следует

Отсюда

                            (13)

Подставляя (13) в (12), получим

Сравнивая полученное равенство с (11), приходим к . Теорема доказана.

Лемма. Поскольку величина  всегда неотрицательна, то по критерию (10) имеет смысл рассматривать только те вершины, для которых .

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

Сформулируем итерационный алгоритм разрезания гиперграфа , при котором множество  разбивается на множества  и :

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

2. Для каждой вершины  в соответствии с (4) и для каждой вершины  в соответствии с (8) определяем величины оценок  и .

3. Определяем все пары , для которых . Если таких пар нет, то алгоритм заканчивает свою работу.

4. Для найденных пар в соответствии с (9) определяем  и находим по (10) величину критерия перестановки . Если  среди всех  найдется хотя бы одна с ,  то переходим к пункту 5, иначе алгоритм заканчивает свою работу.

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

6. В подмножестве  заменяем элемент  на , а в подмножестве  заменяем элемент  на , переходим к пункту 2.

Заключение. Главными достоинствами последовательных алгоритмов компоновки являются их скорость и простота реализации. Кроме того, они позволяют легко учитывать дополнительные ограничения на компоновку: несовместимость отдельных элементов в узле, априорно заданное функциональное распределение некоторых элементов схемы и другие. Основным недостатком этих алгоритмов является локальный пошаговый характер оптимизации, что приводит часто к увеличению числа узлов. Последовательные алгоритмы дают лучшие результаты для схем с невысокой связностью.

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

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

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

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