автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Автоматизация процесса анализа свойств предметной области в САПР горного производства

Министерство науки, высшей школы и технической политики Российской Федерации

Московский ордена Трудового Красного Знамени горный институт

На правах рукописи

СТЕПАНЫ<0В Александр Юрьевич

УДК 622.658.512.22.011.56 (043.3)

АВТОМАТИЗАЦИЯ ПРОЦЕССА АНАЛИЗА СВОЙСТВ ПРЕДМЕТНОЙ ОБЛАСТИ В САПР ГОРНОГО ПРОИЗВОДСТВА

Специальность 05.13.12 — «Системы автоматизации проектирования (промышленность)»

Автореферат диссертации на соискание ученой степени кандидата технических наук

Москва 1992

Работа выполнена; в Московском ордена Трудового Красного Знамени горном институте.

Научный руководитель академик АЕН РФ ГОРБАТОВ В. А.

Официальные оппоненты: д. т. н., проф. ВАГИН В. Н., к. т. н., доц., с. н. с. ЗАХАРОВ В. Н.

Головная организация —Московский инженерно-физический институт.

9 О

Защита диссертации состоится « .¿г-т » Т-". ■ . 1992 г.

О ъ 5

в I. . . час. на заседании специализированного совета •К-053.12.03 Московского ордена Трудового Красного Знамени горного'института по адресу: 117935, Москва, Ленинский проспект, 6.

С диссертацией можно ознакомиться ■ в библиотеке института.

Автореферат разослан

1992 г.

Ученый секретарь специализированного совета

доктор техн. наук, проф. ТОРХОВ В. Л.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность. В последнее время можно наблюдать заметное усложнение САПР: появились "интегрированные САПР", "интеллектуальные САПР" и т.д. Это связано в первуп очередь с усложнением реиае-мых задач, увеличением их размерности, попыткой автоматизировать не только отдельные этапы разработки, такие, как разводка печатных плат, но и целиком процесс проектирования и при этом обеспечить автоматизированную поддержку работы коллективов разработчиков. Безусловной необходимость!) эффективного функционирования САПР становится применение принципов искусственного интеллекта СИИ), что способствует дальнейяему уменьиенив стоимости разработок, снижает риск концептуальных оиибок, допускает работу с малопрофессиональными пользователями, повнаает дружественность систем. Результат их работы может сопровождаться необходимыми о'ъяснениями и количественной оценкой достоверности результата. Кроме того, такие системы инвариантны по отноиении к предметной области, т.к. являются, по сути, лияь средствами обработки заложенных в них знаний. Таким образом. в настоящее время весьма актуальной является разработка интеллектуальных проектирупцих систем или интеллектуальных подсистем действующих САПР.

Ревение этой задачи связано как с исследованиями в области ИИ. так и с теоретическими вопросами создания САПР. Больяой вклад в эти области внесли: О.М.Белоцерковский, Г.С.Поспелов, В.А.Горбатов, В.В.Девятков. В.П.Корячко.И.П.Норенков. Э.В.Попов, Д.А.Поспелов, Н.И.Федунец, Е.Кодд, А.Ньиэлл, Э.Фейгенбаум. Е.Иортлиф.

Обычно САПР должна поддерживать следуищие этапы процесса проектирования:

- исследование проектной проблемы, включающее се формулировку и комплексный анализ;

- поиск стратегии репения;

- оценку принципиальных решений и их описание;

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

- для неопределенных уелг^ий формирование "дерева реиений", способного бесконечно ветвиться, по которому можно оценить тот или

иной вариант решения, причем глцбина ветвления соответствует гл^иине проводимого анализа;

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

Задача анализа в этом случае становится одной из основных при создании САПР. Ее репение базируется на описании (знаниях о) предметной области и целях проектирования. При этом необходимо учитывать объективные ограничения (время, качество) в которых выполняется процесс проектирования.

Целью диссертационной работы является разработка программного комплекса с использованием которого можно автоматизировать процесс анализа в САПР.

Научная новизна работы состоит в:

- постановке задачи анализа в САПР;

- разработке новой модели представления данных - "мультидерево", ориентированной на автоматизацию процесса анализа и позволяющей описывать "е только состояние предметной области, но и процессы, протекающие в ней, а также позволяющей удобно представлять многоаспектность данных;

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

