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

pre од

\ k №

Академия иацк Украина Институт проблем моделирования з энергетике

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

ИЕйКЯИЯН Карзн Вальтерович

УДК 519.72

ПРИМЕНЕНИЕ ФиКДЙКЕНТПЛЬНОГО УРАВНЕНИЯ СЕТИ ПЕТРИ ПРИ

р;-:шш задач виводй нл зшиах в п^одакциокнях систшх

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

АВТОРЕФЕРАТ

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

Киев - 1ЭЭЗ

Работа дополнена d отделе разрядно-аналогозсго моделирования Института проблей моделирования я энергетике АН Украины.

Научный руководитель.

член-корр. АН Украины директор института Евдокимов В.Ф.

Официальные оппоненты: доктор технических наук, профессор. Кцзьмук В.Ь.

кандидат технических наук, старкий научний сотрудник. Сксрик 5Л1.

Всдщаа организация: Киевский институт инвг.неров граиданской авиации.

/7 ииоч*^ .¿¿/ ¿0

Защита состоится ______________ 1993г. в___часов..кии.

на заседании специализированного ученого совета Д 010.01.01 при Институте проблем моделирования в энергетике ПН Украины но адресу: 252680 г.Киев - 164. уд.Генерала Наумова 15.

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

/ У ^CC'UA.

Автореферат разослан "___"______.------1993г.

УчешРссекротарь специализированного совета.

кандидат технических наук ¿Jä-- - Э.И.Семагина

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

Актуальность проблемы. В настоящее время все бсльвсе распространение получают экспертные системы (ЗС).

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

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

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

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

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

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

Иоэтьму создание более универсальных средств и методов об-

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

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

Основкне задачи работы:

