Автоматизация решения типовых задач структурного синтеза

Понятие структуры объекта проектирования (конструкции РЭС либо технологического процесса) является базовым при реализации блочно-иерархического подхода к проектированию. Под " структурой" понимают представление объекта проектирования в виде совокупности взаимосвязанных элементов.

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

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

Пусть, например, изделие состоит из трех модулей, и его структура приведена на рис. 7.1.

Рис. 7.1. Пример трехмодульной структуры изделия

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

Рис. 7.2. Иерархическое дерево решений

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

Каждый из вариантов структуры конструкции или технологии РЭС оценивают с помощью одного или нескольких критериев качества, при этом должны быть заданы соответствующие математические модели для расчета данных критериев. При этом сравнивать различные варианты структуры можно только по экстремальным значениям критериев качества, определяемым по результатам параметрической оптимизации (оптималь­ный набор значений параметров может оказаться различным для различ­ных вариантов структуры). Например, пусть имеются два варианта струк­туры некоторого объекта проектирования. Каждому варианту структуры соответствует своя математическая модель для расчета критериев качества: для 1-го варианта К(Х) - S_i(X), где X — (x_i,..., х_п) - набор внутренних параметров изделия; для 2-го варианта структуры К(Х) = S₂(X). Графики данных моделей приведены на рис. 7.3.

Рис. 7.3

Если лучшим считается изделие с минимальным значением критерия качества К(Х) —> min (например, если К(Х) - стоимость, трудоемкость и т.д.), то лучшим считается вариант структуры S₁(X).

Поиск по-настоящему оптимального варианта структуры объекта проектирования предполагает проведение полного перебора всех вариан­тов структуры (всех полных цепей в дереве решений). Однако при проекти­ровании сложных систем, состоящих из большого числа взаимосвязанных элементов, рассмотрение всех возможных вариантов структуры, даже с у том вычислительных возможностей ЭВМ, практически невозможно. Поэтому на практике используют методы сокращенною перебора, позволяющие исключить из рассмотрения часть неперспективных (с точки зрения улучшения критерия качества) вариантов структуры. При этом, естественно, появляется риск исключить из рассмотрения по-настоящему оптимальное решение. Успех применения каждого из методов сокращенного перебора в большой степени зависит от удачного выбора моделей и алгоритмов оценки качества вариантов структуры. На практике методы полного сокращенного перебора используют три типа поиска наилучшего решение помощью иерархического дерева решений: поиск с возвращением, поиск в глубину и поиск в ширину.

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

Рис. 7.4

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

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

Алгоритмы поиска в ширину в основном реализуются за время O(n²) – O(n⁴).

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

Таким образом, мы рассмотрели три общих принципа организации поиска на дереве решений.

Рис. 7.5

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

При конструкторском проектировании РЭА (радиоэлектронной аппаратуры) решаются задачи, связанные с поиском наилучшего варианта конструкции, удовлетворяющего требованиям технического задания и максимально учитывающего возможности технологической базы производства. Тесная взаимосвязанность задач и большая размерность каждой из них обычно не позволяет предложить метод поиска оптимального конструктивного решения в едином цикле в связи с трудностями создания общей математической модели, комплексно учитывающей особенности конструкторско-технологической базы производства. Поэтому разработка и реализация алгоритмов и методов решения отдельных задач этапа конструкторского проектирования: компоновки, размещения и трассировки, до сих пор остаются актуальными проблемами, решение которых неотъемлемо связано с развитием систем автоматизации проектирования.

На этапе конструкторского проектирования решаются вопросы, связанные с компоновкой элементов логической схемы в модули, модулей в ячейки, ячеек в панели и т. д. Эти задачи в общем случае тесно связаны между собой, и их решение позволяет значительно сократить затраты и трудоемкость указанного этапа в САПР. Обычно задачи компоновки рассматриваются как процесс принятия решений в определенных или неопределенных условиях, в результате выполнения которого части логической схемы располагаются в конструктивных элементах i -го уровня, а эти элементы размещаются в конструктивных элементах (i +1)–го уровня и т.д., причем расположение выполняется с оптимизацией по выбранному критерию.

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

- минимум суммарной длины соединений;

- минимальная длина самого длинного соединения;

- минимум числа пересечения проводников;

- минимум числа изгибов проводников;

- минимальное прижатие проводника к ранее приложенным соединениям;

- минимум числа слоев;

- минимум числа переходов из слоя в слой.

Таким образом, задача размещения элементов на ПП является многокритериальной.

Исходными данными в задаче размещения являются:

