Использование экспертных систем при построении моделей компоновки блоков

УДК 321.3

ИСПОЛЬЗОВАНИЕ ЭКСПЕРТНЫХ СИСТЕМ ПРИ ПОСТРОЕНИИ МОДЕЛЕЙ КОМПОНОВКИ БЛОКОВ[1]

,

Предлагается гибридная модель, основанная на сочетании фреймового, продукционного, объектно-ориентированного и реляционного подходов к представлению знаний в сочетании с элементами нечеткой логики и механизма «правил активации».Основное назначение модели соответствует концептуальному моделированию объектов интеллектуальных САПР на этапах создания быстрого прототипа и ранних стадиях исследовательского варианта экспертных систем. Разработана инструментальная программная система КРИС (Конструктор Разработчика Интеллектуальных Систем). Это позволило повысить качество проектирования систем – на – кристалле.

Введение

Развитие технологии экспертных систем (ЭС) в интеллектуальных САПР приводит к появлению ЭС класса "Личный консультант" [Саймон, 2004; Попов, 1996a; Попов, 1995b; Осипов, 1997; Микони, 1999; Джексон, 2001; Дейт, 2001; Уотермен, 1989; Попов, 1990c]

Это стимулирует рост потребностей в экспертных знаниях (ЭЗ) как товарном продукте. При этом возможности индустрии знаний по-прежнему определяются способностью инженеров знаний извлечь ЭЗ в процессе неформального диалога с экспертами предметной области. Процедуру работы инженера знаний упрощенно можно представить как итерацию, состоящую из двух шагов [Попов, 1990c; и др., 1990; Тарасов, 2002; Сороколетов, 1990; Попов, 2004d].

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

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

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

2. Проблема огрубления. Любая формализация вербальных знаний приводит к огрублению исходных понятий и неизбежна для каждой модели представления. Так, например, переход от Аристотелевой общей логики, характерной для устных форм интервьирования и обладающей полнотой в смысле Гёделя, к логике предикатов, характерной для продукционных моделей ЭС, означает утрату полноты представления знаний [Уотермен, 1989]. «Экспертное знание» обладает также рядом свойств, которые выделяют его из общего понятия «знание». При использовании распространенных моделей представления теряются важные подмножества данных свойств.

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

1. Признаки экспертных знаний в ИСАПР

Термины проблемной области в САПР редко соответствуют тем понятиям, которые использует эксперт. Эксперт пользуется специальным языком. Эксперт, как правило, не использует в рассуждениях многочисленные свойства реальных объектов САПР, а пользуется обобщенными характеристиками, не имеющими прямых физических аналогов. Экспертным знаниям присуща ограниченная когнитивная сложность: эксперт обычно не использует сложных правил; взаимодействие между фрагментами знаний, по-видимому, ограничено. Экспертные знания носят объектно-ориентированный характер. Значительная роль (особенно в задачах проектирования) принадлежит познанию через отрицание по типу "это не есть Х", где свойства понятия (класса понятий) Х определены явно. Для любого фрагмента ЭЗ, в какой бы форме оно не выступало, имеется граничное условие его применимости. Контекст указывается двояко: посредством умолчания и диапазона ожидания (свойств объекта, значений параметра). Диапазон при этом выступает, как правило, в виде списка значений, связанных отношением "И"/"ИЛИ", либо нечеткого множества. Эксперт пользуется гибкой стратегией «разделяй и властвуй» (разбиения общей проблемы на подзадачи и перехода от подзадачи к подзадаче). Гибкость заключается в изменении стратегии решения в зависимости от хода решения; именно это позволяет избегать полного перебора вариантов. Эксперт не пользуется сложными отношениями между понятиями в САПР. Объединение фрагментов ЭЗ в целостную структуру происходит, в основном, двумя способами: за счет установления прямых ассоциативных связей по типу «это относится к Х»; посредством имплицирования некоторых фрагментов экспертных знаний. Чем выше квалификация эксперта, тем большую размерность имеет его личная матрица импликаций.