- проанализировать суцествуьцие подхода и катоде ле*аа(ие в основе процесса внвода на знаниях в ПС;

- проанализировать существующие модели внутреннего представления базы знаний для ПС;

- разработать принципы моделирования базы знаний и процессов вывода на знаниях в ПС при помочи аппарата сетей Петри, позволяющих эффективно использовать фундаментальное уравнение сети Петри (ФЙСЮ;

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

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

- проанализировать полученные методы с точки зрения эффективности разрабатываемых на их основе элементов ЗС и их универсальности.

Метода исследования. В работе использован аппарат сетей Петри и их »^диеикаций, теории графов, теории многеств, математической логики.

Научная новизна и основные палоаекня. выносимые на зациту.

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

2. Модель базы знаний в продукционной системе для случая когда в И/И£И графе процесса вывода отсутствуют циклы.

3. Модель базы знаний в продукционной системе для случая когда в Н/ИЛй графе процесса вывода могут присутствовать циклы.

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

5. 51етод определения циклов в Й/ИЯЙ графе процесса вывода на основе реяения фупданентального уравнения сети Петри.

8. Разработаны принципы для создания алгоритыоз построения внутренней модели на основе анализа база знаний в продукционной системе.

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

Внедрение. Результата диссертационной работы внедрены в следующих ИЙР: - "Разработка оптииальной системы эксплуатации средств аэронавигационного обслуанвания Ь'краинв". lio программе ГКНТ Зкраинч 6.8.3. "Развитие аэронавигационного обслуаивания Нкраини". НПП "Сплайн"; - НИР К 009 - ГБ 92 "йетодика

обоснования требований к средстэан радиотехнического обеспечения полетов и аВ/I и системе их эксплуатации". ШГА; а такге в

fiCÜ ВЭЗ книга.

Апробация работы и пцбликации. Результата работы докладывались и обсуидались:

- на всесоэзной . научно-технической конференции "Проблеви совершенствования радиоэлектронных конплексов н систем обеспечения полетоз", Киев, КНИГА. 1389 г.>:

- na II ыехдународной научно-технической конференции "Проблемы соверкенствоваиия радиоэлектронных комплексов и систем обеспечения пактов", Киев, КНИГА. 1992 г.

По теае диссертации опубликовано четыре печатных работы, одна подготовлена к печати.

Структура диссертации. Работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Всего 10í страница кааииописпого текста, включая 24 иллюстрации.

- 4 -

КРАТКОЕ СОДЕРЖАНИЕ РАБОТИ

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

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

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

I -> 0. (1)

где левая часть I описывает определенную ситуацию, в соответствии с формальными правилами рабочего пространства, а правая часть 0 представляет собой действие, выполнение которого предполагается в случае обнаружения соответствующей ситуации,

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

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

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

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

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

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

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

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

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

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

В настоящее время некоторыми авторами используется моделирование с поксщьв сетей Петри, при которой процесс завода на знаниях в ПС сводится к реаекив задачи достиаимости в сети Петря.

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

Так если функции инцидентности представить как

Pre: Р Т->Н к (2)

Post: Т P->N, (3)

где,

Pre - функция инцидентности позиций с переходами;

Post - функция инцидентности переходов с позициями;

N - множество целых неотрицательных чисел, то Pre и Post можно задать матрицами инцидентности размерами i/to, в которых строки ссответствувт позициям, г столбцы - переходам. Пусть для некоторой СП

С - Pre - Post. (4)

где С - матрица инцидентности, маркировка Кп достижима из маркировки Ко. Тогда если и-- последовательность (возможна пустая) запусков переходов, котооая приводит из Но к Ип то фундаментальным уравнением сети Петри (ФУСП) называется

И it - Mo + f(u) С. (5)

где fiu) - вектор запуска с неотрицательными компонентами.

Однако, подход к анализу СП при помоцк ФУСП имеет следующие недостатки:

- элементы, представлявцне переходы с входами и выходами из одной позиции (петли"), взаимно уничтожаются в матрице С*.

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

- ревение ФЬ'СП является необходимым условием достижимости, но це достаточным.

На сегодняшний день условия достаточности хорояо исследованы лиаь для маркированных графов (ИГ). Полученные в работе T.Xurata. Circuit theoretic analysis and synthesis of Barked graphs. IEEE Trans, on circuits and systess, vol. cas-24, no. 7. July 137? результаты можно представить в виде следующей теоремы.

Теорема 1: (о необходимом и достаточном условии достижимости маркировки Нп от Ко для ларкированных графов).

В МГ маркировка Нп достижима от Но тогда и только тогда,

если:

- ФУСП имеет речение в неотрицательных целых;

- переходи, который в векторе запуска f(u) соответствуют не нулевые компоненты, не принадлежат свободным от маркеров циклам.

Пусть для некоторой сети Петри, коделкрущей процессы вывода j ПС, все ревения действительны, или существует некоторая простая (с tv-чки зрения комбинаторики) проверка, позволявшая определить действительные ревения из мноюства рекений ФУСП. то полученные действительные ревения будут представлять собой множество правил, которые, и только они (для данного варианта ревения) приводят к цели. Т.о. процедура ревения ОЭСП будет аналогична нексеароку метаправилу, выбиравшему для каждого варианта ревения в базе правил и базе фактов только те правила и факты, которые необходимы и достаточны для успевного вывода. Очевидно, что в данном случае нет необходимости в эвристических знаниях для разрешения конфликтов между правилами готовыми к выполнение, т.к. на каждом иаге логического вывода ситуация будет всегда однозначной, а количество безуспееных попыток сопоставления правил

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

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

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

При изучении возможности использования ФУСП в задаче вывода на знаниях будет подразумеваться, что данная задача сфорау-лированна следуюпим образом:

1) пространство вывода представлено И/ИЛИ графом, в котором Я и ИЛИ связи (возможно КСМБ (комбинированная связь)) могут присутствовать, как между входными, так и мевду выходными дугами для вериин данного графа;

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

3) если Н - множество начальных вериин, а N - множество конечных иераин то то для любых двух подмнозеств (н^,} и (sj ) множества М. и лвбых двух подмножеств (п^) и inj) множества S, таких что inj) {Ej} -ff и (n^iflin^} =0 , то вервина '.а^З не достижимы от (Bj) и вераины inj.) не достижима от (п£,};

4) модификация правил осуществляется только зкснертои внев-ниаи, по отноаенип к процессу вывода процедурами.

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

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

Интерпретированная сеть Петри (ИСП) - это пара СК,Р\где N-сеть Петри. Й:Р->А - помечавшая функция над некоторым алфавитом

