Software & Systems

В состав БЗ большинства гибридных ЭСАПР, как правило, включают множество продукционных правил [1, 2]. Правая часть каждого правила обычно определяет некоторую процедуру, связанную с реализацией проектной эвристики. Левая часть правила определяет условия, в которых применение этой эвристики допустимо и эффективно. Условия активизации эвристик в основном определяются состоянием объекта проектирования (видом проектной ситуации Si). В связи с тем, что мощность множества возможных проектных ситуаций {Si} и мощность множества проектных эвристик существенно различаются и имеется немало эмпирических доказательств того, что каждую проектную эвристику можно применить не к единственной Si, а на некотором их подмножестве, продукционные правила для ЭСАПР обычно строятся в виде:

PON(Si)®Dr

где Dr – проектная эвристика; PON(Si) – логическая функция, определяющая некоторый класс проектных ситуаций.

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

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

ОПИСАНИЕ ЗАДАЧИ

В режиме рабочего функционирования гибридной ЭСАПР возникает множество описаний объектов проектирования {Si}; в их числе могут оказаться и такие Si, которые не входили в состав обучающих выборок {Li} и являются новыми, не знакомыми системе проектными ситуациями. В общем случае возможно возникновение двух типов состояний:

а) система генерирует новое описание SiÏ{Li}, которое можно включить в один из представленных в БЗ классов объектов проектирования (проектных ситуаций): SiÎV(PONi),

б) создается такое новое описание объекта проектирования SiÏ{Li}, которое нельзя отнести ни к одному из известных системе классов объектов, то есть SiÏV(PONi).

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

Во втором случае возникает задача расширения знаний системы в области идентификации новых классов объектов проектирования, которая является частным вариантом более общей проблемы – извлечения знаний из баз данных [3, 4]. Генерация новых ситуаций, обладающих рядом признаков, не присущих тем классам, которые представлены множеством {PONi} в БЗ, соответствует возникновению нового факта, не отраженного ранее в системе знаний ЭСАПР.

Так, если база знаний включает некоторый фрагмент Frag(1)={PONi}, причем