- постановке и решении характеризационной задачи многокритериального выбора;

- разработке архитектуры и функциональной структуры универсального программного комплекса поддержки процесса анализа свойств пгедметной области в различных областях человеческой деятельности;

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

Практическая ценность работы состоит в:

- разработке универсального программного комплекса для создания автоматизированных информационных систем по поддержке процесса анализа;

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

- разработке методики проектирования систем анализа свойств предметной области.

С помощью методики и с использованием универсального программного комплекса были реиены четыре практические задачи. Имеются соответствующие акты о внедрении.

Таким образом, на защиту выносятся:

- метод представления данных "мультидерево":

- ревение характеризационной задачи многокритериального выбора;

- алгоритм, реализующий ренение характеризационной задачи;

- архитектура универсального программного комплекса для создания автоматизированных информационных систем анализа свойств предметной области;

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

Основные положения диссертации опубликованы в самостоятельных работах:

- в [11 рассмотрены вопросы, возникавшие в процессе анализа свойств предметной области и определены подходы к методам автоматизации процесса анализа свойств предметной области;

- в [21 определена постановка задачи многокритериального выбора и предложен подход к ее решению;

- в 131 рассматриваются вопросы, связанные с реализацией модели представления данных "мультидерево" и описывается метод доступа.

Результаты работы доложены и обсчждены на:

- семинаре МДНТП "Новые информационные технологии в планировании, управлении и производстве" (Москва, 1991г.);

X!У Всесоюзном симпозиуме "Логическое управление с использованием ЭВМ" (Москва, 1991г.).

Объем работы.

Диссертационная работа состоит из введения, четырех глав и заключения, изложена на 158 страницах, содержит 43 рисунка, библиографию из 98 наименований.

ОСНОВНОЕ С0ДсРШИЕ РАБОТЫ

Изучение состояния проблемы, связанной с автоматизацией

процесса лнализа в САПР показывает, что она должна режаться в комплексе с разработкой:

- способа представления знаний о предметной области, адекватного его применение в рамках задачи анализа;

- способа хранения данных, использующихся в рамках задачи анализа;

- архитектуры, алгоритмов функционирования и взаимодействия модулей, реализующих как способ представления знаний, так и способ их хранения;

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

В настоящей работе были выделены следувдие критерии оценки для выбора модели данных наилучшим образом подходящей для использования ее в системе анализа:

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

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

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

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

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

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

Деревом называется ориентированный граф G = <U,U>, где существует вервина vi. в которую не входит ни одна дуга (голова дерева) и п, п=1,...,К вершин, из которых не выходит ни одной дуги или листьевых вервин. При этом в каждую вервину, кроме vi, может входить только одна дуга и из каждой вервины, кроме листьевых, может выходить не меньше одной дуги.

Определение 1: Вершина vi называется непосредственно подчиненной вершине vj, если между ними существует ребро u(vi,vj).

Определение 2: Вервина vi называется подчиненной вершине vj, если вершины связаны цепью.

Определение 3: Ярусом вершина vi называется множество вершин непосредственно подчиненных данной вервине.

Определение 4: 3-м ярусом вервины vi называется множество вершин, отделенных от vi цепью длины J.

Определение 5: Будем считать, что каждая вершина дерева имеет уникальный идентификатор I], причем два дерева эквивалентны только, тогда когда идентификаторы верпин и их взаимная соподчиненность совпадают.

Определение 6: Объединением двух или более деревьев будем считать дерево, получающееся при склеивании вервин с одинаковыми идентификаторами.

Утверждение 1: В общем случае при объединении двух деревьев может получиться граф, не являющийся деревом.

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

Доказательство: Если даны две цепи С1 и С2. причем если у них совпадают по две вервины, т.е. в С1 и в С2 присутствуют вершины с идентификаторами la,Ib, то в той случае, когда vela подчинена vclb. a vc2a подчинена vc2b, результирующий граф теряет свойство антитранзитивности. Действительно, при объединении такого типа цепей в результирующем графе появляется два пути между вервинами с идентификаторами 1а и Ib.

В том случае, когда vela подчинена vclb, a vc2b подчинена vc2a, в результирующем гпафе появляется цикл.

На основании известного свойства деревьев быть представимыми в виде конечного числа цепей (D-разложимость деревьев) можно сделать

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

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

Расширенное дерево было названо мультидеревом. Нультидеревом называется граф 61 = <ии,и>, который отличается от графа С тем, что каждая вержина графа £1 мосет расцепляться на экземпляры, количество которых соответствует количеству входящих в эту вержину дуг. В каждый экземпляр вершины VII может входить только одна дуга. Из листьевых вершин не могут выходить дуги.

Было выяснено, что с помочью мультидеревьев можно адекватно и непротиворечиво поддерживать процесс объединения и декомпозиции, поскольку мультидеревья не теряют свойство быть мультидеревьями при объединении, при этом в отличие от деревьев с помощью мультидеревьев можно осуществлять процесс, обратный объединении, - процесс декомпозиции.

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

Мультидеревья лишены этого недостатка.

Если подходить к моделировании предметной области с позиции теории БД, то с "ловушкой связности" приходится бороться тем или иным способом во всех моделях данных. Чаще всего для универсальности пользуется реляционной моделью данных, поскольку она обладает привлекательным свойством: допускает применение формального матема-

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

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

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

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

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

Поэтому адрес обычно структурируется при хранении, он разбивается на составные части (например Страна - Россия, Город - Москва, Нлица - Ленинский проспект. Здание - д.6 и т.д.) для того, чтобы увеличить единообразие представления. Следующий аспект представления -попытка обеспечить единообразие с точки зрения обрабатывающего программного комплекса. Пользователя просят не вводить самому значение, а выбирать из каталога допустимых. При этом появляется еце один элемент системы - каталог или словарь, необходимый для единообразного представления данных с одинаковым смыслом. Например, стран в мире конечное количество, и логично хранить не названия стран, а коды, соответствующие этим названиям, уменыаая при этом объем хранения и упрощая поиск. Такой способ хранения данных хорою поддерживается моделью данных "мультидерево".

В последнее время в связи с усложнением поисково - справочных систем возникла новая проблема. Предположим, в системе используются данные о странах как справочная информация. При этом, когда заводятся данные о лицах, в качестве значения некоторых атрибутов может быть ссылка на другой объект. Например: место рождения -> страна -> СССР. При этом СССР может присутствовать в виде ссылки: "страна -> СССР", либо в виде значения "СССР". Смысл в обоих случаях один, но возможности разные. В первом случае ссылка явно указывает ча идентификатор записи в объекте учета "страна", который может сам быть подвержен изменениям (в данный момент времени не "СССР", а "Россия", например), во втором случае для получения дополнительной информации об СССР необходимо осуществлять дополнительно процедуру поиска, если мы захотим посмотреть данные о стране рождения Иванова.

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

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

- ч -

ческих СУБЛ (например ООАВА5,ЯЕУЕЬАТЮН,НПВ5 и др.). Это особенно выгодно при хранении сложных объектов. Так. если надо хранить все должности, которые занимал человек в процессе работы, то если это свойство представлять с помощью реляционной модели данных, то необходимо вводить дополнительное отнопение.

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

Обычно, в соответствии с модельи данных КОДЙСИЛ в объекте учета выделяют однозначные атрибуты, многозначные атрибуты, группы атрибутов, и, соответственно - многозначные группы атрибутов. Если мы используем для представления данных мультидеревья, то все атрибуты хранятся в рамках одной записи. Если же мы будем использовать реля-. ционнуи модель данных, то в общем случае на каждый многозначный атрибут, каждую группу а1рибутов и т.д. необходимо заводить по дополнительному файлу.

Как правило, доступ к файлам, т.е. к внешним носителям, идет на порядок ыедленнее, чем доступ к памяти. Следовательно эффективность модели по доступу к данным можно определить тем, как часто приходится в процессе работы с модельи обращаться к внешней памяти. Обращением к внешней памяти будем считать операцию считывания записи из файла. Тогда если в объекте учета будет Н нелинейных элементов, представление с помощью нультидеревьев будет на С N-1 )*К единиц времени эффективнее при доступе к одному экземпляру учета по сравнению с представлением в реляционном виде.

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

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