-fifi. й={а4,аг....,ал), где aj, соответствует сакту, установленному на определенном зтапе вывода. Если К - частичная функция, т.е. некоторый позициям не сопоставляется ни какого символа, то эти непомеченное позиции называются ] - позициями и помечается одной и той se буквой 1 (дальве для краткости обозначения позиция pj,, еоотвегствувчая факту a¿. будет называться позицией ai).

Б этом случае продукционное правило мовет быть представлено как показано на рисунке 1(а), где множество (a¿, ,...,a¡,h)-представляет собой условную часть правила, п>1, а множество íajf ,я]г ,...,ajm)- заклпчмтсльная часть правила, »>1.

б)

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

Если. !г, 1 то условная часть продукционного правила состоит из нескольких условий, соединенных связкой И. Если е>1 то закля-чительнаа часть состоит из нескольких заключений, соединенных связкой И.

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

Правило 1.

Если в одной позиции находятся два или более маркеров то происходит "слияние" маркеров и вместо нескольких маркеров остается только один.

а)

Правило 2.

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

Модель ИСП. соблидапцая правила 1 и 2, отличается от ординарной СП. Однако для эффективного использования средств, разработанных для анализа СП, необходимо реализовать процесс унификации посредством самой модели, а не внешними относительно СП процедурами. Для этого вводятся дополнительные переходы, а затем для каждого перехода ИСП устанавливается его приоритет. В результате получается ИСП с приоритетами (ИСШП.

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

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

SУ чЩ

Рис. 2.

Дополнительный переход "контэйпер" Icon, имеет более пчзкий приоритет чем prt

pr(tcon) < prt (6)

и принадлежит множеству вспомогательных переходов Tad, для которого :

{ Vt{,£ Tad I pr(tt) < prt > . (?)

Переход tt и факты ( а^ }, отражают последующие воэчозлыг ваги

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

Если в позицию aj помещается более чем один маркер, что возможно при срабатывании нескольких входных переходов для а^, то только один маркер может бить использован для срабатывания перехода tj, а остальные маркеры позиции а( "заставят" сработать переход Icon. Если в позицию aj повещается маркер, а Ц уже сработал то это означает, что в at уже находился маркер и "новый" маркер будет использован лиыь переходом Icon. Если в &(, находится маркер, a ti еще не сработал то в данной ситуации сработает tа не Icon, т.к. t£ обладает более высоким приоритетом.

Если существует множество правил, использующих одну и ту се условную часть, то выполнив операцию исключающего ИЛИ над всеми условиями, составляющими условную часть этих правил, можно показать отножение вежду результатом каждого, вывода и данными, на основе которых делается вывод. Это может быть представленно сетью Петри, как показанно на рисунке 3, Здесь предусматривается дополнительная позиция р, в которую при начальной маркировке Но всегда помещается один иаркер. Дайной позиции не соответствует никакой символ из J) и она помечается буквой 1, однако, р необходима для обеспечения операции исключающего ИЛИ. В этом случае может сработать не более чем один из переходов tf Лг .... Дп.п>1. Переход "контейнер" tcon принадлежит Tad, к функционирует аналогично рисунку 2.

. ai

iak >

Рис. 3. •

Для устранения неопределенности в задании конечной иарки-ровкм Кп вводятся дополнительные переходы 1р. На срабатывание переходов Ьр накладываются следующие условия: переход 1р срабо-

- и -

тает только в той случае если за время выполнения ИСПП в позиций а не будет помечен ни один маркер. Т.о. в результате выполнения ИСПП ни в одной из 1-позиций не будет ни одного маркера, и ко-нечнея маркировка йп будет представлять собой вектор с ненулевыми компонентани, соответствующими только "целевым" фактам продукционной системы.

Начальная маркировка Ко будет представлять собой вектор, в котором МоСа;, 1-1 для позиций, соответствувщих фактам продукционной системы, представлявших собой формулировку задачи, а так же 1-позиций, и Йо(а1)=0 для остальных позиций.

Для предлогенной ИСПП сформулированы и доказаны следующие утверждения.

Элементы ИСГШ, в которых позиции имевт более чем одну вход-нув или выходкус дугу, в каждом варианте решения эквивалентны элементам ординарной СП (ОСП) с копичеством входных и выхедннх дуг для каждой из позиций не превышавшим единицу.

Для ОСП. в которой для каждой из позиций количество входных дуг не превыиает единицу и количество выходных дуг не превывает единицу, справедлива теорема 1.

Утверждение о необходимом и достаточном условии достижимости в ИСПП.

В ИСПП маркировка Нп достижима от начальной маркировки Мо тогда и только тогда, если:

1. ФУСП имеет ревение в неотрицательных целых;

2. учтены приоритеты каждого перехода путей.исклвчения из ревения ФУСП векторов запуска с запрещенными комбинациями срабатываний переходов;

3. переходы, которым в векторе запуска {Чи) соответствузт некулевые компоненты, не принадлежат свободным от маркеров циклам.

Если в ИСПП отсутствупт циклы то необходимым и достаточный условием достижимости маркировки Ип от Но будет выполнение пунктов 1 и 2.

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

ветствующие tcon и tp хотя бг^для одного элемента ИСПП, равны единице.

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

В том случае если решение ФУСП неоднозначно и представляет собой множество Свозможно не ограниченное) векторов запуска то к дальнейаему рассмотрении будут приниматься только те векторы f(u), компоненты которых соответствуют данному утверждении.

Приведены принципы построения матрицы инцидентности ИСПП на основе анализа "упрощенной" матрицы инцидентности.

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

В данной главе сформулированы и доказаны следующие утверждения.

Пусть для ИСПП переходы Ц .Ц.....Ц„ , где n^f образуют

один из циклоз, ац ,att.....ain - позиции данного цикла такие что attFti.t, ti^Failti, если i-ikn, к Ц^Р-Ч, если 1=п (К - отновекие инцидентности, а запись xRy обозначает, что х и j находятся в отношении R). и каждая из позиций id;.} ииеет к-вход-ных переходов, где к>1, тогда если для каждого цикла данной ИСПП ввести дополнительную I-позицкв q и переход tq, где tqfTad и qFlq, согласно следущих правил:

П если существует позиции из iat i, для которых к>1 и а^ одна из таких позиций то установить, что выходным переходом для q (кроме tq) будет t^ такой, что aij Ftfy и один из переходов цикла, а входными переходами для q, будут все вхпднне пеое-ходи для позиций ia;,> за исключением переходов, удонлетворяшцих если Ub<n и t^jFaij если Ь=п. где один из переходов цикла, a (а^);

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

3) если"для начальной маркировки Но цикл не свободен от маркерсв то установить Ko(q)=1, и Ho(q)-0 в противно* случае; тогда выполнение пунктов 1 и 2.утверждения о необходимом и дос-

таточном условии достижимости в ИСПП будет необходимым й достаточным условием достижимости некоторой маркировки Kn oí tío.

ИСПП с дополнительными I-позициями, введенными согласно вы-веприведенкого утверждения будем называть ИСПП с блокирующими позициями С ИСППБ).