(" i) (PONi=j(Poj)) или PONi=j(Pj i))

и имеется новая ситуация SiÏV(Frag(1)), то необходимо найти такое новое описание класса N_PON, что

SiÎV(N_PONi), N_PON U Frag(1),           (1)

V(PONi) ÇV(N_PONi)= 0.

Так как неизвестный класс представлен практически одним объектом Si, возможны два варианта действий. Наиболее простой тактикой является принятие гипотезы

N_PON(Si) = Si;

так как SiÏV(Frag(1)), то условие (1) будет выполняться автоматически. Однако в этом случае наблюдается быстрый рост мощности БЗ при достаточно медленном расширении знаний системы [5].

Более рациональный подход основан на решении задачи построения нового понятия для определения класса объектов, в который включается как новый факт Si, так и группа объектов, ранее раcпознававшихся некоторым понятием PONi из БЗ системы:

SiÎV(N_PON), SiÏV(Frag(1)),

V(N_PON) ÊV(PONi).                                  (2)

Для решения задачи автоматического формирования понятий о некотором классе информационных объектов на основе анализа единственного представителя этого класса – Si и состояния БЗ САПР создан новый алгоритм характеристических аналогий.

АЛГОРИТМ ФОРМИРОВАНИЯ ОПИСАНИЯ КЛАССА ПРОЕКТНЫХ СИТУАЦИЙ

Алгоритм позволяет определить для любого нового, не известного системе факта Si близкий по di класс фактов и соответствующее ему PONi в БЗ системы. Найденное PONi подвергается коррекции с целью выполнения условий (1), (2). Созданная в ходе коррекции функция N_PON рассматривается в качестве гипотезы, определяющей новый класс объектов проектирования:

V(N_PON) = V(PONi) È Si.                                                (3)

Для оценки перспективности гипотезы N_PON генерируется экзаменационная выборка объектов проектирования (EL). Если в ходе анализа объектов из EL условия (2), (3) выполняются, новый факт Si успешно распознается понятием N_PON и все объекты, распознававшиеся понятием PONi, идентифицируются правильно с помощью N_PON, задача (1) успешно решена. В противном случае, из БЗ выбирается новый аналог (PONi), близкий к Si (причем мера близости может быть изменена di), который и подвергается коррекции в соответствии с положениями алгоритма.

Если гипотеза N_PON признается по результатам экзамена удовлетворительной, очевидна необходимость коррекции БЗ системы. Понятие-аналог PONi удаляется из БЗ, а вместо него включается понятие-гипотеза N_PON.

В основе рассматриваемого алгоритма лежит представление о мере близости нового, не известного ранее системе факта Si к некоторому понятию (PONi) из БЗ.

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

di=Sj,       Sj =Sj-1+ ri,    j = 1, ..., m,            (4)

где при j=1 Sj = 0; m – число характеристик в Si; Si =

 r1= (5)

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

r2=(6)

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

Относительный показатель частоты использования характеристики Poj в описании класса можно определить с помощью d3 = d1/m.

Так как d2 характеризует число совпадений в описаниях объекта и функции PONk класса, то d4 будет определять относительный показатель:

d4= d2 /n1,

если PONki= и PONki Í PONi.                 (7)

в остальных случаях множество значений многомерного признака Pi

r1=(8)

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

Анализ соотношений (4-8) показывает, что введенные характеристики позволяют оценивать:

· d1 – абсолютную близость объекта Si классу PONi по числу совпадающих характеристик,

· d2 – локальную близость объекта Si классу PONi в области строгой общности, (отражает число характеристик Si, вошедших в строгую общность (PONki) анализируемого понятия);

· d3 – относительную близость объекта Si классу PONi (учитывает совпадение характеристик и длину описания PONi);

· d4 – относительную локальную близость Si классу PONi;

· d5 – типовую близость объекта Si классу PONi по числу одинаковых признаков (в многомерном пространстве f(Pij) на фоне допустимых вариаций их значений).

Коррекция выделенного в БЗ с помощью di понятия PONi осуществляется с помощью специальных правил, каждое из которых ориентировано на идентификацию определенного типа объекта проектирования.

Правило 1.

Если PONi = PONki & PONDi и (каждый признак из строгой общности входит в описание объекта проектирования)

(" j)   PojÎ PONki ® Poj Î Si, то есть

Si Ç PONi= PONki,                                                              (9)

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

(PojÎ Si    Poj ÎPONDi), тогда:

S1i= Si\PONki,

N_PON = PONki&(PONDi ! S1i).                  (10)

Рассмотрим описания классов и объекта с помощью многомерных признаков, что наиболее часто встречается в задачах САПР. Предположим, в БЗ включены понятия PON1 и PON2:

PON1=(P11&P23&P41)&(P31!P32!P81!P01),

PON2=(P11&P23)&(P31!P33!P81!P91).

Необходимо идентифицировать новый факт Si=P11&P23&P41&P51&P61&P71 на предмет принадлежности к классу.

С помощью характеристики d для коррекции выбирается PON1: в этом примере первое понятие лучше подходит по нескольким характеристикам (d1, d2, d3). По d4 они неразличимы, но так как при многомерных признаках большее доверие характеристике d5, то окончательно выбираем PON1. По (10) формируем:

S1i=(P11&P23&P41&P51&P61&P71)\

(P11&P23&P41)=P51&P61&P71,

N_PON=(P11&P23&P41)&((P31!P32!P81!P01)!

(P51&P61&P71)).

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

Правило 2.

Если по d1 и d2 понятия неразличимы, а по d3 выделено в качестве аналога понятие PONi, причем:

Si Ç PONki= S1i,             PONki\ S1i ¹ 0,

то есть строгая общность (PONki) несколько шире найденного пересечения и включает какие-то дополнительные конъюнкции, не свойственные данному объекту проектирования, тогда так же, как в первом правиле, после удаления из описания объекта проектирования признаков, которые являются общими с конъюнктивной частью функции PON, оставшиеся признаки должны дополнить дизъюнктивную часть понятия:

PojÎSi       PojÎPONDi .

Для этого S2i= Si\ S1i, S3i=PONki\S1i

N_PON=S1i & (PONDi!S2i ).(11)

Признаки, входившие в PONki, но не присущие Si:PojÎ(PONki\S1i), включаются в новое понятие в качестве необязательных характеристик в виде дополнительного конъюнктивного члена:

N_PON= S1i &(PONDi! S2i) &(S3i!ùS3i ).

Например, в БЗ входят PON1 и PON2 и имеется новый факт Si, нуждающийся в идентификации: Si = P11&P23&P51&P61&P71.

PON1=(P11&P23&P41)&(P31!P32),

PON2=(P11&P23)&(P31!P33!P81!P91).

Так как по характеристикам d1, d2, d5 эти понятия неразличимы, выбор аналога класса осуществляется по d3. Для PON1 d3= 2/5, а для PON2 d3= 2/6, следовательно, предпочтительнее работать с PON2:

S1i= P11 &P23; PONk1\S1i= P41,

S2i=P51&P61 &P71,

N_PON=(P11&P23)&

&((P31!P32)!(P51&P61&P71 ))&(P41!ùP41).

Правило 3.

Если аналоги {PONi} имеют в своей строгой общности только один аргумент, общий с Si, то наиболее близким к Si считается понятие с наиболее короткой функцией PONki (при равенстве для всех PONi показателя d5). Тогда общим признаком Pi (при безразличии значений Pij) является:

($i)     S2i &(PONki\S1i)®Pi .

Если этот признак Pi присутствует в Si в качестве значения Pij:

($j)      PijÎSi, S2i=Si\S1i,

S3i = PONki\S1i, S4i= S2i\Pij, тогда

N_PON=S1i & (S3i!Pij)&(PONDi!S4i).          (12)

Например, требуется определить класс для нового факта Si=P11&P22&P51&P61&P71, (БЗ такая же, как в примерах к правилам (1), (2)).

В качестве корректируемого аналога выбрано понятие PON2. По правилу 3:

S1i = P11, S2i=P22& P51&P61&P71,

S3i =PONki\S1i=P23.

Общим признаком для S2i и S3i является P2. В S3i он представлен значением P23, а в S2– значением P22 (то есть Pij=P22), тогда:

S4i = P51 & P61& P71,

N_PON = P11&(P23!P22) &

&((P31!P33!P81!P91)!(P51&P61&P71)).

Правило 4.

Пусть в функцию строгой общности понятия-аналога PONi входит только один аргумент из Si и в Si имеется другой аргумент, общий с PONDi :

($j) S2iÇPONDi=Poj;

PojÎS5i,

S6i =S2i\S5i, тогда 

N_PON = S1i &PONDi&(S3i!S6i).                  (13)

Например, оставив состав БЗ как в предыдущем примере, идентифицируем факт Si=P11& &P31&P51&P61&P71, используя в качестве аналога PON2. По правилу 4 получим:

S1i=P11,      S2i=P31&P51&P61&P71,

S3i=P23,       S6i=P51&P61&P71,

N_PON=P11&(P31!P33!P81!P91)&(P23!(P51&P61&P71)).

Пятое правило позволяет создавать новое определение класса на основе описания факта Si при наличии в БЗ только слабых аналогий.

Правило 5.

Пусть для пары (факт Si и понятие PONi) имеется только одна общая характеристика PojÎ(S2iÇPONki), а функция PONDi включает признак Pr (в виде его значения Prj), который присутствует также и в описании факта Si (только в виде другого значения Pri).

Тогда существует PONDi(1)=PONDi\Prj,

S6i=S2 i\Pri и

N_PON=S1i&((Pr1!Pr3)!PONDi(1))&(S3i!S6i).   (14)

Например, для идентификации факта Si=P11&P32&P51&P61&P71 в качестве наиболее близкого аналога выбран PON2.

S1i =P11,       S2i=P32&P51&P61&P71,

S3i=(PONki\S1i)=P23,    S2iÇPONDi®P3 (пересечение по признакам), P32 Î S2i ,

P31, P32 ÎPOND3,           S6i=P51&P61&P71,

POND3(1)=POND3\(P31&P33)=P81!P91,

N_PON=P11&((P31!P32!P33)!P81!P91)&

&(P23!(P51&P61&P71)).

Алгоритм характеристических аналогий, основанный на правилах (9)-(14), позволяет создавать правдоподобные гипотезы-определения для классов объектов, заданных неполными (L Ì V(PONi)) или очень малыми (до одного объекта) выборками-примерами. При этом главными особенностями алгоритма стано-вятся свойства (1)-(3), благодаря которым увеличение объема знаний системы не вызывает значительного роста мощности БЗ. Система быстро увеличивает свои потенциальные возможности по распознаванию новых объектов и классов, в то же время количество функций в БЗ возрастает существенно медленнее. На основе алгоритма характеристических аналогий разработаны алгоритмы коррекции БЗ для системы ИПРИСА, предназначенной для обучения проектированию систем автоматического управления технологическими процессами.

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

1. Римский Г.В. Теория систем автоматизированного проектирования: интеллектуальные САПР на базе вычислительных комплексов и сетей. - Мн.: Навука i тэхнiка, 1994. - 631 с.

2. Чичварин Н.В. Экспертные компоненты САПР. - М.: Машиностроение, 1991.-240 с.

3. Hall C. The devils in the details: techniques, tools and applications for database mining and knowledge discovery. Intelligent Software Strategies, p.I, v.XI, N9, September 1995.

4. Осипов Г.С. Приобретение знаний интеллектуальными системами: Основы теории и технологии.- М.: Наука. Физматлит, 1997. - 112 с.

5. Филатова Н.Н. Автоматическое формирование знаний в САПР.- Тверь, ТГТУ, 1996. - 144 с.