Для реляционной структуры время доступа к объекту учета составляет не более чем: 2*N*r+R*k2+p2. (1)

В том случае, когда в объекте учета просматривается Z записей, время доступа составляет не более: 2*N*r+R*k2+p2*Z. (2) Для мультидеревьев оценки следующие: 2*r+R*kl+pl. (3)

2*r+R*kl+pl*Z. С 4 >

Для режима обновления в случае реляционной структуры время доступа не болен:

2*N#r+R#k2+p2. (6) -одна ?апись; (2*H*r+R*k2+p2)*Z. (7) -2 записей. Для режима обновления в случае мультидеревьев: 2*r+R*kl+pl. (8) - одна запись;

(2*r+R*kl+pl)*Z. С9) - Z записей.

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

Kl = <2*N*r+R*k2+p2)/(2*r+R*kl+pn К2 = (2*N*r+R*k2+p2*Z)/(2*r+R*kbpl*Z) КЗ = (2*N*r+R*k2+p2)/(2*r+R*kl+pl) К4 = (2*H*r+R*k2+p2 )*!/(. 2*r +R#kl+pl )*Z = (2*N*r+R*k2+p2)/(2*r+R*ki+pl); Если учесть, что величины kl.pl обычно мало отличаются от величин к2,р2, а также предположить, что r/kl = 5, то получается, Ki = К2 = КЗ = К4 = (kl*( 10H+R)+p2)/( ki*( 10+R)+p2).

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

- представить любое дерево;

- обеспечить поддержку разноаспектности подцелей, когда один и

тот же факт влияет на достижение разных подцелей неоднозначно.

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

Для того чтобы ответить на вопрос, подходят ли мультидеревья для использования их при представлении процессов, было предложено считать, что процесс - это то, что представляется сетевым графиком. Если это так, то можно дать однозначный ответ, что мультидеревья подходят для представления процессов, поскольку с их помощью можно представить сеть следующим образом. Пусть сеть представляется антирефлексивным ориентированным графом Б = <и,Ц>. По определению мцль-тидерева, в каждый экземпляр вернины мультидерева не может входить более одной дуги. Следовательно, для того чтобы представить сеть мультидеревон, надо те дуги сети, в которые входит больяе одной дуги, разбить на экземпляры в количестве, равном количеству входящих дуг.

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

- эквивалентирование ( существуют две модели, которые в смысле достижения цели эквивалентны, поскольку и одна, и другая приводят к одинаковому результату):

- достижимость (достижима ли данная цель при текущем состоянии предметной области):

- сравнение или выбор (какая из моделей лучве при текущем состоянии предметной области).

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

Как правило, для уменьвения сложности задач используется метод

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

Указанную проблему можно преоголеть, если ввести понятие дерева многоцелевой д «оппозиции модели. По определению дерева целевой декомпозиции, один и тот же элемент носителя модели может присутствовать в разных деревьях, следовательно, каждой модели И соответствует п деревьев целевой декомпозиции, где,п - количество целей. Склеим эти деревья так, чтобы у них совпали одинаковые элементы носителя: при этом получится дерево многоцелевой декомпозиции модели Нгс, причем каждая дуга взвевивается целью. При таком способе построения дерева Нгс из него всегда можно однозначно выделить деревья Иге! по 1-й цели.

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

Иожно ввести понятие функционала качества 5гс(Ю, который позволил бы давать количественную оценку модели по цели. Будем считать, что модель На лучше модели НЬ по цели 1*с, если 5гс(На) > БгсСНЬ).

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

Пусть задано 1л множество моделей предметной области Н], где I

= 1.....п. В качестве моделей могут выступать образцы техники,

описание процессов и методов и т.д. Каждой модели Н1 соответствует множество требований Я1, которым она может удовлетворять со степенью, определяемой с помощью функции РсШ).