- коммутационная схема (КС) РЭС, задающая связи между ее элементами (в виде матрицы смежности мультиграфа КС , задающей число связей между парами элементов схемы);

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

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

Для построения формальной математической модели компоновочных задач удобно использовать теорию графов. При этом электрическую схему интерпретируют ненаправленным мультиграфом, в котором каждому конструктивному элементу (модулю) ставят в соответствие вершину мультиграфа, а электрическим связям схемы – его ребра. Тогда задача компоновки формулируется следующим образом. Задан мультиграф G(X, U). Требуется “разрезать” его на отдельные куски G1(X1, U1), G2(X2, U2), …, Gk(Xk, Uk) так, чтобы число ребер, соединяющих эти куски, было минимальным, т.е. минимизировать , i ≠ j, где U _ij – множество ребер, соединяющих куски Gi(Xi, Ui) и Gj(Xj, Uj).

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

Известные алгоритмы компоновки можно условно разбить на четыре группы:

- алгоритмы, использующие методы целочисленного программирования;

- последовательные алгоритмы;

- итерационные алгоритмы;

- смешанные алгоритмы.

Алгоритмы первой группы хотя и позволяют получить точное решение задачи, однако для устройства реальной сложности фактически не реализуемы на ЭВМ. В последнее время наибольшее распространение получили приближенные алгоритмы компоновки (последовательные, итерационные, смешанные). При использовании последовательных алгоритмов сначала по определенному правилу выбирают вершину графа, затем осуществляют последовательный выбор вершин (из числа нераспределенных) и присоединение их к формируемому куску графа. После образования первого куска переходят ко второму и т. д. до получения желаемого разрезания исходного графа. В итерационных алгоритмах начальное разрезание графа на куски выполняют произвольным образом; оптимизация компоновки достигается парными или групповыми перестановками вершин графа из различных кусков. Процесс перераспределения вершин заканчивают при получении локального экстремума целевой функции, удовлетворяющим требованиям разработчика. В смешанных алгоритмах компоновки для получения начального варианта “разрезания” используется алгоритм последовательного формирования кусков; дальнейшая оптимизация решения осуществляется перераспределением вершин между отдельными кусками графа.

В последовательных алгоритмах компоновки «разрезание» исходного графа G(X, U) на куски G1(X1, U1), G2(X2, U2), …, Gk(Xk, Uk) сводится к следующему. В графе G(X, U) находят вершину x_i Î X с минимальной локальной степенью p(x_i) = min p(x_j).

Если таких вершин несколько, то предпочтение отдают вершине с максимальным числом кратных ребер. Из множества вершин, смежных с вершинами формируемого куска графа G1(X1, U1), выбирают ту, которая обеспечивает минимальное приращение связей куска с еще нераспределенными вершинами. Данную вершину x_i Î X X1 включают в G1(X1, U1), если не происходит нарушения ограничения по числу внешних связей куска.

Указанный процесс продолжается до тех пор, пока множество X1 не будет содержать n элементов либо присоединение очередной нераспределенной вершины x_j к куску G1(X1, U1) не приведет к нарушению ограничения по числу внешних соединений куска, равному

.

Следует отметить, что величина не является монотонной функцией | X1 |, поэтому, для того чт обы убедится в невозможности дальнейшего формирования куска вследствие нарушения последнего ограничения, необходимо проверить его невыполнимость на последующих шагах увеличения множества X1 вплоть до n. В качестве окончательного варианта выбирают кусок G10(X10, U10), содержащий максимально возможное число вершин графа G(X, U), для которого выполняются ограничения на число внешних связей и входящих в него вершин (n_min - n_max).

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

. Также среди достоинств данной группы алгоритмов выступает высокое быстродействие их при решении задач компоновки.

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

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

В случае минимизации суммарной взвешенной длины соединений формула для расчета изменения значения целевой функ­ции при перестановке местами элементов r_i и r_j, закрепленных в по­зициях t_j и t_g, имеет вид

DF_ij(f, g) = (c_ip - c_jp)(d_fh(p) - d_gh(p)),

где р и h(p) — порядковый номер и позиция закрепления неподвижного элемента r_р.

Если DF_ij(f, g) > 0, то осуществляют перестановку r_i, и r_j, приводящую к уменьшению целевой функции на DF_ij(f, g), после чего производят поиск и перестановку следующей пары эле­ментов и т. д. Процесс заканчивается получением такого варианта размещения, для которого дальнейшее улучшение за счет парных перестановок элементов невозможно.

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