Предложен иетод и разработаны принципы построения алгоритмов для выявления циклов в произвольной ИСПП путем ревения Ф9СП.

Пусть Копий соответствует ситуация, при которой только в I-позициях находится по одному маркеру, а в остальных маркеры отсутствувт, тогда если в ИСПП все переходы из T»ain имсвт не более чем одну входнуп и не более чем одну выходную позицию и при Ko-Monull И Mn-Mnull среди ревений ФНСП для данной ИСПП есть векторы запуска fíu) с ненулевыми значениями соответствувцини некоторым переходам из Taain то эти переходы учавствуит в циклах.

Пусть переход t имеет п входных íaj,} и в. выходных (aj) позиций, где п>1 и в>1 (рис 1(а)). Данный переход может входить в циклы, вклвчавщие вершины и aj, , а[,2 и aj4 ..... а(,„ и ajm. Всего таких циклов может быть пхв.

Элемент ИСПП (рис. 1(а)) можно заменить элементом ИСПП где каждой паре а^ и aj{ поставлен в соответствие отдельный переход t из Tnain такой, что a^Ft и t Fajj.

Очевидно, что функционирование полученной ИСПП будет не адекватно функционировании исходной ИСПП. Однако, т.к. изменена ливь форма связи, между вероинами (a¡,) и (aj >, а сами связи сохранены то сохранены и все циклы, вклвчаицие эти вераины.

Т.о. в результате описанного преобразования получается ИСПП с циклами, в которых каждый переход имеет только по одной входной и выходной позиции, тогда, в данной ситуации, ФУСП может быть использовано для нахождения всех переходов из Teaín (для преобразованной ИСПП) образущих циклы, а следовательно, и всех позиций. учавствув»;их в циклах исходной ИСПП.

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

Задачу наховдения множества (H¡,) маркировок, достижимых от некоторой начальной маркировки Мо, и являвшегося подмножеством заданного множества конечных маркировок (tfnj }, соответствующего множеству Ра5в, можно представить слсдувчиы образом.

Пасть ИСППБ моделирует процесс вывода в некоторой"продукционной системе и множество позиций {a-t> соответствует "целевму" множеству событий Pais. Для каждой позиции ац из ía¡,3 вводится дополнительный выходкой переход tai в из множества переходов Tain причем для Tain выполняется следующее условие:

(V4ÉT ! р(Ч) = prt ). (8)

Очевидно, что некоторая целевая позиция а;, достижима для данной ИСПП при начальной маркировке Но тогда и только тогда если за время функционирования ИСППБ сработал соответствующий ей переход tain. Т.о. будет справедливо следующее утверждение.

В ИСПП, для которой, каждсй целевой позиции a¡, соответствует выходной переход из множества Tais, некоторая целевая позиция aj, достизима при начальной маркировке Но тогда и только тогда если среди речений ФУСП для данной ИСПП в виде

KnuII = Но ^ f(u) Ср, (9)

удовлетворяющих вышеприведенным утверждениям будут векторы ftu) с ненулевой компонентой, соответствувщей выходномц для а^, переходу принадлежащему Tai«. Mnul1 - конечная маркировка, при котерпй во всех позициях ИСПП отсутствуют маркеру..

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

Для постановки задачи достижимости в ИСПП-модсли необходимо задать начальную Но и конечную Кп маркировки. Но и Ип соот-вь'тстьузт условию' и заключению задачи вывода на знаниях в ПС и определяются (на основе полученных з предыдущих главах результатов елвдуючим образом.

1) Если в И/ИЛИ графе процесса вывод* отсутствуют циклы то в данном случае ИСПП-модель представляет собой ИСПП. Тогда для задачи, устанавливающей соответствие некоторого заключения исходны" фактам, в векторе Но Но(р^) = f в тех случаях, кегда P¡,- 1-нозиция, р{_- соответствует исходному факту, входящему в условие задачи; и для остальных позиций КоСр^) = 0. В векторе Ип Kntp¡,j = 1 в тех случаях, когда позиция ri соответствует факту, входящему р заключение задачи, и для остальных позиций

МоСрр = 0.

2) Если в Й/ИЛИ графе процесса вывода могут присутствовать циклы то ИСПП-модель представляет собой ИСШ1Б. В этой случае для задачи, устанавливающей соответствие некоторого заключения исходным фактам, в векторе Мо Мо(р£,> - I для всех 1-позиций. не являвшихся блокирующими, для всех блокирующих позиций, соот-ветствущих циклам ( р^, р^..... р(,„), в которых при данной постановке задачи вывода хотя бы одной из позиций цикла соответствует исходный факт, входяиий в условие задачи, для всех позиций, соответствующих исходным фактам, входящих в условно задачи; и для остальных позиций Мо(р[,) = 0. В векторе Мп Ип(р1) - I в тех-случаях, когда позиция р соответствует факту, входящему в заключение задачи, и для остальных позиций - МоСр^,) = 0.

3) Еслм задача вывода доказывает соответствие произвольного подмножества из некоторого конечного множества заключений (предположений) исходным Фактам, то Но определяется согласно пунктов 1) или 2), в зависимости от того, представляет ли собой ИСПП-мо-дель ИСПГТ или ИСППБ, а в векторе Мл, всем позициям соответствует нуль, Мп(рь) = 0.

На рисунке 4 представлена упроченная структура ПС. использующей внутреннее представление БЗ в виде ИСПП-модели. в К/ИЛИ графе процесса вывода которой могут присутствовать цикла. Функционирования данной системы происходит следующим образом.

1. Эксперт - единственный кто вносит изменения в базу, знаний в виде добавления новых, удаления или корректировки правил.

2. Интерфейс с экспертом предназначен для максимального упрочения операции кодификации БЗ.

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

4. Осуществляется анализ на циклы, з результате которого формируется ИСППБ и создается множество списков вереин, где каждый соответствует отдельному циклу в ИСПП-модели, а вершины, входящие в список являются вериннааи данного цикла.

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

Эксперт

1

Пользователь

Ннт&р^зйс

I

Н 13

Г.асудаке

Получение

Анализ на

ЦИКЛИ

Список цнклог

Получение

I

Рвогние

I

Интер?ейс

Подучеьке 13НК

т~

ОЗмснгнис выводя

Обработка нечетких знаний

йгвина виЕОда

J

Рис. 4.

6. Интерфейс с пользователе» на основе полученной информации формулирует задачу достижимости для ИСПП-аодели в виде определения начальной Мо и конечной Нп маркировок.

7. Отыскиваются ревения ФУСП для полученных ранее матрицы инцидентности ИСППБ и маркировок Ко и Кп.

С. На основе ревения ФНСП из базы знаний выбираются лииь необходимые (для каждого варианта режения) пвавила и Факты и формируется 03 с необходимой информацией (БЗНИ).

Э. Осуществляется обработка нечетких знаний.

10. По необходимости (команде пользователя) происходит объяснения полученных выводов.

Пусть БЗ состоит из а правил и п различных фактов, входящих как в условные так и в заключительные части правил, и для данной

БЗ выполняется следувцее;

- 1 - количество правил, каждое из которых имеет одинаковую услсвнуп часть с хотя бы с одним из правил БЗ, а заклвчительная часть ни где не встречается, кроме как в данном правиле;

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

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

Построение УМИ представляет собой следуицне процедуры;

- создание списка фактов, входящих в 53;

- создание УНИ путем пошагового просмотра Ь'З (каждый ваг соответствует правилу в БЗ). Полученная НИИ будет иметь размерность вхп.

Построение ИСПП на основе ИМИ представляет собой пошаговый просмотр УИИ (каждый иаг соответствует столбцу матрицы). Полученная ЙСПП будет иметь размерность

( в + 1 + г + с ) Х( п + 25 + 2г * 2с ). (10)

Построение ИСПГ1Б основано на выполнении следувщих процедур:

- анализ ЯНИ на циклы;

- построение ИСППБ путем введения дополнительных позиций, ссотвегствуачих циклам.

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

!и!'»г'н' )х( п + 21' +2г' + 2с' ), (11)