Определение 7: Под одноцелевой проектной процедурой будем понимать функцию выбора Н] = русга.Ш, 1 = 1. которая, учитывая текущее состояние предметной области, ставит в соответствие ,Цели

лучшую модель.

Определение 8: Под многоцелевой проектной процедурой будем понимать функция выбора Н] = ру(2аДП, где 1=2.....п.

Определение 9: Под декомпозицией модели Н] по цели будем понимать такое разбиение модели Н} по цели Ш на подмодели Н}к при одновременной декомпозиции цели на подцели 1Мк, когда становится возможным однозначно оценить влияние состояния среды 1л на выполнение всех подцелей. Декомпозиционную процедуру применяют в том случае, когда сложно или невозможно по модели Н] сразу сказать, как она удовлетворяет цели 1!1 в зависимости от состояния среды Za.

Определение 10: Целевой характеристикой модели И] является вектор степеней удовлетворения требованиям Рс(1Ш. 1 = 1.....п.

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

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

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

В качестве примера была рассмотрена многокритериальная задача выбора комплекса технологического оборудования. Обычно такая задача может быть представлена в виде графа СЬ = <иЬ,Ш.>, где вершинам графа соответствуют типы технологического оборудования и типы решений по его применению, при зтом можно выделить уровни вервии в графе. Каждому уровню вершин соответствует множество типов оборудования, которые можно сравнивать между собой. Комплексом будем называть множество вершин, составляющих путь из зервины первого уровня до вершины последнего. Задача состоит в выборе комплекса, наилучве-_ го в конкретных условиях. В общем случае для выбора наилучшего ва-

- 14 -

рианта надо произвести К = Па!

1 = 1___N

вычислений, где N - количество вериин в уровне, Н - количество уровней. Поскольку в реальных задачах N >= 30, Н >= 50, к тому же процедура сравнения вариантов достаточна трудоемка, вычислительнув сложность прямой генерации всех вариантов и сравнения их между собой нельзя считать удовлетворительной.

Для решения этой задачи будем пользоваться следувцим подходом. Каждой вершине графа <'Т присвоим коэффициент ее целевой значимости Кд], который может быть вычислен только на основании состояния предметной области, в дальнейшем будем называть его апостериорным коэффициентом. Сложность вычисления апостериорных коэффициентов пропорциональна количествч вершин графа ей В принципе коэффициенты при вершинах дают возможность оценить каждый вариант путем простого их суммирования или с помощью какого-либо другого способа. Будем считать, что метод вычисления совокупного критерии качества отдельного варианта существует. В то« случае, если оевения, принимаемые на каждом из уровней и графа, не влияют на другие или если выбор на каждом уровне обладает свойством локальности, сложность задачи выбора пропорциональна количеству вервин графа £Ь.

Основная сложность задачи закгвчается в ее переборной сущности в том случае, когда реиенио на одном уровне в графе влияет на качество принимаемых решений на другом уровне. Если все уровни И взаимозависимы, то сложность решения задачи выбора максимальна и пропорциональна КЛН. Следовательно, сложность задачи может колебаться в широких пределах от НАН до Н*И.

Был предложен конструктивный критерий уменьшения сложности решения задачи. В том случае,.если не все уровни взаимозависимы, можно разбить задачу на несколько подзадач. Критерием разбиения может служить взаимозависимость между уровнями графа СИ. Уровни решения, которые являются взаимог висимыми, выделяются в отдельные подзадачи. В этом случае граф СЪ преобразуется к графу сложность задачи уменьшается и становится пропорциональной Ы'АМ*, где И' и Н' -характеристики подзадачи максимальной разме'рности.

Предложенный метод уменьшает сложность решаемой задачи в НЛМ/Я,АН' раз, дает способ определения наилучшего варианта ренения и в реальных условиях позволяет построить программный комплекс,

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

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

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

Пусп. задано описание предметной области Про и модель действия Н(1 в виде графа типа Кь. Поставим в соответствие каждой вернине графа два типа коэффициентов: априорный коэффициент Ка] и апостериорные коэффициенты КП. Априорные коэффициент» будем вычисляттолько в зависимости от состояния предметной области. После вычисления Ка} можно вычислит], апостериорные коэффициенты, которые в общем случае могут бит-, связаны только с теми вариантами, которые били выбраны и с Ка].

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