Следует отметить, что перечисленные признаки экспертных знаний вписываются в понятие «персональный конструкт» практически в том виде, как оно (понятие) было сформулировано в области экспериментальной психиатрии в работах Дж. Келли [Kelly, 1955]. С учетом данных признаков предлагается построение модели ЭС инженером знаний в сфере САПР.

2. Построение гибридной модели знаний

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

Одной из распространенных моделей представления знаний в ИСАПР, и в экспертных системах (ЭС) в частности, является фреймовая модель [Попов, 1996a; Попов, 1995b; Осипов, 1997; Микони, 1999; Джексон, 2001; Дейт, 2001; Уотермен, 1989; Попов, 1990c; Попов, 1990c; и др., 1990]

Данный подход позволяет реализовать базу знаний (БЗ) как надстройку над любой современной реляционной СУБД (MS SQL, Oracle, MySQL, FoxPro и др.), сочетая ее возможности с интеллектуальной обработкой данных на основе механизма фреймов. Здесь каждый фрейм представляется отдельной функцией. Имя фрейма соответствует имени функции, а его значение, определенное в процессе означивания фрейма - возвращаемому функцией значению. Целевые слоты моделируются параметрами функции, начальные слоты - локальными переменными, описанными внутри тела функции. Определяемые слоты могут описываться двумя способами. Активации фрейма соответствует вызов функции. Иерархические связи между фреймами различных уровней организуются путем подстановки функции, моделирующей субфрейм, в качестве параметра функции родительского фрейма. Здесь допустимы не только древовидные иерархии, но и сети фреймов с циклическими участками. Наследование свойств фрейм-моделей достигается автоматически при соблюдении следующих принципов описания слотов: слоты фрейма, выражающие наследуемые его субфреймами свойства, должны описываться переменными в теле головной функции-фрейме. В субфреймах данные имена не должны декларироваться в качестве переменных. При условии их определенности в родительском фрейме, данные слоты-переменные становятся доступны также в любом субфрейме.

Модель является основой разрабатываемого языка инженерии знаний KRIS (Knowledge Representation Instrumental System) и представляет собой следующее. Экспертные знания представляются в виде совокупности поименованных сетей фреймов. Фрейм можно представить как:

(ИМЯ_ФРЕЙМА, коэффициент_использования, время_последнего_

использования, указатель_сети, КУ,

(имя_слота_1,

параметр_типа_1, параметр_типа_2, параметр_типа_3,

тип_диапазона, метод_получения, запрос_текст,

(значение_1 КУ1,

значение_2 КУ2,

... ),

(умолчание_1 КУ1,

умолчание_2 КУ2,

... ),

(элемент_диапазона_1 КУ1,

элемент_диапазона_2 КУ2,

... )),

(имя_слота_2, ... )),

Для каждого слота, таким образом, помимо основного значения указываются значение по умолчанию и допустимый (ожидаемый) диапазон значений, представляющие собой отношения с двумя атрибутами: элементом значения и коэффициентом уверенности (КУ). Для всех слотов устанавливаются три признака типа слота. Параметр_типа_1 указывает на тип слота как параметра подзадачи: начальный (I), целевой (G), определяемый (D). Параметр_типа_2 задает тип списка элементов значения слота: И-список (А), ИЛИ-список (О), нечеткое множество (S). Параметр_типа_3 определяет тип элементов данного списка. Допустимы следующие типы элементов: Процедуральные типы: R - правило-продукция, A - правило активации, P - присоединенная процедура, F - вызов функции, значение которой берется в качестве элемента слота.

Специальные типы: X - ассоциативная ссылка на фрейм (подсеть), U - неопределенный элемент, его атрибуты типа определяются в момент нахождения значения. Типы элементов данных: I - целое число, D - действительное число, C - произвольная символьная строка, L - логическое значение (true, false), V - «регистровые» переменные; служат в роли «почтовых ящиков» для прямого обмена между фреймами (сетями) и для связи с числовыми моделями ПО. B - ссылка на БД: отношение (таблица) внешней реляционной БД, представляющее значение слота.