где I', г*, с' - сбозначавт то же, что и 1, г, с но для преобразованной матрицы инцидентности.

Вторая процедура выполняется в результате введения дополнительных вервин (по одной для каждого мз выявленных циклов). Полученная матрица инцидентности ИСППБ будет иметь размерность

( и |+гк»р )х( п + 21 + 2г + 2с + р), (12)

где р - количество циклов в УЫИ.

Сложность процедуры решения ФУСП определяется размерностьв матрицы инцидентности ИСПП или ИСППБ.

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

комбинаторного взрыва.

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

Существующие ЭС обычно работавт в двух реаинах: формирование и модификация БЗ; поиск ответов на вопросы.

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

- формирование и модификация БЗ, в который будут входить Есе преобразования, связанные с получением ИСШ1 или ИСПП5;

- Поиск ответов на вопросы, в который будут входить непосредственно ревение ФЭСП и обработка модифицированной БЗ с необходимой информацией.

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

Б данной глазе приведены и проанализированы данные экспериментальных исследований влияния структуры и разиернисти БЗ на время логического вывода в ПС, использувщих ИСПП-иодель, для четырех типов структур баз знаний, граф И/ИЛИ вывода для которых представляет собой:

модель ¡1: каждой вервине, начиная с некоторой, неиневцей входных вервин. соответствуют две уникальные выходные вервинч со связью ИЛИ между дугами:

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