Приведем граф к графу псставив в соответствие каждой

вершине графа БЬ у] множество вершин коэффициентов укИ. Из глгдой вершины ук]1 проводится дуга в те вершины графа С^ от которых зависит расчет коэффициентов. Не.: дуги соответствует критерию зависимости принятия варианта решение, соответствующего вершине, при которой стоит коэффициент, от решения, соответствующего пергаиме, из которой выходит дуга, ¡1 этом случае задачу выбора оптим-.лмюгп комплекта можно сформулировать следующим образом. Необходимо выб

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

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

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

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

Для определения, является ли граф 61' !№ декомпозируемым, воспользуемся характеризационным подходом. Выделим запрещенные фигуры, которые не позволяют £1' обладать свойством 1Мс декомпозируеыости. Знание запрещенных фигур позволяет строить констрнктивный критерий упрощения модели и на основании этого создавать эффективные алгоритмы. Основополагающим фактором для построения запрещенных фигур являются знания о закономерностях априорно присутствующих в модели. Дыделекные на основе этих знаний запрещенные фигуры являются теми формальными критериями, используя которые можно выполнять оптимизационную процедуру.

Запрещенной фигурой в нашем случае является г.олновэаимозависимая компонента графа £1'. Существуют два типа полновзанмозависимости для £Ь":