· В ИСАПР разрешены любые сочетания признаков типа 1-3. Например, в качестве G-слота может выступать S-список R-элементов. Задача нахождения значения G-слота будет интерпретироваться как задача построения набора продукций, который и будет рассматриваться в качестве значения. В фрейме может быть любое число слотов каждого типа. Тип диапазона задает тип допустимого диапазона значений, определяемого перечислением, и может быть одним из следующих: SI - «включающее» множество. Допустимы только перечисленные значения; SE - «исключающее» множество. Допустимы любые значения, кроме перечисленных; SA - образец для ввода значения слота пользователем (например, с терминала).

Функционирование модели происходит следующим образом. Процедуральные слоты определяют локальные законы поведения фреймов как объектов и законы их взаимодействия. Первое реализуется посредством (R, P, F)-слотов, второе - посредством (V, B, A)-слотов. R-слоты представляют собой наборы правил-продукций традиционного вида IF - THEN-ELSE, параметрами которых выступают активные фреймы и их отдельные слоты. Активным назовем фрейм, включенный в список кандидатов на вычисление G-слотов при помощи специального механизма активации, являющегося частью машины вывода рассматриваемой модели. На R-правила наложен принцип ограничения взаимодействия. R-правило может изменять значения только слотов того фрейма, в котором оно описано. А-слоты представляют собой наборы продукций с консеквентом специального вида THEN activate(<ФРЕЙМ>), где <ФРЕЙМ> - имя фрейма, активируемого специальной функцией активации [Микони, 1999; Сороколетов, 1990]. Описанный таким образом фрейм представляет персональный конструкт в смысле Дж. Келли [Kelly, 1955], локальное поведение которого определяется присоединенными к нему наборами R-правил, и который может (в зависимости от состояния задачи) имплицировать другие конструкты. Описывая различные условия в А-правилах, можно явным образом программировать стратегию решения задачи, а указывая А-слоты в качестве определяемых и целевых - проектировать изменение стратегии в процессе решения задач ИСАПР. Для реализации последней возможности в машину вывода могут быть встроены специальные функции конструирования А-правил.

Фреймовая модель основана на принципе фрагментации (кластеризации) знаний [Микони, 1999]. При решении задач САПР они в основном используются для компоновки блоков с высокой размерностью. При представлении таблицы в виде фрейма поля записи являются его полями. Например, фрейм – коммутационная схема данных запишется следующим образом (табл.1).

Таблица 1.

N схемы	Название этапа	Параметры	Число частей разбиения	Число элементов в каждой части	Критерий	Используе мая модель
1	Разбиение графа на части	500	5	100	28	Графовая М1

Здесь под параметрами понимается число блоков ЭВА, критерием является суммарное число внешних связей между блоками. С помощью такого фрейма можно описать любую реальную локальную ситуацию компоновки. Использование аппарата разработанных ссылок позволяет реализовать любые сложные модели представления знаний в САПР путём детализации любых фреймов [Микони, 1999; Аверкин и др., 1990]. Тогда в слот вместо номера схемы можно поместить ссылку на список схем. Аналогично можно детализировать любой слот. Фрейм-прототип задаётся совокупностью фреймов-примеров. Основной механизм вывода во фреймовых моделях – это сопоставление. Если фрейм содержит слот «RuleSet:» (множество правил), то при обращении к этому фрейму при обработке правил его вычисление прерывается. Далее начинается реализация правил, находящихся в слоте «RuleSet:». Если при их реализации устанавливается значение этого фрейма, то производится возврат к точке обработки модели представления, из которой пришли во фрейм. Если в правилах фрейма есть имя другого объекта со слотами RuleSet:, то управление передаётся на него и т. д. [Микони, 1999; Сороколетов, 1990].

Например, приведём запись фрейма со слотом «RuleSet:»

Name: Действие выбор алгоритма компоновки

Long Name: Действие алгоритма по разбиению графовой модели на части

Type: Текст алгоритма