модель С; каждой вервине, начиная с некоторой, неиаевщей выходных вервин, соответствуют две уникалышг входные оервины со связьэ \\Ш между дугами;

модель 0: каждой вервине, начиная с некоторой, немеющей выходных вервин, соответствуют две уникальные входной вервини со связью И между дугами.

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

- рсзцлыаты экспериментов .подтверждают тесреткческкз оценки эффективности разработанных методов и алгоритмов;

- в (1С. использующий ИСПП модель, наиболее эффективно обра батьваются БЗ, для которых в И/ИЛИ графе процесса вывода пресб-

ладаят И-веряшш;

- в ПС, кспользувцеП ИСПП-модель. наименее эффективно обрабатывайся 53, для которых в й/Ш графе процесса вывода преоб-яадавт вервшш, входные дуги которых связаны связкой ЙЛН.

Описана ЭС прогнозирования успеваемости студентов в ВУЗе (ЗС ПУС) предназначена для оказания помочи сотрудникам ВЗЗа в прогнозировании созможных результатов учебн студента или абитуриента на конкретных этапах обучения (курс, семестр) на основе знаний, полученных от зкепертов (высококвалифицированных преподавателей), которая кохет быть построена с использование« методов и принципов, полученных в данной работе.

В заклвчеши приводятся основные результаты работы.

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

ОСНОВНЫЕ РЕЗЯПЬТЙТН РАБОТЫ

1. Разработаны принципы построения моделей баз знаний и процессов вывода в ПС на основе интерпретированных сетей Петри с приоритетами (ИСПП). позволявшими эффективно использовать фундаментальное уравнение сети Петри при ревении задач вывода на знаниях.

2. Представлена КСПП-нодель базы знаний в ПС, позволявшая эффективно использовать ОУСП при ревении задач вывода, в которых необходимо доказать соответствие некоторого яаклвчения (предположения) исходным фактам, для случая когда в И/ИЛИ графе процесса вывода отсутствуя! циклы.

3. Представлена ШШ-модель базы знаний в ПС, позволягщая эффективно использовать ФНСП при ревении задач вывода; в которых необходимо доказать соответствие некоторого заклечения (предположения) исходным фактам, для случая когда в И/ИЛИ графе процесса вывода могут присутствовать циклы.

4. Представлена ШШ-кодель базы знаний в ПС, позволявшая эффективно использовать ФУСП при ревении задач вывода, в которых необходимо доказать соответствие произвольного надмножества из некоторого конечного множества заклвчений (предположений) исходным фактам.

5. Разработан метод определения циклов в И/И/Ш графе процесса вывода на знаниях в ПС на основе реиения ФУСП.

6. Разработана принципы для создания алгоритмов построения

внутренней ИСПП-модели в ПС на основе анализа базы знаний в ПС.

Публикации по теме диссертационной работы.

1. Беляевский Л.С., Буров В.А., Курочкин П.И., Ткачен-ко В.П. Келкумян К.В. Оптимизация размецения многопозиционной фазовой радионавигационной системы. В кн.: Проблемы ссвер-ненствования радиоэлектронных комплексов и систем обеспечения полетов. - Тез. док. всесопз. науч.-тех. конф,, Киев: КИЮ, 1389.

2. Давидвк B.C., Иелкумян К.В. Построение локальных вычислительных структур для информационного обеспечения эксплуатации PTI) полетов Якраины. ¡5 кн.: Проблемы совераенствования радиоэлектронных комплексов и систем обеспечения полетов. - Тез. док. II ме»д. кауч.-тех. конф., Киев: КИИГй, 1392.

3. Нелкуыян К.Б., Отблеск Д.Б. Моделирование параллельного алгоритма ревения системы линейных алгебраических, уравнений иерархическими сетями Петри. В кн.: Методы математического моделирования в энергетике. - Киев: Наук, думка, 1932.- 13В с.

4. Мелкумян К.В. Методы распараллеливания вычислительных процедур при решении задач диагностики авиационной техники. Б кн.: Проблемы совервенствования радиоэлектронных комплексов и систем обеспечения полетов. - Тез.. док. II мевд. науч.-тех. конф., Киев: КИИГА, 1932.

Подписано к печати Ю, v£ 03 г. формат 60x84/16 Вуглга oiceiaaa Усл.-печ.лист.МУч.-игд. лист !,й-Ткрая ICO- Паказ St.J.

Полиграф, уч-к Института электродинамики All Украинк, ЙЙ057, Каев-57, проспект Победи, 56.