абсолютная. когда взаимозависимость прослеживается на всех комплектах из £Ь";

- частичная, когда не для всех комплектов из £1" наблюдается взаимозависимость между их элементами.

Ятверждение 2: Граф £1' не обладает свойством 11к декомпозируемости, только тогда, когда максимальная абсолютная взаимозависимая компонента £1" графа £1' равна графу И'-.

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

Утверждение 3: Если граф ГЛ,' не является абсолютной взлимозовисимой кпмпонентпй, всегда можно уменьшить слпзшооть вычислительной процедуры нахождения оптимального комплекта.

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

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

Предложим г.ледуючий алгоритм вычисления наилучшего комплекта: разбить граф СЬ* на непзаимозависимые компоненты ГЛ'Ч; в случае, если- выделенные компоненты являются абсолютно взаимозависимыми, определить в них лучший комплект перебором;

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

- после того как вычислен» лучшие варианты в невзаимоялвисимых компонентах, они однозначно определяют полный лучший комплект.

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

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

Программная система (ПС) - это инструмент, позволявший

создавать широкий круг прикладных систем оГ,,а1от;;и сложноструктурированной информации на базе персональных ЗВИ.

ПС - это комплекс программ, работающих под общим управлением и реализующих стандартные режимы генерации и обработки баз данных прикладных пользовательских систем. ПС позволяет создавать и подключать под ее управление любое число прикладных программ, написанных на языках "С" и "flSSEKBLER" для реиения специальных задач на информации, имеющейся в БД системы. ПС позволяет хранить данные в произвольном формате, а также строить сложные отношения над единицами хранимых данных - объектами. ПС поддерживает ' собственную структуру данных - мультидеревья. Кр>ме этого в базовый комплект ПС включен режим, поддерживающий решение задачи многокритериального выбора.

ПС рассчитана на работу в среде PC DOS версий не ниже 3.0 на IBM-совместимых ПЭВМ, имеющих жесткие (съемные или несъемные) диски.

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

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

Объем ПС около 2Ь0Кб объектных модулей (объем определен по объему библиотек программных модулей).

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

ОСНОВНЫЕ ВКВОДН И РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

4. Создан пакет инструментальных программных средств, позволяющий создавать интеллектуальные подсистемы САПР для реиения разнообразных задач проектирования, которые можно описать с помощью модели представления знаний 'мультидерево". Экспериментальное исследование свойств разработанных программ и получаемых результатов показало применимость созданных средств для реяения практических задач со сложным составом данных и числом анализируемых парауетров порядка 100 при количестве значений каждого параметра порядка 10.

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

Основные положения диспертоции опубликованы в следующих раб!

тах:

1. Ст^плнккпп П.Ю. Пвтоматизация процесса анализа свойств предметной области. !' кн: !!ппне информационные технологии п планировании. управлении я пргнпипдгтпе. -М. МДПТ11. 1111 . .28-34.

2. Степаньков А,И. Автоматизация процесса проектирования на основе манипулирования деревьями многоцелевой декомпозиции предметней области, - В сб. Логическое управление с использованием ЭВМ, АН СССР, V., 1Э91

3. Степаньков А.Ю. Организация системы хранения и манипулирования данными для создания БД САПР, - В сб. Логическое управление с использованием ЭВМ, ПН СССР, П., 1991

Подписано в лечвть 25.5.1992 г. Формат 60x90/16 Объём I печ.л. Тиран: 100 экз. Заказ й

Типография Московского горного института". Ленинский проспект, б