RuleSet:

/*Эти правила определяют действия пользователя, ЭС или алгоритма, выполняемые в неблагоприятной ситуации разбиения:

IF при разбиении графа IS не происходит минимизации суммарного числа внешних рёбер

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

Машина вывода включает в себя три основные компоненты:

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

механизм вывода и активации для наборов А-правил;

общая стратегия управления моделью, представляется следующим алгоритмом:

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

2. Если значения всех G-слотов для текущего уровня активации известны, то возврат к предыдущему уровню активации.

2.1. Если уровень нулевой, то решение достигнуто, конец вывода, переход к шагу 4; иначе переход на шаг 3.

3. Запуск механизма (1) для R-слотов активных фреймов текущего уровня активации в порядке убывания приоритетов фреймов.

3.1. Если значения всех G-слотов определены, то возврат к предыдущему уровню активации, переход на шаг 2.1, иначе переход:

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

3.1.2. Иначе запуск механизма (2) и переход на следующий уровень активации переход на шаг 3.

4. Конец работы алгоритма.

Заключение

Отметим две особенности предлагаемой модели представления ЭЗ, связанные с реализацией и использованием. Списки значений слотов и фреймы могут быть представлены в виде составных отношений с именем <ИМЯ_ФРЕЙМА> и соответствующими атрибутами. Аналогично можно рассматривать и сети. Это позволяет реализовать различные варианты данной модели в среде любой реляционной СУБД.

Основное назначение модели соответствует концептуальному моделированию объектов ИСАПР на этапах создания быстрого прототипа и ранних стадиях исследовательского варианта ЭС. Описанный способ моделирования фреймов применен при создании инструментальной программной системы КРИС (Конструктор Разработчика Интеллектуальных Систем) [Сороколетов, 1990]. Это позволило повысить качество полученной топологии при разработке систем – на – кристалле.

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

[Саймон, 2004] Науки об искусственном// - М.: Эдиториал УРСС, 2004.

[ и др., 1996a] Попов и динамические экспертные системы// - М.: Финансы и статистика, 1996.

[Попов, 1995b] Попов системы реального времени// Открытые системы. №2(10), 1995. http://kiryushin. *****/docs/esrv. htm.

[Осипов, 1997] Осипов знаний интеллектуальными системами// - М.: Наука, 1997.

[Микони, 1999] Микони БЗ и системы выбора// Интеллектуальное управление: новые информационные технологии в задачах управления - М.: Наука,1999,с.68-72.

[Джексон, 2001] Джексон П. Введение в экспертные системы// - М.: Издательский дом «Вильямс», 2001.

[Дейт, 2001] Введение в системы баз данных// (седьмое издание) - М.: Вильямс, 2001.

[Уотермен, 1989] Руководство по экспертным системам// - М.: Мир, 1989.

[Попов, 1990c] Попов интеллект: В 3 кн. Кн. 1. Системы общения и экспертные системы. Справочник / Под ред. . - М.: Радио и связь, 1990.

[Аверкин и др., 1990] Аверкин и формализация знаний. Искусственный интеллект. - М.: Радио и связь, 1990.

[Тарасов, 2002] От многоагентных систем к интеллектуальным организациям: философия, психология, информатика. - М.: Эдиториал УРСС, 2002.

[Сороколетов, 1990] Сороколетов представления знаний как стереотип мышления инженера знаний - разработчика экспертной системы// Экспертные системы в научных исследованиях, автоматизации проектирования и производства. Материалы II Всесоюзного научно-технического семинара. - М.: МФ ЦИПК, 1990, с.12-19.

[Попов, 2004d] Попов с ЭВМ на естественном языке. - М.: Эдиториал УРСС, 2004.

[Kelly, 1955] Kelly G. The Psychology of Personal Constructs. Vols 1 and 2. Norton, New York, 1955.

[1] Работа выполнена при частичной финансовой поддержке программы развития научного потенциала высшей школы годы (проекты РНП.2.1.2.2238, РНП 2.1.2.3193)