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

Структурный синтез — это наиболее трудная для формализации проектная процедура.

Процедуры структурного синтеза классифицируются по ряду признаков.

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

— выбор принципов построения и функционирования технических объектов (определение облика технического объекта). Эта процедура обычно выполняется на стадиях предпроектных исследований и НИР;

— выбор технического решения, т.е. получение функциональных, принципиальных, кинематических схем, конструктивных решений, технологических маршрутов изготовления деталей и узлов. Эта процедура обычно выполняется на стадиях опытно-конструкторских работ (ОКР);

— синтез технической документации. Её цель — преобразование данных о схемах и конструкциях, выраженных во внутреннем языке САПР в виде законченной информационной модели проектируемого объекта, в текстовую и чертежную документацию, оформленную по правилам ЕСКД, ЕСПД и др.

2. По трудностям формализации процедур синтеза выделяют пять уровней сложности.

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

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

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

Задачи четвертого уровня сложности характеризуются выбором варианта структуры во множестве в общем случае неограниченной мощности.

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

3. По типу синтезируемых структур различают процедуры одномерного, схемного и геометрического синтеза.

Одномерный синтез заключается в построении одномерных последовательностей из элементов некоторой природы. Например — описание технологических процессов в форме маршрутной или операционной технологии; вычислительных процессов — в виде алгоритмов и программ для ЭВМ.

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

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

Существует несколько подходов к алгоритмизации задач структурного синтеза. К основным из них относятся:

— перебор законченных структур;

— наращивание структуры;

— выделение варианта из обобщенной структуры;

— трансформация описаний.

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

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

Многие задачи синтеза при этом относятся к третьему уровню сложности. Получающиеся при этом комбинаторные задачи принадлежат к классу NP –полных задач, т.е. точные алгоритмы их решения имеют экспоненциальную сложность. Это означает, что количество вычислительных операций N = ke^a, где k –коэффициент пропорциональности, a –количество элементов в синтезируемой системе (размерность задачи синтеза). Для реальных задач a достаточно велика, поэтому перебор в задачах третьего уровня сложности может быть только частичным, основанным на приближенных, эвристических методах. Так как приближенные алгоритмы известны лишь для отдельных частных задач, то практическая реализация формирования очередных вариантов в большинстве задач перебора возлагается на проектировщика, работающего с ЭВМ в диалоговом режиме. На ЭВМ при этом производится оценка вариантов структур, предлагаемых пользователем.

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

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

В системах структурного синтеза семантические сети, используемые для представления обобщенных структур проектируемых объектов, называют И–ИЛИ– деревьями. В И–ИЛИ– дереве вершины делятся на ярусы (уровни). Вершины могут быть двух типов И и ИЛИ. Вершины И отображают варианты технической реализации составных частей объектов, а вершины ИЛИ — составные части объектов, выделенные по функциональному признаку. Если на верхнем ярусе вершины ИЛИ соответствуют функциональному назначению систем из некоторого класса, то вершины И соседнего яруса отображают способы реализации систем. Вершины ИЛИ и И последующих ярусов отображают функции и способы построения подсистем, блоков, узлов и базовых элементов. Ветви в И–ИЛИ– дереве представляют квалификационные и признаковые отношения между понятиями. Каждой вершине И в И–ИЛИ– дереве может быть поставлен в соответствие некоторый предикат, характеризующий условия выбора этой вершины (альтернативы) при решении конкретных задач синтеза. На рис.2.13 приведен пример И–ИЛИ– дерева для класса технических объектов — вторичные источники электропитания. Вершины ИЛИ показаны прямоугольниками, вершины И — со сглаженными углами. Сплошной линией изображены ветви, соответствующие классификационным отношениям, пунктирной — признаковым отношениям.

Семантические сети могут быть интенсиональными (ИСС) и экстенсиональными (ЭСС). Интенсиональные семантические сети выражают общие закономерности, присущие данной предметной области, и составляют базу знаний. Пример ИСС — это И–ИЛИ– дерево соответствует обобщённой структуре проектируемого объекта. Экстенсиональные семантические сети выражают сведения о конкретных фактах или структурах и составляют базу данных автоматизированной системы проектирования.

Трансформация описаний применяется в случаях, когда известно исходное описание структуры, соответствующее некоторому иерархическому уровню и аспекту проектирования, и необходимо получить результирующее описание, соответствующее другому иерархическому уровню или аспекту. Алгоритмы трансформации основаны на введении правил преобразования элементов и макроэлементов исходных структур в новые формы, соответствующие промежуточной или результирующей структуре. Трансформация описаний широко используется в САПР. Характерный пример трансформационного подхода — алгоритмы синтеза комбинационных логических схем ЭВМ, в которых по описанию логических функций устройства получается функциональная схема, содержащая элементы заданного базиса. Другой пример относится к процедурам оформления конструкторской документации, в которых описание конструкции на внутреннем языке представления данных преобразуется в управляющую информацию для чертёжного автомата.

 

2.13. Семантическая сеть в виде И–ИЛИ–дерева

 

 

Не менее характерный пример из области автоматизации программирования — трансляция программ производится по алгоритмам трансформационного типа.